HOME PUBLICATIONS TALKS  RESEARCH INTERESTS  THEORY LUNCH     TEACHING   

 

Papers by Amir Shpilka

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

  2. On sunflowers and matrix multiplication

  3. New constructions of WOM codes using the Wozencraft ensemble

  4. On the degree of univariate polynomials over the integers

  5. Optimal testing of multivariate polynomials over small prime fields

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

  7. On sums of locally testable affine invariant properties

  8. Symmetric LDPC codes are not necessarily locally testable

  9. On the minimal Fourier degree of symmetric boolean functions

  10. Explicit dimension reduction and its applications

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

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

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

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

  15. On the structure of cubic and quartic polynomials

  16. Improved polynomial identity testing for read-once formulas

  17. On the degree of boolean functions in different characteristics

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

  19. Testing Fourier dimensionality and sparsity

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

  21. Noisy interpolating sets for low degree polynomials

  22. Towards dimension expanders over finite fields

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

  24. Read-once polynomial identity testing

  25. Hardness-randomness tradeoffs for bounded depth arithmetic circuits

  26. The black-box query complexity of polynomial summation

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

  28. Strong lower bounds for approximating distribution support size and the distinct elements problem

  29. Interpolating depth-3 arithmetic circuits with two multiplication gates

  30. Constructions of low-degree and error-correcting e-biased generators

  31. An improved analysis of mergers

  32. Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits
  33. Derandomizing homomorphism testing in general groups
  34. Deterministic polynomial identity testing in non-commutative models

  35. OOn the power of quantum proofs
  36. On e-bias generators in NC0

  37. Locally testable cyclic codes

  38. Learning arithmetic circuits via partial derivatives

  39. Lower bounds for small depth arithmetic and boolean circuits

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

  42. Affine projections of symmetric polynomials

  43. Depth 3 arithmetic circuits over fields of characteristic zero