Rocco A. Servedio

366 papers A* 98A 25B 5C 1Journal 201Unranked 32

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	DNF formulas are efficiently testable with relative error. CoRR Xi Chen, William Pires, Toniann Pitassi, Rocco A. Servedio
2026	A	`conf`	Forrelation Is Extremally Hard. ITCS Uma Girish, Rocco A. Servedio
2026	A*	`conf`	Halfspaces are hard to test with relative error. SODA Xi Chen, Anindya De, Yizhi Huang, Shivam Nadimpalli, Rocco A. Servedio, Tianqi Yang
2026	A*	`conf`	Is nasty noise actually harder than malicious noise? SODA Guy Blanc, Yizhi Huang, Tal Malkin, Rocco A. Servedio
2026	J	`jnl`	Learning Functions of Halfspaces. CoRR Josh Alman, Shyamal Patel, Rocco A. Servedio
2025	J	`jnl`	A Mysterious Connection Between Tolerant Junta Testing and Agnostically Learning Conjunctions. CoRR Xi Chen, Shyamal Patel, Rocco A. Servedio
2025	A*	`conf`	DNF Learning via Locally Mixing Random Walks. STOC Josh Alman, Shivam Nadimpalli, Shyamal Patel, Rocco A. Servedio
2025	J	`jnl`	DNF Learning via Locally Mixing Random Walks. CoRR Josh Alman, Shivam Nadimpalli, Shyamal Patel, Rocco A. Servedio
2025	A*	`conf`	Faster Exact Learning of k-Term DNFs with Membership and Equivalence Queries. FOCS Josh Alman, Shivam Nadimpalli, Shyamal Patel, Rocco A. Servedio
2025	J	`jnl`	Faster exact learning of k-term DNFs with membership and equivalence queries. CoRR Josh Alman, Shivam Nadimpalli, Shyamal Patel, Rocco A. Servedio
2025	J	`jnl`	Forrelation is Extremally Hard. Electron. Colloquium Comput. Complex. Uma Girish, Rocco A. Servedio
2025	J	`jnl`	Halfspaces are hard to test with relative error. CoRR Xi Chen, Anindya De, Yizhi Huang, Shivam Nadimpalli, Rocco A. Servedio, Tianqi Yang
2025	J	`jnl`	Is nasty noise actually harder than malicious noise? CoRR Guy Blanc, Yizhi Huang, Tal Malkin, Rocco A. Servedio
2025	A*	`conf`	Lower Bounds for Convexity Testing. SODA Xi Chen, Anindya De, Shivam Nadimpalli, Rocco A. Servedio, Erik Waingarten
2025	J	`jnl`	Lower Bounds for Leader Election and Collective Coin Flipping, Revisited. CoRR Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach, Rocco A. Servedio
2025	J	`jnl`	Model-agnostic super-resolution in high dimensions. CoRR Xi Chen, Anindya De, Yizhi Huang, Shivam Nadimpalli, Rocco A. Servedio, Tianqi Yang
2025	J	`jnl`	Polynomial-time Trace Reconstruction in the Smoothed Complexity Model. ACM Trans. Algorithms Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha
2025	A*	`conf`	Relative-Error Testing of Conjunctions and Decision Lists. ICALP Xi Chen, William Pires, Toniann Pitassi, Rocco A. Servedio
2025	A*	`conf`	Relative-error monotonicity testing. SODA Xi Chen, Anindya De, Yizhi Huang, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio, Tianqi Yang
2025	J	`jnl`	Relative-error testing of conjunctions and decision lists. CoRR Xi Chen, William Pires, Toniann Pitassi, Rocco A. Servedio
2025	J	`jnl`	Relative-error unateness testing. CoRR Xi Chen, Diptaksho Palit, Kabir Peshawaria, William Pires, Rocco A. Servedio, Yiding Zhang
2025	A*	`conf`	Testing Juntas and Junta Subclasses with Relative Error. COLT Xi Chen, William Pires, Toniann Pitassi, Rocco A. Servedio
2025	J	`jnl`	Testing Juntas and Junta Subclasses with Relative Error. CoRR Xi Chen, William Pires, Toniann Pitassi, Rocco A. Servedio
2025	A	`conf`	Testing Sumsets Is Hard. ESA Xi Chen, Shivam Nadimpalli, Tim Randolph, Rocco A. Servedio, Or Zamir
2025	J	`jnl`	Testing noisy low-degree polynomials for sparsity. CoRR Yiqiao Bao, Anindya De, Shivam Nadimpalli, Rocco A. Servedio, Nathan White
2025	J	`jnl`	The Probably Approximately Correct Learning Model in Computational Learning Theory. CoRR Rocco A. Servedio
2024	A*	`conf`	Detecting Low-Degree Truncation. STOC Anindya De, Huan Li, Shivam Nadimpalli, Rocco A. Servedio
2024	J	`jnl`	Detecting Low-Degree Truncation. CoRR Anindya De, Huan Li, Shivam Nadimpalli, Rocco A. Servedio
2024	A*	`conf`	Gaussian Approximation of Convex Sets by Intersections of Halfspaces. FOCS Anindya De, Shivam Nadimpalli, Rocco A. Servedio
2024	J	`jnl`	Lower Bounds for Convexity Testing. CoRR Xi Chen, Anindya De, Shivam Nadimpalli, Rocco A. Servedio, Erik Waingarten
2024	A*	`conf`	Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity, Unateness, and Juntas. SODA Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio
2024	J	`jnl`	Relative-error monotonicity testing. CoRR Xi Chen, Anindya De, Yizhi Huang, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio, Tianqi Yang
2024	J	`jnl`	Sparsifying Suprema of Gaussian Processes. CoRR Anindya De, Shivam Nadimpalli, Ryan O'Donnell, Rocco A. Servedio
2024	A	`conf`	Testing Intersecting and Union-Closed Families. ITCS Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio
2024	J	`jnl`	Testing Sumsets is Hard. CoRR Xi Chen, Shivam Nadimpalli, Tim Randolph, Rocco A. Servedio, Or Zamir
2024	A	`conf`	Trace Reconstruction from Local Statistical Queries. APPROX/RANDOM Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio
2024	J	`jnl`	Trace reconstruction from local statistical queries. CoRR Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio
2023	A*	`conf`	Approximate Trace Reconstruction from a Single Trace. SODA Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha
2023	A*	`conf`	Explicit orthogonal and unitary designs. FOCS Ryan O'Donnell, Rocco A. Servedio, Pedro Paredes
2023	J	`jnl`	Explicit orthogonal and unitary designs. CoRR Ryan O'Donnell, Rocco A. Servedio, Pedro Paredes
2023	J	`jnl`	Gaussian Approximation of Convex Sets by Intersections of Halfspaces. CoRR Anindya De, Shivam Nadimpalli, Rocco A. Servedio
2023	J	`jnl`	Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity, Unateness, and Juntas. CoRR Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio
2023	A*	`ed.`	Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 2023 STOC Barna Saha, Rocco A. Servedio
2023	A	`conf`	Subset Sum in Time 2 APPROX/RANDOM Xi Chen, Yaonan Jin, Tim Randolph, Rocco A. Servedio
2023	J	`jnl`	Subset Sum in Time 2 CoRR Xi Chen, Yaonan Jin, Tim Randolph, Rocco A. Servedio
2023	A*	`conf`	Testing Convex Truncation. SODA Anindya De, Shivam Nadimpalli, Rocco A. Servedio
2023	J	`jnl`	Testing Convex Truncation. CoRR Anindya De, Shivam Nadimpalli, Rocco A. Servedio
2023	J	`jnl`	Testing Intersecting and Union-Closed Families. CoRR Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio
2022	J	`jnl`	A Lower Bound on Cycle-Finding in Sparse Digraphs. ACM Trans. Algorithms Xi Chen, Tim Randolph, Rocco A. Servedio, Timothy Sun
2022	J	`jnl`	Approximate Trace Reconstruction from a Single Trace. CoRR Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha
2022	A*	`conf`	Approximating Sumset Size. SODA Anindya De, Shivam Nadimpalli, Rocco A. Servedio
2022	A*	`conf`	Average-Case Subset Balancing Problems. SODA Xi Chen, Yaonan Jin, Tim Randolph, Rocco A. Servedio
2022	A	`conf`	Convex Influences. ITCS Anindya De, Shivam Nadimpalli, Rocco A. Servedio
2022	J	`jnl`	Fooling Polytopes. J. ACM Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan
2022	J	`jnl`	Improved Pseudorandom Generators from Pseudorandom Multi-switching Lemmas. Theory Comput. Rocco A. Servedio, Li-Yang Tan
2022	A*	`conf`	Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces. SODA Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha
2022	A*	`conf`	Near-Optimal Statistical Query Lower Bounds for Agnostically Learning Intersections of Halfspaces with Gaussian Marginals. COLT Daniel J. Hsu, Clayton Hendrick Sanford, Rocco A. Servedio, Emmanouil-Vasileios Vlatakis-Gkaragkounis
2022	J	`jnl`	Near-Optimal Statistical Query Lower Bounds for Agnostically Learning Intersections of Halfspaces with Gaussian Marginals. CoRR Daniel Hsu, Clayton Sanford, Rocco A. Servedio, Emmanouil V. Vlatakis-Gkaragkounis
2022	J	`jnl`	The Perils of Being Unhinged: On the Accuracy of Classifiers Minimizing a Noise-Robust Convex Loss. Neural Comput. Philip M. Long, Rocco A. Servedio
2021	J	`jnl`	Approximating Sumset Size. CoRR Anindya De, Shivam Nadimpalli, Rocco A. Servedio
2021	J	`jnl`	Average-Case Subset Balancing Problems. CoRR Xi Chen, Yaonan Jin, Tim Randolph, Rocco A. Servedio
2021	J	`jnl`	Convex Influences. CoRR Anindya De, Shivam Nadimpalli, Rocco A. Servedio
2021	—	`conf`	Deterministic Approximate Counting of Polynomial Threshold Functions via a Derandomized Regularity Lemma. APPROX-RANDOM Rocco A. Servedio, Li-Yang Tan
2021	J	`jnl`	Fooling Gaussian PTFs via Local Hyperconcentration. CoRR Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan, Daniel Kane
2021	—	`conf`	Fourier Growth of Structured 𝔽 APPROX-RANDOM Jaroslaw Blasiok, Peter Ivanov, Yaonan Jin, Chin Ho Lee, Rocco A. Servedio, Emanuele Viola
2021	J	`jnl`	Fourier growth of structured $\mathbb{F}_2$-polynomials and applications. CoRR Jaroslaw Blasiok, Peter Ivanov, Yaonan Jin, Chin Ho Lee, Rocco A. Servedio, Emanuele Viola
2021	J	`jnl`	Fourier growth of structured 𝔽 Electron. Colloquium Comput. Complex. Jaroslaw Blasiok, Peter Ivanov, Yaonan Jin, Chin Ho Lee, Rocco A. Servedio, Emanuele Viola
2021	A*	`conf`	Learning sparse mixtures of permutations from noisy information. COLT Anindya De, Ryan O'Donnell, Rocco A. Servedio
2021	J	`jnl`	Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces. CoRR Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha
2021	A*	`conf`	On the Approximation Power of Two-Layer Networks of Random ReLUs. COLT Daniel Hsu, Clayton Sanford, Rocco A. Servedio, Emmanouil V. Vlatakis-Gkaragkounis
2021	J	`jnl`	On the Approximation Power of Two-Layer Networks of Random ReLUs. CoRR Daniel Hsu, Clayton Sanford, Rocco A. Servedio, Emmanouil V. Vlatakis-Gkaragkounis
2021	A	`conf`	Polynomial-Time Trace Reconstruction in the Low Deletion Rate Regime. ITCS Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha
2021	A*	`conf`	Polynomial-time trace reconstruction in the smoothed complexity model. SODA Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha
2021	A	`conf`	Quantitative Correlation Inequalities via Semigroup Interpolation. ITCS Anindya De, Shivam Nadimpalli, Rocco A. Servedio
2021	A*	`conf`	Reconstructing weighted voting schemes from partial information about their power indices. COLT Huck Bennett, Anindya De, Rocco A. Servedio, Emmanouil-Vasileios Vlatakis-Gkaragkounis
2021	J	`jnl`	The perils of being unhinged: On the accuracy of classifiers minimizing a noise-robust convex loss. CoRR Philip M. Long, Rocco A. Servedio
2021	A*	`conf`	Weak learning convex sets under normal distributions. COLT Anindya De, Rocco A. Servedio
2020	A*	`conf`	A Lower Bound on Cycle-Finding in Sparse Digraphs. SODA Xi Chen, Tim Randolph, Rocco A. Servedio, Timothy Sun
2020	A*	`conf`	Fooling Gaussian PTFs via local hyperconcentration. STOC Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan
2020	A*	`conf`	Learning from satisfying assignments under continuous distributions. SODA Clément L. Canonne, Anindya De, Rocco A. Servedio
2020	J	`jnl`	Polynomial-time trace reconstruction in the low deletion rate regime. CoRR Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha
2020	J	`jnl`	Polynomial-time trace reconstruction in the smoothed complexity model. CoRR Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha
2020	J	`jnl`	Quantitative Correlation Inequalities via Semigroup Interpolation. CoRR Anindya De, Shivam Nadimpalli, Rocco A. Servedio
2020	J	`jnl`	Reconstructing weighted voting schemes from partial information about their power indices. CoRR Huck Bennett, Anindya De, Rocco A. Servedio, Emmanouil-Vasileios Vlatakis-Gkaragkounis
2020	J	`jnl`	Sharp Bounds for Population Recovery. Theory Comput. Anindya De, Ryan O'Donnell, Rocco A. Servedio
2020	A*	`conf`	Testing noisy linear functions for sparsity. STOC Xue Chen, Anindya De, Rocco A. Servedio
2019	J	`jnl`	A Lower Bound on Cycle-Finding in Sparse Digraphs. CoRR Xi Chen, Tim Randolph, Rocco A. Servedio, Timothy Sun
2019	A*	`conf`	Beyond Trace Reconstruction: Population Recovery from the Deletion Channel. FOCS Frank Ban, Xi Chen, Adam Freilich, Rocco A. Servedio, Sandip Sinha
2019	J	`jnl`	Beyond trace reconstruction: Population recovery from the deletion channel. CoRR Frank Ban, Xi Chen, Adam Freilich, Rocco A. Servedio, Sandip Sinha
2019	A	`conf`	Density Estimation for Shift-Invariant Multidimensional Distributions. ITCS Anindya De, Philip M. Long, Rocco A. Servedio
2019	J	`jnl`	Distribution-free Junta Testing. ACM Trans. Algorithms Zhengyang Liu, Xi Chen, Rocco A. Servedio, Ying Sheng, Jinyu Xie
2019	—	`conf`	Efficient Average-Case Population Recovery in the Presence of Insertions and Deletions. APPROX-RANDOM Frank Ban, Xi Chen, Rocco A. Servedio, Sandip Sinha
2019	J	`jnl`	Efficient average-case population recovery in the presence of insertions and deletions. CoRR Frank Ban, Xi Chen, Rocco A. Servedio, Sandip Sinha
2019	A*	`conf`	Fooling polytopes. STOC Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan
2019	—	`conf`	Improved Pseudorandom Generators from Pseudorandom Multi-Switching Lemmas. APPROX-RANDOM Rocco A. Servedio, Li-Yang Tan
2019	J	`jnl`	Kruskal-Katona for convex sets, with applications. CoRR Anindya De, Rocco A. Servedio
2019	J	`jnl`	Learning from satisfying assignments under continuous distributions. CoRR Clément L. Canonne, Anindya De, Rocco A. Servedio
2019	A*	`conf`	Pseudorandomness for read-k DNF formulas. SODA Rocco A. Servedio, Li-Yang Tan
2019	A	`conf`	Simple and Efficient Pseudorandom Generators from Gaussian Processes. CCC Eshan Chattopadhyay, Anindya De, Rocco A. Servedio
2019	J	`jnl`	Testing noisy linear functions for sparsity. CoRR Xue Chen, Anindya De, Rocco A. Servedio
2018	A	`ed.`	33rd Computational Complexity Conference, CCC 2018, San Diego, CA, USA, June 22-24, 2018 CCC Rocco A. Servedio
2018	J	`jnl`	Density estimation for shift-invariant multidimensional distributions. CoRR Anindya De, Philip M. Long, Rocco A. Servedio
2018	J	`jnl`	Deterministic search for CNF satisfying assignments in almost polynomial time. CoRR Rocco A. Servedio, Li-Yang Tan
2018	J	`jnl`	Distribution-free Junta Testing. CoRR Xi Chen, Zhengyang Liu, Rocco A. Servedio, Ying Sheng, Jinyu Xie
2018	A*	`conf`	Distribution-free junta testing. STOC Zhengyang Liu, Xi Chen, Rocco A. Servedio, Ying Sheng, Jinyu Xie
2018	J	`jnl`	Fooling Polytopes. CoRR Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan
2018	J	`jnl`	Fooling Polytopes. Electron. Colloquium Comput. Complex. Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan
2018	J	`jnl`	Improved pseudorandom generators from pseudorandom multi-switching lemmas. CoRR Rocco A. Servedio, Li-Yang Tan
2018	A*	`conf`	Learning Sums of Independent Random Variables with Sparse Collective Support. FOCS Anindya De, Philip M. Long, Rocco A. Servedio
2018	J	`jnl`	Learning Sums of Independent Random Variables with Sparse Collective Support. CoRR Anindya De, Philip M. Long, Rocco A. Servedio
2018	J	`jnl`	Learning sparse mixtures of rankings from noisy information. CoRR Anindya De, Ryan O'Donnell, Rocco A. Servedio
2018	—	`conf`	Luby-Velickovic-Wigderson Revisited: Improved Correlation Bounds and Pseudorandom Generators for Depth-Two Circuits. APPROX-RANDOM Rocco A. Servedio, Li-Yang Tan
2018	J	`jnl`	Luby-Veličković-Wigderson revisited: Improved correlation bounds and pseudorandom generators for depth-two circuits. CoRR Rocco A. Servedio, Li-Yang Tan
2018	J	`jnl`	Settling the Query Complexity of Non-adaptive Junta Testing. J. ACM Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie
2018	J	`jnl`	Simple and efficient pseudorandom generators from Gaussian processes. Electron. Colloquium Comput. Complex. Eshan Chattopadhyay, Anindya De, Rocco A. Servedio
2017	—	`conf`	Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces. APPROX-RANDOM Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten
2017	J	`jnl`	Adaptivity is exponentially powerful for testing monotonicity of halfspaces. CoRR Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten
2017	A*	`conf`	Addition is exponentially harder than counting for shallow monotone circuits. STOC Xi Chen, Igor C. Oliveira, Rocco A. Servedio
2017	J	`jnl`	An Average-Case Depth Hierarchy Theorem for Boolean Circuits. J. ACM Johan Håstad, Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan
2017	A*	`conf`	Deterministic Search for CNF Satisfying Assignments in Almost Polynomial Time. FOCS Rocco A. Servedio, Li-Yang Tan
2017	A*	`conf`	Fooling Intersections of Low-Weight Halfspaces. FOCS Rocco A. Servedio, Li-Yang Tan
2017	J	`jnl`	Fooling intersections of low-weight halfspaces. CoRR Rocco A. Servedio, Li-Yang Tan
2017	A*	`conf`	Optimal mean-based algorithms for trace reconstruction. STOC Anindya De, Ryan O'Donnell, Rocco A. Servedio
2017	—	`conf`	Sample-Based High-Dimensional Convexity Testing. APPROX-RANDOM Xi Chen, Adam Freilich, Rocco A. Servedio, Timothy Sun
2017	J	`jnl`	Sample-based high-dimensional convexity testing. CoRR Xi Chen, Adam Freilich, Rocco A. Servedio, Timothy Sun
2017	A	`conf`	Settling the Query Complexity of Non-Adaptive Junta Testing. CCC Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie
2017	J	`jnl`	Settling the query complexity of non-adaptive junta testing. CoRR Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie
2017	J	`jnl`	Settling the query complexity of non-adaptive junta testing. Electron. Colloquium Comput. Complex. Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie
2017	J	`jnl`	Sharp bounds for population recovery. CoRR Anindya De, Ryan O'Donnell, Rocco A. Servedio
2017	J	`jnl`	The Inverse Shapley value problem. Games Econ. Behav. Anindya De, Ilias Diakonikolas, Rocco A. Servedio
2017	A	`conf`	What Circuit Classes Can Be Learned with Non-Trivial Savings?. ITCS Rocco A. Servedio, Li-Yang Tan
2016	J	`jnl`	A Robust Khintchine Inequality, and Algorithms for Computing Optimal Constants in Fourier Analysis and High-Dimensional Geometry. SIAM J. Discret. Math. Anindya De, Ilias Diakonikolas, Rocco A. Servedio
2016	A	`conf`	Degree and Sensitivity: Tails of Two Distributions. CCC Parikshit Gopalan, Rocco A. Servedio, Avi Wigderson
2016	J	`jnl`	Degree and Sensitivity: tails of two distributions. CoRR Parikshit Gopalan, Rocco A. Servedio, Avishay Tal, Avi Wigderson
2016	J	`jnl`	Degree and Sensitivity: tails of two distributions. Electron. Colloquium Comput. Complex. Parikshit Gopalan, Rocco A. Servedio, Avishay Tal, Avi Wigderson
2016	A*	`conf`	Near-optimal small-depth lower bounds for small distance connectivity. STOC Xi Chen, Igor C. Oliveira, Rocco A. Servedio, Li-Yang Tan
2016	J	`jnl`	Optimal mean-based algorithms for trace reconstruction. CoRR Anindya De, Ryan O'Donnell, Rocco A. Servedio
2016	A*	`conf`	Poly-logarithmic Frege depth lower bounds via an expander switching lemma. STOC Toniann Pitassi, Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan
2016	A	`conf`	Smooth Boolean Functions are Easy: Efficient Algorithms for Low-Sensitivity Functions. ITCS Parikshit Gopalan, Noam Nisan, Rocco A. Servedio, Kunal Talwar, Avi Wigderson
2015	A	`conf`	Adaptivity Helps for Testing Juntas. CCC Rocco A. Servedio, Li-Yang Tan, John Wright
2015	J	`jnl`	Addition is exponentially harder than counting for shallow monotone circuits. CoRR Xi Chen, Igor C. Oliveira, Rocco A. Servedio
2015	J	`jnl`	Addition is exponentially harder than counting for shallow monotone circuits. Electron. Colloquium Comput. Complex. Xi Chen, Igor Carboni Oliveira, Rocco A. Servedio
2015	A*	`conf`	An Average-Case Depth Hierarchy Theorem for Boolean Circuits. FOCS Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan
2015	J	`jnl`	An average-case depth hierarchy theorem for Boolean circuits. CoRR Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan
2015	J	`jnl`	An average-case depth hierarchy theorem for Boolean circuits. Electron. Colloquium Comput. Complex. Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan
2015	A*	`conf`	Boolean Function Monotonicity Testing Requires (Almost) n STOC Xi Chen, Anindya De, Rocco A. Servedio, Li-Yang Tan
2015	J	`jnl`	Complexity Theory Column 89: The Polynomial Hierarchy, Random Oracles, and Boolean Circuits. SIGACT News Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan
2015	J	`jnl`	Exponentially Improved Algorithms and Lower Bounds for Testing Signed Majorities. Algorithmica Dana Ron, Rocco A. Servedio
2015	—	`conf`	Learning Circuits with few Negations. APPROX-RANDOM Eric Blais, Clément L. Canonne, Igor C. Oliveira, Rocco A. Servedio, Li-Yang Tan
2015	J	`jnl`	Learning Poisson Binomial Distributions. Algorithmica Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio
2015	A*	`conf`	Learning from satisfying assignments. SODA Anindya De, Ilias Diakonikolas, Rocco A. Servedio
2015	J	`jnl`	Near-optimal small-depth lower bounds for small distance connectivity. CoRR Xi Chen, Igor C. Oliveira, Rocco A. Servedio, Li-Yang Tan
2015	J	`jnl`	Noise Stable Halfspaces are Close to Very Small Juntas. Chic. J. Theor. Comput. Sci. Ilias Diakonikolas, Ragesh Jaiswal, Rocco A. Servedio, Li-Yang Tan, Andrew Wan
2015	A*	`ed.`	Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015 STOC Rocco A. Servedio, Ronitt Rubinfeld
2015	J	`jnl`	Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions. CoRR Parikshit Gopalan, Noam Nisan, Rocco A. Servedio, Kunal Talwar, Avi Wigderson
2015	J	`jnl`	Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions. Electron. Colloquium Comput. Complex. Parikshit Gopalan, Noam Nisan, Rocco A. Servedio, Kunal Talwar, Avi Wigderson
2015	J	`jnl`	Testing Probability Distributions using Conditional Samples. SIAM J. Comput. Clément L. Canonne, Dana Ron, Rocco A. Servedio
2014	A*	`conf`	A Polynomial-time Approximation Scheme for Fault-tolerant Distributed Storage. SODA Constantinos Daskalakis, Anindya De, Ilias Diakonikolas, Ankur Moitra, Rocco A. Servedio
2014	J	`jnl`	A Regularity Lemma and Low-Weight Approximators for Low-Degree Polynomial Threshold Functions. Theory Comput. Ilias Diakonikolas, Rocco A. Servedio, Li-Yang Tan, Andrew Wan
2014	J	`jnl`	Average Sensitivity and Noise Sensitivity of Polynomial Threshold Functions. SIAM J. Comput. Ilias Diakonikolas, Prasad Raghavendra, Rocco A. Servedio, Li-Yang Tan
2014	J	`jnl`	Boolean function monotonicity testing requires (almost) n CoRR Xi Chen, Anindya De, Rocco A. Servedio, Li-Yang Tan
2014	A	`conf`	Deterministic Approximate Counting for Juntas of Degree-2 Polynomial Threshold Functions. CCC Anindya De, Ilias Diakonikolas, Rocco A. Servedio
2014	A*	`conf`	Efficient density estimation via piecewise polynomial approximation. STOC Siu On Chan, Ilias Diakonikolas, Rocco A. Servedio, Xiaorui Sun
2014	A*	`conf`	Efficient deterministic approximate counting for low-degree polynomial threshold functions. STOC Anindya De, Rocco A. Servedio
2014	J	`jnl`	Learning Theory Comput. Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio
2014	J	`jnl`	Learning circuits with few negations. CoRR Eric Blais, Clément L. Canonne, Igor C. Oliveira, Rocco A. Servedio, Li-Yang Tan
2014	J	`jnl`	Learning circuits with few negations. Electron. Colloquium Comput. Complex. Eric Blais, Clément L. Canonne, Igor Carboni Oliveira, Rocco A. Servedio, Li-Yang Tan
2014	—	`conf`	Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms. NIPS Siu On Chan, Ilias Diakonikolas, Rocco A. Servedio, Xiaorui Sun
2014	J	`jnl`	Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms. CoRR Siu On Chan, Ilias Diakonikolas, Rocco A. Servedio, Xiaorui Sun
2014	J	`jnl`	Nearly Optimal Solutions for the Chow Parameters Problem and Low-Weight Approximation of Halfspaces. J. ACM Anindya De, Ilias Diakonikolas, Vitaly Feldman, Rocco A. Servedio
2014	A*	`conf`	New Algorithms and Lower Bounds for Monotonicity Testing. FOCS Xi Chen, Rocco A. Servedio, Li-Yang Tan
2014	J	`jnl`	New algorithms and lower bounds for monotonicity testing. CoRR Xi Chen, Rocco A. Servedio, Li-Yang Tan
2014	—	`conf`	On DNF Approximators for Monotone Boolean Functions. ICALP (1) Eric Blais, Johan Håstad, Rocco A. Servedio, Li-Yang Tan
2014	J	`jnl`	On the Weight of Halfspaces over Hamming Balls. SIAM J. Discret. Math. Philip M. Long, Rocco A. Servedio
2014	A*	`conf`	Testing equivalence between distributions using conditional samples. SODA Clément L. Canonne, Dana Ron, Rocco A. Servedio
2013	J	`jnl`	A Polynomial-time Approximation Scheme for Fault-tolerant Distributed Storage. CoRR Constantinos Daskalakis, Anindya De, Ilias Diakonikolas, Ankur Moitra, Rocco A. Servedio
2013	—	`conf`	A Robust Khintchine Inequality, and Algorithms for Computing Optimal Constants in Fourier Analysis and High-Dimensional Geometry. ICALP (1) Anindya De, Ilias Diakonikolas, Rocco A. Servedio
2013	J	`jnl`	Algorithms and hardness results for parallel large margin learning. J. Mach. Learn. Res. Philip M. Long, Rocco A. Servedio
2013	—	`conf`	Consistency versus Realizable H-Consistency for Multiclass Classification. ICML (3) Philip M. Long, Rocco A. Servedio
2013	J	`jnl`	Deterministic Approximate Counting for Degree-$2$ Polynomial Threshold Functions. CoRR Anindya De, Ilias Diakonikolas, Rocco A. Servedio
2013	J	`jnl`	Deterministic Approximate Counting for Degree-2 Polynomial Threshold Functions. Electron. Colloquium Comput. Complex. Anindya De, Ilias Diakonikolas, Rocco A. Servedio
2013	J	`jnl`	Deterministic Approximate Counting for Juntas of Degree-$2$ Polynomial Threshold Functions. CoRR Anindya De, Ilias Diakonikolas, Rocco A. Servedio
2013	J	`jnl`	Deterministic Approximate Counting for Juntas of Degree-2 Polynomial Threshold Functions. Electron. Colloquium Comput. Complex. Anindya De, Ilias Diakonikolas, Rocco A. Servedio
2013	J	`jnl`	Efficient Density Estimation via Piecewise Polynomial Approximation CoRR Siu On Chan, Ilias Diakonikolas, Rocco A. Servedio, Xiaorui Sun
2013	J	`jnl`	Efficient deterministic approximate counting for low degree polynomial threshold functions. Electron. Colloquium Comput. Complex. Anindya De, Rocco A. Servedio
2013	J	`jnl`	Efficient deterministic approximate counting for low-degree polynomial threshold functions. CoRR Anindya De, Rocco A. Servedio
2013	A*	`conf`	Exponentially Improved Algorithms and Lower Bounds for Testing Signed Majorities. SODA Dana Ron, Rocco A. Servedio
2013	J	`jnl`	Exponentially improved algorithms and lower bounds for testing signed majorities. Electron. Colloquium Comput. Complex. Dana Ron, Rocco A. Servedio
2013	J	`jnl`	Improved Approximation of Linear Threshold Functions. Comput. Complex. Ilias Diakonikolas, Rocco A. Servedio
2013	A*	`conf`	Learning Sums of Independent Integer Random Variables. FOCS Constantinos Daskalakis, Ilias Diakonikolas, Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan
2013	A*	`conf`	Learning mixtures of structured distributions over discrete domains. SODA Siu On Chan, Ilias Diakonikolas, Rocco A. Servedio, Xiaorui Sun
2013	A	`conf`	Low-weight halfspaces for sparse boolean vectors. ITCS Philip M. Long, Rocco A. Servedio
2013	A*	`conf`	Testing SODA Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio, Gregory Valiant, Paul Valiant
2012	J	`jnl`	A high-dimensional surprise: technical perspective. Commun. ACM Rocco A. Servedio
2012	J	`jnl`	A robust Khintchine inequality, and algorithms for computing optimal constants in Fourier analysis and high-dimensional geometry. CoRR Anindya De, Ilias Diakonikolas, Rocco A. Servedio
2012	—	`ed.`	Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Cambridge, MA, USA, August 15-17, 2012. Proceedings APPROX-RANDOM Anupam Gupta, Klaus Jansen, José D. P. Rolim, Rocco A. Servedio
2012	J	`jnl`	Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial Threshold Functions. Electron. Colloquium Comput. Complex. Rocco A. Servedio, Li-Yang Tan, Justin Thaler
2012	A*	`conf`	Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial Threshold Functions. COLT Rocco A. Servedio, Li-Yang Tan, Justin Thaler
2012	J	`jnl`	Inverse Problems in Approximate Uniform Generation. Electron. Colloquium Comput. Complex. Anindya De, Ilias Diakonikolas, Rocco A. Servedio
2012	J	`jnl`	Inverse problems in approximate uniform generation CoRR Anindya De, Ilias Diakonikolas, Rocco A. Servedio
2012	A*	`conf`	Learning SODA Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio
2012	J	`jnl`	Learning mixtures of structured distributions over discrete domains CoRR Siu On Chan, Ilias Diakonikolas, Rocco A. Servedio, Xiaorui Sun
2012	A*	`conf`	Learning poisson binomial distributions. STOC Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio
2012	J	`jnl`	Nearly optimal solutions for the Chow Parameters Problem and low-weight approximation of halfspaces CoRR Anindya De, Ilias Diakonikolas, Vitaly Feldman, Rocco A. Servedio
2012	J	`jnl`	Nearly optimal solutions for the Chow Parameters Problem and low-weight approximation of halfspaces. Electron. Colloquium Comput. Complex. Anindya De, Ilias Diakonikolas, Vitaly Feldman, Rocco A. Servedio
2012	A*	`conf`	Nearly optimal solutions for the chow parameters problem and low-weight approximation of halfspaces. STOC Anindya De, Ilias Diakonikolas, Vitaly Feldman, Rocco A. Servedio
2012	J	`jnl`	On a special case of rigidity. Electron. Colloquium Comput. Complex. Rocco A. Servedio, Emanuele Viola
2012	J	`jnl`	On the Distribution of the Fourier Spectrum of Halfspaces CoRR Ilias Diakonikolas, Ragesh Jaiswal, Rocco A. Servedio, Li-Yang Tan, Andrew Wan
2012	A*	`conf`	Private data release via learning thresholds. SODA Moritz Hardt, Guy N. Rothblum, Rocco A. Servedio
2012	J	`jnl`	Special Section on the Forty-First Annual ACM Symposium on Theory of Computing (STOC 2009). SIAM J. Comput. Nicole Immorlica, Jonathan Katz, Michael Mitzenmacher, Rocco A. Servedio, Chris Umans
2012	J	`jnl`	Testing probability distributions using conditional samples CoRR Clément L. Canonne, Dana Ron, Rocco A. Servedio
2012	J	`jnl`	Testing probability distributions using conditional samples. Electron. Colloquium Comput. Complex. Clément L. Canonne, Dana Ron, Rocco A. Servedio
2012	J	`jnl`	The Inverse Shapley Value Problem CoRR Anindya De, Ilias Diakonikolas, Rocco A. Servedio
2012	—	`conf`	The Inverse Shapley Value Problem. ICALP (1) Anindya De, Ilias Diakonikolas, Rocco A. Servedio
2012	J	`jnl`	The Inverse Shapley Value Problem. Electron. Colloquium Comput. Complex. Anindya De, Ilias Diakonikolas, Rocco A. Servedio
2012	A*	`conf`	Tight Bounds on Proper Equivalence Query Learning of DNF. COLT Lisa Hellerstein, Devorah Kletenik, Linda Sellie, Rocco A. Servedio
2011	—	`conf`	A Canonical Form for Testing Boolean Function Properties. APPROX-RANDOM Dana Dachman-Soled, Rocco A. Servedio
2011	—	`conf`	Algorithms and hardness results for parallel large margin learning. NIPS Rocco A. Servedio, Philip M. Long
2011	J	`jnl`	Efficiency versus Convergence of Boolean Kernels for On-Line Learning Algorithms CoRR Roni Khardon, Dan Roth, Rocco A. Servedio
2011	J	`jnl`	Efficiently Testing Sparse Algorithmica Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Rocco A. Servedio, Andrew Wan
2011	A*	`conf`	Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions. SODA Ilias Diakonikolas, Ryan O'Donnell, Rocco A. Servedio, Yi Wu
2011	J	`jnl`	Learning $k$-Modal Distributions via Testing CoRR Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio
2011	J	`jnl`	Learning Poisson Binomial Distributions CoRR Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio
2011	—	`conf`	Learning large-margin halfspaces with more malicious noise. NIPS Philip M. Long, Rocco A. Servedio
2011	J	`jnl`	Learning random monotone DNF. Discret. Appl. Math. Jeffrey C. Jackson, Homin K. Lee, Rocco A. Servedio, Andrew Wan
2011	J	`jnl`	Learning transformed product distributions CoRR Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio
2011	A*	`conf`	Lower Bounds and Hardness Amplification for Learning Shallow Monotone Formulas. COLT Vitaly Feldman, Homin K. Lee, Rocco A. Servedio
2011	J	`jnl`	Private Data Release via Learning Thresholds CoRR Moritz Hardt, Guy N. Rothblum, Rocco A. Servedio
2011	J	`jnl`	Testing $k$-Modal Distributions: Optimal Algorithms via Reductions CoRR Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio, Gregory Valiant, Paul Valiant
2011	J	`jnl`	Testing Fourier Dimensionality and Sparsity. SIAM J. Comput. Parikshit Gopalan, Ryan O'Donnell, Rocco A. Servedio, Amir Shpilka, Karl Wimmer
2011	J	`jnl`	The Chow Parameters Problem. SIAM J. Comput. Ryan O'Donnell, Rocco A. Servedio
2011	J	`jnl`	Tight Bounds on Proper Equivalence Query Learning of DNF CoRR Lisa Hellerstein, Devorah Kletenik, Linda Sellie, Rocco A. Servedio
2010	A	`conf`	A Regularity Lemma, and Low-Weight Approximators, for Low-Degree Polynomial Threshold Functions. CCC Ilias Diakonikolas, Rocco A. Servedio, Li-Yang Tan, Andrew Wan
2010	J	`jnl`	Bounded Independence Fools Halfspaces. SIAM J. Comput. Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A. Servedio, Emanuele Viola
2010	A*	`conf`	Bounding the average sensitivity and noise sensitivity of polynomial threshold functions. STOC Ilias Diakonikolas, Prahladh Harsha, Adam R. Klivans, Raghu Meka, Prasad Raghavendra, Rocco A. Servedio, Li-Yang Tan
2010	J	`jnl`	Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions CoRR Ilias Diakonikolas, Ryan O'Donnell, Rocco A. Servedio, Yi Wu
2010	—	`conf`	Learning and Lower Bounds for AC APPROX-RANDOM Parikshit Gopalan, Rocco A. Servedio
2010	J	`jnl`	Learning and Lower Bounds for AC Electron. Colloquium Comput. Complex. Parikshit Gopalan, Rocco A. Servedio
2010	J	`jnl`	Lower Bounds and Hardness Amplification for Learning Shallow Monotone Formulas. Electron. Colloquium Comput. Complex. Vitaly Feldman, Homin K. Lee, Rocco A. Servedio
2010	J	`jnl`	New degree bounds for polynomial threshold functions. Comb. Ryan O'Donnell, Rocco A. Servedio
2010	J	`jnl`	Random classification noise defeats all convex potential boosters. Mach. Learn. Philip M. Long, Rocco A. Servedio
2010	A*	`conf`	Restricted Boltzmann Machines are Hard to Approximately Evaluate or Simulate. ICML Philip M. Long, Rocco A. Servedio
2010	—	`ch.`	Testing (Subclasses of) Halfspaces. Property Testing Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio
2010	J	`jnl`	Testing Halfspaces. SIAM J. Comput. Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio
2010	—	`ch.`	Testing by Implicit Learning: A Brief Survey. Property Testing Rocco A. Servedio
2009	J	`jnl`	A regularity lemma, and low-weight approximators, for low-degree polynomial threshold functions CoRR Ilias Diakonikolas, Rocco A. Servedio, Li-Yang Tan, Andrew Wan
2009	J	`jnl`	Average sensitivity and noise sensitivity of polynomial threshold functions CoRR Ilias Diakonikolas, Prasad Raghavendra, Rocco A. Servedio, Li-Yang Tan
2009	J	`jnl`	Bounded Independence Fools Halfspaces CoRR Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A. Servedio, Emanuele Viola
2009	A*	`conf`	Bounded Independence Fools Halfspaces. FOCS Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A. Servedio, Emanuele Viola
2009	J	`jnl`	Bounded Independence Fools Halfspaces. Electron. Colloquium Comput. Complex. Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A. Servedio, Emanuele Viola
2009	J	`jnl`	Distribution-Free Testing Lower Bound for Basic Boolean Functions. Theory Comput. Dana Glasner, Rocco A. Servedio
2009	J	`jnl`	Improved Approximation of Linear Threshold Functions CoRR Ilias Diakonikolas, Rocco A. Servedio
2009	A	`conf`	Improved Approximation of Linear Threshold Functions. CCC Ilias Diakonikolas, Rocco A. Servedio
2009	—	`conf`	Learning Halfspaces with Malicious Noise. ICALP (1) Adam R. Klivans, Philip M. Long, Rocco A. Servedio
2009	J	`jnl`	Learning Halfspaces with Malicious Noise. J. Mach. Learn. Res. Adam R. Klivans, Philip M. Long, Rocco A. Servedio
2009	J	`jnl`	Optimal Cryptographic Hardness of Learning Monotone Functions. Theory Comput. Dana Dachman-Soled, Homin K. Lee, Tal Malkin, Rocco A. Servedio, Andrew Wan, Hoeteck Wee
2009	J	`jnl`	Preface. Theor. Comput. Sci. Marcus Hutter, Rocco A. Servedio
2009	—	`conf`	Testing Fourier Dimensionality and Sparsity. ICALP (1) Parikshit Gopalan, Ryan O'Donnell, Rocco A. Servedio, Amir Shpilka, Karl Wimmer
2009	A*	`conf`	Testing halfspaces. SODA Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio
2009	J	`jnl`	Testing monotone high-dimensional distributions. Random Struct. Algorithms Ronitt Rubinfeld, Rocco A. Servedio
2009	—	`conf`	Testing ±1-weight halfspace. APPROX-RANDOM Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio
2008	A*	`ed.`	21st Annual Conference on Learning Theory - COLT 2008, Helsinki, Finland, July 9-12, 2008 COLT Rocco A. Servedio, Tong Zhang
2008	—	`conf`	Adaptive Martingale Boosting. NIPS Philip M. Long, Rocco A. Servedio
2008	J	`jnl`	Agnostically Learning Halfspaces. SIAM J. Comput. Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour, Rocco A. Servedio
2008	J	`jnl`	Efficiently Testing Sparse GF(2) Polynomials CoRR Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Rocco A. Servedio, Andrew Wan
2008	—	`conf`	Efficiently Testing Sparse GF(2) Polynomials. ICALP (1) Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Rocco A. Servedio, Andrew Wan
2008	J	`jnl`	Extremal properties of polynomial threshold functions. J. Comput. Syst. Sci. Ryan O'Donnell, Rocco A. Servedio
2008	—	`ch.`	Learning Constant-Depth Circuits. Encyclopedia of Algorithms Rocco A. Servedio
2008	A*	`conf`	Learning Geometric Concepts via Gaussian Surface Area. FOCS Adam R. Klivans, Ryan O'Donnell, Rocco A. Servedio
2008	J	`jnl`	Learning Mixtures of Product Distributions over Discrete Domains. SIAM J. Comput. Jon Feldman, Ryan O'Donnell, Rocco A. Servedio
2008	—	`conf`	Learning Random Monotone DNF. APPROX-RANDOM Jeffrey C. Jackson, Homin K. Lee, Rocco A. Servedio, Andrew Wan
2008	J	`jnl`	Learning intersections of halfspaces with a margin. J. Comput. Syst. Sci. Adam R. Klivans, Rocco A. Servedio
2008	J	`jnl`	Learning unions of omega(1)-dimensional rectangles. Theor. Comput. Sci. Alp Atici, Rocco A. Servedio
2008	—	`conf`	Optimal Cryptographic Hardness of Learning Monotone Functions. ICALP (1) Dana Dachman-Soled, Homin K. Lee, Tal Malkin, Rocco A. Servedio, Andrew Wan, Hoeteck Wee
2008	A*	`conf`	Random classification noise defeats all convex potential boosters. ICML Philip M. Long, Rocco A. Servedio
2008	A*	`conf`	The chow parameters problem. STOC Ryan O'Donnell, Rocco A. Servedio
2007	B	`ed.`	Algorithmic Learning Theory, 18th International Conference, ALT 2007, Sendai, Japan, October 1-4, 2007, Proceedings ALT Marcus Hutter, Rocco A. Servedio, Eiji Takimoto
2007	—	`conf`	Boosting the Area under the ROC Curve. NIPS Philip M. Long, Rocco A. Servedio
2007	J	`jnl`	DNF are teachable in the average case. Mach. Learn. Homin K. Lee, Rocco A. Servedio, Andrew Wan
2007	J	`jnl`	Discriminative learning can succeed where generative learning fails. Inf. Process. Lett. Philip M. Long, Rocco A. Servedio, Hans Ulrich Simon
2007	—	`conf`	Distribution-Free Testing Lower Bounds for Basic Boolean Functions. APPROX-RANDOM Dana Glasner, Rocco A. Servedio
2007	B	`conf`	Editors' Introduction. ALT Marcus Hutter, Rocco A. Servedio, Eiji Takimoto
2007	J	`jnl`	Every Linear Threshold Function has a Low-Weight Approximator. Comput. Complex. Rocco A. Servedio
2007	A*	`conf`	Highly Efficient Secrecy-Preserving Proofs of Correctness of Computations and Applications. LICS Michael O. Rabin, Rocco A. Servedio, Christopher Thorpe
2007	J	`jnl`	LP Decoding Corrects a Constant Fraction of Errors. IEEE Trans. Inf. Theory Jon Feldman, Tal Malkin, Rocco A. Servedio, Clifford Stein, Martin J. Wainwright
2007	J	`jnl`	Learning Monotone Decision Trees in Polynomial Time. SIAM J. Comput. Ryan O'Donnell, Rocco A. Servedio
2007	J	`jnl`	Learning Random Monotone DNF. Electron. Colloquium Comput. Complex. Jeffrey C. Jackson, Homin K. Lee, Rocco A. Servedio, Andrew Wan
2007	J	`jnl`	On PAC learning algorithms for rich Boolean function classes. Theor. Comput. Sci. Lisa Hellerstein, Rocco A. Servedio
2007	—	`conf`	One-Pass Boosting. NIPS Zafer Barutçuoglu, Philip M. Long, Rocco A. Servedio
2007	J	`jnl`	Quantum Algorithms for Learning and Testing Juntas CoRR Alp Atici, Rocco A. Servedio
2007	J	`jnl`	Quantum Algorithms for Learning and Testing Juntas. Quantum Inf. Process. Alp Atici, Rocco A. Servedio
2007	J	`jnl`	Separating Models of Learning from Correlated and Uncorrelated Data. J. Mach. Learn. Res. Ariel Elbaz, Homin K. Lee, Rocco A. Servedio, Andrew Wan
2007	J	`jnl`	Testing Halfspaces. Electron. Colloquium Comput. Complex. Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio
2007	A*	`conf`	Testing for Concise Representations. FOCS Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A. Servedio, Andrew Wan
2007	J	`jnl`	Testing for Concise Representations. Electron. Colloquium Comput. Complex. Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A. Servedio, Andrew Wan
2006	—	`conf`	Attribute-efficient learning of decision lists and linear threshold functions under unconcentrated distributions. NIPS Philip M. Long, Rocco A. Servedio
2006	A*	`conf`	DNF Are Teachable in the Average Case. COLT Homin K. Lee, Rocco A. Servedio, Andrew Wan
2006	A*	`conf`	Discriminative Learning Can Succeed Where Generative Learning Fails. COLT Philip M. Long, Rocco A. Servedio
2006	A	`conf`	Every Linear Threshold Function has a Low-Weight Approximator. CCC Rocco A. Servedio
2006	A	`conf`	Learning Monotone Decision Trees in Polynomial Time. CCC Ryan O'Donnell, Rocco A. Servedio
2006	B	`conf`	Learning Unions of ALT Alp Atici, Rocco A. Servedio
2006	J	`jnl`	On Learning Random DNF Formulas Under the Uniform Distribution. Theory Comput. Jeffrey C. Jackson, Rocco A. Servedio
2006	C	`conf`	On PAC Learning Algorithms for Rich Boolean Function Classes. TAMC Rocco A. Servedio
2006	J	`jnl`	On learning embedded midbit functions. Theor. Comput. Sci. Rocco A. Servedio
2006	A*	`conf`	PAC Learning Axis-Aligned Mixtures of Gaussians with No Separation Assumption. COLT Jon Feldman, Rocco A. Servedio, Ryan O'Donnell
2006	J	`jnl`	PAC Learning Mixtures of Axis-Aligned Gaussians with No Separation Assumption CoRR Jon Feldman, Ryan O'Donnell, Rocco A. Servedio
2006	J	`jnl`	Polynomial certificates for propositional classes. Inf. Comput. Marta Arias, Aaron Feigelson, Roni Khardon, Rocco A. Servedio
2006	J	`jnl`	Toward Attribute Efficient Learning of Decision Lists and Parities. J. Mach. Learn. Res. Adam R. Klivans, Rocco A. Servedio
2005	A*	`conf`	Agnostically Learning Halfspaces. FOCS Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour, Rocco A. Servedio
2005	J	`jnl`	Boosting in the presence of noise. J. Comput. Syst. Sci. Adam Tauman Kalai, Rocco A. Servedio
2005	J	`jnl`	Computing sparse permanents faster. Inf. Process. Lett. Rocco A. Servedio, Andrew Wan
2005	J	`jnl`	Efficiency versus Convergence of Boolean Kernels for On-Line Learning Algorithms. J. Artif. Intell. Res. Roni Khardon, Dan Roth, Rocco A. Servedio
2005	A*	`conf`	Every decision tree has an in.uential variable. FOCS Ryan O'Donnell, Michael E. Saks, Oded Schramm, Rocco A. Servedio
2005	J	`jnl`	Every decision tree has an influential variable CoRR Ryan O'Donnell, Michael E. Saks, Oded Schramm, Rocco A. Servedio
2005	J	`jnl`	Improved Bounds on Quantum Learning Algorithms. Quantum Inf. Process. Alp Atici, Rocco A. Servedio
2005	J	`jnl`	Learning DNF from random walks. J. Comput. Syst. Sci. Nader H. Bshouty, Elchanan Mossel, Ryan O'Donnell, Rocco A. Servedio
2005	J	`jnl`	Learning Random Log-Depth Decision Trees under Uniform Distribution. SIAM J. Comput. Jeffrey C. Jackson, Rocco A. Servedio
2005	J	`jnl`	Learning Unions of $\omega(1)$-Dimensional Rectangles CoRR Alp Atici, Rocco A. Servedio
2005	A*	`conf`	Learning mixtures of product distributions over discrete domains. FOCS Jon Feldman, Ryan O'Donnell, Rocco A. Servedio
2005	A*	`conf`	Martingale Boosting. COLT Philip M. Long, Rocco A. Servedio
2005	J	`jnl`	Maximum Margin Algorithms with Boolean Kernels. J. Mach. Learn. Res. Roni Khardon, Rocco A. Servedio
2005	—	`conf`	On Learning Random DNF Formulas Under the Uniform Distribution. APPROX-RANDOM Jeffrey C. Jackson, Rocco A. Servedio
2005	A*	`conf`	Separating Models of Learning from Correlated and Uncorrelated Data. COLT Ariel Elbaz, Homin K. Lee, Rocco A. Servedio, Andrew Wan
2005	A*	`conf`	Testing monotone high-dimensional distributions. STOC Ronitt Rubinfeld, Rocco A. Servedio
2005	A*	`conf`	Unsupervised evidence integration. ICML Philip M. Long, Vinay Varadan, Sarah Gilman, Mark Treshock, Rocco A. Servedio
2004	J	`jnl`	Equivalences and Separations Between Quantum and Classical Learnability. SIAM J. Comput. Rocco A. Servedio, Steven J. Gortler
2004	J	`jnl`	Improved Bounds on Quantum Learning Algorithms CoRR Alp Atici, Rocco A. Servedio
2004	B	`conf`	LP decoding corrects a constant fraction of errors. ISIT Jon Feldman, Tal Malkin, Rocco A. Servedio, Cliff Stein, Martin J. Wainwright
2004	J	`jnl`	Learning DNF in time 2 J. Comput. Syst. Sci. Adam R. Klivans, Rocco A. Servedio
2004	A*	`conf`	Learning Intersections of Halfspaces with a Margin. COLT Adam R. Klivans, Rocco A. Servedio
2004	J	`jnl`	Learning functions of k relevant variables. J. Comput. Syst. Sci. Elchanan Mossel, Ryan O'Donnell, Rocco A. Servedio
2004	J	`jnl`	Learning intersections and thresholds of halfspaces. J. Comput. Syst. Sci. Adam R. Klivans, Ryan O'Donnell, Rocco A. Servedio
2004	J	`jnl`	Monotone Boolean formulas can approximate monotone linear threshold functions. Discret. Appl. Math. Rocco A. Servedio
2004	J	`jnl`	On learning monotone DNF under product distributions. Inf. Comput. Rocco A. Servedio
2004	A*	`conf`	Perceptron-Like Performance for Intersections of Halfspaces. COLT Adam R. Klivans, Rocco A. Servedio
2004	A*	`conf`	Toward Attribute Efficient Learning of Decision Lists and Parities. COLT Adam R. Klivans, Rocco A. Servedio
2003	J	`jnl`	Boosting and Hard-Core Set Construction. Mach. Learn. Adam R. Klivans, Rocco A. Servedio
2003	A*	`conf`	Boosting in the presence of noise. STOC Adam Kalai, Rocco A. Servedio
2003	A	`conf`	Extremal properties of polynomial threshold functions. CCC Ryan O'Donnell, Rocco A. Servedio
2003	A*	`conf`	Learning DNF from Random Walks. FOCS Nader H. Bshouty, Elchanan Mossel, Ryan O'Donnell, Rocco A. Servedio
2003	A*	`conf`	Learning Random Log-Depth Decision Trees under the Uniform Distribution. COLT Jeffrey C. Jackson, Rocco A. Servedio
2003	A*	`conf`	Learning juntas. STOC Elchanan Mossel, Ryan O'Donnell, Rocco A. Servedio
2003	A*	`conf`	Maximum Margin Algorithms with Boolean Kernels. COLT Roni Khardon, Rocco A. Servedio
2003	A*	`conf`	New degree bounds for polynomial threshold functions. STOC Ryan O'Donnell, Rocco A. Servedio
2003	A*	`conf`	Polynomial Certificates for Propositional Classes. COLT Marta Arias, Roni Khardon, Rocco A. Servedio
2003	J	`jnl`	Smooth Boosting and Learning with Malicious Noise. J. Mach. Learn. Res. Rocco A. Servedio
2003	J	`jnl`	Toward Attribute Efficient Learning Algorithms CoRR Adam R. Klivans, Rocco A. Servedio
2002	A	`conf`	Learnability beyond AC0. CCC Jeffrey C. Jackson, Adam R. Klivans, Rocco A. Servedio
2002	A*	`conf`	Learnability beyond AC0. STOC Jeffrey C. Jackson, Adam R. Klivans, Rocco A. Servedio
2002	A*	`conf`	Learning Intersections and Thresholds of Halfspaces. FOCS Adam R. Klivans, Ryan O'Donnell, Rocco A. Servedio
2002	B	`conf`	On Learning Embedded Midbit Functions. ALT Rocco A. Servedio
2002	J	`jnl`	PAC Analogues of Perceptron and Winnow Via Boosting the Margin. Mach. Learn. Rocco A. Servedio
2002	J	`jnl`	Perceptron, Winnow, and PAC Learning. SIAM J. Comput. Rocco A. Servedio
2001	—	`conf`	Efficiency versus Convergence of Boolean Kernels for On-Line Learning Algorithms. NIPS Roni Khardon, Dan Roth, Rocco A. Servedio
2001	A*	`conf`	Learning DNF in time 2 STOC Adam R. Klivans, Rocco A. Servedio
2001	J	`jnl`	On Learning Monotone DNF under Product Distributions Electron. Colloquium Comput. Complex. Rocco A. Servedio
2001	—	`conf`	On Learning Monotone DNF under Product Distributions. COLT/EuroCOLT Rocco A. Servedio
2001	J	`jnl`	On the limits of efficient teachability. Inf. Process. Lett. Rocco A. Servedio
2001	A	`conf`	Quantum versus Classical Learnability. CCC Rocco A. Servedio, Steven J. Gortler
2001	A*	`conf`	Separating Quantum and Classical Learning. ICALP Rocco A. Servedio
2001	—	`conf`	Smooth Boosting and Learning with Malicious Noise. COLT/EuroCOLT Rocco A. Servedio
2000	J	`jnl`	Computational Sample Complexity and Attribute-Efficient Learning. J. Comput. Syst. Sci. Rocco A. Servedio
2000	A*	`conf`	PAC Analogues of Perceptron and Winnow via Boosting the Margin. COLT Rocco A. Servedio
1999	A*	`conf`	Boosting and Hard-Core Sets. FOCS Adam R. Klivans, Rocco A. Servedio
1999	A*	`conf`	Computational Sample Complexity and Attribute-Efficient Learning. STOC Rocco A. Servedio
1999	A*	`conf`	On PAC Learning Using Winnow, Perceptron, and a Perceptron-like Algorithm. COLT Rocco A. Servedio