Rocco A. Servedio

According to our database, Rocco A. Servedio authored at least 190 papers between 1999 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2024

Testing Sumsets is Hard.

Xi Chen, Shivam Nadimpalli, Tim Randolph, Rocco A. Servedio, Or Zamir

CoRR, 2024

Detecting Low-Degree Truncation.

Anindya De, Huan Li, Shivam Nadimpalli, Rocco A. Servedio

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity, Unateness, and Juntas.

Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Testing Intersecting and Union-Closed Families.

Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

Trace Reconstruction from Local Statistical Queries.

Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio

Proceedings of the Approximation, 2024

2023

Gaussian Approximation of Convex Sets by Intersections of Halfspaces.

Anindya De, Shivam Nadimpalli, Rocco A. Servedio

CoRR, 2023

Testing Convex Truncation.

Anindya De, Shivam Nadimpalli, Rocco A. Servedio

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Approximate Trace Reconstruction from a Single Trace.

Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Explicit orthogonal and unitary designs.

Ryan O'Donnell, Rocco A. Servedio, Pedro Paredes

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Subset Sum in Time 2^n/2 / poly(n).

Xi Chen, Yaonan Jin, Tim Randolph, Rocco A. Servedio

Proceedings of the Approximation, 2023

2022

Improved Pseudorandom Generators from Pseudorandom Multi-switching Lemmas.

Rocco A. Servedio, Li-Yang Tan

Theory Comput., 2022

A Lower Bound on Cycle-Finding in Sparse Digraphs.

Xi Chen, Tim Randolph, Rocco A. Servedio, Timothy Sun

ACM Trans. Algorithms, 2022

The Perils of Being Unhinged: On the Accuracy of Classifiers Minimizing a Noise-Robust Convex Loss.

Philip M. Long, Rocco A. Servedio

Neural Comput., 2022

Approximating Sumset Size.

Anindya De, Shivam Nadimpalli, Rocco A. Servedio

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Average-Case Subset Balancing Problems.

Xi Chen, Yaonan Jin, Tim Randolph, Rocco A. Servedio

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces.

Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Convex Influences.

Anindya De, Shivam Nadimpalli, Rocco A. Servedio

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

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

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

2021

Fourier growth of structured 𝔽₂-polynomials and applications.

Jaroslaw Blasiok, Peter Ivanov, Yaonan Jin, Chin Ho Lee, Rocco A. Servedio, Emanuele Viola

Electron. Colloquium Comput. Complex., 2021

Fourier growth of structured $\mathbb{F}_2$-polynomials and applications.

Jaroslaw Blasiok, Peter Ivanov, Yaonan Jin, Chin Ho Lee, Rocco A. Servedio, Emanuele Viola

CoRR, 2021

Fooling Gaussian PTFs via Local Hyperconcentration.

Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan, Daniel Kane

CoRR, 2021

Polynomial-time trace reconstruction in the smoothed complexity model.

Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Quantitative Correlation Inequalities via Semigroup Interpolation.

Anindya De, Shivam Nadimpalli, Rocco A. Servedio

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Polynomial-Time Trace Reconstruction in the Low Deletion Rate Regime.

Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

On the Approximation Power of Two-Layer Networks of Random ReLUs.

Daniel Hsu, Clayton Sanford, Rocco A. Servedio, Emmanouil V. Vlatakis-Gkaragkounis

Proceedings of the Conference on Learning Theory, 2021

Weak learning convex sets under normal distributions.

Anindya De, Rocco A. Servedio

Proceedings of the Conference on Learning Theory, 2021

Learning sparse mixtures of permutations from noisy information.

Anindya De, Ryan O'Donnell, Rocco A. Servedio

Proceedings of the Conference on Learning Theory, 2021

Reconstructing weighted voting schemes from partial information about their power indices.

Huck Bennett, Anindya De, Rocco A. Servedio, Emmanouil-Vasileios Vlatakis-Gkaragkounis

Proceedings of the Conference on Learning Theory, 2021

Deterministic Approximate Counting of Polynomial Threshold Functions via a Derandomized Regularity Lemma.

Rocco A. Servedio, Li-Yang Tan

Proceedings of the Approximation, 2021

2020

Sharp Bounds for Population Recovery.

Anindya De, Ryan O'Donnell, Rocco A. Servedio

Theory Comput., 2020

Fooling Gaussian PTFs via local hyperconcentration.

Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Testing noisy linear functions for sparsity.

Xue Chen, Anindya De, Rocco A. Servedio

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Learning from satisfying assignments under continuous distributions.

Clément L. Canonne, Anindya De, Rocco A. Servedio

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

2019

Distribution-free Junta Testing.

Zhengyang Liu, Xi Chen, Rocco A. Servedio, Ying Sheng, Jinyu Xie

ACM Trans. Algorithms, 2019

Kruskal-Katona for convex sets, with applications.

Anindya De, Rocco A. Servedio

CoRR, 2019

Pseudorandomness for read-k DNF formulas.

Rocco A. Servedio, Li-Yang Tan

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Density Estimation for Shift-Invariant Multidimensional Distributions.

Anindya De, Philip M. Long, Rocco A. Servedio

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Beyond Trace Reconstruction: Population Recovery from the Deletion Channel.

Frank Ban, Xi Chen, Adam Freilich, Rocco A. Servedio, Sandip Sinha

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Efficient Average-Case Population Recovery in the Presence of Insertions and Deletions.

Frank Ban, Xi Chen, Rocco A. Servedio, Sandip Sinha

Proceedings of the Approximation, 2019

2018

Fooling Polytopes.

Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan

Electron. Colloquium Comput. Complex., 2018

Simple and efficient pseudorandom generators from Gaussian processes.

Eshan Chattopadhyay, Anindya De, Rocco A. Servedio

Electron. Colloquium Comput. Complex., 2018

Learning sparse mixtures of rankings from noisy information.

Anindya De, Ryan O'Donnell, Rocco A. Servedio

CoRR, 2018

Learning Sums of Independent Random Variables with Sparse Collective Support.

Anindya De, Philip M. Long, Rocco A. Servedio

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

Luby-Velickovic-Wigderson Revisited: Improved Correlation Bounds and Pseudorandom Generators for Depth-Two Circuits.

Rocco A. Servedio, Li-Yang Tan

Proceedings of the Approximation, 2018

2017

An Average-Case Depth Hierarchy Theorem for Boolean Circuits.

Johan Håstad, Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan

J. ACM, 2017

Settling the query complexity of non-adaptive junta testing.

Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie

Electron. Colloquium Comput. Complex., 2017

Optimal mean-based algorithms for trace reconstruction.

Anindya De, Ryan O'Donnell, Rocco A. Servedio

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

What Circuit Classes Can Be Learned with Non-Trivial Savings?.

Rocco A. Servedio, Li-Yang Tan

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

Fooling Intersections of Low-Weight Halfspaces.

Rocco A. Servedio, Li-Yang Tan

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Deterministic Search for CNF Satisfying Assignments in Almost Polynomial Time.

Rocco A. Servedio, Li-Yang Tan

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces.

Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten

Proceedings of the Approximation, 2017

Sample-Based High-Dimensional Convexity Testing.

Xi Chen, Adam Freilich, Rocco A. Servedio, Timothy Sun

Proceedings of the Approximation, 2017

2016

A Robust Khintchine Inequality, and Algorithms for Computing Optimal Constants in Fourier Analysis and High-Dimensional Geometry.

Anindya De, Ilias Diakonikolas, Rocco A. Servedio

SIAM J. Discret. Math., 2016

Degree and Sensitivity: tails of two distributions.

Parikshit Gopalan, Rocco A. Servedio, Avishay Tal, Avi Wigderson

Electron. Colloquium Comput. Complex., 2016

Poly-logarithmic Frege depth lower bounds via an expander switching lemma.

Toniann Pitassi, Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Near-optimal small-depth lower bounds for small distance connectivity.

Xi Chen, Igor C. Oliveira, Rocco A. Servedio, Li-Yang Tan

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Degree and Sensitivity: Tails of Two Distributions.

Parikshit Gopalan, Rocco A. Servedio, Avi Wigderson

Proceedings of the 31st Conference on Computational Complexity, 2016

2015

Complexity Theory Column 89: The Polynomial Hierarchy, Random Oracles, and Boolean Circuits.

Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan

SIGACT News, 2015

Testing Probability Distributions using Conditional Samples.

Clément L. Canonne, Dana Ron, Rocco A. Servedio

SIAM J. Comput., 2015

An average-case depth hierarchy theorem for Boolean circuits.

Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan

Electron. Colloquium Comput. Complex., 2015

Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions.

Parikshit Gopalan, Noam Nisan, Rocco A. Servedio, Kunal Talwar, Avi Wigderson

Electron. Colloquium Comput. Complex., 2015

Addition is exponentially harder than counting for shallow monotone circuits.

Xi Chen, Igor Carboni Oliveira, Rocco A. Servedio

Electron. Colloquium Comput. Complex., 2015

Noise Stable Halfspaces are Close to Very Small Juntas.

Ilias Diakonikolas, Ragesh Jaiswal, Rocco A. Servedio, Li-Yang Tan, Andrew Wan

Chic. J. Theor. Comput. Sci., 2015

Learning Poisson Binomial Distributions.

Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio

Algorithmica, 2015

Boolean Function Monotonicity Testing Requires (Almost) n^1/2 Non-adaptive Queries.

Xi Chen, Anindya De, Rocco A. Servedio, Li-Yang Tan

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Learning from satisfying assignments.

Anindya De, Ilias Diakonikolas, Rocco A. Servedio

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Adaptivity Helps for Testing Juntas.

Rocco A. Servedio, Li-Yang Tan, John Wright

Proceedings of the 30th Conference on Computational Complexity, 2015

2014

A Regularity Lemma and Low-Weight Approximators for Low-Degree Polynomial Threshold Functions.

Ilias Diakonikolas, Rocco A. Servedio, Li-Yang Tan, Andrew Wan

Theory Comput., 2014

Learning <i>k</i>-Modal Distributions via Testing.

Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio

Theory Comput., 2014

On the Weight of Halfspaces over Hamming Balls.

Philip M. Long, Rocco A. Servedio

SIAM J. Discret. Math., 2014

Average Sensitivity and Noise Sensitivity of Polynomial Threshold Functions.

Ilias Diakonikolas, Prasad Raghavendra, Rocco A. Servedio, Li-Yang Tan

SIAM J. Comput., 2014

Learning circuits with few negations.

Eric Blais, Clément L. Canonne, Igor Carboni Oliveira, Rocco A. Servedio, Li-Yang Tan

Electron. Colloquium Comput. Complex., 2014

Efficient density estimation via piecewise polynomial approximation.

Siu On Chan, Ilias Diakonikolas, Rocco A. Servedio, Xiaorui Sun

Proceedings of the Symposium on Theory of Computing, 2014

A Polynomial-time Approximation Scheme for Fault-tolerant Distributed Storage.

Constantinos Daskalakis, Anindya De, Ilias Diakonikolas, Ankur Moitra, Rocco A. Servedio

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Testing equivalence between distributions using conditional samples.

Clément L. Canonne, Dana Ron, Rocco A. Servedio

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms.

Siu On Chan, Ilias Diakonikolas, Rocco A. Servedio, Xiaorui Sun

Proceedings of the Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, 2014

On DNF Approximators for Monotone Boolean Functions.

Eric Blais, Johan Håstad, Rocco A. Servedio, Li-Yang Tan

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

New Algorithms and Lower Bounds for Monotonicity Testing.

Xi Chen, Rocco A. Servedio, Li-Yang Tan

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013

Algorithms and hardness results for parallel large margin learning.

Philip M. Long, Rocco A. Servedio

J. Mach. Learn. Res., 2013

Exponentially improved algorithms and lower bounds for testing signed majorities.

Dana Ron, Rocco A. Servedio

Electron. Colloquium Comput. Complex., 2013

Efficient deterministic approximate counting for low degree polynomial threshold functions.

Anindya De, Rocco A. Servedio

Electron. Colloquium Comput. Complex., 2013

Deterministic Approximate Counting for Degree-2 Polynomial Threshold Functions.

Anindya De, Ilias Diakonikolas, Rocco A. Servedio

Electron. Colloquium Comput. Complex., 2013

Deterministic Approximate Counting for Juntas of Degree-2 Polynomial Threshold Functions.

Anindya De, Ilias Diakonikolas, Rocco A. Servedio

Electron. Colloquium Comput. Complex., 2013

Improved Approximation of Linear Threshold Functions.

Ilias Diakonikolas, Rocco A. Servedio

Comput. Complex., 2013

Testing <i>k</i>-Modal Distributions: Optimal Algorithms via Reductions.

Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio, Gregory Valiant, Paul Valiant

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Learning mixtures of structured distributions over discrete domains.

Siu On Chan, Ilias Diakonikolas, Rocco A. Servedio, Xiaorui Sun

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Low-weight halfspaces for sparse boolean vectors.

Philip M. Long, Rocco A. Servedio

Proceedings of the Innovations in Theoretical Computer Science, 2013

Consistency versus Realizable H-Consistency for Multiclass Classification.

Philip M. Long, Rocco A. Servedio

Proceedings of the 30th International Conference on Machine Learning, 2013

Learning Sums of Independent Integer Random Variables.

Constantinos Daskalakis, Ilias Diakonikolas, Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012

Special Section on the Forty-First Annual ACM Symposium on Theory of Computing (STOC 2009).

Nicole Immorlica, Jonathan Katz, Michael Mitzenmacher, Rocco A. Servedio, Chris Umans

SIAM J. Comput., 2012

Tight Bounds on Proper Equivalence Query Learning of DNF.

Lisa Hellerstein, Devorah Kletenik, Linda Sellie, Rocco A. Servedio

Proceedings of the COLT 2012, 2012

On a special case of rigidity.

Rocco A. Servedio, Emanuele Viola

Electron. Colloquium Comput. Complex., 2012

Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial Threshold Functions.

Rocco A. Servedio, Li-Yang Tan, Justin Thaler

Electron. Colloquium Comput. Complex., 2012

The Inverse Shapley Value Problem.

Anindya De, Ilias Diakonikolas, Rocco A. Servedio

Electron. Colloquium Comput. Complex., 2012

Inverse Problems in Approximate Uniform Generation.

Anindya De, Ilias Diakonikolas, Rocco A. Servedio

Electron. Colloquium Comput. Complex., 2012

Nearly optimal solutions for the Chow Parameters Problem and low-weight approximation of halfspaces.

Anindya De, Ilias Diakonikolas, Vitaly Feldman, Rocco A. Servedio

Electron. Colloquium Comput. Complex., 2012

On the Distribution of the Fourier Spectrum of Halfspaces

Ilias Diakonikolas, Ragesh Jaiswal, Rocco A. Servedio, Li-Yang Tan, Andrew Wan

CoRR, 2012

A high-dimensional surprise: technical perspective.

Rocco A. Servedio

Commun. ACM, 2012

Private data release via learning thresholds.

Moritz Hardt, Guy N. Rothblum, Rocco A. Servedio

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

2011

The Chow Parameters Problem.

Ryan O'Donnell, Rocco A. Servedio

SIAM J. Comput., 2011

Testing Fourier Dimensionality and Sparsity.

Parikshit Gopalan, Ryan O'Donnell, Rocco A. Servedio, Amir Shpilka, Karl Wimmer

SIAM J. Comput., 2011

Learning random monotone DNF.

Jeffrey C. Jackson, Homin K. Lee, Rocco A. Servedio, Andrew Wan

Discret. Appl. Math., 2011

Testing $k$-Modal Distributions: Optimal Algorithms via Reductions

Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio, Gregory Valiant, Paul Valiant

CoRR, 2011

Learning $k$-Modal Distributions via Testing

Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio

CoRR, 2011

Learning transformed product distributions

Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio

CoRR, 2011

Efficiently Testing Sparse <i>GF</i>(2) Polynomials.

Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Rocco A. Servedio, Andrew Wan

Algorithmica, 2011

Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions.

Ilias Diakonikolas, Ryan O'Donnell, Rocco A. Servedio, Yi Wu

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Learning large-margin halfspaces with more malicious noise.

Philip M. Long, Rocco A. Servedio

Proceedings of the Advances in Neural Information Processing Systems 24: 25th Annual Conference on Neural Information Processing Systems 2011. Proceedings of a meeting held 12-14 December 2011, 2011

A Canonical Form for Testing Boolean Function Properties.

Dana Dachman-Soled, Rocco A. Servedio

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

Testing Halfspaces.

Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio

SIAM J. Comput., 2010

Bounded Independence Fools Halfspaces.

Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A. Servedio, Emanuele Viola

SIAM J. Comput., 2010

Random classification noise defeats all convex potential boosters.

Philip M. Long, Rocco A. Servedio

Mach. Learn., 2010

Learning and Lower Bounds for AC⁰ with Threshold Gates.

Parikshit Gopalan, Rocco A. Servedio

Electron. Colloquium Comput. Complex., 2010

Lower Bounds and Hardness Amplification for Learning Shallow Monotone Formulas.

Vitaly Feldman, Homin K. Lee, Rocco A. Servedio

Electron. Colloquium Comput. Complex., 2010

New degree bounds for polynomial threshold functions.

Ryan O'Donnell, Rocco A. Servedio

Comb., 2010

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

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Testing by Implicit Learning: A Brief Survey.

Rocco A. Servedio

Proceedings of the Property Testing - Current Research and Surveys, 2010

Testing (Subclasses of) Halfspaces.

Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio

Proceedings of the Property Testing - Current Research and Surveys, 2010

Restricted Boltzmann Machines are Hard to Approximately Evaluate or Simulate.

Philip M. Long, Rocco A. Servedio

Proceedings of the 27th International Conference on Machine Learning (ICML-10), 2010

2009

Distribution-Free Testing Lower Bound for Basic Boolean Functions.

Dana Glasner, Rocco A. Servedio

Theory Comput., 2009

Optimal Cryptographic Hardness of Learning Monotone Functions.

Dana Dachman-Soled, Homin K. Lee, Tal Malkin, Rocco A. Servedio, Andrew Wan, Hoeteck Wee

Theory Comput., 2009

Preface.

Marcus Hutter, Rocco A. Servedio

Theor. Comput. Sci., 2009

Testing monotone high-dimensional distributions.

Ronitt Rubinfeld, Rocco A. Servedio

Random Struct. Algorithms, 2009

Learning Halfspaces with Malicious Noise.

Adam R. Klivans, Philip M. Long, Rocco A. Servedio

J. Mach. Learn. Res., 2009

Testing ±1-weight halfspace.

Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio

Proceedings of the Approximation, 2009

2008

Learning Constant-Depth Circuits.

Rocco A. Servedio

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Learning unions of omega(1)-dimensional rectangles.

Alp Atici, Rocco A. Servedio

Theor. Comput. Sci., 2008

Agnostically Learning Halfspaces.

Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour, Rocco A. Servedio

SIAM J. Comput., 2008

Learning Mixtures of Product Distributions over Discrete Domains.

Jon Feldman, Ryan O'Donnell, Rocco A. Servedio

SIAM J. Comput., 2008

Extremal properties of polynomial threshold functions.

Ryan O'Donnell, Rocco A. Servedio

J. Comput. Syst. Sci., 2008

Learning intersections of halfspaces with a margin.

Adam R. Klivans, Rocco A. Servedio

J. Comput. Syst. Sci., 2008

Adaptive Martingale Boosting.

Philip M. Long, Rocco A. Servedio

Proceedings of the Advances in Neural Information Processing Systems 21, 2008

Efficiently Testing Sparse GF(2) Polynomials.

Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Rocco A. Servedio, Andrew Wan

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

Learning Geometric Concepts via Gaussian Surface Area.

Adam R. Klivans, Ryan O'Donnell, Rocco A. Servedio

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007

LP Decoding Corrects a Constant Fraction of Errors.

Jon Feldman, Tal Malkin, Rocco A. Servedio, Clifford Stein, Martin J. Wainwright

IEEE Trans. Inf. Theory, 2007

On PAC learning algorithms for rich Boolean function classes.

Lisa Hellerstein, Rocco A. Servedio

Theor. Comput. Sci., 2007

Learning Monotone Decision Trees in Polynomial Time.

Ryan O'Donnell, Rocco A. Servedio

SIAM J. Comput., 2007

Quantum Algorithms for Learning and Testing Juntas.

Alp Atici, Rocco A. Servedio

Quantum Inf. Process., 2007

DNF are teachable in the average case.

Homin K. Lee, Rocco A. Servedio, Andrew Wan

Mach. Learn., 2007

Separating Models of Learning from Correlated and Uncorrelated Data.

Ariel Elbaz, Homin K. Lee, Rocco A. Servedio, Andrew Wan

J. Mach. Learn. Res., 2007

Discriminative learning can succeed where generative learning fails.

Philip M. Long, Rocco A. Servedio, Hans Ulrich Simon

Inf. Process. Lett., 2007

Testing for Concise Representations.

Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A. Servedio, Andrew Wan

Electron. Colloquium Comput. Complex., 2007

Every Linear Threshold Function has a Low-Weight Approximator.

Rocco A. Servedio

Comput. Complex., 2007

Boosting the Area under the ROC Curve.

Philip M. Long, Rocco A. Servedio

Proceedings of the Advances in Neural Information Processing Systems 20, 2007

One-Pass Boosting.

Zafer Barutçuoglu, Philip M. Long, Rocco A. Servedio

Proceedings of the Advances in Neural Information Processing Systems 20, 2007

Highly Efficient Secrecy-Preserving Proofs of Correctness of Computations and Applications.

Michael O. Rabin, Rocco A. Servedio, Christopher Thorpe

Proceedings of the 22nd IEEE Symposium on Logic in Computer Science (LICS 2007), 2007

Distribution-Free Testing Lower Bounds for Basic Boolean Functions.

Dana Glasner, Rocco A. Servedio

Proceedings of the Approximation, 2007

Editors' Introduction.

Marcus Hutter, Rocco A. Servedio, Eiji Takimoto

Proceedings of the Algorithmic Learning Theory, 18th International Conference, 2007

2006

On Learning Random DNF Formulas Under the Uniform Distribution.

Jeffrey C. Jackson, Rocco A. Servedio

Theory Comput., 2006

On learning embedded midbit functions.

Rocco A. Servedio

Theor. Comput. Sci., 2006

Toward Attribute Efficient Learning of Decision Lists and Parities.

Adam R. Klivans, Rocco A. Servedio

J. Mach. Learn. Res., 2006

Polynomial certificates for propositional classes.

Marta Arias, Aaron Feigelson, Roni Khardon, Rocco A. Servedio

Inf. Comput., 2006

PAC Learning Mixtures of Axis-Aligned Gaussians with No Separation Assumption

Jon Feldman, Ryan O'Donnell, Rocco A. Servedio

CoRR, 2006

On PAC Learning Algorithms for Rich Boolean Function Classes.

Rocco A. Servedio

Proceedings of the Theory and Applications of Models of Computation, 2006

Attribute-efficient learning of decision lists and linear threshold functions under unconcentrated distributions.

Philip M. Long, Rocco A. Servedio

Proceedings of the Advances in Neural Information Processing Systems 19, 2006

Discriminative Learning Can Succeed Where Generative Learning Fails.

Philip M. Long, Rocco A. Servedio

Proceedings of the Learning Theory, 19th Annual Conference on Learning Theory, 2006

PAC Learning Axis-Aligned Mixtures of Gaussians with No Separation Assumption.

Jon Feldman, Rocco A. Servedio, Ryan O'Donnell

Proceedings of the Learning Theory, 19th Annual Conference on Learning Theory, 2006

Learning Unions of <i>omega</i>(1)-Dimensional Rectangles.

Alp Atici, Rocco A. Servedio

Proceedings of the Algorithmic Learning Theory, 17th International Conference, 2006

2005

Learning Random Log-Depth Decision Trees under Uniform Distribution.

Jeffrey C. Jackson, Rocco A. Servedio

SIAM J. Comput., 2005

Improved Bounds on Quantum Learning Algorithms.

Alp Atici, Rocco A. Servedio

Quantum Inf. Process., 2005

Maximum Margin Algorithms with Boolean Kernels.

Roni Khardon, Rocco A. Servedio

J. Mach. Learn. Res., 2005

Boosting in the presence of noise.

Adam Tauman Kalai, Rocco A. Servedio

J. Comput. Syst. Sci., 2005

Learning DNF from random walks.

Nader H. Bshouty, Elchanan Mossel, Ryan O'Donnell, Rocco A. Servedio

J. Comput. Syst. Sci., 2005

Efficiency versus Convergence of Boolean Kernels for On-Line Learning Algorithms.

Roni Khardon, Dan Roth, Rocco A. Servedio

J. Artif. Intell. Res., 2005

Computing sparse permanents faster.

Rocco A. Servedio, Andrew Wan

Inf. Process. Lett., 2005

Every decision tree has an influential variable

Ryan O'Donnell, Michael E. Saks, Oded Schramm, Rocco A. Servedio

CoRR, 2005

Unsupervised evidence integration.

Philip M. Long, Vinay Varadan, Sarah Gilman, Mark Treshock, Rocco A. Servedio

Proceedings of the Machine Learning, 2005

Every decision tree has an in.uential variable.

Ryan O'Donnell, Michael E. Saks, Oded Schramm, Rocco A. Servedio

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

Martingale Boosting.

Philip M. Long, Rocco A. Servedio

Proceedings of the Learning Theory, 18th Annual Conference on Learning Theory, 2005

2004

Equivalences and Separations Between Quantum and Classical Learnability.

Rocco A. Servedio, Steven J. Gortler

SIAM J. Comput., 2004

Learning functions of k relevant variables.

Elchanan Mossel, Ryan O'Donnell, Rocco A. Servedio

J. Comput. Syst. Sci., 2004

Learning DNF in time 2^{Õ(n^1/3)}.

Adam R. Klivans, Rocco A. Servedio

J. Comput. Syst. Sci., 2004

Learning intersections and thresholds of halfspaces.

Adam R. Klivans, Ryan O'Donnell, Rocco A. Servedio

J. Comput. Syst. Sci., 2004

Monotone Boolean formulas can approximate monotone linear threshold functions.

Rocco A. Servedio

Discret. Appl. Math., 2004

Perceptron-Like Performance for Intersections of Halfspaces.

Adam R. Klivans, Rocco A. Servedio

Proceedings of the Learning Theory, 17th Annual Conference on Learning Theory, 2004

2003

Boosting and Hard-Core Set Construction.

Adam R. Klivans, Rocco A. Servedio

Mach. Learn., 2003

Smooth Boosting and Learning with Malicious Noise.

Rocco A. Servedio

J. Mach. Learn. Res., 2003

Toward Attribute Efficient Learning Algorithms

Adam R. Klivans, Rocco A. Servedio

CoRR, 2003

Learning juntas.

Elchanan Mossel, Ryan O'Donnell, Rocco A. Servedio

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Polynomial Certificates for Propositional Classes.

Marta Arias, Roni Khardon, Rocco A. Servedio

Proceedings of the Computational Learning Theory and Kernel Machines, 2003

2002

Perceptron, Winnow, and PAC Learning.

Rocco A. Servedio

SIAM J. Comput., 2002

PAC Analogues of Perceptron and Winnow Via Boosting the Margin.

Rocco A. Servedio

Mach. Learn., 2002

Learnability beyond AC0.

Jeffrey C. Jackson, Adam R. Klivans, Rocco A. Servedio

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

2001

On the limits of efficient teachability.

Rocco A. Servedio

Inf. Process. Lett., 2001

On Learning Monotone DNF under Product Distributions

Rocco A. Servedio

Electron. Colloquium Comput. Complex., 2001

Separating Quantum and Classical Learning.

Rocco A. Servedio

Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

Quantum versus Classical Learnability.

Rocco A. Servedio, Steven J. Gortler

Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

2000

Computational Sample Complexity and Attribute-Efficient Learning.

Rocco A. Servedio

J. Comput. Syst. Sci., 2000

1999

Boosting and Hard-Core Sets.

Adam R. Klivans, Rocco A. Servedio

Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

On PAC Learning Using Winnow, Perceptron, and a Perceptron-like Algorithm.

Rocco A. Servedio

Proceedings of the Twelfth Annual Conference on Computational Learning Theory, 1999