| 2026 | ICALP | Sublinear-Query Relative-Error Testing of Halfspaces. | Xi Chen, Anindya De, Yizhi Huang, Shivam Nadimpalli, Rocco A. Servedio, Tianqi Yang |
| 2026 | ICALP | Relative-Error Unateness Testing. | Xi Chen, Diptaksho Palit, Kabir Peshawaria, William Pires, Rocco A. Servedio, Yiding Zhang |
| 2026 | SODA | Halfspaces are hard to test with relative error. | Xi Chen, Anindya De, Yizhi Huang, Shivam Nadimpalli, Rocco A. Servedio, Tianqi Yang |
| 2026 | SODA | Is nasty noise actually harder than malicious noise? | Guy Blanc, Yizhi Huang, Tal Malkin, Rocco A. Servedio |
| 2026 | STOC | Learning Functions of Halfspaces. | Josh Alman, Shyamal Patel, Rocco A. Servedio |
| 2026 | STOC | Testing Noisy Low-Degree Polynomials for Sparsity. | Yiqiao Bao, Anindya De, Shivam Nadimpalli, Rocco A. Servedio, Nathan White |
| 2026 | STOC | Improved Bounds for Coin Flipping, Leader Election, and Random Selection. | Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach, Rocco A. Servedio |
| 2026 | STOC | A Mysterious Connection between Tolerant Junta Testing and Agnostically Learning Conjunctions. | Xi Chen, Shyamal Patel, Rocco A. Servedio |
| 2026 | STOC | Sparsifying Suprema of Gaussian Processes. | Anindya De, Shivam Nadimpalli, Ryan O'Donnell, Rocco A. Servedio |
| 2025 | COLT | Testing Juntas and Junta Subclasses with Relative Error. | Xi Chen, William Pires, Toniann Pitassi, Rocco A. Servedio |
| 2025 | ESA | Testing Sumsets Is Hard. | Xi Chen, Shivam Nadimpalli, Tim Randolph, Rocco A. Servedio, Or Zamir |
| 2025 | FOCS | Faster Exact Learning of k-Term DNFs with Membership and Equivalence Queries. | Josh Alman, Shivam Nadimpalli, Shyamal Patel, Rocco A. Servedio |
| 2025 | ICALP | Relative-Error Testing of Conjunctions and Decision Lists. | Xi Chen, William Pires, Toniann Pitassi, Rocco A. Servedio |
| 2025 | SODA | Relative-error monotonicity testing. | Xi Chen, Anindya De, Yizhi Huang, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio, Tianqi Yang |
| 2025 | SODA | Lower Bounds for Convexity Testing. | Xi Chen, Anindya De, Shivam Nadimpalli, Rocco A. Servedio, Erik Waingarten |
| 2025 | STOC | DNF Learning via Locally Mixing Random Walks. | Josh Alman, Shivam Nadimpalli, Shyamal Patel, Rocco A. Servedio |
| 2024 | FOCS | Gaussian Approximation of Convex Sets by Intersections of Halfspaces. | Anindya De, Shivam Nadimpalli, Rocco A. Servedio |
| 2024 | SODA | Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity, Unateness, and Juntas. | Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio |
| 2024 | STOC | Detecting Low-Degree Truncation. | Anindya De, Huan Li, Shivam Nadimpalli, Rocco A. Servedio |
| 2023 | FOCS | Explicit orthogonal and unitary designs. | Ryan O'Donnell, Rocco A. Servedio, Pedro Paredes |
| 2023 | SODA | Approximate Trace Reconstruction from a Single Trace. | Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha |
| 2023 | SODA | Testing Convex Truncation. | Anindya De, Shivam Nadimpalli, Rocco A. Servedio |
| 2022 | COLT | Near-Optimal Statistical Query Lower Bounds for Agnostically Learning Intersections of Halfspaces with Gaussian Marginals. | Daniel J. Hsu, Clayton Hendrick Sanford, Rocco A. Servedio, Emmanouil-Vasileios Vlatakis-Gkaragkounis |
| 2022 | SODA | Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces. | Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha |
| 2022 | SODA | Average-Case Subset Balancing Problems. | Xi Chen, Yaonan Jin, Tim Randolph, Rocco A. Servedio |
| 2022 | SODA | Approximating Sumset Size. | Anindya De, Shivam Nadimpalli, Rocco A. Servedio |
| 2021 | COLT | Reconstructing weighted voting schemes from partial information about their power indices. | Huck Bennett, Anindya De, Rocco A. Servedio, Emmanouil-Vasileios Vlatakis-Gkaragkounis |
| 2021 | COLT | Learning sparse mixtures of permutations from noisy information. | Anindya De, Ryan O'Donnell, Rocco A. Servedio |
| 2021 | COLT | Weak learning convex sets under normal distributions. | Anindya De, Rocco A. Servedio |
| 2021 | COLT | On the Approximation Power of Two-Layer Networks of Random ReLUs. | Daniel Hsu, Clayton Sanford, Rocco A. Servedio, Emmanouil V. Vlatakis-Gkaragkounis |
| 2021 | SODA | Polynomial-time trace reconstruction in the smoothed complexity model. | Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha |
| 2020 | SODA | Learning from satisfying assignments under continuous distributions. | Clment L. Canonne, Anindya De, Rocco A. Servedio |
| 2020 | SODA | A Lower Bound on Cycle-Finding in Sparse Digraphs. | Xi Chen, Tim Randolph, Rocco A. Servedio, Timothy Sun |
| 2020 | STOC | Testing noisy linear functions for sparsity. | Xue Chen, Anindya De, Rocco A. Servedio |
| 2020 | STOC | Fooling Gaussian PTFs via local hyperconcentration. | Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan |
| 2019 | FOCS | Beyond Trace Reconstruction: Population Recovery from the Deletion Channel. | Frank Ban, Xi Chen, Adam Freilich, Rocco A. Servedio, Sandip Sinha |
| 2019 | SODA | Pseudorandomness for read-k DNF formulas. | Rocco A. Servedio, Li-Yang Tan |
| 2019 | STOC | Fooling polytopes. | Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan |
| 2018 | FOCS | Learning Sums of Independent Random Variables with Sparse Collective Support. | Anindya De, Philip M. Long, Rocco A. Servedio |
| 2018 | STOC | Distribution-free junta testing. | Zhengyang Liu, Xi Chen, Rocco A. Servedio, Ying Sheng, Jinyu Xie |
| 2017 | FOCS | Deterministic Search for CNF Satisfying Assignments in Almost Polynomial Time. | Rocco A. Servedio, Li-Yang Tan |
| 2017 | FOCS | Fooling Intersections of Low-Weight Halfspaces. | Rocco A. Servedio, Li-Yang Tan |
| 2017 | STOC | Addition is exponentially harder than counting for shallow monotone circuits. | Xi Chen, Igor C. Oliveira, Rocco A. Servedio |
| 2017 | STOC | Optimal mean-based algorithms for trace reconstruction. | Anindya De, Ryan O'Donnell, Rocco A. Servedio |
| 2016 | STOC | Near-optimal small-depth lower bounds for small distance connectivity. | Xi Chen, Igor C. Oliveira, Rocco A. Servedio, Li-Yang Tan |
| 2016 | STOC | Poly-logarithmic Frege depth lower bounds via an expander switching lemma. | Toniann Pitassi, Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan |
| 2015 | FOCS | An Average-Case Depth Hierarchy Theorem for Boolean Circuits. | Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan |
| 2015 | SODA | Learning from satisfying assignments. | Anindya De, Ilias Diakonikolas, Rocco A. Servedio |
| 2015 | STOC | Boolean Function Monotonicity Testing Requires (Almost) n | Xi Chen, Anindya De, Rocco A. Servedio, Li-Yang Tan |
| 2014 | FOCS | New Algorithms and Lower Bounds for Monotonicity Testing. | Xi Chen, Rocco A. Servedio, Li-Yang Tan |
| 2014 | ICALP | On DNF Approximators for Monotone Boolean Functions. | Eric Blais, Johan Hstad, Rocco A. Servedio, Li-Yang Tan |
| 2014 | SODA | Testing equivalence between distributions using conditional samples. | Clment L. Canonne, Dana Ron, Rocco A. Servedio |
| 2014 | SODA | A Polynomial-time Approximation Scheme for Fault-tolerant Distributed Storage. | Constantinos Daskalakis, Anindya De, Ilias Diakonikolas, Ankur Moitra, Rocco A. Servedio |
| 2014 | STOC | Efficient density estimation via piecewise polynomial approximation. | Siu On Chan, Ilias Diakonikolas, Rocco A. Servedio, Xiaorui Sun |
| 2014 | STOC | Efficient deterministic approximate counting for low-degree polynomial threshold functions. | Anindya De, Rocco A. Servedio |
| 2013 | FOCS | Learning Sums of Independent Integer Random Variables. | Constantinos Daskalakis, Ilias Diakonikolas, Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan |
| 2013 | ICALP | A Robust Khintchine Inequality, and Algorithms for Computing Optimal Constants in Fourier Analysis and High-Dimensional Geometry. | Anindya De, Ilias Diakonikolas, Rocco A. Servedio |
| 2013 | ICML | Consistency versus Realizable H-Consistency for Multiclass Classification. | Philip M. Long, Rocco A. Servedio |
| 2013 | SODA | Learning mixtures of structured distributions over discrete domains. | Siu On Chan, Ilias Diakonikolas, Rocco A. Servedio, Xiaorui Sun |
| 2013 | SODA | Testing | Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio, Gregory Valiant, Paul Valiant |
| 2013 | SODA | Exponentially Improved Algorithms and Lower Bounds for Testing Signed Majorities. | Dana Ron, Rocco A. Servedio |
| 2012 | ICALP | The Inverse Shapley Value Problem. | Anindya De, Ilias Diakonikolas, Rocco A. Servedio |
| 2012 | SODA | Learning | Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio |
| 2012 | SODA | Private data release via learning thresholds. | Moritz Hardt, Guy N. Rothblum, Rocco A. Servedio |
| 2012 | STOC | Learning poisson binomial distributions. | Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio |
| 2012 | STOC | Nearly optimal solutions for the chow parameters problem and low-weight approximation of halfspaces. | Anindya De, Ilias Diakonikolas, Vitaly Feldman, Rocco A. Servedio |
| 2011 | SODA | Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions. | Ilias Diakonikolas, Ryan O'Donnell, Rocco A. Servedio, Yi Wu |
| 2010 | ICML | Restricted Boltzmann Machines are Hard to Approximately Evaluate or Simulate. | Philip M. Long, Rocco A. Servedio |
| 2010 | STOC | Bounding the average sensitivity and noise sensitivity of polynomial threshold functions. | Ilias Diakonikolas, Prahladh Harsha, Adam R. Klivans, Raghu Meka, Prasad Raghavendra, Rocco A. Servedio, Li-Yang Tan |
| 2009 | FOCS | Bounded Independence Fools Halfspaces. | Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A. Servedio, Emanuele Viola |
| 2009 | ICALP | Testing Fourier Dimensionality and Sparsity. | Parikshit Gopalan, Ryan O'Donnell, Rocco A. Servedio, Amir Shpilka, Karl Wimmer |
| 2009 | ICALP | Learning Halfspaces with Malicious Noise. | Adam R. Klivans, Philip M. Long, Rocco A. Servedio |
| 2009 | SODA | Testing halfspaces. | Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio |
| 2008 | FOCS | Learning Geometric Concepts via Gaussian Surface Area. | Adam R. Klivans, Ryan O'Donnell, Rocco A. Servedio |
| 2008 | ICALP | Optimal Cryptographic Hardness of Learning Monotone Functions. | Dana Dachman-Soled, Homin K. Lee, Tal Malkin, Rocco A. Servedio, Andrew Wan, Hoeteck Wee |
| 2008 | ICALP | Efficiently Testing Sparse GF(2) Polynomials. | Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Rocco A. Servedio, Andrew Wan |
| 2008 | ICML | Random classification noise defeats all convex potential boosters. | Philip M. Long, Rocco A. Servedio |
| 2008 | STOC | The chow parameters problem. | Ryan O'Donnell, Rocco A. Servedio |
| 2007 | ALT | Editors' Introduction. | Marcus Hutter, Rocco A. Servedio, Eiji Takimoto |
| 2007 | FOCS | Testing for Concise Representations. | Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A. Servedio, Andrew Wan |
| 2007 | LICS | Highly Efficient Secrecy-Preserving Proofs of Correctness of Computations and Applications. | Michael O. Rabin, Rocco A. Servedio, Christopher Thorpe |
| 2006 | ALT | Learning Unions of | Alp Atici, Rocco A. Servedio |
| 2006 | COLT | PAC Learning Axis-Aligned Mixtures of Gaussians with No Separation Assumption. | Jon Feldman, Rocco A. Servedio, Ryan O'Donnell |
| 2006 | COLT | DNF Are Teachable in the Average Case. | Homin K. Lee, Rocco A. Servedio, Andrew Wan |
| 2006 | COLT | Discriminative Learning Can Succeed Where Generative Learning Fails. | Philip M. Long, Rocco A. Servedio |
| 2006 | TAMC | On PAC Learning Algorithms for Rich Boolean Function Classes. | Rocco A. Servedio |
| 2005 | COLT | Separating Models of Learning from Correlated and Uncorrelated Data. | Ariel Elbaz, Homin K. Lee, Rocco A. Servedio, Andrew Wan |
| 2005 | COLT | Martingale Boosting. | Philip M. Long, Rocco A. Servedio |
| 2005 | FOCS | Agnostically Learning Halfspaces. | Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour, Rocco A. Servedio |
| 2005 | FOCS | Every decision tree has an in.uential variable. | Ryan O'Donnell, Michael E. Saks, Oded Schramm, Rocco A. Servedio |
| 2005 | FOCS | Learning mixtures of product distributions over discrete domains. | Jon Feldman, Ryan O'Donnell, Rocco A. Servedio |
| 2005 | ICML | Unsupervised evidence integration. | Philip M. Long, Vinay Varadan, Sarah Gilman, Mark Treshock, Rocco A. Servedio |
| 2005 | STOC | Testing monotone high-dimensional distributions. | Ronitt Rubinfeld, Rocco A. Servedio |
| 2004 | COLT | Learning Intersections of Halfspaces with a Margin. | Adam R. Klivans, Rocco A. Servedio |
| 2004 | COLT | Perceptron-Like Performance for Intersections of Halfspaces. | Adam R. Klivans, Rocco A. Servedio |
| 2004 | COLT | Toward Attribute Efficient Learning of Decision Lists and Parities. | Adam R. Klivans, Rocco A. Servedio |
| 2004 | ISIT | LP decoding corrects a constant fraction of errors. | Jon Feldman, Tal Malkin, Rocco A. Servedio, Cliff Stein, Martin J. Wainwright |
| 2003 | COLT | Polynomial Certificates for Propositional Classes. | Marta Arias, Roni Khardon, Rocco A. Servedio |
| 2003 | COLT | Learning Random Log-Depth Decision Trees under the Uniform Distribution. | Jeffrey C. Jackson, Rocco A. Servedio |
| 2003 | COLT | Maximum Margin Algorithms with Boolean Kernels. | Roni Khardon, Rocco A. Servedio |
| 2003 | FOCS | Learning DNF from Random Walks. | Nader H. Bshouty, Elchanan Mossel, Ryan O'Donnell, Rocco A. Servedio |
| 2003 | STOC | Boosting in the presence of noise. | Adam Kalai, Rocco A. Servedio |
| 2003 | STOC | Learning juntas. | Elchanan Mossel, Ryan O'Donnell, Rocco A. Servedio |
| 2003 | STOC | New degree bounds for polynomial threshold functions. | Ryan O'Donnell, Rocco A. Servedio |
| 2002 | ALT | On Learning Embedded Midbit Functions. | Rocco A. Servedio |
| 2002 | FOCS | Learning Intersections and Thresholds of Halfspaces. | Adam R. Klivans, Ryan O'Donnell, Rocco A. Servedio |
| 2002 | STOC | Learnability beyond AC0. | Jeffrey C. Jackson, Adam R. Klivans, Rocco A. Servedio |
| 2001 | COLT | Smooth Boosting and Learning with Malicious Noise. | Rocco A. Servedio |
| 2001 | COLT | On Learning Monotone DNF under Product Distributions. | Rocco A. Servedio |
| 2001 | ICALP | Separating Quantum and Classical Learning. | Rocco A. Servedio |
| 2001 | STOC | Learning DNF in time 2 | Adam R. Klivans, Rocco A. Servedio |
| 2000 | COLT | PAC Analogues of Perceptron and Winnow via Boosting the Margin. | Rocco A. Servedio |
| 1999 | COLT | On PAC Learning Using Winnow, Perceptron, and a Perceptron-like Algorithm. | Rocco A. Servedio |
| 1999 | FOCS | Boosting and Hard-Core Sets. | Adam R. Klivans, Rocco A. Servedio |
| 1999 | STOC | Computational Sample Complexity and Attribute-Efficient Learning. | Rocco A. Servedio |