Amir Shpilka

Publications

1. Tensor Reconstruction Beyond Constant Rank
   • Authors: Shir Peleg, Amir Shpilka, Ben Lee Volk
   • 2022


2. On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts
   • Authors: Suryajith Chillara, Coral Grichener, Amir Shpilka
   • STACS 2023


3. Reed-Muller Codes
   • Authors: Emmanuel Abbe, Ori Sberlo, Amir Shpilka, Min Ye
   • Foundations and Trends in Communications and Information Theory 2023


4. Robust Sylvester-Gallai type theorem for quadratic polynomials
   • Authors: Shir Peleg, Amir Shpilka
   • SOCG 2022


5. Explicit and Efficient Constructions of linear Codes Against Adversarial Insertions and Deletions
   • Authors: Roni Con, Amir Shpilka, Zachi Tamo
   • IEEE 2022


6. Reed Solomon Codes Against Adversarial Insertions and Deletions
   • Authors: Roni Con, Amir Shpilka, Zachi Tamo
   • IEEE 2023 (Preliminary verstion in ISIT 2022)


7. Lower Bounds on Stabilizer Rank
   • Authors: Shir Peleg, Amir Shpilka, Ben Lee Volk
   • Quantum 2022 (Preliminary version in ITCS 2022, QIP 2022)


8. Hitting Sets and Reconstruction for Dense Orbits in VP\(_e\) and \(\Sigma\Pi\Sigma\) circuits
   • Authors: Dori Medini, Amir Shpilka
   • CCC 2021


9. Polynomial time deterministic identity testing algorithm for \(\Sigma^{[3]}\Pi\Sigma\Pi^{[2]}\) circuits via Edelstein-Kelly type theorem for quadratic polynomials
   • Authors: Shir Peleg, Amir Shpilka
   • STOC 2021


10. Reed-Muller Codes: Theory and Algorithms
    • Authors: Emmanuel Abbe, Amir Shpilka, Min Ye
    • IEEE TIT 2020


11. Improved Constructions of Coding Schemes for the Binary Deletion Channel and the Poisson Repeat Channel
    • Authors: Roni Con, Amir Shpilka
    • IEEE TIT 2022 (preliminary version in ISIT 2020)


12. A generalized Sylvester-Gallai type theorem for quadratic polynomials
    • Authors: Shir Peleg, Amir Shpilka
    • CCC 2020


13. On the Performance of Reed-Muller Codes with respect to Random Errors and Erasures
    • Authors: Ori Sberlo, Amir Shpilka
    • SODA 2020


14. Sylvester-Gallai type theorems for quadratic polynomials
    • Author: Amir Shpilka
    • Discrete Analysis (preliminary version in STOC 2019)


15. A learning problem that is independent of the set theory ZFC axioms
    • Authors: Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, Amir Yehudayoff
    • Nature Machine Intelligence 2019
    • Invited paper STOC 2021


16. A PSPACE Construction of a Hitting Set for the Closure of Small Algebraic Circuits
    • Authors: Michael A. Forbes, Amir Shpilka
    • STOC 2018


17. Succinct Hitting Sets and Barriers to Proving Algebraic Circuits Lower Bounds
    • Authors: Michael A. Forbes, Amir Shpilka, Ben Lee Volk
    • ToC 2018 (preliminary version in STOC 2017)


18. 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
    • ToCT 2018 (preliminary version in CCC 2016)


19. Proof Complexity Lower Bounds from Algebraic Circuit Complexity
    • Authors: Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson
    • ToC 2021 (preliminary version in CCC 2016)


20. Decoding high rate Reed-Muller codes from random errors in near linear time
    • Authors: Ramprasad Saptharishi, Amir Shpilka and Ben Lee Volk
    • IEEE TIT 2017 (preliminary version in STOC 2016)


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


22. Teaching and compressing for low VC-dimension
    • Authors: Shay Moran, Amir Shpilka, Avi Wigderson and Amir Yehudayoff
    • In A Journey Through Discrete Mathematics: A Tribute to Jiri Matousek (preliminary version in FOCS 2015)


23. 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)


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


25. Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound
    • Authors: Gillat Kol, Shay Moran, Amir Shpilka and Amir Yehudayoff
    • CC 2019 (preliminary version in ICALP 2014)


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


27. 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)


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


29. 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)


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


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


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


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


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


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


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


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


38. On the degree of univariate polynomials over the integers
    • Authors: Gil Cohen, Amir Shpilka and Avishay Tal
    • Combinatorica 2017 (preliminary version in LITCS 2012)


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


40. 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)


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


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


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


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


45. 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.


46. 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)


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


48. 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)


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


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


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


52. Reconstruction of generalized depth-3 arithmetic circuits with bounded top fan-in
    • Authors: Zohar S. Karnin and Amir Shpilka
    • CCC 2009
    • There is a flaw in the proof of Theorem 5.3. See the paper Tensor Reconstruction Beyond Constant Rank for explanation and correction.


53. 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)


54. Explicit construction of a small epsilon-net for linear threshold functions
    • Authors: Yuval Rabani and Amir Shpilka
    • SICOMP 2010 (preliminary version in STOC 2009)
    • New version: fixed the proof of Lemma 2.7 and other inaccuracies in the SICOMP version
    • Summary of changes


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


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


57. 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)


58. 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


59. 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


60. 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)


61. 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)


62. 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)


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


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


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


66. 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)
    
    
67. Derandomizing homomorphism testing in general groups
    • Authors: Amir Shpilka and Avi Wigderson
    • SICOMP 2006 (preliminary version in STOC 2004)
    
    
68. Deterministic polynomial identity testing in non-commutative models
• Authors: Ran Raz and Amir Shpilka
• CC 2005 (preliminary version in CCC 2004)


69. On the power of quantum proofs
    • Authors: Ran Raz and Amir Shpilka
    • CCC 2004
    
    
70. On e-bias generators in NC0
• Authors: Elchanan Mossel, Amir Shpilka and Luca Trevisan
• RSA 2006 (preliminary version in FOCS 2003)


71. Locally testable cyclic codes
• Authors: Laszlo Babai, Amir Shpilka and Daniel Stefankovic
• IEEE TIT 2005 (preliminary version in FOCS 2003)


72. Learning arithmetic circuits via partial derivatives
• Authors: Adam Klivans and Amir Shpilka
• ToC 2006 (preliminary version in COLT 2003)


73. Lower bounds for small depth arithmetic and boolean circuits
• Author: Amir Shpilka
• Ph.D. Thesis 2001


74. Lower bounds for matrix product
    • Author: Amir Shpilka
    • SICOMP 2003 (preliminary version in FOCS 2001)
    
    
75. Lower bounds for matrix product, in bounded depth circuits with arbitrary gates
• Authors: Ran Raz and Amir Shpilka
• SICOMP 2003 (preliminary version in STOC 2001)


76. Affine projections of symmetric polynomials
• Author: Amir Shpilka
• JCSS 2002 (preliminary version in CCC 2001)


77. Depth 3 arithmetic circuits over fields of characteristic zero
• Authors: Amir Shpilka and Avi Wigderson
• CC 2001 (preliminary version in CCC 1999)