Conference SOS is not obviously automatizable, even approximately 2017 • Leibniz International Proceedings in Informatics • 67: O'Donnell R
Conference Sum of Squares Lower Bounds for Refuting any CSP 2017 • Annual ACM Symposium on Theory of Computing • 132-145 Kothari PK, Mori R, O'Donnell R, Witmer D
Journal Article Convergence, unanimity and disagreement in majority dynamics on unimodular graphs and random graphs 2016 • Stochastic Processes and their Applications • 126(9):2719-2733 Benjamini I, Chan S-O, O’Donnell R, Tamuz O, Tan L-Y
Conference Efficient quantum tomography 2016 • Annual ACM Symposium on Theory of Computing • 899-912 O'Donnell R, Wright J
Journal Article Hypercontractive inequalities via SOS, and the Frankl-Rödl graph 2016 • Discrete Analysis • 4(2016):1-21 Kauers M, O'Donnell R, Tan LY, Zhou Y
Conference Polynomial Bounds for Decoupling, with Applications 2016 • Leibniz International Proceedings in Informatics • 50: O'Donnell R, Zhao Y
Conference Beating the random assignment on constraint satisfaction problems of bounded degree 2015 • Leibniz International Proceedings in Informatics • 40:110-123 Barak B, Moitra A, O'Donnell R, Raghavendra P, Regev O, Steurer D, Trevisan L, Vijayaraghavan A, Witmer D, Wright J
Conference Hardness of Max-2Lin and Max-3Lin over Integers, Reals, and Large Cyclic Groups 2015 • ACM Transactions on Computation Theory • 7(2): O'Donnell R, Wu Y, Zhou Y
Conference How to Refute a Random CSP 2015 • Annual Symposium on Foundations of Computer Science • 689-708 Allen SR, O'Donnell R, Witmer D
Conference Improved NP-inapproximability for 2-variable linear equations 2015 • Leibniz International Proceedings in Informatics • 40:341-360 Håstad J, Huang S, Manokaran R, O'Donnell R, Wright J
Conference Quantum Spectrum Testing 2015 • Annual ACM Symposium on Theory of Computing • 529-538 O'Donnell R, Wright J
Conference A composition theorem for parity kill number 2014 • Proceedings of the Annual IEEE Conference on Computational Complexity • 144-154 O'Donnell R, Wright J, Zhao Y, Sun X, Tan L-Y
Conference Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs 2014 1659-1677 O'Donnell R, Wright J, Wu C, Zhou Y
Conference Hypercontractive inequalities via SOS, and the Frankl–Rödl graph 2014 1644-1658 Kauers M, O'Donnell R, Tan L-Y, Zhou Y
Conference New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover 2014 • ACM Transactions on Computation Theory • 6(1):1-20 Austrin P, O’Donnell R, Tan L-Y, Wright J
Conference One time-traveling bit is as good as logarithmically many 2014 • Leibniz International Proceedings in Informatics • 29:469-480 O'Donnell R, Say ACC
Journal Article Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny) 2014 • ACM Transactions on Computation Theory • 6(1):1-13 O’Donnell R, Wu Y, Zhou Y
Conference Social choice, computational complexity, Gaussian geometry, and Boolean functions 2014 • Proceeding of the International Congress of Mathematicans Icm 2014 • 4:633-658 O'Donnell R
Journal Article Special Section on the Fifty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010) 2014 • SIAM journal on computing (Print) • 43(1):255-255 Lau LC, Malkin T, O'Donnell R, Trevisan L
Conference A Composition Theorem for the Fourier Entropy-Influence Conjecture 2013 • Lecture Notes in Computer Science • 7965:780-791 O’Donnell R, Tan L-Y
Conference Approximability and proof complexity 2013 • PROCEEDINGS OF THE TWENTY-FOURTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS (SODA 2013) • 1537-1556 O'Donnell R, Zhou Y
Journal Article KKL, Kruskal--Katona, and Monotone Nets 2013 • SIAM journal on computing (Print) • 42(6):2375-2399 O'Donnell R, Wimmer K
Conference Learning Sums of Independent Integer Random Variables 2013 • Annual Symposium on Foundations of Computer Science • 217-226 Daskalakis C, Diakonikolas I, O'Donnell R, Servedio RA, Tan L-Y
