Papers by Amir Shpilka

  1. Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound

  2. Testing Equivalence of Polynomials under Shifts

  3. Equivalence of Polynomial Identity Testing and Deterministic Multivariate Polynomial Factorization

  4. Pseudorandomness for Multilinear Read-Once Algebraic Branching Programs, in any Order

  5. Direct Sum Fails for Zero Error Average Communication

  6. On the Structure of Boolean Functions with Small Spectral Norm

  7. Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing

  8. Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs

  9. Capacity achieving multiwrite WOM codes

  10. High Sum-Rate Three-Write and Non-Binary WOM Codes

  11. On identity testing of tensors, low-rank recovery and compressed sensing

  12. On sunflowers and matrix multiplication

  13. New constructions of WOM codes using the Wozencraft ensemble

  14. On the degree of univariate polynomials over the integers

  15. Optimal testing of multivariate polynomials over small prime fields

  16. Tight lower bounds for 2-query LCCs over finite fields

  17. On sums of locally testable affine invariant properties

  18. Symmetric LDPC codes are not necessarily locally testable

  19. On the minimal Fourier degree of symmetric Boolean functions

  20. Explicit dimension reduction and its applications

  21. Arithmetic circuits: A survey of recent results and open questions

  22. Pseudorandom generators for CC0[p] and the Fourier spectrum of low-degree polynomials over finite fields

  23. On the relation between polynomial identity testing and finding variable disjoint factors

  24. Deterministic identity testing of depth 4 multilinear circuits with bounded top fan-in

  25. On the structure of cubic and quartic polynomials

  26. Improved polynomial identity testing for read-once formulas

  27. On the degree of boolean functions in different characteristics

  28. Reconstruction of generalized depth-3 arithmetic circuits with bounded top fan-in

  29. Testing Fourier dimensionality and sparsity

  30. Explicit construction of a small epsilon-net for linear threshold functions

  31. Noisy interpolating sets for low degree polynomials

  32. Towards dimension expanders over finite fields

  33. Deterministic black box polynomial identity testing of depth-3 arithmetic circuits with bounded top fan-in

  34. Read-once polynomial identity testing

  35. Hardness-randomness tradeoffs for bounded depth arithmetic circuits

  36. The black-box query complexity of polynomial summation

  37. A lower bound for the size of syntactically multilinear arithmetic circuits

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

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

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

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

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

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

  44. Deterministic polynomial identity testing in non-commutative models

  45. On the power of quantum proofs
    • Authors: Ran Raz and Amir Shpilka
    •  [bib ] CCC 2004

  46. On e-bias generators in NC0

  47. Locally testable cyclic codes

  48. Learning arithmetic circuits via partial derivatives

  49. Lower bounds for small depth arithmetic and boolean circuits

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

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

  52. Affine projections of symmetric polynomials

  53. Depth 3 arithmetic circuits over fields of characteristic zero