HOME PUBLICATIONS TALKS  RESEARCH INTERESTS  THEORY SEMINAR     TEACHING   

 

Papers by Amir Shpilka

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

  2. Explicit Dimension Reduction and Its Applications

  3. On the degree of symmetric functions on the Boolean cube

  4. On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors

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

  6. On the Structure of Cubic and Quartic Polynomials

  7. Improved Polynomial Identity Testing for Read-Once Formulas

  8. On the degree of Boolean functions in different characteristics

  9. Reconstruction of Generalized Depth-3 Arithmetic Circuits with Bounded Top Fan-in

  10. Testing Fourier dimensionality and sparsity

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

  12. Noisy Interpolating Sets for Low Degree Polynomials

  13. Towards Dimension Expanders Over Finite Fields.

  14. Deterministic Black Box Polynomial Identity Testing of Depth-3 Arithmetic Circuits with Bounded Top Fan-in.

  15. Read-once Polynomial Identity Testing

  16. Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits

  17. The Black-Box Query Complexity of Polynomial Summation.

  18. A Lower Bound for The Size of Syntactically Multilinear Arithmetic Circuits.

  19. Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem.

  20. Interpolating Depth-3 Arithmetic Circuits with Two Multiplication Gates.

  21. Constructions of Low-Degree and Error-Correcting e-Biased Generators.

  22. An Improved Analysis of Mergers.

  23. Locally Decodable Codes with 2 queries and Polynomial Identity Testing for depth 3 circuits.
  24. Derandomizing Homomorphism Testing in General Groups.
  25. Deterministic Polynomial Identity Testing in Non-Commutative Models.

  26. On the power of Quantum Proofs.

  27. On e-bias generators in NC0.

  28. Locally Testable Cyclic Codes.

  29. Learning Arithmetic Circuits via Partial Derivatives.

  30. Lower Bounds for Small Depth Arithmetic and Boolean Circuits.

  31. Lower Bounds for Matrix Product.

  32. Lower Bounds for Matrix Product, in Bounded Depth Circuits with Arbitrary Gates.

  33. Affine Projections of Symmetric Polynomials.

  34. Depth 3 Arithmetic Circuits over Fields of Characteristic Zero.