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 SO, O'Donnell R, Tamuz O, Tan LY
Conference Efficient quantum tomography 2016 • Annual ACM Symposium on Theory of Computing • 19-21-June-2016: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 Conditioning and covariance on caterpillars 2015 • 2015 IEEE Information Theory Workshop, ITW 2015 Allen SR, O'Donnell R
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 • 2015-December:689-708 Allen SR, Odonnell 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 • 14-17-June-2015: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 Goldreich's PRG: Evidence for near-optimal polynomial stretch 2014 • Proceedings of the Annual IEEE Conference on Computational Complexity • 1-12 O'Donnell R, Witmer D
Conference Hardness of robust graph isomorphism, lasserre gaps, and asymmetry of random graphs 2014 • Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms • 1659-1677 O'Donnell R, Wright J, Wu C, Zhou Y
Conference Hypercontractive inequalities via SOS, and the frankl-rodl graph 2014 • Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms • 1644-1658 Kauers M, O'Donnell R, Tan LY, Zhou Y
Conference New NP-hardness results for 3-coloring and 2-to-1 Label Cover 2014 • ACM Transactions on Computation Theory • 6(1): Austrin P, O'Donnell R, Tan LY, 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): 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 symposium on foundations of computer science (FOCS 2010) 2014 • SIAM journal on computing (Print) • 43(1):255 Lau LC, Malkin T, O'Donnell R, Trevisan L
Conference Testing surface area 2014 • Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms • 1204-1214 Kothari P, Nayyeri A, O'Donnell R, Wu C
Conference A composition theorem for the Fourier entropy-influence conjecture 2013 • Lecture Notes in Computer Science • 7965 LNCS(PART 1):780-791 O'Donnell R, Tan LY
Conference Approximability and proof complexity 2013 • Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms • 1537-1556 O'Donnell R, Zhou Y
Journal Article KKL, KruskalKatona, and monotone nets 2013 • SIAM journal on computing (Print) • 42(6):2375-2399 O'Donnell R, Wimmer K
