| Publication | Date of Publication | Type |
|---|
On hardness of testing equivalence to sparse polynomials under shifts
| 2024-10-08 | Paper |
Optimal two-dimensional Reed-Solomon codes correcting insertions and deletions
IEEE Transactions on Information Theory | 2024-07-23 | Paper |
Robust Sylvester-Gallai type theorem for quadratic polynomials
| 2024-05-14 | Paper |
scientific article; zbMATH DE number 7829342 (Why is no real title available?)
| 2024-04-09 | Paper |
Reed Solomon Codes Against Adversarial Insertions and Deletions
IEEE Transactions on Information Theory | 2024-03-19 | Paper |
Explicit and Efficient Constructions of Linear Codes Against Adversarial Insertions and Deletions
IEEE Transactions on Information Theory | 2024-03-14 | Paper |
Learnability can be independent of set theory (invited paper)
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
Polynomial time deterministic identity testing algorithm for Σ [3 ΠΣΠ [2] circuits via Edelstein–Kelly type theorem for quadratic polynomials]
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
New Bounds on Quotient Polynomials with Applications to Exact Divisibility and Divisibility Testing of Sparse Polynomials
| 2023-08-07 | Paper |
Hitting sets and reconstruction for dense orbits in VPe and ΣΠΣ circuits
| 2023-07-12 | Paper |
Discreteness of asymptotic tensor ranks
| 2023-06-02 | Paper |
Reed-Muller Codes
Foundations and Trends™ in Communications and Information Theory | 2023-01-23 | Paper |
A generalized Sylvester–Gallai-type theorem for quadratic polynomials
Forum of Mathematics, Sigma | 2022-12-19 | Paper |
Corrigendum: Explicit Construction of a Small Epsilon-Net for Linear Threshold Functions
SIAM Journal on Computing | 2022-11-15 | Paper |
A generalized sylvester-gallai type theorem for quadratic polynomials
| 2022-07-21 | Paper |
Improved Constructions of Coding Schemes for the Binary Deletion Channel and the Poisson Repeat Channel
IEEE Transactions on Information Theory | 2022-07-13 | Paper |
scientific article; zbMATH DE number 7471587 (Why is no real title available?)
Theory of Computing | 2022-02-09 | Paper |
Reed–Muller Codes: Theory and Algorithms
IEEE Transactions on Information Theory | 2021-07-23 | Paper |
On the performance of Reed-Muller codes with respect to random errors and erasures
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms | 2021-02-02 | Paper |
Sylvester-Gallai type theorems for quadratic polynomials
Discrete Analysis | 2020-10-20 | Paper |
Sylvester-Gallai type theorems for quadratic polynomials
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
A PSPACE construction of a hitting set for the closure of small algebraic circuits
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing | 2019-08-22 | Paper |
Approximate nonnegative rank is equivalent to the smooth rectangle bound
Computational Complexity | 2019-06-20 | Paper |
scientific article; zbMATH DE number 7009617 (Why is no real title available?)
Theory of Computing | 2019-01-31 | Paper |
On the degree of univariate polynomials over the integers
Combinatorica | 2018-04-12 | Paper |
Teaching and Compressing for Low VC-Dimension
A Journey Through Discrete Mathematics | 2018-02-26 | Paper |
Proof complexity lower bounds from algebraic circuit complexity
| 2017-10-10 | Paper |
Efficiently decoding Reed-Muller codes from random errors
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2017-09-29 | Paper |
Succinct hitting sets and barriers to proving algebraic circuits lower bounds
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
On the structure of Boolean functions with small spectral norm
Computational Complexity | 2017-07-28 | Paper |
Efficiently Decoding Reed–Muller Codes From Random Errors
IEEE Transactions on Information Theory | 2017-07-27 | Paper |
New Constructions of WOM Codes Using the Wozencraft Ensemble
IEEE Transactions on Information Theory | 2017-06-08 | Paper |
Direct sum fails for zero error average communication
Proceedings of the 5th conference on Innovations in theoretical computer science | 2017-05-19 | Paper |
On the structure of Boolean functions with small spectral norm
Proceedings of the 5th conference on Innovations in theoretical computer science | 2017-05-19 | Paper |
Capacity-Achieving Multiwrite WOM Codes
IEEE Transactions on Information Theory | 2017-05-16 | Paper |
High Sum-Rate Three-Write and Nonbinary WOM Codes
IEEE Transactions on Information Theory | 2017-05-16 | Paper |
Reed–Muller Codes for Random Erasures and Errors
IEEE Transactions on Information Theory | 2017-04-28 | Paper |
Tight lower bounds for linear \(2\)-query LCCs over finite fields. With an appendix by Sergey Yekhanin.
Combinatorica | 2017-03-31 | Paper |
Direct sum fails for zero-error average communication
Algorithmica | 2016-11-29 | Paper |
On the degree of univariate polynomials over the integers
Proceedings of the 3rd Innovations in Theoretical Computer Science Conference | 2016-10-07 | Paper |
Subexponential size hitting sets for bounded depth multilinear formulas
Computational Complexity | 2016-06-30 | Paper |
Read-once polynomial identity testing
Computational Complexity | 2015-09-21 | Paper |
Reed-Muller codes for random erasures and errors
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing | 2015-08-21 | Paper |
Hitting sets for multilinear read-once algebraic branching programs, in any order
Proceedings of the forty-sixth annual ACM symposium on Theory of computing | 2015-06-26 | Paper |
Equivalence of polynomial identity testing and polynomial factorization
Computational Complexity | 2015-06-23 | Paper |
Lower bounds for matrix product, in bounded depth circuits with arbitrary gates
Proceedings of the thirty-third annual ACM symposium on Theory of computing | 2015-02-27 | Paper |
Explicit construction of a small epsilon-net for linear threshold functions
Proceedings of the forty-first annual ACM symposium on Theory of computing | 2015-02-04 | Paper |
On reconstruction and testing of read-once formulas
Theory of Computing | 2015-02-03 | Paper |
On the minimal Fourier degree of symmetric Boolean functions
Combinatorica | 2014-08-14 | Paper |
Deterministic identity testing of depth-\(4\) multilinear circuits with bounded top fan-in
Proceedings of the forty-second ACM symposium on Theory of computing | 2014-08-13 | Paper |
On the structure of cubic and quartic polynomials
Proceedings of the forty-second ACM symposium on Theory of computing | 2014-08-13 | Paper |
Optimal Testing of Multivariate Polynomials over Small Prime Fields
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science | 2014-07-30 | Paper |
Tight Lower Bounds for 2-query LCCs over Finite Fields
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science | 2014-07-30 | Paper |
Testing equivalence of polynomials under shifts
Automata, Languages, and Programming | 2014-07-01 | Paper |
Approximate nonnegative rank is equivalent to the smooth rectangle bound
Automata, Languages, and Programming | 2014-07-01 | Paper |
On identity testing of tensors, low-rank recovery and compressed sensing
Proceedings of the forty-fourth annual ACM symposium on Theory of computing | 2014-05-13 | Paper |
Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in
SIAM Journal on Computing | 2014-04-11 | Paper |
Pseudorandom generators for \(\mathrm{CC}^0[p\) and the Fourier spectrum of low-degree polynomials over finite fields]
Computational Complexity | 2014-01-29 | Paper |
Explicit Noether normalization for simultaneous conjugation via polynomial identity testing
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2013-10-04 | Paper |
Optimal testing of multivariate polynomials over small prime fields
SIAM Journal on Computing | 2013-07-24 | Paper |
On sunflowers and matrix multiplication
Computational Complexity | 2013-07-19 | Paper |
Capacity achieving two-write WOM codes
LATIN 2012: Theoretical Informatics | 2012-06-29 | Paper |
Explicit dimension reduction and its applications
SIAM Journal on Computing | 2012-05-30 | Paper |
Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in
Combinatorica | 2011-12-20 | Paper |
Towards dimension expanders over finite fields
Combinatorica | 2011-12-20 | Paper |
Testing Fourier dimensionality and sparsity
SIAM Journal on Computing | 2011-11-07 | Paper |
On Sums of Locally Testable Affine Invariant Properties
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2011-08-17 | Paper |
Recent results on polynomial identity testing
Computer Science – Theory and Applications | 2011-06-17 | Paper |
Noisy interpolating sets for low-degree polynomials
Theory of Computing | 2011-05-24 | Paper |
scientific article; zbMATH DE number 5899249 (Why is no real title available?)
Theory of Computing | 2011-05-24 | Paper |
Explicit construction of a small \(\epsilon\)-net for linear threshold functions
SIAM Journal on Computing | 2011-04-04 | Paper |
The black-box query complexity of polynomial summation
Computational Complexity | 2011-02-18 | Paper |
Constructions of low-degree and error-correcting \(\varepsilon \)-biased generators
Computational Complexity | 2011-02-18 | Paper |
The complexity of Boolean functions in different characteristics
Computational Complexity | 2011-02-18 | Paper |
Arithmetic circuits: a survey of recent results and open questions
Foundations and Trends® in Theoretical Computer Science | 2011-01-24 | Paper |
On the relation between polynomial identity testing and finding variable disjoint factors
Automata, Languages and Programming | 2010-09-07 | Paper |
Hardness-randomness tradeoffs for bounded depth arithmetic circuits
SIAM Journal on Computing | 2010-09-06 | Paper |
Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Derandomizing homomorphism testing in general groups
Proceedings of the thirty-sixth annual ACM symposium on Theory of computing | 2010-08-15 | Paper |
Learning arithmetic circuits via partial derivatives.
Lecture Notes in Computer Science | 2010-03-23 | Paper |
Interpolation of depth-3 arithmetic circuits with two multiplication gates
SIAM Journal on Computing | 2010-01-06 | Paper |
Improved Polynomial Identity Testing for Read-Once Formulas
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2009-10-28 | Paper |
A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
SIAM Journal on Computing | 2009-08-20 | Paper |
Testing Fourier Dimensionality and Sparsity
Automata, Languages and Programming | 2009-07-14 | Paper |
Read-once polynomial identity testing
| 2009-01-05 | Paper |
scientific article; zbMATH DE number 5485462 (Why is no real title available?)
| 2009-01-05 | Paper |
scientific article; zbMATH DE number 5485588 (Why is no real title available?)
| 2009-01-05 | Paper |
Locally Testable Cyclic Codes
IEEE Transactions on Information Theory | 2008-12-21 | Paper |
An improved analysis of linear mergers
Computational Complexity | 2008-02-22 | Paper |
Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits
SIAM Journal on Computing | 2007-10-22 | Paper |
Derandomizing Homomorphism Testing in General Groups
SIAM Journal on Computing | 2007-09-07 | Paper |
On ε‐biased generators in NC0
Random Structures \& Algorithms | 2006-09-06 | Paper |
Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
Lecture Notes in Computer Science | 2006-07-07 | Paper |
Deterministic polynomial identity testing in non-commutative models
Computational Complexity | 2005-06-16 | Paper |
Lower Bounds for Matrix Product
SIAM Journal on Computing | 2003-09-28 | Paper |
Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates
SIAM Journal on Computing | 2003-06-19 | Paper |
Affine projections of symmetric polynomials.
Journal of Computer and System Sciences | 2003-05-14 | Paper |
Depth-3 arithmetic circuits over fields of characteristic zero
Computational Complexity | 2002-02-28 | Paper |
