HOME PUBLICATIONS TALKS  RESEARCH INTERESTS  THEORY LUNCH     TEACHING   

 

Papers by Amir Shpilka

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

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

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

  4. Capacity achieving multiwrite WOM codes

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

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

  7. On sunflowers and matrix multiplication

  8. New constructions of WOM codes using the Wozencraft ensemble

  9. On the degree of univariate polynomials over the integers

  10. Optimal testing of multivariate polynomials over small prime fields

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

  12. On sums of locally testable affine invariant properties

  13. Symmetric LDPC codes are not necessarily locally testable

  14. On the minimal Fourier degree of symmetric boolean functions

  15. Explicit dimension reduction and its applications

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

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

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

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

  20. On the structure of cubic and quartic polynomials

  21. Improved polynomial identity testing for read-once formulas

  22. On the degree of boolean functions in different characteristics

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

  24. Testing Fourier dimensionality and sparsity

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

  26. Noisy interpolating sets for low degree polynomials

  27. Towards dimension expanders over finite fields

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

  29. Read-once polynomial identity testing

  30. Hardness-randomness tradeoffs for bounded depth arithmetic circuits

  31. The black-box query complexity of polynomial summation

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

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

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

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

  36. An improved analysis of mergers

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

  40. On the power of quantum proofs
  41. On e-bias generators in NC0

  42. Locally testable cyclic codes

  43. Learning arithmetic circuits via partial derivatives

  44. Lower bounds for small depth arithmetic and boolean circuits

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

  47. Affine projections of symmetric polynomials

  48. Depth 3 arithmetic circuits over fields of characteristic zero