| Publication | Date of Publication | Type |
|---|
| Pseudorandomness properties of random reversible circuits | 2026-02-04 | Paper |
| Explicit orthogonal and unitary designs | 2025-08-15 | Paper |
| Query-optimal estimation of unitary channels in diamond distance | 2025-08-15 | Paper |
| Explicit near-fully X-Ramanujan graphs | 2025-08-12 | Paper |
| How to refute a random CSP | 2025-08-05 | Paper |
| High-dimensional expanders from Chevalley groups | 2024-07-05 | Paper |
Improved quantum data analysis
TheoretiCS | 2024-07-03 | Paper |
| The SDP value of random 2CSPs | 2024-06-24 | Paper |
scientific article; zbMATH DE number 7829320 (Why is no real title available?)
(available as arXiv preprint) | 2024-04-09 | Paper |
Optimizing strongly interacting fermionic Hamiltonians
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | 2023-12-08 | Paper |
Fiber bundle codes: breaking the <i>n</i> <sup>1/2</sup> polylog( <i>n</i> ) barrier for Quantum LDPC codes
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
Improved Quantum data analysis
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
Pauli error estimation via population recovery
(available as arXiv preprint) | 2023-06-26 | Paper |
scientific article; zbMATH DE number 7650935 (Why is no real title available?)
(available as arXiv preprint) | 2023-02-07 | Paper |
Lower bounds for testing complete positivity and quantum separability
(available as arXiv preprint) | 2022-10-13 | Paper |
| Mean estimation when you have the source code; or, quantum Monte Carlo methods | 2022-08-16 | Paper |
| Sherali-adams strikes back | 2022-07-27 | Paper |
| scientific article; zbMATH DE number 7559077 (Why is no real title available?) | 2022-07-18 | Paper |
scientific article; zbMATH DE number 7559092 (Why is no real title available?)
(available as arXiv preprint) | 2022-07-18 | Paper |
Fooling Polytopes
Journal of the ACM | 2022-03-31 | Paper |
Log-Sobolev inequality for the multislice, with applications
Electronic Journal of Probability | 2022-03-30 | Paper |
| High-Dimensional Expanders from Chevalley Groups | 2022-03-07 | Paper |
Sherali-Adams strikes back
Theory of Computing | 2021-10-25 | Paper |
Quantum spectrum testing
Communications in Mathematical Physics | 2021-09-30 | Paper |
scientific article; zbMATH DE number 7378666 (Why is no real title available?)
(available as arXiv preprint) | 2021-08-04 | Paper |
| The SDP value of random 2CSPs | 2021-08-02 | Paper |
Explicit Near-Ramanujan Graphs of Every Degree
SIAM Journal on Computing | 2021-03-24 | Paper |
| The Quantum Union Bound made easy | 2021-03-13 | Paper |
<i>X</i>-Ramanujan graphs
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms | 2021-02-02 | Paper |
Explicit near-Ramanujan graphs of every degree
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing | 2021-01-19 | Paper |
Fooling Gaussian PTFs via local hyperconcentration
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing | 2021-01-19 | Paper |
Sharp bounds for population recovery
Theory of Computing | 2020-12-17 | Paper |
| Explicit near-fully X-Ramanujan graphs | 2020-09-05 | Paper |
scientific article; zbMATH DE number 7204467 (Why is no real title available?)
(available as arXiv preprint) | 2020-05-27 | Paper |
Fooling polytopes
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
The weakness of CTC qubits and the power of approximate counting
ACM Transactions on Computation Theory | 2019-12-06 | Paper |
The threshold for SDP-refutation of random regular NAE-3SAT
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
Testing surface area
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
Hypercontractive inequalities via SOS, and the Frankl–Rödl graph
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
The SDP value for random two-eigenvalue CSPs
(available as arXiv preprint) | 2019-06-16 | Paper |
Approximability and proof complexity
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-05-15 | Paper |
| Testing halfspaces | 2019-05-06 | Paper |
| 3-bit dictator testing: 1 vs. 5/8 | 2019-05-06 | Paper |
Optimal mean-based algorithms for trace reconstruction
The Annals of Applied Probability | 2019-04-24 | Paper |
$X$-Ramanujan Graphs
(available as arXiv preprint) | 2019-04-06 | Paper |
Gaussian noise sensitivity and Fourier tails
Israel Journal of Mathematics | 2018-06-29 | Paper |
| SOS is not obviously automatizable, even approximately | 2018-05-03 | Paper |
Social choice, computational complexity, Gaussian geometry, and Boolean functions
(available as arXiv preprint) | 2017-11-06 | Paper |
Polynomial bounds for decoupling, with applications
(available as arXiv preprint) | 2017-10-10 | Paper |
| Hardness results for agnostically learning low-degree polynomial threshold functions | 2017-09-29 | Paper |
Hardness results for agnostically learning low-degree polynomial threshold functions
(available as arXiv preprint) | 2017-09-29 | Paper |
Optimal mean-based algorithms for trace reconstruction
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
Sum of squares lower bounds for refuting any CSP
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
| One time-traveling bit is as good as logarithmically many | 2017-04-25 | Paper |
Hardness of MAX-2Lin and MAX-3Lin over integers, reals, and large cyclic groups
ACM Transactions on Computation Theory | 2016-10-24 | Paper |
Hypercontractive inequalities via SOS, and the Frankl-Rödl graph
Discrete Analysis | 2016-10-10 | Paper |
Linear programming, width-1 CSPs, and robust satisfaction
Proceedings of the 3rd Innovations in Theoretical Computer Science Conference | 2016-10-07 | Paper |
Convergence, unanimity and disagreement in majority dynamics on unimodular graphs and random graphs
Stochastic Processes and their Applications | 2016-08-08 | Paper |
Algorithmic signaling of features in auction design
Algorithmic Game Theory | 2015-11-04 | Paper |
Optimal bounds for estimating entropy with PMF queries
Mathematical Foundations of Computer Science 2015 | 2015-09-16 | Paper |
Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny)
ACM Transactions on Computation Theory | 2015-09-07 | Paper |
Quantum spectrum testing
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing | 2015-08-21 | Paper |
Conditional hardness for satisfiable 3-CSPs
Proceedings of the forty-first annual ACM symposium on Theory of computing | 2015-02-04 | Paper |
On the Fourier tails of bounded functions over the discrete cube
Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing | 2014-11-25 | Paper |
Sharpness of KKL on Schreier graphs
Electronic Communications in Probability | 2014-09-22 | Paper |
KKL, Kruskal-Katona, and Monotone Nets
2009 50th Annual IEEE Symposium on Foundations of Computer Science | 2014-07-25 | Paper |
| Conditioning and covariance on caterpillars | 2014-07-16 | Paper |
Analysis of Boolean Functions
(available as arXiv preprint) | 2014-07-09 | Paper |
Pareto optimal solutions for smoothed analysts
Proceedings of the forty-third annual ACM symposium on Theory of computing | 2014-06-05 | Paper |
KKL, Kruskal-Katona, and monotone nets
SIAM Journal on Computing | 2014-04-11 | Paper |
A composition theorem for the Fourier entropy-influence conjecture
Automata, Languages, and Programming | 2013-08-06 | Paper |
Pareto optimal solutions for smoothed analysts
SIAM Journal on Computing | 2013-02-04 | Paper |
| Open Problems in Analysis of Boolean Functions | 2012-04-28 | Paper |
New degree bounds for polynomial threshold functions
Combinatorica | 2011-12-19 | Paper |
Testing Fourier dimensionality and sparsity
SIAM Journal on Computing | 2011-11-07 | Paper |
SDP gaps and UGC-hardness for max-cut-gain
Theory of Computing | 2011-05-24 | Paper |
The Chow parameters problem
SIAM Journal on Computing | 2011-05-17 | Paper |
Testing Halfspaces
SIAM Journal on Computing | 2010-11-04 | Paper |
Testing (Subclasses of) Halfspaces
Property Testing | 2010-10-12 | Paper |
Polynomial regression under arbitrary product distributions
Machine Learning | 2010-10-07 | Paper |
SDP gaps for 2-to-1 and other Label-Cover variants
Automata, Languages and Programming | 2010-09-07 | Paper |
Learning juntas
Proceedings of the thirty-fifth annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
New degree bounds for polynomial threshold functions
Proceedings of the thirty-fifth annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Hardness amplification within NP
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing | 2010-08-05 | Paper |
Noise stability of functions with low influences: invariance and optimality
Annals of Mathematics. Second Series | 2010-05-27 | Paper |
Noise stability of functions with low influences: invariance and optimality
Annals of Mathematics. Second Series | 2010-05-27 | Paper |
Testing ±1-weight halfspace
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2009-10-28 | Paper |
Testing Fourier Dimensionality and Sparsity
Automata, Languages and Programming | 2009-07-14 | Paper |
| scientific article; zbMATH DE number 5485570 (Why is no real title available?) | 2009-01-05 | Paper |
| scientific article; zbMATH DE number 5485564 (Why is no real title available?) | 2009-01-05 | Paper |
| scientific article; zbMATH DE number 5485545 (Why is no real title available?) | 2009-01-05 | Paper |
Learning Mixtures of Product Distributions over Discrete Domains
SIAM Journal on Computing | 2008-10-28 | Paper |
Eliminating Cycles in the Discrete Torus
LATIN 2006: Theoretical Informatics | 2008-09-18 | Paper |
Learning Monotone Decision Trees in Polynomial Time
SIAM Journal on Computing | 2008-06-19 | Paper |
Eliminating cycles in the discrete torus
Algorithmica | 2008-04-23 | Paper |
On the Fourier tails of bounded functions over the discrete cube
Israel Journal of Mathematics | 2008-04-01 | Paper |
Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
SIAM Journal on Computing | 2008-03-28 | Paper |
Extremal properties of polynomial threshold functions
Journal of Computer and System Sciences | 2008-03-11 | Paper |
Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality
Israel Journal of Mathematics | 2008-02-22 | Paper |
Approximation by DNF: Examples and Counterexamples
Automata, Languages and Programming | 2007-11-28 | Paper |
PAC Learning Axis-Aligned Mixtures of Gaussians with No Separation Assumption
Learning Theory | 2007-09-14 | Paper |
Learning DNF from random walks
Journal of Computer and System Sciences | 2005-10-10 | Paper |
Coin flipping from a cosmic source: On error correction of truly random bits
Random Structures & Algorithms | 2005-08-29 | Paper |
| scientific article; zbMATH DE number 2119731 (Why is no real title available?) | 2004-11-29 | Paper |
Learning functions of \(k\) relevant variables
Journal of Computer and System Sciences | 2004-11-18 | Paper |
Hardness amplification within NP
Journal of Computer and System Sciences | 2004-10-04 | Paper |
Learning intersections and thresholds of halfspaces
Journal of Computer and System Sciences | 2004-08-06 | Paper |
On the noise sensitivity of monotone functions
Random Structures & Algorithms | 2003-10-22 | Paper |
| scientific article; zbMATH DE number 1984562 (Why is no real title available?) | 2003-09-22 | Paper |
Pseudorandom Permutations from Random Reversible Circuits
(available as arXiv preprint) | N/A | Paper |
