Publications

  1. Succinct Hitting Sets and Barriers to Proving Algebraic Circuits Lower Bounds
    • Authors: Michael A. Forbes, Amir Shpilka, Ben Lee Volk
    • To appear STOC 2017

  2. Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs
    • Authors: Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk
    • CCC 2016

  3. Proof Complexity Lower Bounds from Algebraic Circuit Complexity
    • Authors: Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson
    • CCC 2016

  4. Decoding high rate Reed-Muller codes from random errors in near linear time
    • Authors: Ramprasad Saptharishi, Amir Shpilka and Ben Lee Volk
    • STOC 2016

  5. Challenges in Polynomial Factorization
    • Authors: Michael A. Forbes, Amir Shpilka
    • Sigact theory column 2015

  6. Teaching and compressing for low VC-dimension
    • Authors: Shay Moran, Amir Shpilka, Avi Wigderson and Amir Yehudayoff
    • FOCS 2015

  7. Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas
    • Authors: Rafael Mendes de Oliveira, Amir Shpilka and Ben Lee Volk
    • CC 2016 (preliminary version in CCC 2015)

  8. Reed-Muller codes for random erasures and errors
    • Authors: Emmanuel Abbe, Amir Shpilka and Avi Wigderson
    • IEEE 2015 (preliminary version in STOC 2015)

  9. Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound
    • Authors: Gillat Kol, Shay Moran, Amir Shpilka and Amir Yehudayoff
    • ICALP 2014

  10. Testing Equivalence of Polynomials under Shifts
    • Authors: Zeev Dvir, Rafael Mendes de Oliveira and Amir Shpilka
    • ICALP 2014

  11. Equivalence of Polynomial Identity Testing and Deterministic Multivariate Polynomial Factorization
    • Authors: Swastik Kopparty, Shubhangi Saraf and Amir Shpilka
    • CC 2015 (preliminary version in CCC 2014)

  12. Pseudorandomness for Multilinear Read-Once Algebraic Branching Programs, in any Order
    • Authors: Michael Forbes, Ramprasad Saptharishi and Amir Shpilka
    • STOC 2014

  13. Direct Sum Fails for Zero Error Average Communication
    • Authors: Gillat Kol, Shay Moran, Amir Shpilka and Amir Yehudayoff
    • Algorithmica 2016 (preliminary version in ITCS 2014)

  14. On the Structure of Boolean Functions with Small Spectral Norm
    • Authors: Amir Shpilka, Avishay Tal and Ben lee Volk
    • Combinatorica 2017 (preliminary version in ITCS 2014)

  15. Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing
    • Authors: Michael Forbes and Amir Shpilka
    • RANDOM 2013

  16. Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs
    • Authors: Michael Forbes and Amir Shpilka
    • FOCS 2013

  17. Capacity achieving multiwrite WOM codes
    • Author: Amir Shpilka
    • IEEE TIT 2014

  18. High Sum-Rate Three-Write and Non-Binary WOM Codes
    • Authors: Eitan Yaakobi and Amir Shpilka
    • IEEE TIT 2014 (preliminary version in ISIT 2012)

  19. On identity testing of tensors, low-rank recovery and compressed sensing
    • Authors: Michael Forbes and Amir Shpilka
    • STOC 2012

  20. On sunflowers and matrix multiplication
    • Authors: Noga Alon, Amir Shpilka and Chris Umans
    • CC 2013 (preliminary version in CCC 2012)

  21. New constructions of WOM codes using the Wozencraft ensemble
    • Author: Amir Shpilka
    • IEEE TIT 2013 (preliminary version in LATIN 2012)

  22. On the degree of univariate polynomials over the integers
    • Authors: Gil Cohen, Amir Shpilka and Avishay Tal
    • ITCS 2012

  23. Optimal testing of multivariate polynomials over small prime fields
    • Authors: Elad Haramaty, Amir Shpilka and Madhu Sudan
    • SICOMP 2013 (preliminary version in FOCS 2011)

  24. Tight lower bounds for 2-query LCCs over finite fields
    • Authors: Arnab Bhattacharyya, Zeev Dvir, Shubhangi Saraf and Amir Shpilka
    • Combinatorica 2016 (preliminary version in FOCS 2011)

  25. On sums of locally testable affine invariant properties
    • Authors: Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka and Madhu Sudan
    • RANDOM 2011

  26. Symmetric LDPC codes are not necessarily locally testable
    • Authors: Eli Ben-Sasson, Ghid Maatouk, Amir Shpilka and Madhu Sudan
    • CCC 2011

  27. On the minimal Fourier degree of symmetric Boolean functions
    • Authors: Amir Shpilka and Avishay Tal
    • CC 2014 (preliminary version in CCC 2011)

  28. Explicit dimension reduction and its applications
    • Authors: Zohar S. Karnin, Yuval Rabani and Amir Shpilka
    • SICOMP 2012 (preliminary version in CCC 2011)

  29. Arithmetic circuits: A survey of recent results and open questions
    • Authors: Amir Shpilka and Amir Yehudayoff
    • Foundations and Trends in Theoretical Computer Science 2010
    • Foundations and Trends in TCS version.

  30. Pseudorandom generators for CC0[p] and the Fourier spectrum of low-degree polynomials over finite fields
    • Authors: Shachar Lovett, Partha Mukhopadhyay and Amir Shpilka
    • CC 2013 (preliminary version in FOCS 2010)

  31. On the relation between polynomial identity testing and finding variable disjoint factors
    • Authors: Amir Shpilka and Ilya Volkovich
    • ICALP  2010

  32. Deterministic identity testing of depth 4 multilinear circuits with bounded top fan-in
    • Authors: Zohar S. Karnin, Partha Mukhppadhyay, Amir Shpilka and Ilya Volkovich
    • SICOMP 2013 (preliminary version in STOC 2010)

  33. On the structure of cubic and quartic polynomials
    • Authors: Elad Haramaty and Amir Shpilka
    • STOC 2010

  34. Improved polynomial identity testing for read-once formulas
    • Authors: Amir Shpilka and Ilya Volkovich
    • RANDOM 2009
    • Journal version combining PIT algorithms from the paper "Read-Once polynomial Identity Testing" (STOC 2008).

  35. On the degree of boolean functions in different characteristics
    • Authors: Parikshit Gopalan, Shachar Lovett and Amir Shpilka
    • CC 2010 (preliminary version in CCC 2009)

  36. Reconstruction of generalized depth-3 arithmetic circuits with bounded top fan-in
    • Authors: Zohar S. Karnin and Amir Shpilka
    • CCC 2009

  37. Testing Fourier dimensionality and sparsity
    • Authors: Parikshit Gopalan, Ryan O'Donnell, Rocco Servedio, Amir Shpilka and Karl Wimmer
    • SICOMP 2011 (preliminary version in ICALP 2009)

  38. Explicit construction of a small epsilon-net for linear threshold functions
    • Authors: Yuval Rabani and Amir Shpilka
    • SICOMP 2010 (preliminary version in STOC 2009)

  39. Noisy interpolating sets for low degree polynomials
    • Authors: Zeev Dvir and Amir Shpilka
    • ToC 2011 (preliminary version in CCC 2008)

  40. Towards dimension expanders over finite fields
    • Authors: Zeev Dvir and Amir Shpilka
    • Combinatorica 2011 (preliminary version in CCC 2008)

  41. Deterministic black box polynomial identity testing of depth-3 arithmetic circuits with bounded top fan-in
    • Authors: Zohar S. Karnin and Amir Shpilka
    • Combinatorica 2011 (preliminary version in CCC 2008)

  42. Read-once polynomial identity testing
    • Authors: Amir Shpilka and Ilya Volkovich
    • ToC 2014 (preliminary version in STOC 2008)
    • Journal version containing algorithms for Read-Once testing

  43. Hardness-randomness tradeoffs for bounded depth arithmetic circuits
    • Authors: Zeev Dvir, Amir Shpilka and Amir Yehudayoff
    • SICOMP 2009 (preliminary version in STOC 2008)
    • New version: fixed a flaw in the proof of lemma 3.1 in the SICOMP version
    • Errata: the main statmenet holds only for fields of characteristic zero or high enough characteristic

  44. The black-box query complexity of polynomial summation
    • Authors: Ali Juma, Valentine Kabanets, Charles Rackoff and Amir Shpilka
    • CC 2009 (preliminary version in ECCC Report TR07-125, 2007)

  45. A lower bound for the size of syntactically multilinear arithmetic circuits
    • Authors: Ran Raz, Amir Shpilka and Amir Yehudayoff
    • SICOMP 2008 (preliminary version in FOCS 2007)

  46. Strong lower bounds for approximating distribution support size and the distinct elements problem
    • Authors: Sofya Raskhodnikova, Dana Ron, Amir Shpilka and Adam Smith
    • SICOMP 2009 (preliminary version in FOCS 2007)

  47. Interpolating depth-3 arithmetic circuits with two multiplication gates
    • Author: Amir Shpilka
    • SICOMP 2009 (preliminary version in STOC 2007)

  48. Constructions of low-degree and error-correcting e-biased generators
    • Author: Amir Shpilka
    • CC 2009 (preliminary version in CCC 2006)

  49. An improved analysis of mergers
    • Authors: Zeev Dvir and Amir Shpilka
    • CC 2007 (preliminary version in Random 2005)

  50. Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits
    • Authors: Zeev Dvir and Amir Shpilka
    • SICOMP 2006 (preliminary version in STOC 2005)

  51. Derandomizing homomorphism testing in general groups
    • Authors: Amir Shpilka and Avi Wigderson
    • SICOMP 2006 (preliminary version in STOC 2004)

  52. Deterministic polynomial identity testing in non-commutative models

  53. On the power of quantum proofs
    • Authors: Ran Raz and Amir Shpilka
    • CCC 2004

  54. On e-bias generators in NC0

  55. Locally testable cyclic codes

  56. Learning arithmetic circuits via partial derivatives

  57. Lower bounds for small depth arithmetic and boolean circuits

  58. Lower bounds for matrix product
    • Author: Amir Shpilka
    • SICOMP 2003 (preliminary version in FOCS 2001)

  59. Lower bounds for matrix product, in bounded depth circuits with arbitrary gates

  60. Affine projections of symmetric polynomials

  61. Depth 3 arithmetic circuits over fields of characteristic zero