Publications

  • Lower Bounds for Set-Multilinear Branching Programs

  • New Bounds on Quotient Polynomials with Applications to Exact Divisibility and Divisibility Testing of Sparse Polynomials

  • Optimal Two-Dimensional Reed–Solomon Codes Correcting Insertions and Deletions

  • Discreteness of asymptotic tensor ranks

  • Tensor Reconstruction Beyond Constant Rank

  • On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts

  • Reed-Muller Codes

  • Robust Sylvester-Gallai type theorem for quadratic polynomials

  • Explicit and Efficient Constructions of linear Codes Against Adversarial Insertions and Deletions

  • Reed Solomon Codes Against Adversarial Insertions and Deletions

  • Lower Bounds on Stabilizer Rank

  • Hitting Sets and Reconstruction for Dense Orbits in VP\(_e\) and \(\Sigma\Pi\Sigma\) circuits

  • Polynomial time deterministic identity testing algorithm for \(\Sigma^{[3]}\Pi\Sigma\Pi^{[2]}\) circuits via Edelstein-Kelly type theorem for quadratic polynomials

  • Reed-Muller Codes: Theory and Algorithms

  • Improved Constructions of Coding Schemes for the Binary Deletion Channel and the Poisson Repeat Channel

  • A generalized Sylvester-Gallai type theorem for quadratic polynomials

  • On the Performance of Reed-Muller Codes with respect to Random Errors and Erasures

  • Sylvester-Gallai type theorems for quadratic polynomials

  • A learning problem that is independent of the set theory ZFC axioms

  • A PSPACE Construction of a Hitting Set for the Closure of Small Algebraic Circuits

  • Succinct Hitting Sets and Barriers to Proving Algebraic Circuits Lower Bounds

  • Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs

  • Proof Complexity Lower Bounds from Algebraic Circuit Complexity

  • Decoding high rate Reed-Muller codes from random errors in near linear time

  • Challenges in Polynomial Factorization

  • Teaching and compressing for low VC-dimension

  • Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas

  • Reed-Muller codes for random erasures and errors

  • Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound

  • Testing Equivalence of Polynomials under Shifts

  • Equivalence of Polynomial Identity Testing and Deterministic Multivariate Polynomial Factorization

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

  • Direct Sum Fails for Zero Error Average Communication

  • On the Structure of Boolean Functions with Small Spectral Norm

  • Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing

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

  • Capacity achieving multiwrite WOM codes

  • High Sum-Rate Three-Write and Non-Binary WOM Codes

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

  • On sunflowers and matrix multiplication

  • New constructions of WOM codes using the Wozencraft ensemble

  • On the degree of univariate polynomials over the integers

  • Optimal testing of multivariate polynomials over small prime fields

  • Tight lower bounds for 2-query LCCs over finite fields

  • On sums of locally testable affine invariant properties

  • Symmetric LDPC codes are not necessarily locally testable

  • On the minimal Fourier degree of symmetric Boolean functions

  • Explicit dimension reduction and its applications

  • Arithmetic circuits: A survey of recent results and open questions

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

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

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

  • On the structure of cubic and quartic polynomials

  • Improved polynomial identity testing for read-once formulas

  • On the degree of boolean functions in different characteristics

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

  • Testing Fourier dimensionality and sparsity

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

  • Noisy interpolating sets for low degree polynomials

  • Towards dimension expanders over finite fields

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

  • Read-once polynomial identity testing

  • Hardness-randomness tradeoffs for bounded depth arithmetic circuits

  • The black-box query complexity of polynomial summation

  • A lower bound for the size of syntactically multilinear arithmetic circuits

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

  • Interpolating depth-3 arithmetic circuits with two multiplication gates

  • Constructions of low-degree and error-correcting e-biased generators

  • An improved analysis of mergers

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

  • On the power of quantum proofs
  • On e-bias generators in NC0

  • Locally testable cyclic codes

  • Learning arithmetic circuits via partial derivatives

  • Lower bounds for small depth arithmetic and boolean circuits

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

  • Affine projections of symmetric polynomials

  • Depth 3 arithmetic circuits over fields of characteristic zero