Conference X-Ramanujan graphs 2020 • Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms • 2020-January:1226-1243 Mohanty S, O'Donnell R
Conference On Closeness to <i>k</i>-Wise Uniformity 2018 • Leibniz International Proceedings in Informatics • 116: O'Donnell R, Zhao Y
Conference Bounding Laconic Proof Systems by Solving CSPs in Parallel 2017 • PROCEEDINGS OF THE 29TH ACM SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES (SPAA'17) • 95-99 Li J, O'Donnell R
Conference Efficient Quantum Tomography II 2017 • Annual ACM Symposium on Theory of Computing • 962-974 O'Donnell R, Wright J
Conference Optimal Mean-Based Algorithms for Trace Reconstruction 2017 • Annual ACM Symposium on Theory of Computing • 1047-1056 De A, O'Donnell R, Servedio RA
Conference Quantum automata cannot detect biased coins, even in the limit 2017 • Leibniz International Proceedings in Informatics • 80: Kindler G, O'Donnell R
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