Papers by Amir Shpilka

Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound

Authors: Gillat Kol, Shay Moran, Amir Shpilka and Amir Yehudayoff
 [bib] To appear in ICALP 2014

Testing Equivalence of Polynomials under Shifts

Authors: Zeev Dvir, Rafael Mendes de Oliveira and Amir Shpilka
 [bib] To appear in ICALP 2014

Equivalence of Polynomial Identity Testing and Deterministic Multivariate Polynomial Factorization

Authors: Swastik Kopparty, Shubhangi Saraf and Amir Shpilka
 [bib] To appear in CCC 2014

Pseudorandomness for Multilinear ReadOnce Algebraic Branching Programs, in any Order

Authors: Michael Forbes, Ramprasad Saptharishi and Amir Shpilka
 [bib] To appear in STOC 2014

Direct Sum Fails for Zero Error Average Communication

Authors: Gillat Kol, Shay Moran, Amir Shpilka and Amir Yehudayoff
 [bib] ITCS 2014

On the Structure of Boolean Functions with Small Spectral Norm

Authors: Amir Shpilka, Avishay Tal and Ben lee Volk
 [bib] ITCS 2014

Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing

Authors: Michael Forbes and Amir Shpilka
 [bib] RANDOM 2013

Quasipolynomialtime Identity Testing of NonCommutative and ReadOnce Oblivious Algebraic Branching Programs

Authors: Michael Forbes and Amir Shpilka
 [bib] FOCS 2013

Capacity achieving multiwrite WOM codes

Author: Amir Shpilka
 [bib] Manuscript 2012

High SumRate ThreeWrite and NonBinary WOM Codes

Authors: Eitan Yaakobi and Amir Shpilka
 [bib] ISIT 2012

On identity testing of tensors, lowrank recovery and compressed sensing

Authors: Michael Forbes and Amir Shpilka
 [bib] STOC 2012

On sunflowers and matrix multiplication

Authors: Noga Alon, Amir Shpilka and Chris Umans
 [bib] CC 2013 (preliminary version in CCC 2012)

New constructions of WOM codes using the Wozencraft ensemble

Author: Amir Shpilka
 [bib] 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
 [bib] ITCS 2012

Optimal testing of multivariate polynomials over small prime fields
 Authors: Elad Haramaty, Amir Shpilka and Madhu Sudan
 [bib] 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
 [bib] FOCS 2011

On sums of locally testable
affine invariant properties

Authors: Eli BenSasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka and Madhu Sudan

[bib] RANDOM 2011

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

[bib] CCC 2011

On the minimal Fourier degree of symmetric Boolean functions

Authors: Amir Shpilka and Avishay Tal

[bib] CCC 2011

Explicit dimension
reduction and its applications

Authors: Zohar S. Karnin, Yuval Rabani and Amir Shpilka

[bib] SICOMP 2012 (preliminary version in CCC 2011)

Arithmetic circuits: A survey of recent results and open questions

Authors: Amir Shpilka and Amir Yehudayoff
 [bib]
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
 [bib] FOCS 2010
 On
the relation between polynomial identity testing and finding variable disjoint factors
 Authors: Amir Shpilka and Ilya Volkovich
 [bib] 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
 [bib] STOC 2010
 On the structure of cubic
and quartic polynomials
 Authors: Elad Haramaty and Amir Shpilka
 [bib] STOC 2010
 Improved polynomial
identity testing for readonce formulas
 Authors: Amir Shpilka and Ilya Volkovich
 [bib] 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
 [bib] CC 2010
(preliminary version in CCC 2009)
 Reconstruction
of generalized depth3 arithmetic circuits with bounded top
fanin
 Authors: Zohar S. Karnin and Amir Shpilka
 [bib] CCC
2009

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

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

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

Towards
dimension expanders over finite fields
 Authors: Zeev Dvir and Amir Shpilka
 [bib] 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
 [bib] Combinatorica
2011 (preliminary version in CCC
2008)

Readonce polynomial identity testing
 Authors: Amir Shpilka and Ilya Volkovich
 [bib] STOC 2008
 Journal version containing algorithms for ReadOnce testing
 Hardnessrandomness
tradeoffs
for bounded depth arithmetic circuits
 Authors: Zeev Dvir, Amir Shpilka and Amir Yehudayoff
 [bib] SICOMP 2009 (preliminary version in STOC 2008)
 New version: fixed a flaw in the proof of lemma 3.1 in the SICOMP version

The blackbox
query complexity of polynomial summation
 Authors: Ali Juma, Valentine Kabanets, Charles Rackoff and Amir Shpilka
 [bib] 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
 [bib] SICOMP 2008
(preliminary version in FOCS 2 2007)
 Strong lower bounds for
approximating distribution support size and the distinct elements problem
 Authors: Sofya Raskhodnikova, Dana Ron, Amir Shpilka and Adam Smith
 [bib]
SICOMP 2009 (preliminary version in FOCS 2007)

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

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

An improved analysis of mergers
 Authors: Zeev Dvir and Amir Shpilka
 [bib] 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
 [bib] SICOMP
2006 (preliminary version in STOC 2005)

Derandomizing homomorphism
testing in general groups
 Authors: Amir Shpilka and Avi Wigderson
 [bib] SICOMP
2006 (preliminary version in STOC 2004)
 Deterministic
polynomial identity testing
in noncommutative models
 Authors: Ran Raz and Amir Shpilka
 [bib] CC
2005 (preliminary version in CCC 2004)
 On
the power of quantum proofs
 Authors: Ran Raz and Amir Shpilka
 [bib ]
CCC 2004
 On
ebias generators in NC0
 Authors: Elchanan Mossel, Amir Shpilka and Luca Trevisan

[bib] RSA 2006
(preliminary version in FOCS 2003)
 Locally
testable cyclic codes
 Authors: Laszlo Babai, Amir Shpilka and Daniel Stefankovic

[bib]
IEEE TIT 2005 (preliminary version in FOCS 2003)

Learning
arithmetic circuits
via partial derivatives
 Authors: Adam Klivans and Amir Shpilka

[bib]
ToC 2006 (preliminary version in COLT 2003)

Lower bounds for small depth arithmetic and boolean circuits
 Author: Amir Shpilka
 [bib]
Ph.D. Thesis 2001
 Lower
bounds
for matrix product
 Author: Amir Shpilka
 [bib]
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

[bib]
SICOMP
2003 (preliminary version in STOC 2001)

Affine projections of symmetric polynomials
 Author: Amir Shpilka
 [bib]
JCSS
2002 (preliminary version in CCC 2001)

Depth 3 arithmetic circuits
over fields of characteristic zero
 Authors: Amir Shpilka and Avi Wigderson

[bib]
CC 2001 (preliminary version in CCC 1999)