Amir Shpilka

Publications

1. New Bounds on Quotient Polynomials with Applications to Exact Divisibility and Divisibility Testing of Sparse Polynomials
   • Authors: Ido Nahshon, Amir Shpilka.
   • 2023


2. Discreteness of asymptotic tensor ranks
   • Authors: Jop Briët, Matthias Christandl, Itai Leigh, Amir Shpilka, Jeroen Zuiddam.
   • 2023


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


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


5. Reed-Muller Codes
   • Authors: Emmanuel Abbe, Ori Sberlo, Amir Shpilka, Min Ye
   • Foundations and Trends in Theoretical Computer Science 2023
   • Foundations and Trends in TCS version.


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


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


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


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


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


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


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


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


14. A generalized Sylvester-Gallai type theorem for quadratic polynomials
    • Authors: Shir Peleg, Amir Shpilka
    • Forum of Mathematics, Sigma 2022 (preliminary version in CCC 2020)


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


76. Lower bounds for matrix product
    • Author: Amir Shpilka
    • SICOMP 2003 (preliminary version in FOCS 2001)
    
    
77. 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)


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


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