Ryan O'Donnell

TheoretiCS, 2024

Quartic quantum speedups for planted inference.

[BibT_eX]

[DOI]

Alexander Schmidhuber

Robin Kothari

Ryan Babbush

CoRR, 2024

Pseudorandom Permutations from Random Reversible Circuits.

[BibT_eX]

[DOI]

William He

CoRR, 2024

2023

Quantum chi-squared tomography and mutual information testing.

[BibT_eX]

[DOI]

Steven T. Flammia

CoRR, 2023

Mean estimation when you have the source code; or, quantum Monte Carlo methods.

[BibT_eX]

[DOI]

Robin Kothari

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Explicit orthogonal and unitary designs.

[BibT_eX]

[DOI]

Pedro Paredes

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Query-optimal estimation of unitary channels in diamond distance.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022

Explicit Near-Ramanujan Graphs of Every Degree.

[BibT_eX]

[DOI]

Pedro Paredes

SIAM J. Comput., June, 2022

Optimizing strongly interacting fermionic Hamiltonians.

[BibT_eX]

[DOI]

Matthew B. Hastings

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

The Quantum Union Bound made easy.

[BibT_eX]

[DOI]

Ramgopal Venkateswaran

Proceedings of the 5th Symposium on Simplicity in Algorithms, 2022

Explicit Abelian Lifts and Quantum LDPC Codes.

[BibT_eX]

[DOI]

Fernando Granha Jeronimo

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

The SDP Value of Random 2CSPs.

[BibT_eX]

[DOI]

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Toward Instance-Optimal State Certification With Incoherent Measurements.

[BibT_eX]

[DOI]

Sitan Chen

Jerry Li

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

High-Dimensional Expanders from Chevalley Groups.

[BibT_eX]

[DOI]

Kevin Pratt

Proceedings of the 37th Computational Complexity Conference, 2022

2021

Sherali-Adams Strikes Back.

[BibT_eX]

[DOI]

Tselil Schramm

Theory Comput., 2021

Pauli error estimation via Population Recovery.

[BibT_eX]

[DOI]

Steven T. Flammia

Quantum, 2021

Analysis of Boolean Functions.

[BibT_eX]

[DOI]

CoRR, 2021

Fooling Gaussian PTFs via Local Hyperconcentration.

[BibT_eX]

[DOI]

CoRR, 2021

Fiber bundle codes: breaking the n1/2 polylog(n) barrier for Quantum LDPC codes.

[BibT_eX]

[DOI]

Matthew B. Hastings

Jeongwan Haah

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Quantum Approximate Counting with Nonadaptive Grover Iterations.

[BibT_eX]

[DOI]

Ramgopal Venkateswaran

Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science, 2021

Learning sparse mixtures of permutations from noisy information.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2021

2020

Editorial from the New Editor-in-Chief.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2020

Sharp Bounds for Population Recovery.

[BibT_eX]

[DOI]

Theory Comput., 2020

Fiber Bundle Codes: Breaking the N1/2 polylog(N) Barrier for Quantum LDPC Codes.

[BibT_eX]

[DOI]

Matthew B. Hastings

Jeongwan Haah

CoRR, 2020

Fooling Gaussian PTFs via local hyperconcentration.

[BibT_eX]

[DOI]

Li-Yang Tan

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

The SDP Value for Random Two-Eigenvalue CSPs.

[BibT_eX]

[DOI]

Pedro Paredes

Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science, 2020

X-Ramanujan graphs.

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Lower Bounds for Testing Complete Positivity and Quantum Separability.

[BibT_eX]

[DOI]

Costin Badescu

Proceedings of the LATIN 2020: Theoretical Informatics, 2020

Explicit near-fully X-Ramanujan graphs.

[BibT_eX]

[DOI]

Xinyu Wu

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

X-Ramanujan Graphs.

[BibT_eX]

[DOI]

CoRR, 2019

Quantum state certification.

[BibT_eX]

[DOI]

Costin Badescu

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

The threshold for SDP-refutation of random regular NAE-3SAT.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

SOS Lower Bounds with Hard Constraints: Think Global, Act Local.

[BibT_eX]

[DOI]

Pravesh K. Kothari

Tselil Schramm

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

A Log-Sobolev Inequality for the Multislice, with Applications.

[BibT_eX]

[DOI]

Yuval Filmus

Xinyu Wu

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

2018

Special Issue: CCC 2017: Guest Editor's Foreword.

[BibT_eX]

[DOI]

Shachar Lovett

Theory Comput., 2018

Fooling Polytopes.

[BibT_eX]

[DOI]

Li-Yang Tan

Electron. Colloquium Comput. Complex., 2018

Learning sparse mixtures of rankings from noisy information.

[BibT_eX]

[DOI]

CoRR, 2018

On Closeness to k-Wise Uniformity.

[BibT_eX]

[DOI]

Yu Zhao

Proceedings of the Approximation, 2018

2017

Improved NP-Inapproximability for 2-Variable Linear Equations.

[BibT_eX]

[DOI]

Theory Comput., 2017

Guest Column: A Primer on the Statistics of Longest Increasing Subsequences and Quantum States (Shortened Version).

[BibT_eX]

[DOI]

SIGACT News, 2017

Efficient quantum tomography II.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Sum of squares lower bounds for refuting any CSP.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Optimal mean-based algorithms for trace reconstruction.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Quantum Automata Cannot Detect Biased Coins, Even in the Limit.

[BibT_eX]

[DOI]

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016

The weakness of CTC qubits and the power of approximate counting.

[BibT_eX]

[DOI]

A. C. Cem Say

Electron. Colloquium Comput. Complex., 2016

SOS is not obviously automatizable, even approximately.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

Bounding laconic proof systems by solving CSPs in parallel.

[BibT_eX]

[DOI]

Jason Li

Electron. Colloquium Comput. Complex., 2016

Efficient quantum tomography.

[BibT_eX]

[DOI]

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Polynomial Bounds for Decoupling, with Applications.

[BibT_eX]

[DOI]

Yu Zhao

Proceedings of the 31st Conference on Computational Complexity, 2016

2015

Hardness of Max-2Lin and Max-3Lin over Integers, Reals, and Large Cyclic Groups.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2015

Beating the random assignment on constraint satisfaction problems of bounded degree.

[BibT_eX]

[DOI]

Aravindan Vijayaraghavan

Electron. Colloquium Comput. Complex., 2015

Continuous analogues of the Most Informative Function problem.

[BibT_eX]

[DOI]

CoRR, 2015

Quantum Spectrum Testing.

[BibT_eX]

[DOI]

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Algorithmic Signaling of Features in Auction Design.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Game Theory - 8th International Symposium, 2015

Optimal Bounds for Estimating Entropy with PMF Queries.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

Conditioning and covariance on caterpillars.

[BibT_eX]

[DOI]

Sarah R. Allen

Proceedings of the 2015 IEEE Information Theory Workshop, 2015

How to Refute a Random CSP.

[BibT_eX]

[DOI]

Sarah R. Allen

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014

New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2014

Special Section on the Fifty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010).

[BibT_eX]

[DOI]

SIAM J. Comput., 2014

One time-travelling bit is as good as logarithmically many.

[BibT_eX]

[DOI]

A. C. Cem Say

Electron. Colloquium Comput. Complex., 2014

Social choice, computational complexity, Gaussian geometry, and Boolean functions.

[BibT_eX]

[DOI]

CoRR, 2014

Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Testing Surface Area.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Hypercontractive inequalities via SOS, and the Frankl-Rödl graph.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

One Time-traveling Bit is as Good as Logarithmically Many.

[BibT_eX]

[DOI]

A. C. Cem Say

Proceedings of the 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, 2014

A Composition Theorem for Parity Kill Number.

[BibT_eX]

[DOI]

Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

Goldreich's PRG: Evidence for Near-Optimal Polynomial Stretch.

[BibT_eX]

[DOI]

Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

Analysis of Boolean Functions.

[BibT_eX]

[DOI]

Cambridge University Press, ISBN: 978-1-10-703832-5, 2014

2013

Special Issue on Analysis of Boolean Functions: Guest Editors' Foreword.

[BibT_eX]

[DOI]

Theory Comput., 2013

KKL, Kruskal-Katona, and Monotone Nets.

[BibT_eX]

[DOI]

Karl Wimmer

SIAM J. Comput., 2013

Approximability and proof complexity.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

A Composition Theorem for the Fourier Entropy-Influence Conjecture.

[BibT_eX]

[DOI]

Li-Yang Tan

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

Learning Sums of Independent Integer Random Variables.

[BibT_eX]

[DOI]

Constantinos Daskalakis

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012

Pareto Optimal Solutions for Smoothed Analysts.

[BibT_eX]

[DOI]

Ankur Moitra

SIAM J. Comput., 2012

Hypercontractive inequalities via SOS, with an application to Vertex-Cover

[BibT_eX]

[DOI]

CoRR, 2012

Open Problems in Analysis of Boolean Functions

[BibT_eX]

[DOI]

CoRR, 2012

Improved small-set expansion from higher eigenvalues

[BibT_eX]

[DOI]

CoRR, 2012

Spherical cubes: optimal foams from computational hardness amplification.

[BibT_eX]

[DOI]

Commun. ACM, 2012

A new point of NP-hardness for unique games.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Linear programming, width-1 CSPs, and robust satisfaction.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

Gaussian Noise Sensitivity and Fourier Tails.

[BibT_eX]

[DOI]

Proceedings of the 27th Conference on Computational Complexity, 2012

A New Point of NP-Hardness for 2-to-1 Label Cover.

[BibT_eX]

[DOI]

Per Austrin

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011

The Chow Parameters Problem.

[BibT_eX]

[DOI]

SIAM J. Comput., 2011

Testing Fourier Dimensionality and Sparsity.

[BibT_eX]

[DOI]

SIAM J. Comput., 2011

Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

The Fourier Entropy-Influence Conjecture for Certain Classes of Boolean Functions.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

2010

Testing Halfspaces.

[BibT_eX]

[DOI]

SIAM J. Comput., 2010

Polynomial regression under arbitrary product distributions.

[BibT_eX]

[DOI]

Eric Blais

Karl Wimmer

Mach. Learn., 2010

Fooling functions of halfspaces under product distributions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

New degree bounds for polynomial threshold functions.

[BibT_eX]

[DOI]

Comb., 2010

Testing (Subclasses of) Halfspaces.

[BibT_eX]

[DOI]

Proceedings of the Property Testing - Current Research and Surveys, 2010

SDP Gaps for 2-to-1 and Other Label-Cover Variants.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

Lower Bounds for Testing Function Isomorphism.

[BibT_eX]

[DOI]

Eric Blais

Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010

k + Decision Trees - (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Algorithms for Sensor Systems, 2010

2009

SDP Gaps and UGC-hardness for Max-Cut-Gain.

[BibT_eX]

[DOI]

Subhash Khot

Theory Comput., 2009

Optimal lower bounds for locality sensitive hashing (except when q is tiny).

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

Conditional hardness for satisfiable 3-CSPs.

[BibT_eX]

[DOI]

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

3-bit dictator testing: 1 vs. 5/8.

[BibT_eX]

[DOI]

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Testing ±1-weight halfspace.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2009

2008

Learning Mixtures of Product Distributions over Discrete Domains.

[BibT_eX]

[DOI]

Jon Feldman

SIAM J. Comput., 2008

Extremal properties of polynomial threshold functions.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2008

Some Topics in Analysis of Boolean Functions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2008

Eliminating Cycles in the Discrete Torus.

[BibT_eX]

[DOI]

Algorithmica, 2008

An optimal sdp algorithm for max-cut, and equally optimal long code tests.

[BibT_eX]

[DOI]

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Learning Geometric Concepts via Gaussian Surface Area.

[BibT_eX]

[DOI]

Adam R. Klivans

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

Spherical Cubes and Rounding in High Dimensions.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007

Learning Monotone Decision Trees in Polynomial Time.

[BibT_eX]

[DOI]

SIAM J. Comput., 2007

Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?.

[BibT_eX]

[DOI]

SIAM J. Comput., 2007

Understanding Parallel Repetition Requires Understanding Foams.

[BibT_eX]

[DOI]

Uriel Feige

Electron. Colloquium Comput. Complex., 2007

Approximation by DNF: Examples and Counterexamples.

[BibT_eX]

[DOI]

Karl Wimmer

Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

2006

PAC Learning Mixtures of Axis-Aligned Gaussians with No Separation Assumption

[BibT_eX]

[DOI]

Jon Feldman

CoRR, 2006

On the fourier tails of bounded functions over the discrete cube.

[BibT_eX]

[DOI]

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

SDP gaps and UGC-hardness for MAXCUTGAIN.

[BibT_eX]

[DOI]

Subhash Khot

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

PAC Learning Axis-Aligned Mixtures of Gaussians with No Separation Assumption.

[BibT_eX]

[DOI]

Jon Feldman

Proceedings of the Learning Theory, 19th Annual Conference on Learning Theory, 2006

2005

Coin flipping from a cosmic source: On error correction of truly random bits.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2005

Learning DNF from random walks.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2005

Noise stability of functions with low influences: invariance and optimality

[BibT_eX]

[DOI]

Krzysztof Oleszkiewicz

CoRR, 2005

Every decision tree has an influential variable

[BibT_eX]

[DOI]

CoRR, 2005

Every decision tree has an in.uential variable.

[BibT_eX]

[DOI]

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

Noise stability of functions with low in.uences invariance and optimality.

[BibT_eX]

[DOI]

Krzysztof Oleszkiewicz

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

2004

Hardness amplification within NP.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2004

Learning functions of k relevant variables.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2004

Learning intersections and thresholds of halfspaces.

[BibT_eX]

[DOI]

Adam R. Klivans

J. Comput. Syst. Sci., 2004

2003

On the noise sensitivity of monotone functions.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2003

Learning juntas.

[BibT_eX]

[DOI]

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

2002

Hardness amplification within NP.

[BibT_eX]

[DOI]

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Derandomized dimensionality reduction with applications.

[BibT_eX]

[DOI]

Lars Engebretsen

Piotr Indyk