Amir Shpilka

Noga Alon, Amir Shpilka, Christopher Umans: On sunflowers and matrix multiplication. Computational Complexity 22(2): 219-243 (2013)

Michael A. Forbes, Amir Shpilka: Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing. CoRR abs/1303.0084 (2013)

Amir Shpilka, Ben lee Volk: On the Structure of Boolean Functions with Small Spectral Norm. CoRR abs/1304.0371 (2013)

Michael A. Forbes, Amir Shpilka: Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing. Electronic Colloquium on Computational Complexity (ECCC) 20: 33 (2013)

Amir Shpilka, Ben lee Volk: On the Structure of Boolean Functions with Small Spectral Norm. Electronic Colloquium on Computational Complexity (ECCC) 20: 49 (2013)

Zohar Shay Karnin, Yuval Rabani, Amir Shpilka: Explicit Dimension Reduction and Its Applications. SIAM J. Comput. 41(1): 219-249 (2012)

Noga Alon, Amir Shpilka, Christopher Umans: On Sunflowers and Matrix Multiplication. IEEE Conference on Computational Complexity 2012: 214-223

Gil Cohen, Amir Shpilka, Avishay Tal: On the degree of univariate polynomials over the integers. ITCS 2012: 409-427

Eitan Yaakobi, Amir Shpilka: High sum-rate three-write and non-binary WOM codes. ISIT 2012: 1386-1390

Amir Shpilka: Capacity Achieving Two-Write WOM Codes. LATIN 2012: 631-642

Michael A. Forbes, Amir Shpilka: On identity testing of tensors, low-rank recovery and compressed sensing. STOC 2012: 163-172

Amir Shpilka: Capacity achieving multiwrite WOM codes. CoRR abs/1209.1128 (2012)

Michael A. Forbes, Amir Shpilka: Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs. CoRR abs/1209.2408 (2012)

Michael A. Forbes, Amir Shpilka: Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs. Electronic Colloquium on Computational Complexity (ECCC) 19: 115 (2012)

Zeev Dvir, Amir Shpilka: Towards dimension expanders over finite fields. Combinatorica 31(3): 305-320 (2011)

Zohar Shay Karnin, Amir Shpilka: Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in. Combinatorica 31(3): 333-364 (2011)

Parikshit Gopalan, Ryan O'Donnell, Rocco A. Servedio, Amir Shpilka, Karl Wimmer: Testing Fourier Dimensionality and Sparsity. SIAM J. Comput. 40(4): 1075-1100 (2011)

Zeev Dvir, Amir Shpilka: Noisy Interpolating Sets for Low-Degree Polynomials. Theory of Computing 7(1): 1-18 (2011)

Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka, Madhu Sudan: On Sums of Locally Testable Affine Invariant Properties. APPROX-RANDOM 2011: 400-411

Eli Ben-Sasson, Ghid Maatouk, Amir Shpilka, Madhu Sudan: Symmetric LDPC Codes are not Necessarily Locally Testable. IEEE Conference on Computational Complexity 2011: 55-65

Amir Shpilka, Avishay Tal: On the Minimal Fourier Degree of Symmetric Boolean Functions. IEEE Conference on Computational Complexity 2011: 200-209

Zohar Shay Karnin, Yuval Rabani, Amir Shpilka: Explicit Dimension Reduction and Its Applications. IEEE Conference on Computational Complexity 2011: 262-272

Amir Shpilka: Recent Results on Polynomial Identity Testing. CSR 2011: 397-400

Elad Haramaty, Amir Shpilka, Madhu Sudan: Optimal Testing of Multivariate Polynomials over Small Prime Fields. FOCS 2011: 629-637

Arnab Bhattacharyya, Zeev Dvir, Amir Shpilka, Shubhangi Saraf: Tight Lower Bounds for 2-query LCCs over Finite Fields. FOCS 2011: 638-647

Amir Shpilka: New constructions of WOM codes using the Wozencraft ensemble. CoRR abs/1110.6590 (2011)

Michael A. Forbes, Amir Shpilka: On Identity Testing of Tensors, Low-rank Recovery and Compressed Sensing. CoRR abs/1111.0663 (2011)

Gil Cohen, Amir Shpilka, Avishay Tal: On the Degree of Univariate Polynomials Over the Integers. Electronic Colloquium on Computational Complexity (ECCC) 18: 2 (2011)

Arnab Bhattacharyya, Zeev Dvir, Shubhangi Saraf, Amir Shpilka: Tight lower bounds for 2-query LCCs over finite fields. Electronic Colloquium on Computational Complexity (ECCC) 18: 54 (2011)

Elad Haramaty, Amir Shpilka, Madhu Sudan: Optimal testing of multivariate polynomials over small prime fields. Electronic Colloquium on Computational Complexity (ECCC) 18: 59 (2011)

Noga Alon, Amir Shpilka, Christopher Umans: On Sunflowers and Matrix Multiplication. Electronic Colloquium on Computational Complexity (ECCC) 18: 67 (2011)

Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka, Madhu Sudan: On Sums of Locally Testable Affine Invariant Properties. Electronic Colloquium on Computational Complexity (ECCC) 18: 79 (2011)

Michael A. Forbes, Amir Shpilka: On Identity Testing of Tensors, Low-rank Recovery and Compressed Sensing. Electronic Colloquium on Computational Complexity (ECCC) 18: 147 (2011)

Parikshit Gopalan, Amir Shpilka, Shachar Lovett: The Complexity of Boolean Functions in Different Characteristics. Computational Complexity 19(2): 235-263 (2010)

Amir Shpilka, Amir Yehudayoff: Arithmetic Circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science 5(3-4): 207-388 (2010)

Yuval Rabani, Amir Shpilka: Explicit Construction of a Small Epsilon-Net for Linear Threshold Functions. SIAM J. Comput. 39(8): 3501-3520 (2010)

Shachar Lovett, Partha Mukhopadhyay, Amir Shpilka: Pseudorandom Generators for CC0[p] and the Fourier Spectrum of Low-Degree Polynomials over Finite Fields. FOCS 2010: 695-704

Amir Shpilka, Ilya Volkovich: On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors. ICALP (1) 2010: 408-419

Elad Haramaty, Amir Shpilka: On the structure of cubic and quartic polynomials. STOC 2010: 331-340

Zohar Shay Karnin, Partha Mukhopadhyay, Amir Shpilka, Ilya Volkovich: Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in. STOC 2010: 649-658

Amir Shpilka, Ilya Volkovich: Read-Once Polynomial Identity Testing. Electronic Colloquium on Computational Complexity (ECCC) 17: 11 (2010)

Shachar Lovett, Partha Mukhopadhyay, Amir Shpilka: Pseudorandom generators for CC₀[p] and the Fourier spectrum of low-degree polynomials over finite fields. Electronic Colloquium on Computational Complexity (ECCC) 17: 33 (2010)

Amir Shpilka, Ilya Volkovich: On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors. Electronic Colloquium on Computational Complexity (ECCC) 17: 36 (2010)

Gil Cohen, Amir Shpilka: On the degree of symmetric functions on the Boolean cube. Electronic Colloquium on Computational Complexity (ECCC) 17: 39 (2010)

Amir Shpilka, Avishay Tal: On the Minimal Fourier Degree of Symmetric Boolean Functions. Electronic Colloquium on Computational Complexity (ECCC) 17: 178 (2010)

Eli Ben-Sasson, Ghid Maatouk, Amir Shpilka, Madhu Sudan: Symmetric LDPC codes are not necessarily locally testable. Electronic Colloquium on Computational Complexity (ECCC) 17: 199 (2010)

Ali Juma, Valentine Kabanets, Charles Rackoff, Amir Shpilka: The Black-Box Query Complexity of Polynomial Summation. Computational Complexity 18(1): 59-79 (2009)

Amir Shpilka: Constructions of Low-degree and Error-Correcting epsilon-Biased Generators. Computational Complexity 18(4): 495-525 (2009)

Amir Shpilka: Interpolation of Depth-3 Arithmetic Circuits with Two Multiplication Gates. SIAM J. Comput. 38(6): 2130-2161 (2009)

Sofya Raskhodnikova, Dana Ron, Amir Shpilka, Adam Smith: Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem. SIAM J. Comput. 39(3): 813-842 (2009)

Zeev Dvir, Amir Shpilka, Amir Yehudayoff: Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits. SIAM J. Comput. 39(4): 1279-1293 (2009)

Amir Shpilka, Ilya Volkovich: Improved Polynomial Identity Testing for Read-Once Formulas. APPROX-RANDOM 2009: 700-713

Parikshit Gopalan, Shachar Lovett, Amir Shpilka: On the Complexity of Boolean Functions in Different Characteristics. IEEE Conference on Computational Complexity 2009: 173-183

Zohar Shay Karnin, Amir Shpilka: Reconstruction of Generalized Depth-3 Arithmetic Circuits with Bounded Top Fan-in. IEEE Conference on Computational Complexity 2009: 274-285

Parikshit Gopalan, Ryan O'Donnell, Rocco A. Servedio, Amir Shpilka, Karl Wimmer: Testing Fourier Dimensionality and Sparsity. ICALP (1) 2009: 500-512

Yuval Rabani, Amir Shpilka: Explicit construction of a small epsilon-net for linear threshold functions. STOC 2009: 649-658

Parikshit Gopalan, Shachar Lovett, Amir Shpilka: On the Complexity of Boolean Functions in Different Characteristics. Electronic Colloquium on Computational Complexity (ECCC) 16: 48 (2009)

Elad Haramaty, Amir Shpilka: On the Structure of Cubic and Quartic Polynomials. Electronic Colloquium on Computational Complexity (ECCC) 16: 80 (2009)

Zohar Shay Karnin, Partha Mukhopadhyay, Amir Shpilka, Ilya Volkovich: Deterministic identity testing of depth 4 multilinear circuits with bounded top fan-in. Electronic Colloquium on Computational Complexity (ECCC) 16: 116 (2009)

Zohar Shay Karnin, Yuval Rabani, Amir Shpilka: Explicit Dimension Reduction and Its Applications. Electronic Colloquium on Computational Complexity (ECCC) 16: 121 (2009)

Ran Raz, Amir Shpilka, Amir Yehudayoff: A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits. SIAM J. Comput. 38(4): 1624-1647 (2008)

Zeev Dvir, Amir Shpilka: Noisy Interpolating Sets for Low Degree Polynomials. IEEE Conference on Computational Complexity 2008: 140-148

Zohar Shay Karnin, Amir Shpilka: Black Box Polynomial Identity Testing of Generalized Depth-3 Arithmetic Circuits with Bounded Top Fan-In. IEEE Conference on Computational Complexity 2008: 280-291

Zeev Dvir, Amir Shpilka: Towards Dimension Expanders over Finite Fields. IEEE Conference on Computational Complexity 2008: 304-310

Amir Shpilka, Ilya Volkovich: Read-once polynomial identity testing. STOC 2008: 507-516

Zeev Dvir, Amir Shpilka, Amir Yehudayoff: Hardness-randomness tradeoffs for bounded depth arithmetic circuits. STOC 2008: 741-748

Zeev Dvir, Amir Shpilka: Noisy Interpolating Sets for Low Degree Polynomials. Electronic Colloquium on Computational Complexity (ECCC) 15(004) (2008)

Zeev Dvir, Amir Shpilka: An Improved Analysis of Linear Mergers. Computational Complexity 16(1): 34-59 (2007)

Zeev Dvir, Amir Shpilka: Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits. SIAM J. Comput. 36(5): 1404-1434 (2007)

Ran Raz, Amir Shpilka, Amir Yehudayoff: A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits. FOCS 2007: 438-448

Sofya Raskhodnikova, Dana Ron, Amir Shpilka, Adam Smith: Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem. FOCS 2007: 559-569

Amir Shpilka: Interpolation of depth-3 arithmetic circuits with two multiplication gates. STOC 2007: 284-293

Zohar Shay Karnin, Amir Shpilka: Black Box Polynomial Identity Testing of Depth-3 Arithmetic Circuits with Bounded Top Fan-in. Electronic Colloquium on Computational Complexity (ECCC) 14(042) (2007)

Zeev Dvir, Amir Shpilka, Amir Yehudayoff: Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits. Electronic Colloquium on Computational Complexity (ECCC) 14(121) (2007)

Zeev Dvir, Amir Shpilka: Towards Dimension Expanders Over Finite Fields. Electronic Colloquium on Computational Complexity (ECCC) 14(122) (2007)

Ali Juma, Valentine Kabanets, Charles Rackoff, Amir Shpilka: The black-box query complexity of polynomial summation. Electronic Colloquium on Computational Complexity (ECCC) 14(125) (2007)

Elchanan Mossel, Amir Shpilka, Luca Trevisan: On epsilon-biased generators in NC⁰. Random Struct. Algorithms 29(1): 56-81 (2006)

Amir Shpilka, Avi Wigderson: Derandomizing Homomorphism Testing in General Groups. SIAM J. Comput. 36(4): 1215-1230 (2006)

Adam R. Klivans, Amir Shpilka: Learning Restricted Models of Arithmetic Circuits. Theory of Computing 2(1): 185-206 (2006)

Amir Shpilka: Constructions of Low-Degree and Error-Correcting in-Biased Generators. IEEE Conference on Computational Complexity 2006: 33-45

Ran Raz, Amir Shpilka, Amir Yehudayoff: A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits. Electronic Colloquium on Computational Complexity (ECCC) 13(060) (2006)

Ran Raz, Amir Shpilka: Deterministic polynomial identity testing in non-commutative models. Computational Complexity 14(1): 1-19 (2005)

László Babai, Amir Shpilka, Daniel Stefankovic: Locally testable cyclic codes. IEEE Transactions on Information Theory 51(8): 2849-2858 (2005)

Zeev Dvir, Amir Shpilka: An Improved Analysis of Mergers. APPROX-RANDOM 2005: 270-281

Zeev Dvir, Amir Shpilka: Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits. STOC 2005: 592-601

Zeev Dvir, Amir Shpilka: Locally Decodable Codes with 2 queries and Polynomial Identity Testing for depth 3 circuits. Electronic Colloquium on Computational Complexity (ECCC)(044) (2005)

Zeev Dvir, Amir Shpilka: An Improved Analysis of Mergers. Electronic Colloquium on Computational Complexity (ECCC)(067) (2005)

Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Amir Shpilka, Adam Smith: Sublinear Algorithms for Approximating String Compressibility and the Distribution Support Size. Electronic Colloquium on Computational Complexity (ECCC)(125) (2005)

Amir Shpilka: Constructions of low-degree and error-correcting epsilon-biased sets. Electronic Colloquium on Computational Complexity (ECCC)(155) (2005)

Ran Raz, Amir Shpilka: Deterministic Polynomial Identity Testing in Non-Commutative Models. IEEE Conference on Computational Complexity 2004: 215-222

Ran Raz, Amir Shpilka: On the Power of Quantum Proofs. IEEE Conference on Computational Complexity 2004: 260-274

Amir Shpilka, Avi Wigderson: Derandomizing homomorphism testing in general groups. STOC 2004: 427-435

Ran Raz, Amir Shpilka: Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates. SIAM J. Comput. 32(2): 488-513 (2003)

Amir Shpilka: Lower Bounds for Matrix Product. SIAM J. Comput. 32(5): 1185-1200 (2003)

Adam Klivans, Amir Shpilka: Learning Arithmetic Circuits via Partial Derivatives. COLT 2003: 463-476

László Babai, Amir Shpilka, Daniel Stefankovic: Locally Testable Cyclic Codes. FOCS 2003: 116-125

Elchanan Mossel, Amir Shpilka, Luca Trevisan: On e-Biased Generators in NC0. FOCS 2003: 136-145

Elchanan Mossel, Amir Shpilka, Luca Trevisan: On epsilon-Biased Generators in NC0. Electronic Colloquium on Computational Complexity (ECCC)(043) (2003)

Amir Shpilka: Affine projections of symmetric polynomials. J. Comput. Syst. Sci. 65(4): 639-659 (2002)

Amir Shpilka: Lower Bounds for Matrix Product. CoRR cs.CC/0201001 (2002)

Amir Shpilka, Avi Wigderson: Depth-3 arithmetic circuits over fields of characteristic zero. Computational Complexity 10(1): 1-27 (2001)

Amir Shpilka: Affine Projections of Symmetric Polynomials. IEEE Conference on Computational Complexity 2001: 160-171

Amir Shpilka: Lower Bounds for Matrix Product. FOCS 2001: 358-367

Ran Raz, Amir Shpilka: Lower bounds for matrix product, in bounded depth circuits with arbitrary gates. STOC 2001: 409-418

Amir Shpilka: Affine Projections of Symmetric Polynomials. Electronic Colloquium on Computational Complexity (ECCC) 8(35) (2001)

Amir Shpilka: Lower bounds for matrix product. Electronic Colloquium on Computational Complexity (ECCC) 8(060) (2001)

Ran Raz, Amir Shpilka: Lower Bounds for Matrix Product, in Bounded Depth Circuits with Arbitrary Gates. Electronic Colloquium on Computational Complexity (ECCC) 7(29) (2000)

Amir Shpilka, Avi Wigderson: Depth-3 Arithmetic Formulae over Fields of Characteristic Zero. IEEE Conference on Computational Complexity 1999: 87-

Amir Shpilka, Avi Wigderson: Depth-3 Arithmetic Formulae over Fields of Characteristic Zero. Electronic Colloquium on Computational Complexity (ECCC) 6(23) (1999)