Ryan O'Donnell

222 papers A* 59A 22B 5C 1Journal 118Unranked 15

Year	Rank	Type	Title / Venue / Authors
2026	A*	`conf`	A Classical Quadratic Speedup for Planted k xor. SODA Meghal Gupta, William He, Ryan O'Donnell, Noah G. Singer
2025	J	`jnl`	A Classical Quadratic Speedup for Planted CoRR Meghal Gupta, William He, Ryan O'Donnell, Noah G. Singer
2025	A*	`conf`	Explicit Two-Sided Vertex Expanders beyond the Spectral Barrier. STOC Jun-Ting Hsieh, Ting-Chun Lin, Sidhanth Mohanty, Ryan O'Donnell, Rachel Yun Zhang
2025	J	`jnl`	Few Single-Qubit Measurements Suffice to Certify Any Quantum State. CoRR Meghal Gupta, William He, Ryan O'Donnell
2025	J	`jnl`	Generalized Samorodnitsky noisy function inequalities, with applications to error-correcting codes. CoRR Olakunle S. Abawonse, Jan Hazla, Ryan O'Donnell
2025	J	`jnl`	Instance-Optimal Quantum State Certification with Entangled Measurements. CoRR Ryan O'Donnell, Chirag Wadhwa
2025	A*	`conf`	Learning the Closest Product State. STOC Ainesh Bakshi, John Bostanci, William Kretschmer, Zeph Landau, Jerry Li, Allen Liu, Ryan O'Donnell, Ewin Tang
2025	J	`jnl`	Low-soundness direct-product testers and PCPs from Kaufman-Oppenheim complexes. CoRR Ryan O'Donnell, Noah G. Singer
2025	J	`jnl`	Low-soundness direct-product testers and PCPs from Kaufman-Oppenheim complexes. Electron. Colloquium Comput. Complex. Ryan O'Donnell, Noah Singer
2025	J	`jnl`	No exponential quantum speedup for SIS CoRR Robin Kothari, Ryan O'Donnell, Kewen Wu
2025	J	`jnl`	Non-iid hypothesis testing: from classical to quantum. CoRR Giacomo De Palma, Marco Fanizza, Connor Mowry, Ryan O'Donnell
2025	—	`conf`	Pseudorandomness Properties of Random Reversible Circuits. CRYPTO (1) William Gay, William He, Nicholas Kocurek, Ryan O'Donnell
2025	J	`jnl`	Pseudorandomness Properties of Random Reversible Circuits. CoRR William Gay, William He, Nicholas Kocurek, Ryan O'Donnell
2025	A*	`conf`	Quartic quantum speedups for planted inference. SODA Alexander Schmidhuber, Ryan O'Donnell, Robin Kothari, Ryan Babbush
2025	J	`jnl`	SPAM Tolerance for Pauli Error Estimation. CoRR Ryan O'Donnell, Samvitti Sharma
2025	J	`jnl`	Sampling and Identity-Testing Without Approximate Tensorization of Entropy. CoRR William Gay, William He, Nicholas Kocurek, Ryan O'Donnell
2025	—	`conf`	Uniformity Testing When You Have the Source Code. TQC Clément L. Canonne, Robin Kothari, Ryan O'Donnell
2024	J	`jnl`	Coboundary expansion inside Chevalley coset complex HDXs. CoRR Ryan O'Donnell, Noah G. Singer
2024	J	`jnl`	Explicit Two-Sided Vertex Expanders Beyond the Spectral Barrier. CoRR Jun-Ting Hsieh, Ting-Chun Lin, Sidhanth Mohanty, Ryan O'Donnell, Rachel Yun Zhang
2024	J	`jnl`	Improved quantum data analysis. TheoretiCS Costin Badescu, Ryan O'Donnell
2024	A*	`ed.`	Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024 STOC Bojan Mohar, Igor Shinkar, Ryan O'Donnell
2024	J	`jnl`	Quantum chi-squared tomography and mutual information testing. Quantum Steven T. Flammia, Ryan O'Donnell
2024	J	`jnl`	Quartic quantum speedups for planted inference. CoRR Alexander Schmidhuber, Ryan O'Donnell, Robin Kothari, Ryan Babbush
2024	J	`jnl`	Sparsifying Suprema of Gaussian Processes. CoRR Anindya De, Shivam Nadimpalli, Ryan O'Donnell, Rocco A. Servedio
2024	J	`jnl`	Uniformity testing when you have the source code. CoRR Clément L. Canonne, Robin Kothari, Ryan O'Donnell
2023	A*	`conf`	Explicit orthogonal and unitary designs. FOCS Ryan O'Donnell, Rocco A. Servedio, Pedro Paredes
2023	J	`jnl`	Explicit orthogonal and unitary designs. CoRR Ryan O'Donnell, Rocco A. Servedio, Pedro Paredes
2023	A*	`conf`	Mean estimation when you have the source code; or, quantum Monte Carlo methods. SODA Robin Kothari, Ryan O'Donnell
2023	J	`jnl`	Quantum chi-squared tomography and mutual information testing. CoRR Steven T. Flammia, Ryan O'Donnell
2023	A*	`conf`	Query-optimal estimation of unitary channels in diamond distance. FOCS Jeongwan Haah, Robin Kothari, Ryan O'Donnell, Ewin Tang
2023	J	`jnl`	Query-optimal estimation of unitary channels in diamond distance. CoRR Jeongwan Haah, Robin Kothari, Ryan O'Donnell, Ewin Tang
2022	A	`conf`	Explicit Abelian Lifts and Quantum LDPC Codes. ITCS Fernando Granha Jeronimo, Tushant Mittal, Ryan O'Donnell, Pedro Paredes, Madhur Tulsiani
2022	J	`jnl`	Explicit Near-Ramanujan Graphs of Every Degree. SIAM J. Comput. Sidhanth Mohanty, Ryan O'Donnell, Pedro Paredes
2022	J	`jnl`	Fooling Polytopes. J. ACM Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan
2022	A	`conf`	High-Dimensional Expanders from Chevalley Groups. CCC Ryan O'Donnell, Kevin Pratt
2022	J	`jnl`	High-Dimensional Expanders from Chevalley Groups. CoRR Ryan O'Donnell, Kevin Pratt
2022	J	`jnl`	Mean estimation when you have the source code; or, quantum Monte Carlo methods. CoRR Robin Kothari, Ryan O'Donnell
2022	A*	`conf`	Optimizing strongly interacting fermionic Hamiltonians. STOC Matthew B. Hastings, Ryan O'Donnell
2022	—	`conf`	The Quantum Union Bound made easy. SOSA Ryan O'Donnell, Ramgopal Venkateswaran
2022	A*	`conf`	The SDP Value of Random 2CSPs. ICALP Amulya Musipatla, Ryan O'Donnell, Tselil Schramm, Xinyu Wu
2022	A*	`conf`	Toward Instance-Optimal State Certification With Incoherent Measurements. COLT Sitan Chen, Jerry Li, Ryan O'Donnell
2021	J	`jnl`	Analysis of Boolean Functions. CoRR Ryan O'Donnell
2021	J	`jnl`	Explicit Abelian Lifts and Quantum LDPC Codes. CoRR Fernando Granha Jeronimo, Tushant Mittal, Ryan O'Donnell, Pedro Paredes, Madhur Tulsiani
2021	A*	`conf`	Fiber bundle codes: breaking the STOC Matthew B. Hastings, Jeongwan Haah, Ryan O'Donnell
2021	J	`jnl`	Fooling Gaussian PTFs via Local Hyperconcentration. CoRR Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan, Daniel Kane
2021	A*	`conf`	Improved Quantum data analysis. STOC Costin Badescu, Ryan O'Donnell
2021	A*	`conf`	Learning sparse mixtures of permutations from noisy information. COLT Anindya De, Ryan O'Donnell, Rocco A. Servedio
2021	J	`jnl`	Optimizing Strongly Interacting Fermionic Hamiltonians. CoRR Matthew B. Hastings, Ryan O'Donnell
2021	—	`conf`	Pauli Error Estimation via Population Recovery. TQC Steven T. Flammia, Ryan O'Donnell
2021	J	`jnl`	Pauli error estimation via Population Recovery. Quantum Steven T. Flammia, Ryan O'Donnell
2021	A	`conf`	Quantum Approximate Counting with Nonadaptive Grover Iterations. STACS Ramgopal Venkateswaran, Ryan O'Donnell
2021	J	`jnl`	Sherali-Adams Strikes Back. Theory Comput. Ryan O'Donnell, Tselil Schramm
2021	J	`jnl`	The SDP value of random 2CSPs. CoRR Amulya Musipatla, Ryan O'Donnell, Tselil Schramm, Xinyu Wu
2021	J	`jnl`	Toward Instance-Optimal State Certification With Incoherent Measurements. CoRR Sitan Chen, Jerry Li, Ryan O'Donnell
2020	J	`jnl`	Editorial from the New Editor-in-Chief. ACM Trans. Comput. Theory Ryan O'Donnell
2020	A*	`conf`	Explicit near-Ramanujan graphs of every degree. STOC Sidhanth Mohanty, Ryan O'Donnell, Pedro Paredes
2020	A*	`conf`	Explicit near-fully X-Ramanujan graphs. FOCS Ryan O'Donnell, Xinyu Wu
2020	J	`jnl`	Explicit near-fully X-Ramanujan graphs. CoRR Ryan O'Donnell, Xinyu Wu
2020	J	`jnl`	Fiber Bundle Codes: Breaking the N CoRR Matthew B. Hastings, Jeongwan Haah, Ryan O'Donnell
2020	A*	`conf`	Fooling Gaussian PTFs via local hyperconcentration. STOC Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan
2020	J	`jnl`	Improved quantum data analysis. CoRR Costin Badescu, Ryan O'Donnell
2020	B	`conf`	Lower Bounds for Testing Complete Positivity and Quantum Separability. LATIN Costin Badescu, Ryan O'Donnell
2020	J	`jnl`	Sharp Bounds for Population Recovery. Theory Comput. Anindya De, Ryan O'Donnell, Rocco A. Servedio
2020	A	`conf`	The SDP Value for Random Two-Eigenvalue CSPs. STACS Sidhanth Mohanty, Ryan O'Donnell, Pedro Paredes
2019	A	`conf`	A Log-Sobolev Inequality for the Multislice, with Applications. ITCS Yuval Filmus, Ryan O'Donnell, Xinyu Wu
2019	J	`jnl`	Explicit near-Ramanujan graphs of every degree. CoRR Sidhanth Mohanty, Ryan O'Donnell, Pedro Paredes
2019	A*	`conf`	Fooling polytopes. STOC Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan
2019	A*	`conf`	Quantum state certification. STOC Costin Badescu, Ryan O'Donnell, John Wright
2019	A	`conf`	SOS Lower Bounds with Hard Constraints: Think Global, Act Local. ITCS Pravesh K. Kothari, Ryan O'Donnell, Tselil Schramm
2019	A	`conf`	Sherali - Adams Strikes Back. CCC Ryan O'Donnell, Tselil Schramm
2019	J	`jnl`	The SDP value for random two-eigenvalue CSPs. CoRR Sidhanth Mohanty, Ryan O'Donnell, Pedro Paredes
2019	A*	`conf`	The threshold for SDP-refutation of random regular NAE-3SAT. SODA Yash Deshpande, Andrea Montanari, Ryan O'Donnell, Tselil Schramm, Subhabrata Sen
2019	J	`jnl`	X-Ramanujan Graphs. CoRR Sidhanth Mohanty, Ryan O'Donnell
2018	J	`jnl`	A log-Sobolev inequality for the multislice, with applications. CoRR Yuval Filmus, Ryan O'Donnell, Xinyu Wu
2018	J	`jnl`	Fooling Polytopes. CoRR Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan
2018	J	`jnl`	Fooling Polytopes. Electron. Colloquium Comput. Complex. Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan
2018	J	`jnl`	Learning sparse mixtures of rankings from noisy information. CoRR Anindya De, Ryan O'Donnell, Rocco A. Servedio
2018	—	`conf`	On Closeness to k-Wise Uniformity. APPROX-RANDOM Ryan O'Donnell, Yu Zhao
2018	J	`jnl`	On closeness to k-wise uniformity. CoRR Ryan O'Donnell, Yu Zhao
2018	J	`jnl`	SOS lower bounds with hard constraints: think global, act local. CoRR Pravesh Kothari, Ryan O'Donnell, Tselil Schramm
2018	J	`jnl`	Sherali-Adams Strikes Back. CoRR Ryan O'Donnell, Tselil Schramm
2018	J	`jnl`	Special Issue: CCC 2017: Guest Editor's Foreword. Theory Comput. Shachar Lovett, Ryan O'Donnell
2018	J	`jnl`	The Weakness of CTC Qubits and the Power of Approximate Counting. ACM Trans. Comput. Theory Ryan O'Donnell, A. C. Cem Say
2018	J	`jnl`	The threshold for SDP-refutation of random regular NAE-3SAT. CoRR Yash Deshpande, Andrea Montanari, Ryan O'Donnell, Tselil Schramm, Subhabrata Sen
2017	A	`ed.`	32nd Computational Complexity Conference, CCC 2017, Riga, Latvia, July 6-9, 2017 Ryan O'Donnell
2017	B	`conf`	Bounding Laconic Proof Systems by Solving CSPs in Parallel. SPAA Jason Li, Ryan O'Donnell
2017	A*	`conf`	Efficient quantum tomography II. STOC Ryan O'Donnell, John Wright
2017	J	`jnl`	Guest Column: A Primer on the Statistics of Longest Increasing Subsequences and Quantum States (Shortened Version). SIGACT News Ryan O'Donnell, John Wright
2017	J	`jnl`	Improved NP-Inapproximability for 2-Variable Linear Equations. Theory Comput. Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O'Donnell, John Wright
2017	A*	`conf`	Optimal mean-based algorithms for trace reconstruction. STOC Anindya De, Ryan O'Donnell, Rocco A. Servedio
2017	A*	`conf`	Quantum Automata Cannot Detect Biased Coins, Even in the Limit. ICALP Guy Kindler, Ryan O'Donnell
2017	J	`jnl`	Quantum state certification. CoRR Costin Badescu, Ryan O'Donnell, John Wright
2017	A	`conf`	SOS Is Not Obviously Automatizable, Even Approximately. ITCS Ryan O'Donnell
2017	J	`jnl`	Sharp bounds for population recovery. CoRR Anindya De, Ryan O'Donnell, Rocco A. Servedio
2017	A*	`conf`	Sum of squares lower bounds for refuting any CSP. STOC Pravesh K. Kothari, Ryuhei Mori, Ryan O'Donnell, David Witmer
2017	J	`jnl`	Sum of squares lower bounds for refuting any CSP. CoRR Pravesh K. Kothari, Ryuhei Mori, Ryan O'Donnell, David Witmer
2016	J	`jnl`	Bounding laconic proof systems by solving CSPs in parallel. Electron. Colloquium Comput. Complex. Jason Li, Ryan O'Donnell
2016	J	`jnl`	Efficient quantum tomography II. CoRR Ryan O'Donnell, John Wright
2016	A*	`conf`	Efficient quantum tomography. STOC Ryan O'Donnell, John Wright
2016	J	`jnl`	Optimal mean-based algorithms for trace reconstruction. CoRR Anindya De, Ryan O'Donnell, Rocco A. Servedio
2016	A	`conf`	Polynomial Bounds for Decoupling, with Applications. CCC Ryan O'Donnell, Yu Zhao
2016	J	`jnl`	Quantum automata cannot detect biased coins, even in the limit. CoRR Guy Kindler, Ryan O'Donnell
2016	J	`jnl`	SOS is not obviously automatizable, even approximately. Electron. Colloquium Comput. Complex. Ryan O'Donnell
2016	J	`jnl`	The weakness of CTC qubits and the power of approximate counting. Electron. Colloquium Comput. Complex. Ryan O'Donnell, A. C. Cem Say
2015	B	`conf`	Algorithmic Signaling of Features in Auction Design. SAGT Shaddin Dughmi, Nicole Immorlica, Ryan O'Donnell, Li-Yang Tan
2015	—	`conf`	Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree. APPROX-RANDOM Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright
2015	J	`jnl`	Beating the random assignment on constraint satisfaction problems of bounded degree. CoRR Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright
2015	J	`jnl`	Beating the random assignment on constraint satisfaction problems of bounded degree. Electron. Colloquium Comput. Complex. Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright
2015	B	`conf`	Conditioning and covariance on caterpillars. ITW Sarah R. Allen, Ryan O'Donnell
2015	J	`jnl`	Continuous analogues of the Most Informative Function problem. CoRR Guy Kindler, Ryan O'Donnell, David Witmer
2015	J	`jnl`	Efficient quantum tomography. CoRR Ryan O'Donnell, John Wright
2015	J	`jnl`	Hardness of Max-2Lin and Max-3Lin over Integers, Reals, and Large Cyclic Groups. ACM Trans. Comput. Theory Ryan O'Donnell, Yi Wu, Yuan Zhou
2015	A*	`conf`	How to Refute a Random CSP. FOCS Sarah R. Allen, Ryan O'Donnell, David Witmer
2015	J	`jnl`	How to refute a random CSP. CoRR Sarah R. Allen, Ryan O'Donnell, David Witmer
2015	—	`conf`	Improved NP-Inapproximability for 2-Variable Linear Equations. APPROX-RANDOM Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O'Donnell, John Wright
2015	—	`conf`	Optimal Bounds for Estimating Entropy with PMF Queries. MFCS (2) Cafer Caferov, Baris Kaya, Ryan O'Donnell, A. C. Cem Say
2015	J	`jnl`	Polynomial bounds for decoupling, with applications. CoRR Ryan O'Donnell, Yu Zhao
2015	A*	`conf`	Quantum Spectrum Testing. STOC Ryan O'Donnell, John Wright
2014	A	`conf`	A Composition Theorem for Parity Kill Number. CCC Ryan O'Donnell, John Wright, Yu Zhao, Xiaorui Sun, Li-Yang Tan
2014	—	`book`	Analysis of Boolean Functions. Ryan O'Donnell
2014	J	`jnl`	Conditioning and covariance on caterpillars. CoRR Sarah R. Allen, Ryan O'Donnell
2014	A	`conf`	Goldreich's PRG: Evidence for Near-Optimal Polynomial Stretch. CCC Ryan O'Donnell, David Witmer
2014	A*	`conf`	Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs. SODA Ryan O'Donnell, John Wright, Chenggang Wu, Yuan Zhou
2014	J	`jnl`	Hardness of robust graph isomorphism, Lasserre gaps, and asymmetry of random graphs. CoRR Ryan O'Donnell, John Wright, Chenggang Wu, Yuan Zhou
2014	A*	`conf`	Hypercontractive inequalities via SOS, and the Frankl-Rödl graph. SODA Manuel Kauers, Ryan O'Donnell, Li-Yang Tan, Yuan Zhou
2014	J	`jnl`	New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover. ACM Trans. Comput. Theory Per Austrin, Ryan O'Donnell, Li-Yang Tan, John Wright
2014	—	`conf`	One Time-traveling Bit is as Good as Logarithmically Many. FSTTCS Ryan O'Donnell, A. C. Cem Say
2014	J	`jnl`	One time-travelling bit is as good as logarithmically many. Electron. Colloquium Comput. Complex. Ryan O'Donnell, A. C. Cem Say
2014	J	`jnl`	Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny). ACM Trans. Comput. Theory Ryan O'Donnell, Yi Wu, Yuan Zhou
2014	J	`jnl`	Social choice, computational complexity, Gaussian geometry, and Boolean functions. CoRR Ryan O'Donnell
2014	J	`jnl`	Special Section on the Fifty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010). SIAM J. Comput. Lap Chi Lau, Tal Malkin, Ryan O'Donnell, Luca Trevisan
2014	A*	`conf`	Testing Surface Area. SODA Pravesh Kothari, Amir Nayyeri, Ryan O'Donnell, Chenggang Wu
2013	—	`conf`	A Composition Theorem for the Fourier Entropy-Influence Conjecture. ICALP (1) Ryan O'Donnell, Li-Yang Tan
2013	J	`jnl`	A composition theorem for parity kill number. CoRR Ryan O'Donnell, Xiaorui Sun, Li-Yang Tan, John Wright, Yu Zhao
2013	J	`jnl`	A composition theorem for the Fourier Entropy-Influence conjecture CoRR Ryan O'Donnell, Li-Yang Tan
2013	A*	`conf`	Approximability and proof complexity. SODA Ryan O'Donnell, Yuan Zhou
2013	J	`jnl`	KKL, Kruskal-Katona, and Monotone Nets. SIAM J. Comput. Ryan O'Donnell, Karl Wimmer
2013	A*	`conf`	Learning Sums of Independent Integer Random Variables. FOCS Constantinos Daskalakis, Ilias Diakonikolas, Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan
2013	J	`jnl`	Special Issue on Analysis of Boolean Functions: Guest Editors' Foreword. Theory Comput. Elchanan Mossel, Ryan O'Donnell
2012	—	`conf`	A New Point of NP-Hardness for 2-to-1 Label Cover. APPROX-RANDOM Per Austrin, Ryan O'Donnell, John Wright
2012	J	`jnl`	A new point of NP-hardness for 2-to-1 Label Cover CoRR Per Austrin, Ryan O'Donnell, John Wright
2012	A*	`conf`	A new point of NP-hardness for unique games. STOC Ryan O'Donnell, John Wright
2012	J	`jnl`	Approximability and proof complexity CoRR Ryan O'Donnell, Yuan Zhou
2012	A	`conf`	Gaussian Noise Sensitivity and Fourier Tails. CCC Guy Kindler, Ryan O'Donnell
2012	J	`jnl`	Hypercontractive inequalities via SOS, with an application to Vertex-Cover CoRR Manuel Kauers, Ryan O'Donnell, Li-Yang Tan, Yuan Zhou
2012	J	`jnl`	Improved small-set expansion from higher eigenvalues CoRR Ryan O'Donnell, David Witmer
2012	A	`conf`	Linear programming, width-1 CSPs, and robust satisfaction. ITCS Gábor Kun, Ryan O'Donnell, Suguru Tamaki, Yuichi Yoshida, Yuan Zhou
2012	J	`jnl`	New NP-hardness results for 3-Coloring and 2-to-1 Label Cover CoRR Per Austrin, Ryan O'Donnell, Li-Yang Tan, John Wright
2012	J	`jnl`	Open Problems in Analysis of Boolean Functions CoRR Ryan O'Donnell
2012	J	`jnl`	Pareto Optimal Solutions for Smoothed Analysts. SIAM J. Comput. Ankur Moitra, Ryan O'Donnell
2012	J	`jnl`	Spherical cubes: optimal foams from computational hardness amplification. Commun. ACM Guy Kindler, Anup Rao, Ryan O'Donnell, Avi Wigderson
2011	A*	`conf`	Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions. SODA Ilias Diakonikolas, Ryan O'Donnell, Rocco A. Servedio, Yi Wu
2011	A	`conf`	Hardness of Max-2Lin and Max-3Lin over Integers, Reals, and Large Cyclic Groups. CCC Ryan O'Donnell, Yi Wu, Yuan Zhou
2011	A	`conf`	Optimal lower bounds for locality sensitive hashing (except when q is tiny). ICS Ryan O'Donnell, Yi Wu, Yuan Zhou
2011	A*	`conf`	Pareto optimal solutions for smoothed analysts. STOC Ankur Moitra, Ryan O'Donnell
2011	J	`jnl`	Testing Fourier Dimensionality and Sparsity. SIAM J. Comput. Parikshit Gopalan, Ryan O'Donnell, Rocco A. Servedio, Amir Shpilka, Karl Wimmer
2011	J	`jnl`	The Chow Parameters Problem. SIAM J. Comput. Ryan O'Donnell, Rocco A. Servedio
2011	—	`conf`	The Fourier Entropy-Influence Conjecture for Certain Classes of Boolean Functions. ICALP (1) Ryan O'Donnell, John Wright, Yuan Zhou
2010	A	`conf`	Fooling Functions of Halfspaces under Product Distributions. CCC Parikshit Gopalan, Ryan O'Donnell, Yi Wu, David Zuckerman
2010	J	`jnl`	Fooling functions of halfspaces under product distributions CoRR Parikshit Gopalan, Ryan O'Donnell, Yi Wu, David Zuckerman
2010	J	`jnl`	Fooling functions of halfspaces under product distributions. Electron. Colloquium Comput. Complex. Yi Wu, Ryan O'Donnell, David Zuckerman, Parikshit Gopalan
2010	J	`jnl`	Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions CoRR Ilias Diakonikolas, Ryan O'Donnell, Rocco A. Servedio, Yi Wu
2010	A	`conf`	Lower Bounds for Testing Function Isomorphism. CCC Eric Blais, Ryan O'Donnell
2010	J	`jnl`	New degree bounds for polynomial threshold functions. Comb. Ryan O'Donnell, Rocco A. Servedio
2010	J	`jnl`	Pareto Optimal Solutions for Smoothed Analysts CoRR Ankur Moitra, Ryan O'Donnell
2010	J	`jnl`	Polynomial regression under arbitrary product distributions. Mach. Learn. Eric Blais, Ryan O'Donnell, Karl Wimmer
2010	—	`conf`	SDP Gaps for 2-to-1 and Other Label-Cover Variants. ICALP (1) Venkatesan Guruswami, Subhash Khot, Ryan O'Donnell, Preyas Popat, Madhur Tulsiani, Yi Wu
2010	—	`ch.`	Testing (Subclasses of) Halfspaces. Property Testing Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio
2010	J	`jnl`	Testing Halfspaces. SIAM J. Comput. Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio
2010	C	`conf`	k ALGOSENSORS James Aspnes, Eric Blais, Murat Demirbas, Ryan O'Donnell, Atri Rudra, Steve Uurtamo
2009	A*	`conf`	3-bit dictator testing: 1 vs. 5/8. SODA Ryan O'Donnell, Yi Wu
2009	A*	`conf`	Conditional hardness for satisfiable 3-CSPs. STOC Ryan O'Donnell, Yi Wu
2009	A*	`conf`	KKL, Kruskal-Katona, and Monotone Nets. FOCS Ryan O'Donnell, Karl Wimmer
2009	J	`jnl`	Optimal lower bounds for locality sensitive hashing (except when q is tiny) CoRR Ryan O'Donnell, Yi Wu, Yuan Zhou
2009	J	`jnl`	Optimal lower bounds for locality sensitive hashing (except when q is tiny). Electron. Colloquium Comput. Complex. Ryan O'Donnell, Yi Wu, Yuan Zhou
2009	J	`jnl`	SDP Gaps and UGC-hardness for Max-Cut-Gain. Theory Comput. Subhash Khot, Ryan O'Donnell
2009	—	`conf`	Testing Fourier Dimensionality and Sparsity. ICALP (1) Parikshit Gopalan, Ryan O'Donnell, Rocco A. Servedio, Amir Shpilka, Karl Wimmer
2009	A*	`conf`	Testing halfspaces. SODA Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio
2009	—	`conf`	Testing ±1-weight halfspace. APPROX-RANDOM Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio
2008	A*	`conf`	An optimal sdp algorithm for max-cut, and equally optimal long code tests. STOC Ryan O'Donnell, Yi Wu
2008	J	`jnl`	Eliminating Cycles in the Discrete Torus. Algorithmica Béla Bollobás, Guy Kindler, Imre Leader, Ryan O'Donnell
2008	J	`jnl`	Extremal properties of polynomial threshold functions. J. Comput. Syst. Sci. Ryan O'Donnell, Rocco A. Servedio
2008	A*	`conf`	Learning Geometric Concepts via Gaussian Surface Area. FOCS Adam R. Klivans, Ryan O'Donnell, Rocco A. Servedio
2008	J	`jnl`	Learning Mixtures of Product Distributions over Discrete Domains. SIAM J. Comput. Jon Feldman, Ryan O'Donnell, Rocco A. Servedio
2008	A*	`conf`	Polynomial Regression under Arbitrary Product Distributions. COLT Eric Blais, Ryan O'Donnell, Karl Wimmer
2008	J	`jnl`	Some Topics in Analysis of Boolean Functions. Electron. Colloquium Comput. Complex. Ryan O'Donnell
2008	A*	`conf`	Some topics in analysis of boolean functions. STOC Ryan O'Donnell
2008	A*	`conf`	Spherical Cubes and Rounding in High Dimensions. FOCS Guy Kindler, Ryan O'Donnell, Anup Rao, Avi Wigderson
2008	A*	`conf`	The chow parameters problem. STOC Ryan O'Donnell, Rocco A. Servedio
2007	A*	`conf`	Approximation by DNF: Examples and Counterexamples. ICALP Ryan O'Donnell, Karl Wimmer
2007	J	`jnl`	Learning Monotone Decision Trees in Polynomial Time. SIAM J. Comput. Ryan O'Donnell, Rocco A. Servedio
2007	J	`jnl`	Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?. SIAM J. Comput. Subhash Khot, Guy Kindler, Elchanan Mossel, Ryan O'Donnell
2007	J	`jnl`	Testing Halfspaces. Electron. Colloquium Comput. Complex. Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio
2007	A	`conf`	Understanding Parallel Repetition Requires Understanding Foams. CCC Uriel Feige, Guy Kindler, Ryan O'Donnell
2007	J	`jnl`	Understanding Parallel Repetition Requires Understanding Foams. Electron. Colloquium Comput. Complex. Uriel Feige, Guy Kindler, Ryan O'Donnell
2006	B	`conf`	Eliminating Cycles in the Discrete Torus. LATIN Béla Bollobás, Guy Kindler, Imre Leader, Ryan O'Donnell
2006	A	`conf`	Learning Monotone Decision Trees in Polynomial Time. CCC Ryan O'Donnell, Rocco A. Servedio
2006	A*	`conf`	On the fourier tails of bounded functions over the discrete cube. STOC Irit Dinur, Ehud Friedgut, Guy Kindler, Ryan O'Donnell
2006	A*	`conf`	PAC Learning Axis-Aligned Mixtures of Gaussians with No Separation Assumption. COLT Jon Feldman, Rocco A. Servedio, Ryan O'Donnell
2006	J	`jnl`	PAC Learning Mixtures of Axis-Aligned Gaussians with No Separation Assumption CoRR Jon Feldman, Ryan O'Donnell, Rocco A. Servedio
2006	A*	`conf`	SDP gaps and UGC-hardness for MAXCUTGAIN. FOCS Subhash Khot, Ryan O'Donnell
2005	J	`jnl`	Coin flipping from a cosmic source: On error correction of truly random bits. Random Struct. Algorithms Elchanan Mossel, Ryan O'Donnell
2005	A*	`conf`	Every decision tree has an in.uential variable. FOCS Ryan O'Donnell, Michael E. Saks, Oded Schramm, Rocco A. Servedio
2005	J	`jnl`	Every decision tree has an influential variable CoRR Ryan O'Donnell, Michael E. Saks, Oded Schramm, Rocco A. Servedio
2005	J	`jnl`	Learning DNF from random walks. J. Comput. Syst. Sci. Nader H. Bshouty, Elchanan Mossel, Ryan O'Donnell, Rocco A. Servedio
2005	A*	`conf`	Learning mixtures of product distributions over discrete domains. FOCS Jon Feldman, Ryan O'Donnell, Rocco A. Servedio
2005	A*	`conf`	Noise stability of functions with low in.uences invariance and optimality. FOCS Elchanan Mossel, Ryan O'Donnell, Krzysztof Oleszkiewicz
2005	J	`jnl`	Noise stability of functions with low influences: invariance and optimality CoRR Elchanan Mossel, Ryan O'Donnell, Krzysztof Oleszkiewicz
2005	J	`jnl`	Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs? Electron. Colloquium Comput. Complex. Guy Kindler, Ryan O'Donnell, Subhash Khot, Elchanan Mossel
2004	J	`jnl`	Hardness amplification within J. Comput. Syst. Sci. Ryan O'Donnell
2004	J	`jnl`	Learning functions of k relevant variables. J. Comput. Syst. Sci. Elchanan Mossel, Ryan O'Donnell, Rocco A. Servedio
2004	J	`jnl`	Learning intersections and thresholds of halfspaces. J. Comput. Syst. Sci. Adam R. Klivans, Ryan O'Donnell, Rocco A. Servedio
2004	A*	`conf`	Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs? FOCS Subhash Khot, Guy Kindler, Elchanan Mossel, Ryan O'Donnell
2003	A	`conf`	Extremal properties of polynomial threshold functions. CCC Ryan O'Donnell, Rocco A. Servedio
2003	A*	`conf`	Learning DNF from Random Walks. FOCS Nader H. Bshouty, Elchanan Mossel, Ryan O'Donnell, Rocco A. Servedio
2003	A*	`conf`	Learning juntas. STOC Elchanan Mossel, Ryan O'Donnell, Rocco A. Servedio
2003	A*	`conf`	New degree bounds for polynomial threshold functions. STOC Ryan O'Donnell, Rocco A. Servedio
2003	J	`jnl`	On the noise sensitivity of monotone functions. Random Struct. Algorithms Elchanan Mossel, Ryan O'Donnell
2002	A*	`conf`	Derandomized dimensionality reduction with applications. SODA Lars Engebretsen, Piotr Indyk, Ryan O'Donnell
2002	A	`conf`	Hardness Amplification within NP. CCC Ryan O'Donnell
2002	A*	`conf`	Hardness amplification within NP. STOC Ryan O'Donnell
2002	A*	`conf`	Learning Intersections and Thresholds of Halfspaces. FOCS Adam R. Klivans, Ryan O'Donnell, Rocco A. Servedio