Rocco A. Servedio

According to our database1, Rocco A. Servedio authored at least 164 papers between 1999 and 2020.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepage:

On csauthors.net:

Bibliography

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

Fooling Gaussian PTFs via local hyperconcentration.
Proceedings of the Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Testing noisy linear functions for sparsity.
Proceedings of the Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

A Lower Bound on Cycle-Finding in Sparse Digraphs.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Learning from satisfying assignments under continuous distributions.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

2019
Distribution-free Junta Testing.
ACM Trans. Algorithms, 2019

Kruskal-Katona for convex sets, with applications.
CoRR, 2019

Pseudorandomness for read-k DNF formulas.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Density Estimation for Shift-Invariant Multidimensional Distributions.
Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Beyond Trace Reconstruction: Population Recovery from the Deletion Channel.
Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Improved Pseudorandom Generators from Pseudorandom Multi-Switching Lemmas.
Proceedings of the Approximation, 2019

Efficient Average-Case Population Recovery in the Presence of Insertions and Deletions.
Proceedings of the Approximation, 2019

2018
Settling the Query Complexity of Non-adaptive Junta Testing.
J. ACM, 2018

Fooling Polytopes.
Electronic Colloquium on Computational Complexity (ECCC), 2018

Simple and efficient pseudorandom generators from Gaussian processes.
Electronic Colloquium on Computational Complexity (ECCC), 2018

Learning sparse mixtures of rankings from noisy information.
CoRR, 2018

Learning Sums of Independent Random Variables with Sparse Collective Support.
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.
Proceedings of the Approximation, 2018

2017
An Average-Case Depth Hierarchy Theorem for Boolean Circuits.
J. ACM, 2017

Sharp bounds for population recovery.
CoRR, 2017

Optimal mean-based algorithms for trace reconstruction.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

What Circuit Classes Can Be Learned with Non-Trivial Savings?.
Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

Fooling Intersections of Low-Weight Halfspaces.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Deterministic Search for CNF Satisfying Assignments in Almost Polynomial Time.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces.
Proceedings of the Approximation, 2017

Sample-Based High-Dimensional Convexity Testing.
Proceedings of the Approximation, 2017

2016
A Robust Khintchine Inequality, and Algorithms for Computing Optimal Constants in Fourier Analysis and High-Dimensional Geometry.
SIAM J. Discret. Math., 2016

Degree and Sensitivity: tails of two distributions.
Electronic Colloquium on Computational Complexity (ECCC), 2016

Poly-logarithmic Frege depth lower bounds via an expander switching lemma.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Near-optimal small-depth lower bounds for small distance connectivity.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Degree and Sensitivity: Tails of Two Distributions.
Proceedings of the 31st Conference on Computational Complexity, 2016

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

An average-case depth hierarchy theorem for Boolean circuits.
Electronic Colloquium on Computational Complexity (ECCC), 2015

Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions.
Electronic Colloquium on Computational Complexity (ECCC), 2015

Addition is exponentially harder than counting for shallow monotone circuits.
Electronic Colloquium on Computational Complexity (ECCC), 2015

Noise Stable Halfspaces are Close to Very Small Juntas.
Chic. J. Theor. Comput. Sci., 2015

Exponentially Improved Algorithms and Lower Bounds for Testing Signed Majorities.
Algorithmica, 2015

Learning Poisson Binomial Distributions.
Algorithmica, 2015

Boolean Function Monotonicity Testing Requires (Almost) n<sup>1/2</sup> Non-adaptive Queries.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Learning from satisfying assignments.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Adaptivity Helps for Testing Juntas.
Proceedings of the 30th Conference on Computational Complexity, 2015

2014
A Regularity Lemma and Low-Weight Approximators for Low-Degree Polynomial Threshold Functions.
Theory Comput., 2014

Learning <i>k</i>-Modal Distributions via Testing.
Theory Comput., 2014

On the Weight of Halfspaces over Hamming Balls.
SIAM J. Discret. Math., 2014

Average Sensitivity and Noise Sensitivity of Polynomial Threshold Functions.
SIAM J. Comput., 2014

Nearly Optimal Solutions for the Chow Parameters Problem and Low-Weight Approximation of Halfspaces.
J. ACM, 2014

Learning circuits with few negations.
Electronic Colloquium on Computational Complexity (ECCC), 2014

Efficient density estimation via piecewise polynomial approximation.
Proceedings of the Symposium on Theory of Computing, 2014

A Polynomial-time Approximation Scheme for Fault-tolerant Distributed Storage.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Testing equivalence between distributions using conditional samples.
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.
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.
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

New Algorithms and Lower Bounds for Monotonicity Testing.
Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013
Algorithms and hardness results for parallel large margin learning.
J. Mach. Learn. Res., 2013

Efficient deterministic approximate counting for low degree polynomial threshold functions.
Electronic Colloquium on Computational Complexity (ECCC), 2013

Deterministic Approximate Counting for Degree-2 Polynomial Threshold Functions.
Electronic Colloquium on Computational Complexity (ECCC), 2013

Deterministic Approximate Counting for Juntas of Degree-2 Polynomial Threshold Functions.
Electronic Colloquium on Computational Complexity (ECCC), 2013

Improved Approximation of Linear Threshold Functions.
Comput. Complex., 2013

Testing <i>k</i>-Modal Distributions: Optimal Algorithms via Reductions.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Learning mixtures of structured distributions over discrete domains.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Low-weight halfspaces for sparse boolean vectors.
Proceedings of the Innovations in Theoretical Computer Science, 2013

Consistency versus Realizable H-Consistency for Multiclass Classification.
Proceedings of the 30th International Conference on Machine Learning, 2013

Learning Sums of Independent Integer Random Variables.
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).
SIAM J. Comput., 2012

Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial Threshold Functions.
Proceedings of the COLT 2012, 2012

Tight Bounds on Proper Equivalence Query Learning of DNF.
Proceedings of the COLT 2012, 2012

On a special case of rigidity.
Electronic Colloquium on Computational Complexity (ECCC), 2012

The Inverse Shapley Value Problem.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Inverse Problems in Approximate Uniform Generation.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Testing probability distributions using conditional samples.
Electronic Colloquium on Computational Complexity (ECCC), 2012

On the Distribution of the Fourier Spectrum of Halfspaces
CoRR, 2012

A high-dimensional surprise: technical perspective.
Commun. ACM, 2012

Private data release via learning thresholds.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

2011
The Chow Parameters Problem.
SIAM J. Comput., 2011

Testing Fourier Dimensionality and Sparsity.
SIAM J. Comput., 2011

Lower Bounds and Hardness Amplification for Learning Shallow Monotone Formulas.
Proceedings of the COLT 2011, 2011

Testing $k$-Modal Distributions: Optimal Algorithms via Reductions
CoRR, 2011

Learning $k$-Modal Distributions via Testing
CoRR, 2011

Learning transformed product distributions
CoRR, 2011

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

Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Learning large-margin halfspaces with more malicious noise.
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.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010
Random classification noise defeats all convex potential boosters.
Mach. Learn., 2010

Learning and Lower Bounds for AC<sup>0</sup> with Threshold Gates.
Electronic Colloquium on Computational Complexity (ECCC), 2010

New degree bounds for polynomial threshold functions.
Comb., 2010

Bounding the average sensitivity and noise sensitivity of polynomial threshold functions.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Testing by Implicit Learning: A Brief Survey.
Proceedings of the Property Testing - Current Research and Surveys, 2010

Testing (Subclasses of) Halfspaces.
Proceedings of the Property Testing - Current Research and Surveys, 2010

Restricted Boltzmann Machines are Hard to Approximately Evaluate or Simulate.
Proceedings of the 27th International Conference on Machine Learning (ICML-10), 2010

2009
Distribution-Free Testing Lower Bound for Basic Boolean Functions.
Theory Comput., 2009

Optimal Cryptographic Hardness of Learning Monotone Functions.
Theory Comput., 2009

Preface.
Theor. Comput. Sci., 2009

Testing monotone high-dimensional distributions.
Random Struct. Algorithms, 2009

Learning Halfspaces with Malicious Noise.
J. Mach. Learn. Res., 2009

Bounded Independence Fools Halfspaces.
Electronic Colloquium on Computational Complexity (ECCC), 2009

Testing ±1-weight halfspace.
Proceedings of the Approximation, 2009

2008
Learning Constant-Depth Circuits.
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Learning unions of omega(1)-dimensional rectangles.
Theor. Comput. Sci., 2008

Agnostically Learning Halfspaces.
SIAM J. Comput., 2008

Learning Mixtures of Product Distributions over Discrete Domains.
SIAM J. Comput., 2008

Extremal properties of polynomial threshold functions.
J. Comput. Syst. Sci., 2008

Learning intersections of halfspaces with a margin.
J. Comput. Syst. Sci., 2008

Adaptive Martingale Boosting.
Proceedings of the Advances in Neural Information Processing Systems 21, 2008

Efficiently Testing Sparse GF(2) Polynomials.
Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

Learning Geometric Concepts via Gaussian Surface Area.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007
LP Decoding Corrects a Constant Fraction of Errors.
IEEE Trans. Inf. Theory, 2007

On PAC learning algorithms for rich Boolean function classes.
Theor. Comput. Sci., 2007

Learning Monotone Decision Trees in Polynomial Time.
SIAM J. Comput., 2007

Quantum Algorithms for Learning and Testing Juntas.
Quantum Inf. Process., 2007

DNF are teachable in the average case.
Mach. Learn., 2007

Separating Models of Learning from Correlated and Uncorrelated Data.
J. Mach. Learn. Res., 2007

Discriminative learning can succeed where generative learning fails.
Inf. Process. Lett., 2007

Testing Halfspaces.
Electronic Colloquium on Computational Complexity (ECCC), 2007

Learning Random Monotone DNF.
Electronic Colloquium on Computational Complexity (ECCC), 2007

Testing for Concise Representations.
Electronic Colloquium on Computational Complexity (ECCC), 2007

Every Linear Threshold Function has a Low-Weight Approximator.
Comput. Complex., 2007

Boosting the Area under the ROC Curve.
Proceedings of the Advances in Neural Information Processing Systems 20, 2007

One-Pass Boosting.
Proceedings of the Advances in Neural Information Processing Systems 20, 2007

Highly Efficient Secrecy-Preserving Proofs of Correctness of Computations and Applications.
Proceedings of the 22nd IEEE Symposium on Logic in Computer Science (LICS 2007), 2007

Distribution-Free Testing Lower Bounds for Basic Boolean Functions.
Proceedings of the Approximation, 2007

Editors' Introduction.
Proceedings of the Algorithmic Learning Theory, 18th International Conference, 2007

2006
On Learning Random DNF Formulas Under the Uniform Distribution.
Theory Comput., 2006

On learning embedded midbit functions.
Theor. Comput. Sci., 2006

Toward Attribute Efficient Learning of Decision Lists and Parities.
J. Mach. Learn. Res., 2006

Polynomial certificates for propositional classes.
Inf. Comput., 2006

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

On PAC Learning Algorithms for Rich Boolean Function Classes.
Proceedings of the Theory and Applications of Models of Computation, 2006

Attribute-efficient learning of decision lists and linear threshold functions under unconcentrated distributions.
Proceedings of the Advances in Neural Information Processing Systems 19, 2006

Discriminative Learning Can Succeed Where Generative Learning Fails.
Proceedings of the Learning Theory, 19th Annual Conference on Learning Theory, 2006

PAC Learning Axis-Aligned Mixtures of Gaussians with No Separation Assumption.
Proceedings of the Learning Theory, 19th Annual Conference on Learning Theory, 2006

Learning Unions of <i>omega</i>(1)-Dimensional Rectangles.
Proceedings of the Algorithmic Learning Theory, 17th International Conference, 2006

2005
Learning Random Log-Depth Decision Trees under Uniform Distribution.
SIAM J. Comput., 2005

Improved Bounds on Quantum Learning Algorithms.
Quantum Inf. Process., 2005

Maximum Margin Algorithms with Boolean Kernels.
J. Mach. Learn. Res., 2005

Boosting in the presence of noise.
J. Comput. Syst. Sci., 2005

Learning DNF from random walks.
J. Comput. Syst. Sci., 2005

Efficiency versus Convergence of Boolean Kernels for On-Line Learning Algorithms.
J. Artif. Intell. Res., 2005

Computing sparse permanents faster.
Inf. Process. Lett., 2005

Every decision tree has an influential variable
CoRR, 2005

Unsupervised evidence integration.
Proceedings of the Machine Learning, 2005

Every decision tree has an in.uential variable.
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

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

2004
Equivalences and Separations Between Quantum and Classical Learnability.
SIAM J. Comput., 2004

Learning functions of k relevant variables.
J. Comput. Syst. Sci., 2004

Learning DNF in time 2<sup>Õ(n<sup>1/3</sup>)</sup>.
J. Comput. Syst. Sci., 2004

Learning intersections and thresholds of halfspaces.
J. Comput. Syst. Sci., 2004

Monotone Boolean formulas can approximate monotone linear threshold functions.
Discret. Appl. Math., 2004

Perceptron-Like Performance for Intersections of Halfspaces.
Proceedings of the Learning Theory, 17th Annual Conference on Learning Theory, 2004

2003
Boosting and Hard-Core Set Construction.
Mach. Learn., 2003

Smooth Boosting and Learning with Malicious Noise.
J. Mach. Learn. Res., 2003

Toward Attribute Efficient Learning Algorithms
CoRR, 2003

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

Polynomial Certificates for Propositional Classes.
Proceedings of the Computational Learning Theory and Kernel Machines, 2003

2002
Perceptron, Winnow, and PAC Learning.
SIAM J. Comput., 2002

PAC Analogues of Perceptron and Winnow Via Boosting the Margin.
Mach. Learn., 2002

Learnability beyond AC0.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

2001
On the limits of efficient teachability.
Inf. Process. Lett., 2001

On Learning Monotone DNF under Product Distributions
Electronic Colloquium on Computational Complexity (ECCC), 2001

Separating Quantum and Classical Learning.
Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

Quantum versus Classical Learnability.
Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

2000
Computational Sample Complexity and Attribute-Efficient Learning.
J. Comput. Syst. Sci., 2000

1999
Boosting and Hard-Core Sets.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

On PAC Learning Using Winnow, Perceptron, and a Perceptron-like Algorithm.
Proceedings of the Twelfth Annual Conference on Computational Learning Theory, 1999


  Loading...