| Publication | Date of Publication | Type |
|---|
| Quantum versus randomized communication complexity, with efficient players | 2026-04-15 | Paper |
| Shrinkage under random projections, and cubic formula lower bounds for AC^0 (extended abstract) | 2026-04-15 | Paper |
| Weighted pseudorandom generators via inverse analysis of random walks and shortcutting | 2025-08-15 | Paper |
| Tight time-space lower bounds for constant-pass learning | 2025-08-15 | Paper |
| Fourier growth of communication protocols for XOR functions | 2025-08-15 | Paper |
| Fooling constant-depth threshold circuits (extended abstract) | 2025-08-13 | Paper |
| Rigid matrices from rectangular PCPs or: hard claims have complex proofs | 2025-08-12 | Paper |
| Towards optimal separations between quantum and randomized query complexities | 2025-08-12 | Paper |
| Shrinkage of De Morgan formulae by spectral techniques | 2025-08-05 | Paper |
| Improved average-case lower bounds for DeMorgan formula size | 2025-05-20 | Paper |
| New PRGs for unbounded-width/adaptive-order read-once branching programs | 2024-11-14 | Paper |
| Depth-\(d\) threshold circuits vs. depth-\((d+1)\) and-or trees | 2024-05-08 | Paper |
| Quantum cryptography in Algorithmica | 2024-05-08 | Paper |
Rigid matrices from rectangular PCPs
SIAM Journal on Computing | 2024-04-24 | Paper |
scientific article; zbMATH DE number 7789147 (Why is no real title available?)
Theory of Computing | 2024-01-16 | Paper |
| Pseudorandom Generators for Read-Once Monotone Branching Programs | 2023-11-20 | Paper |
Degree vs. approximate degree and Quantum implications of Huang’s sensitivity theorem
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
Fourier growth of parity decision trees
(available as arXiv preprint) | 2023-07-12 | Paper |
Junta distance approximation with sub-exponential queries
(available as arXiv preprint) | 2023-07-12 | Paper |
Oracle Separation of BQP and PH
Journal of the ACM | 2023-04-27 | Paper |
| On the computational power of radio channels | 2023-02-03 | Paper |
Quantum versus randomized communication complexity, with efficient players
Computational Complexity | 2022-11-24 | Paper |
On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions
Lecture Notes in Computer Science | 2022-08-30 | Paper |
| Time-space lower bounds for two-pass learning | 2022-07-27 | Paper |
| \(\mathrm{AC}^0[p]\) lower bounds against MCSP via the coin problem | 2022-07-21 | Paper |
| Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates | 2022-07-18 | Paper |
| Cubic Formula Size Lower Bounds Based on Compositions with Majority | 2022-07-18 | Paper |
Lower bounds for 2-query LCCs over large alphabet
(available as arXiv preprint) | 2021-07-28 | Paper |
| Pseudorandom generators for low sensitivity functions | 2021-06-15 | Paper |
| Tight bounds on the Fourier spectrum of \(\mathsf{AC}^0\) | 2020-05-26 | Paper |
Oracle separation of BQP and PH
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
Pseudorandom generators for width-3 branching programs
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
Improved pseudorandomness for unordered branching programs through local monotonicity
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing | 2019-08-22 | Paper |
Extractor-based time-space lower bounds for learning
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing | 2019-08-22 | Paper |
Matrix rigidity of random Toeplitz matrices
Computational Complexity | 2018-08-03 | Paper |
Low-sensitivity functions from unambiguous certificates
(available as arXiv preprint) | 2018-05-03 | Paper |
On the degree of univariate polynomials over the integers
Combinatorica | 2018-04-12 | Paper |
The choice and agreement problems of a random function
Information Processing Letters | 2018-03-16 | Paper |
| scientific article; zbMATH DE number 6850428 (Why is no real title available?) | 2018-03-15 | Paper |
| On the sensitivity conjecture | 2017-12-19 | Paper |
Matrix rigidity of random toeplitz matrices
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2017-09-29 | Paper |
Two structural results for low degree polynomials and applications
(available as arXiv preprint) | 2017-08-31 | Paper |
Time-space hardness of learning sparse parities
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
Formula lower bounds via the quantum method
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 |
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 |
Properties and applications of Boolean function composition
Proceedings of the 4th conference on Innovations in Theoretical Computer Science | 2017-05-16 | Paper |
Improved average-case lower bounds for De Morgan formula size: matching worst-case lower bound
SIAM Journal on Computing | 2017-02-15 | Paper |
On the degree of univariate polynomials over the integers
Proceedings of the 3rd Innovations in Theoretical Computer Science Conference | 2016-10-07 | Paper |
On fractional block sensitivity
Chicago Journal of Theoretical Computer Science | 2016-08-16 | Paper |
On the minimal Fourier degree of symmetric Boolean functions
Combinatorica | 2014-08-14 | Paper |
