Publications

Polynomial time deterministic identity testing algorithm for \(\Sigma^{[3]}\Pi\Sigma\Pi^{[2]}\) circuits via EdelsteinKelly type theorem for quadratic polynomials
 Authors: Shir Peleg, Amir Shpilka

ReedMuller Codes: Theory and Algorithms
 Authors: Emmanuel Abbe, Amir Shpilka, Min Ye

Explicit and Efficient Constructions of Coding Schemes for the Binary Deletion Channel and the Poisson Repeat Channel
 Authors: Roni Con, Amir Shpilka
 ISIT 2020

A generalized SylvesterGallai type theorem for quadratic polynomials
 Authors: Shir Peleg, Amir Shpilka
 CCC 2020

On the Performance of ReedMuller Codes with respect to Random Errors and Erasures
 Authors: Ori Sberlo, Amir Shpilka
 SODA 2020

SylvesterGallai type theorems for quadratic polynomials
 Author: Amir Shpilka
 Discrete Analysis (preliminary version in STOC 2019)

A learning problem that is independent of the set theory ZFC axioms
 Authors: Shai BenDavid, Pavel Hrubes, Shay Moran, Amir Shpilka, Amir Yehudayoff
 Nature Machine Intelligence 2019

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

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)

Identity Testing and Lower Bounds for Readk Oblivious Algebraic Branching Programs
 Authors: Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk
 ToCT 2018 (preliminary version in CCC 2016)

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

Decoding high rate ReedMuller 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)

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

Teaching and compressing for low VCdimension
 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)

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)

ReedMuller codes for random erasures and errors
 Authors: Emmanuel Abbe, Amir Shpilka and Avi Wigderson
 IEEE TIT 2015 (preliminary version in STOC 2015)

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)

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

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)

Pseudorandomness for Multilinear ReadOnce Algebraic Branching Programs, in any Order
 Authors: Michael Forbes, Ramprasad Saptharishi and Amir Shpilka
 STOC 2014

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)

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)

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

Quasipolynomialtime Identity Testing of NonCommutative and ReadOnce Oblivious Algebraic Branching Programs
 Authors: Michael Forbes and Amir Shpilka
 FOCS 2013

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

High SumRate ThreeWrite and NonBinary WOM Codes
 Authors: Eitan Yaakobi and Amir Shpilka
 IEEE TIT 2014 (preliminary version in ISIT 2012)

On identity testing of tensors, lowrank recovery and compressed sensing
 Authors: Michael Forbes and Amir Shpilka
 STOC 2012

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

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

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

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

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

On sums of locally testable
affine invariant properties
 Authors: Eli BenSasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka and Madhu Sudan
 RANDOM 2011

Symmetric LDPC codes
are not necessarily locally testable
 Authors: Eli BenSasson, Ghid Maatouk, Amir Shpilka and Madhu Sudan
 CCC 2011

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

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

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.
 Pseudorandom
generators for CC0[p] and the Fourier spectrum of lowdegree polynomials over
finite fields
 Authors: Shachar Lovett, Partha Mukhopadhyay and Amir Shpilka
 CC 2013 (preliminary version in FOCS 2010)
 On
the relation between polynomial identity testing and finding variable disjoint factors
 Authors: Amir Shpilka and Ilya Volkovich
 ICALP 2010
 Deterministic
identity testing of depth 4 multilinear circuits with bounded top fanin
 Authors: Zohar S. Karnin, Partha Mukhppadhyay, Amir Shpilka and Ilya Volkovich
 SICOMP 2013 (preliminary version in STOC 2010)
 On the structure of cubic
and quartic polynomials
 Authors: Elad Haramaty and Amir Shpilka
 STOC 2010
 Improved polynomial
identity testing for readonce formulas
 Authors: Amir Shpilka and Ilya Volkovich
 CC 2015 (preliminary version in RANDOM 2009)
 Journal version combining PIT algorithms from the paper "ReadOnce polynomial Identity Testing" (STOC 2008).
 On the degree
of boolean functions in different characteristics
 Authors: Parikshit Gopalan, Shachar Lovett and Amir Shpilka
 CC 2010 (preliminary version in CCC 2009)
 Reconstruction
of generalized depth3 arithmetic circuits with bounded top
fanin
 Authors: Zohar S. Karnin and Amir Shpilka
 CCC 2009

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)

Explicit construction of a small epsilonnet
for linear threshold functions
 Authors: Yuval Rabani and Amir Shpilka
 SICOMP 2010 (preliminary version in STOC 2009)

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

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

Deterministic black box polynomial identity
testing
of depth3 arithmetic
circuits with bounded top fanin
 Authors: Zohar S. Karnin and Amir Shpilka
 Combinatorica 2011 (preliminary version in CCC 2008)

Readonce polynomial identity testing
 Authors: Amir Shpilka and Ilya Volkovich
 ToC 2014 (preliminary version in STOC 2008)
 Journal version containing algorithms for ReadOnce testing
 Hardnessrandomness
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

The blackbox
query complexity of polynomial summation
 Authors: Ali Juma, Valentine Kabanets, Charles Rackoff and Amir Shpilka
 CC 2009 (preliminary version in ECCC Report TR07125, 2007)
 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)
 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)

Interpolating depth3 arithmetic circuits
with two multiplication gates
 Author: Amir Shpilka
 SICOMP 2009 (preliminary version in STOC 2007)

Constructions of lowdegree and errorcorrecting ebiased
generators
 Author: Amir Shpilka
 CC 2009 (preliminary version in CCC 2006)

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

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)

Derandomizing homomorphism
testing in general groups
 Authors: Amir Shpilka and Avi Wigderson
 SICOMP 2006 (preliminary version in STOC 2004)
 Deterministic polynomial identity testing in noncommutative models
 Authors: Ran Raz and Amir Shpilka
 CC 2005 (preliminary version in CCC 2004)
 On
the power of quantum proofs
 Authors: Ran Raz and Amir Shpilka
 CCC 2004
 On ebias generators in NC0
 Authors: Elchanan Mossel, Amir Shpilka and Luca Trevisan
 RSA 2006 (preliminary version in FOCS 2003)
 Locally testable cyclic codes
 Authors: Laszlo Babai, Amir Shpilka and Daniel Stefankovic
 IEEE TIT 2005 (preliminary version in FOCS 2003)
 Learning arithmetic circuits via partial derivatives
 Authors: Adam Klivans and Amir Shpilka
 ToC 2006 (preliminary version in COLT 2003)
 Lower bounds for small depth arithmetic and boolean circuits
 Author: Amir Shpilka
 Ph.D. Thesis 2001
 Lower
bounds
for matrix product
 Author: Amir Shpilka
 SICOMP 2003 (preliminary version in FOCS 2001)
 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)
 Affine projections of symmetric polynomials
 Author: Amir Shpilka
 JCSS 2002 (preliminary version in CCC 2001)
 Depth 3 arithmetic circuits over fields of characteristic zero
 Authors: Amir Shpilka and Avi Wigderson
 CC 2001 (preliminary version in CCC 1999)