Conference A New Point of NP-Hardness for 2-to-1 Label Cover 2012 • Lecture Notes in Computer Science • 7408:1-12 Austrin P, O’Donnell R, Wright J
Conference A new point of NP-hardness for unique games 2012 • Annual ACM Symposium on Theory of Computing • 289-306 O'Donnell R, Wright J
Conference Gaussian Noise Sensitivity and Fourier Tails 2012 • Proceedings of the Annual IEEE Conference on Computational Complexity • 137-147 Kindler G, O'Donnell R
Conference Linear programming, width-1 CSPs, and robust satisfaction 2012 484-495 Kun G, O'Donnell R, Tamaki S, Yoshida Y, Zhou Y
Conference Pareto Optimal Solutions for Smoothed Analysts 2012 • SIAM journal on computing (Print) • 41(5):1266-1284 Moitra A, O'Donnell R
Conference Spherical Cubes: Optimal Foams from Computational Hardness Amplification 2012 • Communications of the ACM • 55(10):90-97 Kindler G, Rao A, O'Donnell R, Wigderson A
Conference Hardness of Max-2Lin and Max-3Lin over integers, reals, and large cyclic 2011 • Proceedings of the Annual IEEE Conference on Computational Complexity • 23-33 O'Donnell R, Wu Y, Zhou Y
Conference Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions 2011 1590-1606 Diakonikolas I, O'Donnell R, Servedio RA, Wu Y
Journal Article Improved Methods for PCA-Based Reconstructions: Case Study Using the Steig et al. (2009) Antarctic Temperature Reconstruction 2011 • Journal of Climate • 24(8):2099-2115 O’Donnell R, Lewis N, McIntyre S, Condon J
Conference Pareto optimal solutions for smoothed analysts 2011 • Annual ACM Symposium on Theory of Computing • 225-234 Moitra A, O'Donnell R
Journal Article Testing Fourier Dimensionality and Sparsity 2011 • SIAM journal on computing (Print) • 40(4):1075-1100 Gopalan P, O'Donnell R, Servedio RA, Shpilka A, Wimmer K
Journal Article The Chow Parameters Problem 2011 • SIAM journal on computing (Print) • 40(1):165-199 O'Donnell R, Servedio RA
Conference The Fourier Entropy-Influence Conjecture for Certain Classes of Boolean Functions 2011 • Lecture Notes in Computer Science • 6755:330-341 O'Donnell R, Wright J, Zhou Y
Conference Fooling Functions of Halfspaces under Product Distributions 2010 • Proceedings of the Annual IEEE Conference on Computational Complexity • 223-234 Gopalan P, O'Donnell R, Wu Y, Zuckerman D
Conference k + Decision Trees 2010 • Lecture Notes in Computer Science • 6451:74-88 Aspnes J, Blais E, Demirbas M, O’Donnell R, Rudra A, Uurtamo S
Conference k<sup>+</sup> decision trees - (Extended abstract) 2010 • Lecture Notes in Computer Science • 6451 LNCS:74-88 Aspnes J, Blais E, Demirbas M, O'Donnell R, Rudra A, Uurtamo S
Conference Lower bounds for testing function isomorphism 2010 • Proceedings of the Annual IEEE Conference on Computational Complexity • 235-246 Blais E, O'Donnell R
Journal Article New degree bounds for polynomial threshold functions 2010 • Combinatorica • 30(3):327-358 O’Donnell R, Servedio RA
Journal Article Polynomial regression under arbitrary product distributions 2010 • Machine Learning • 80(2-3):273-294 Blais E, O’Donnell R, Wimmer K
Conference SDP Gaps for 2-to-1 and Other Label-Cover Variants 2010 • Lecture Notes in Computer Science • 6198:617-+ Guruswami V, Khot S, O'Donnell R, Popat P, Tulsiani M, Wu Y
Conference Testing (Subclasses of) Halfspaces 2010 • Lecture Notes in Computer Science • 6390:334-340 Matulef K, O’Donnell R, Rubinfeld R, Servedio R
Conference 3-Bit Dictator Testing: 1 vs. 5/8 2009 • PROCEEDINGS OF THE TWENTIETH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS • 365-374 O'Donnell R, Wu Y
Conference KKL, Kruskal-Katona, and Monotone Nets 2009 • Annual Symposium on Foundations of Computer Science • 725-734 O'Donnell R, Wimmer K
Conference Proceedings of the Annual IEEE Conference on Computational Complexity: Preface 2009 • Proceedings of the Annual IEEE Conference on Computational Complexity Buhrmann H, Gál A, Goldreich O, Håstad J, Krause M, O'Donnell R, Razborov A, Regev O, Umans C, Yekhanin S
Conference Testing Fourier Dimensionality and Sparsity 2009 • Lecture Notes in Computer Science • 5555:500-512 Gopalan P, O’Donnell R, Servedio RA, Shpilka A, Wimmer K
