| Publication | Date of Publication | Type |
|---|
Superpolynomial lower bounds against low-depth algebraic circuits
Journal of the ACM | 2025-10-23 | Paper |
| Low-degree testing over grids | 2025-01-14 | Paper |
| Towards optimal depth-reductions for algebraic formulas | 2024-11-19 | Paper |
| On the VNP-hardness of some monomial symmetric polynomials | 2024-09-12 | Paper |
| Vanishing spaces of random sets and applications to Reed-Muller codes | 2024-07-05 | Paper |
| On the partial derivative method applied to lopsided set-multilinear polynomials | 2024-07-05 | Paper |
A robust version of Hegedűs's lemma, with applications
TheoretiCS | 2024-07-03 | Paper |
| Optimal explicit small-depth formulas for the coin problem | 2024-05-08 | Paper |
Set-multilinear and non-commutative formula lower bounds for iterated matrix multiplication
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | 2023-12-08 | Paper |
scientific article; zbMATH DE number 7768387 (Why is no real title available?)
(available as arXiv preprint) | 2023-11-20 | Paper |
On the probabilistic degree of OR over the reals
Random Structures & Algorithms | 2023-10-12 | Paper |
| The discrepancy of greater-than | 2023-09-15 | Paper |
Schur polynomials do not have small formulas if the determinant does not
Computational Complexity | 2023-07-10 | Paper |
| scientific article; zbMATH DE number 7650325 (Why is no real title available?) | 2023-02-03 | Paper |
| scientific article; zbMATH DE number 7650319 (Why is no real title available?) | 2023-02-03 | Paper |
| Parity helps to compute majority | 2022-07-27 | Paper |
scientific article; zbMATH DE number 7561742 (Why is no real title available?)
(available as arXiv preprint) | 2022-07-21 | Paper |
scientific article; zbMATH DE number 7561310 (Why is no real title available?)
(available as arXiv preprint) | 2022-07-21 | Paper |
A \#SAT algorithm for small constant-depth circuits with PTF gates
(available as arXiv preprint) | 2022-07-18 | Paper |
A \#SAT algorithm for small constant-depth circuits with PTF gates
Algorithmica | 2022-03-22 | Paper |
Strongly Exponential Separation between Monotone VP and Monotone VNP
ACM Transactions on Computation Theory | 2022-03-07 | Paper |
Decoding variants of Reed-Muller codes over finite grids
ACM Transactions on Computation Theory | 2022-03-07 | Paper |
| On Vanishing Properties of Polynomials on Symmetric Sets of the Boolean Cube, in Positive Characteristic | 2021-11-09 | Paper |
On the Probabilistic Degrees of Symmetric Boolean Functions
SIAM Journal on Discrete Mathematics | 2021-09-17 | Paper |
A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus$ via the Coin Problem]
SIAM Journal on Computing | 2021-09-10 | Paper |
| Deterministically counting satisfying assignments for constant-depth circuits with parity gates, with implications for lower bounds | 2021-08-04 | Paper |
| A quadratic size-hierarchy theorem for small-depth multilinear formulas | 2021-07-28 | Paper |
| Local decoding and testing of polynomials over grids | 2021-06-15 | Paper |
A robust version of Hegedus’s lemma, with applications
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing | 2021-01-19 | Paper |
Local decoding and testing of polynomials over grids
Random Structures & Algorithms | 2020-11-30 | Paper |
Local decoding and testing of polynomials over grids
Random Structures & Algorithms | 2020-11-30 | Paper |
Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications.
(available as arXiv preprint) | 2020-08-05 | Paper |
| Separation of \(\mathrm{AC}^0[\oplus\) formulas and circuits] | 2020-05-27 | Paper |
| scientific article; zbMATH DE number 7204375 (Why is no real title available?) | 2020-05-26 | Paper |
scientific article; zbMATH DE number 7166711 (Why is no real title available?)
Theory of Computing | 2020-02-12 | Paper |
A fixed-depth size-hierarchy theorem for AC 0 [⊕ via the coin problem]
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees
Computational Complexity | 2019-08-30 | Paper |
| On some recent projection switching lemmas for small depth circuits | 2019-07-03 | Paper |
On polynomial approximations to \(\mathrm{AC}^0\)
Random Structures & Algorithms | 2019-05-02 | Paper |
Certifying polynomials for \(\mathsf{AC}^0[\oplus\) circuits, with applications to lower bounds and circuit compression]
Theory of Computing | 2019-01-31 | Paper |
Robust Multiplication-Based Tests for Reed–Muller Codes
IEEE Transactions on Information Theory | 2019-01-18 | Paper |
Small-depth multilinear formula lower bounds for iterated matrix multiplication with applications
SIAM Journal on Computing | 2019-01-14 | Paper |
Average-case lower bounds and satisfiability algorithms for small threshold circuits
Theory of Computing | 2018-06-15 | Paper |
scientific article; zbMATH DE number 6861917 (Why is no real title available?)
(available as arXiv preprint) | 2018-04-19 | Paper |
Robust multiplication-based tests for Reed-Muller codes
(available as arXiv preprint) | 2018-04-19 | Paper |
scientific article; zbMATH DE number 6862104 (Why is no real title available?)
(available as arXiv preprint) | 2018-04-19 | Paper |
On the hardness of the noncommutative determinant
Computational Complexity | 2018-04-18 | Paper |
Composition limits and separating examples for some Boolean function complexity measures
Combinatorica | 2018-02-22 | Paper |
The shifted partial derivative complexity of elementary symmetric polynomials
Theory of Computing | 2017-10-11 | Paper |
Average-case lower bounds and satisfiability algorithms for small threshold circuits
(available as arXiv preprint) | 2017-10-10 | Paper |
An exponential lower bound for homogeneous depth four arithmetic formulas
SIAM Journal on Computing | 2017-03-10 | Paper |
Super-polylogarithmic hypergraph coloring hardness via low-degree long codes
SIAM Journal on Computing | 2017-03-10 | Paper |
| On Improved Degree Lower Bounds for Polynomial Approximation. | 2017-02-21 | Paper |
| Certifying polynomials for AC^0(parity) circuits, with applications | 2017-01-26 | Paper |
Derandomized graph product results using the low degree long code
(available as arXiv preprint) | 2017-01-24 | Paper |
Lower bounds for non-commutative skew circuits
Theory of Computing | 2016-11-01 | Paper |
A tail bound for read-\(k\) families of functions
Random Structures & Algorithms | 2015-10-12 | Paper |
Lower bounds for depth-4 formulas computing iterated matrix multiplication
SIAM Journal on Computing | 2015-10-08 | Paper |
The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials
Mathematical Foundations of Computer Science 2015 | 2015-09-16 | Paper |
Lower bounds for depth 4 formulas computing iterated matrix multiplication
Proceedings of the forty-sixth annual ACM symposium on Theory of computing | 2015-06-26 | Paper |
Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas
Proceedings of the forty-sixth annual ACM symposium on Theory of computing | 2015-06-26 | Paper |
Super-polylogarithmic hypergraph coloring hardness via low-degree long codes
Proceedings of the forty-sixth annual ACM symposium on Theory of computing | 2015-06-26 | Paper |
On the hardness of the noncommutative determinant
Proceedings of the forty-second ACM symposium on Theory of computing | 2014-08-13 | Paper |
Almost settling the hardness of noncommutative determinant
Proceedings of the forty-third annual ACM symposium on Theory of computing | 2014-06-05 | Paper |
On the limits of sparsification
Automata, Languages, and Programming | 2013-08-12 | Paper |
Optimal Hitting Sets for Combinatorial Shapes
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2012-11-02 | Paper |
| Arithmetic circuits and the Hadamard product of polynomials | 2012-10-24 | Paper |
| The remote point problem, small bias spaces, and expanding generator sets | 2012-01-23 | Paper |
Correlation bounds for poly-size \(\mathrm{AC}^0\) circuits with \(n^{1 - o(1)}\) symmetric gates
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2011-08-17 | Paper |
Streaming algorithms for recognizing nearly well-parenthesized expressions
Mathematical Foundations of Computer Science 2011 | 2011-08-17 | Paper |
New results on noncommutative and commutative polynomial identity testing
Computational Complexity | 2011-02-18 | Paper |
On Lower Bounds for Constant Width Arithmetic Circuits
Algorithms and Computation | 2009-12-17 | Paper |
