Forbes, Michael A.; Shpilka, Amir; Tzameret, Iddo; Wigderson, Avi Proof complexity lower bounds from algebraic circuit complexity. (English) Zbl 07471587 Theory Comput. 17, Paper No. 10, 88 p. (2021). MSC: 68Q06 03F20 68Q15 68Q17 PDFBibTeX XMLCite \textit{M. A. Forbes} et al., Theory Comput. 17, Paper No. 10, 88 p. (2021; Zbl 07471587) Full Text: DOI
Shpilka, Amir Sylvester-Gallai type theorems for quadratic polynomials. (English) Zbl 1456.68039 Discrete Anal. 2020, Paper No. 13, 34 p. (2020). MSC: 68Q06 52C10 68U05 68W20 68W30 PDFBibTeX XMLCite \textit{A. Shpilka}, Discrete Anal. 2020, Paper No. 13, 34 p. (2020; Zbl 1456.68039) Full Text: DOI arXiv
Shpilka, Amir Sylvester-Gallai type theorems for quadratic polynomials. (English) Zbl 1434.68162 Charikar, Moses (ed.) et al., Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, STOC ’19, Phoenix, AZ, USA, June 23–26, 2019. New York, NY: Association for Computing Machinery (ACM). 1203-1214 (2019). MSC: 68Q06 68U05 68W20 68W30 PDFBibTeX XMLCite \textit{A. Shpilka}, in: Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, STOC '19, Phoenix, AZ, USA, June 23--26, 2019. New York, NY: Association for Computing Machinery (ACM). 1203--1214 (2019; Zbl 1434.68162) Full Text: DOI arXiv
Anderson, Matthew; Forbes, Michael A.; Saptharishi, Ramprasad; Shpilka, Amir; Volk, Ben Lee Identity testing and lower bounds for read-\(k\) oblivious algebraic branching programs. (English) Zbl 1427.68077 ACM Trans. Comput. Theory 10, No. 1, Article No. 3, 30 p. (2018). MSC: 68Q06 68Q17 68W40 PDFBibTeX XMLCite \textit{M. Anderson} et al., ACM Trans. Comput. Theory 10, No. 1, Article No. 3, 30 p. (2018; Zbl 1427.68077) Full Text: DOI
Forbes, Michael A.; Shpilka, Amir A PSPACE construction of a hitting set for the closure of small algebraic circuits. (English) Zbl 1428.68171 Diakonikolas, Ilias (ed.) et al., Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, STOC ’18, Los Angeles, CA, USA, June 25–29, 2018. New York, NY: Association for Computing Machinery (ACM). 1180-1192 (2018). MSC: 68Q25 68Q06 PDFBibTeX XMLCite \textit{M. A. Forbes} and \textit{A. Shpilka}, in: Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, STOC '18, Los Angeles, CA, USA, June 25--29, 2018. New York, NY: Association for Computing Machinery (ACM). 1180--1192 (2018; Zbl 1428.68171) Full Text: DOI arXiv
Forbes, Michael A.; Shpilka, Amir; Volk, Ben Lee Succinct hitting sets and barriers to proving lower bounds for algebraic circuits. (English) Zbl 1412.68081 Theory Comput. 14, Paper No. 18, 45 p. (2018). MSC: 68Q25 68Q17 68W20 PDFBibTeX XMLCite \textit{M. A. Forbes} et al., Theory Comput. 14, Paper No. 18, 45 p. (2018; Zbl 1412.68081) Full Text: DOI
Forbes, Michael A.; Shpilka, Amir; Volk, Ben Lee Succinct hitting sets and barriers to proving algebraic circuits lower bounds. (English) Zbl 1369.68240 Hatami, Hamed (ed.) et al., Proceedings of the 49th annual ACM SIGACT symposium on theory of computing, STOC ’17, Montreal, QC, Canada, June 19–23, 2017. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4528-6). 653-664 (2017). MSC: 68Q25 68Q17 68W20 PDFBibTeX XMLCite \textit{M. A. Forbes} et al., in: Proceedings of the 49th annual ACM SIGACT symposium on theory of computing, STOC '17, Montreal, QC, Canada, June 19--23, 2017. New York, NY: Association for Computing Machinery (ACM). 653--664 (2017; Zbl 1369.68240) Full Text: DOI arXiv
Anderson, Matthew; Forbes, Michael A.; Saptharishi, Ramprasad; Shpilka, Amir; Volk, Ben Lee Identity testing and lower bounds for read-\(k\) oblivious algebraic branching programs. (English) Zbl 1380.68175 Raz, Ran (ed.), 31st conference on computational complexity, CCC’16, Tokyo, Japan, May 29 – June 1, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-008-8). LIPIcs – Leibniz International Proceedings in Informatics 50, Article 30, 25 p. (2016). MSC: 68Q05 68P05 68Q17 68Q25 68W20 PDFBibTeX XMLCite \textit{M. Anderson} et al., LIPIcs -- Leibniz Int. Proc. Inform. 50, Article 30, 25 p. (2016; Zbl 1380.68175) Full Text: DOI arXiv
Oliveira, Rafael; Shpilka, Amir; Volk, Ben Lee Subexponential size hitting sets for bounded depth multilinear formulas. (English) Zbl 1388.68132 Zuckerman, David (ed.), 30th conference on computational complexity, CCC’15, Portland, OR, USA, June 17–19, 2015. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-81-1). LIPIcs – Leibniz International Proceedings in Informatics 33, 304-322 (2015). MSC: 68Q25 68Q05 68Q17 68W20 94C10 PDFBibTeX XMLCite \textit{R. Oliveira} et al., LIPIcs -- Leibniz Int. Proc. Inform. 33, 304--322 (2015; Zbl 1388.68132) Full Text: DOI arXiv
Kopparty, Swastik; Saraf, Shubhangi; Shpilka, Amir Equivalence of polynomial identity testing and polynomial factorization. (English) Zbl 1319.65035 Comput. Complexity 24, No. 2, 295-331 (2015). Reviewer: Anton Iliev (Plovdiv) MSC: 65H04 65Y04 12D05 PDFBibTeX XMLCite \textit{S. Kopparty} et al., Comput. Complexity 24, No. 2, 295--331 (2015; Zbl 1319.65035) Full Text: DOI
Dvir, Zeev; Shpilka, Amir Noisy interpolating sets for low-degree polynomials. (English) Zbl 1229.68038 Theory Comput. 7, Paper No. 1, 1-18 (2011). Reviewer: Ulrich Tipp (Krefeld) MSC: 68P30 68Q25 PDFBibTeX XMLCite \textit{Z. Dvir} and \textit{A. Shpilka}, Theory Comput. 7, Paper No. 1, 1--18 (2011; Zbl 1229.68038) Full Text: DOI
Juma, Ali; Kabanets, Valentine; Rackoff, Charles; Shpilka, Amir The black-box query complexity of polynomial summation. (English) Zbl 1213.68263 Comput. Complexity 18, No. 1, 59-79 (2009). MSC: 68Q05 68Q15 68Q17 68Q25 PDFBibTeX XMLCite \textit{A. Juma} et al., Comput. Complexity 18, No. 1, 59--79 (2009; Zbl 1213.68263) Full Text: DOI
Shpilka, Amir; Yehudayoff, Amir Arithmetic circuits: a survey of recent results and open questions. (English) Zbl 1205.68175 Found. Trends Theor. Comput. Sci. 5, No. 3-4, 207-388 (2009). MSC: 68Q17 68N30 PDFBibTeX XMLCite \textit{A. Shpilka} and \textit{A. Yehudayoff}, Found. Trends Theor. Comput. Sci. 5, No. 3--4, 207--388 (2009; Zbl 1205.68175) Full Text: DOI
Dvir, Zeev; Shpilka, Amir Locally decodable codes with two queries and polynomial identity testing for depth 3 circuits. (English) Zbl 1124.68042 SIAM J. Comput. 36, No. 5, 1404-1434 (2007). MSC: 68Q25 94B65 PDFBibTeX XMLCite \textit{Z. Dvir} and \textit{A. Shpilka}, SIAM J. Comput. 36, No. 5, 1404--1434 (2007; Zbl 1124.68042) Full Text: DOI
Raz, Ran; Shpilka, Amir Deterministic polynomial identity testing in non-commutative models. (English) Zbl 1096.68070 Comput. Complexity 14, No. 1, 1-19 (2005). Reviewer: Mihai Cipu (Bucureşti) MSC: 68Q25 68W30 12Y05 PDFBibTeX XMLCite \textit{R. Raz} and \textit{A. Shpilka}, Comput. Complexity 14, No. 1, 1--19 (2005; Zbl 1096.68070) Full Text: DOI