Rocco A. Servedio

Available identifiers

zbMath Open servedio.rocco-aWikidataQ102248339 ScholiaQ102248339MaRDI QIDQ371199

List of research outcomes

Publication	Date of Publication	Type
Subset sum in time \(2^{n/2}/\text{poly}(n)\)	2025-01-14	Paper
Mildly exponential lower bounds on tolerant testers for monotonicity, unateness, and juntas	2024-11-28	Paper
Average-case subset balancing problems	2024-07-19	Paper
Near-optimal average-case approximate trace reconstruction from few traces	2024-07-19	Paper
Approximating sumset size	2024-07-19	Paper
Approximate trace reconstruction from a single trace	2024-05-14	Paper
https://portal.mardi4nfdi.de/entity/Q6126286	2024-04-09	Paper
https://portal.mardi4nfdi.de/entity/Q6147251	2024-01-15	Paper
Deterministic Approximate Counting of Polynomial Threshold Functions via a Derandomized Regularity Lemma.	2023-11-20	Paper
https://portal.mardi4nfdi.de/entity/Q6070398	2023-11-20	Paper
Gaussian Approximation of Convex Sets by Intersections of Halfspaces	2023-11-14	Paper
A Lower Bound on Cycle-Finding in Sparse Digraphs	2023-10-31	Paper
Testing Convex Truncation	2023-05-04	Paper
https://portal.mardi4nfdi.de/entity/Q5875500	2023-02-03	Paper
https://portal.mardi4nfdi.de/entity/Q5875501	2023-02-03	Paper
Simple and efficient pseudorandom generators from gaussian processes	2022-07-27	Paper
https://portal.mardi4nfdi.de/entity/Q5090402	2022-07-18	Paper
The Perils of Being Unhinged: On the Accuracy of Classifiers Minimizing a Noise-Robust Convex Loss	2022-06-13	Paper
Quantitative correlation inequalities via extremal power series	2022-05-20	Paper
https://portal.mardi4nfdi.de/entity/Q5077146	2022-05-18	Paper
Fooling Polytopes	2022-03-31	Paper
https://portal.mardi4nfdi.de/entity/Q5009555	2021-08-04	Paper
Sample-Based High-Dimensional Convexity Testing.	2021-07-28	Paper
Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces	2021-07-28	Paper
Approximating Sumset Size	2021-07-26	Paper
https://portal.mardi4nfdi.de/entity/Q5149248	2021-02-08	Paper
Learning from satisfying assignments under continuous distributions	2021-02-02	Paper
A Lower Bound on Cycle-Finding in Sparse Digraphs	2021-02-02	Paper
Testing noisy linear functions for sparsity	2021-01-19	Paper
Fooling Gaussian PTFs via local hyperconcentration	2021-01-19	Paper
Quantitative Correlation Inequalities via Semigroup Interpolation	2020-12-22	Paper
Sharp bounds for population recovery	2020-12-17	Paper
Reconstructing weighted voting schemes from partial information about their power indices	2020-07-19	Paper
https://portal.mardi4nfdi.de/entity/Q5111156	2020-05-26	Paper
Fooling polytopes	2020-01-30	Paper
Kruskal-Katona for convex sets, with applications	2019-10-31	Paper
Pseudorandomness for read-k DNF formulas	2019-10-15	Paper
Distribution-free Junta Testing	2019-08-22	Paper
Efficient average-case population recovery in the presence of insertions and deletions	2019-07-12	Paper
A Polynomial-time Approximation Scheme for Fault-tolerant Distributed Storage	2019-06-20	Paper
Testing equivalence between distributions using conditional samples	2019-06-20	Paper
Exponentially improved algorithms and lower bounds for testing signed majorities	2019-05-15	Paper
Learning mixtures of structured distributions over discrete domains	2019-05-15	Paper
Testing k-Modal Distributions: Optimal Algorithms via Reductions	2019-05-15	Paper
https://portal.mardi4nfdi.de/entity/Q5743387	2019-05-10	Paper
https://portal.mardi4nfdi.de/entity/Q5743483	2019-05-10	Paper
https://portal.mardi4nfdi.de/entity/Q4633833	2019-05-06	Paper
Optimal mean-based algorithms for trace reconstruction	2019-04-24	Paper
Distribution-free Junta Testing	2019-03-28	Paper
Settling the Query Complexity of Non-adaptive Junta Testing	2019-02-25	Paper
A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting	2018-08-10	Paper
Learning Sums of Independent Random Variables with Sparse Collective Support	2018-07-18	Paper
An Average-Case Depth Hierarchy Theorem for Boolean Circuits	2018-05-17	Paper
What Circuit Classes Can Be Learned with Non-Trivial Savings?	2018-05-03	Paper
The inverse Shapley value problem	2017-10-24	Paper
https://portal.mardi4nfdi.de/entity/Q5368747	2017-10-10	Paper
Learning from satisfying assignments	2017-10-05	Paper
Poly-logarithmic Frege depth lower bounds via an expander switching lemma	2017-09-29	Paper
Near-optimal small-depth lower bounds for small distance connectivity	2017-09-29	Paper
https://portal.mardi4nfdi.de/entity/Q5365141	2017-09-29	Paper
Learning circuits with few negations	2017-08-31	Paper
Addition is exponentially harder than counting for shallow monotone circuits	2017-08-17	Paper
Optimal mean-based algorithms for trace reconstruction	2017-08-17	Paper
Low-weight halfspaces for sparse boolean vectors	2017-05-16	Paper
Computational sample complexity and attribute-efficient learning	2016-09-29	Paper
A robust Khintchine inequality, and algorithms for computing optimal constants in Fourier analysis and high-dimensional geometry	2016-05-26	Paper
Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions	2016-04-15	Paper
https://portal.mardi4nfdi.de/entity/Q3466401	2016-02-01	Paper
Boolean Function Monotonicity Testing Requires (Almost) n 1/2 Non-adaptive Queries	2015-08-21	Paper
Exponentially improved algorithms and lower bounds for testing signed majorities	2015-07-10	Paper
Efficient deterministic approximate counting for low-degree polynomial threshold functions	2015-06-26	Paper
Efficient density estimation via piecewise polynomial approximation	2015-06-26	Paper
Testing Probability Distributions using Conditional Samples	2015-06-11	Paper
Learning Poisson binomial distributions	2015-05-21	Paper
Learning DNF in time	2015-02-27	Paper
Learning $k$-Modal Distributions via Testing	2015-02-03	Paper
On the Weight of Halfspaces over Hamming Balls	2014-12-22	Paper
https://portal.mardi4nfdi.de/entity/Q2933930	2014-12-08	Paper
https://portal.mardi4nfdi.de/entity/Q3191611	2014-10-06	Paper
Nearly Optimal Solutions for the Chow Parameters Problem and Low-Weight Approximation of Halfspaces	2014-09-12	Paper
Bounding the average sensitivity and noise sensitivity of polynomial threshold functions	2014-08-13	Paper
Bounded Independence Fools Halfspaces	2014-07-25	Paper
On DNF Approximators for Monotone Boolean Functions	2014-07-01	Paper
Average Sensitivity and Noise Sensitivity of Polynomial Threshold Functions	2014-06-04	Paper
Learning Poisson binomial distributions	2014-05-13	Paper
Nearly Optimal Solutions for the Chow Parameters Problem and Low-Weight Approximation of Halfspaces	2014-05-13	Paper
Deterministic Approximate Counting for Degree-$2$ Polynomial Threshold Functions	2013-11-27	Paper
Deterministic Approximate Counting for Juntas of Degree-$2$ Polynomial Threshold Functions	2013-11-27	Paper
Improved approximation of linear threshold functions	2013-09-30	Paper
The inverse Shapley value problem	2013-08-12	Paper
A robust Khintchine inequality, and algorithms for computing optimal constants in Fourier analysis and high-dimensional geometry	2013-08-06	Paper
Learning halfspaces with malicious noise	2012-04-17	Paper
On the Distribution of the Fourier Spectrum of Halfspaces	2012-02-29	Paper
New degree bounds for polynomial threshold functions	2011-12-19	Paper
Testing Fourier Dimensionality and Sparsity	2011-11-07	Paper
Efficiently testing sparse \(\text{GF}(2)\) polynomials	2011-11-07	Paper
https://portal.mardi4nfdi.de/entity/Q3174077	2011-10-12	Paper
https://portal.mardi4nfdi.de/entity/Q3093360	2011-10-12	Paper
https://portal.mardi4nfdi.de/entity/Q3093302	2011-10-12	Paper
A Canonical Form for Testing Boolean Function Properties	2011-08-17	Paper
https://portal.mardi4nfdi.de/entity/Q3002810	2011-05-24	Paper
https://portal.mardi4nfdi.de/entity/Q3002770	2011-05-24	Paper
https://portal.mardi4nfdi.de/entity/Q3002813	2011-05-24	Paper
The Chow Parameters Problem	2011-05-17	Paper
Bounded Independence Fools Halfspaces	2011-04-04	Paper
Learning random monotone DNF	2011-03-10	Paper
Testing Halfspaces	2010-11-04	Paper
Testing (Subclasses of) Halfspaces	2010-10-12	Paper
Testing by Implicit Learning: A Brief Survey	2010-10-12	Paper
Random classification noise defeats all convex potential boosters	2010-10-07	Paper
Learning and Lower Bounds for AC 0 with Threshold Gates	2010-09-10	Paper
Learning juntas	2010-08-16	Paper
Boosting in the presence of noise	2010-08-16	Paper
New degree bounds for polynomial threshold functions	2010-08-16	Paper
Testing monotone high-dimensional distributions	2010-08-16	Paper
Learnability beyond AC 0	2010-08-05	Paper
Discriminative learning can succeed where generative learning fails	2010-03-24	Paper
Learning Theory and Kernel Machines	2010-03-23	Paper
Learning Theory and Kernel Machines	2010-03-23	Paper
Learning Theory and Kernel Machines	2010-03-23	Paper
Computing sparse permanents faster	2009-12-18	Paper
Testing ±1-weight halfspace	2009-10-28	Paper
Testing Fourier Dimensionality and Sparsity	2009-07-14	Paper
Learning Halfspaces with Malicious Noise	2009-07-14	Paper
DNF are teachable in the average case	2009-03-31	Paper
Testing monotone high‐dimensional distributions	2009-03-04	Paper
Distribution-Free Testing Lower Bounds for Basic Boolean Functions	2009-02-17	Paper
https://portal.mardi4nfdi.de/entity/Q5302075	2009-01-05	Paper
Agnostically Learning Halfspaces	2008-12-22	Paper
LP Decoding Corrects a Constant Fraction of Errors	2008-12-21	Paper
Learning Random Monotone DNF	2008-11-27	Paper
Learning Mixtures of Product Distributions over Discrete Domains	2008-10-28	Paper
Learning unions of \(\omega(1)\)-dimensional rectangles	2008-10-22	Paper
Learning Unions of ω(1)-Dimensional Rectangles	2008-09-04	Paper
Optimal Cryptographic Hardness of Learning Monotone Functions	2008-08-28	Paper
Efficiently Testing Sparse GF(2) Polynomials	2008-08-28	Paper
Editors’ Introduction	2008-08-19	Paper
Learning Monotone Decision Trees in Polynomial Time	2008-06-19	Paper
Extremal properties of polynomial threshold functions	2008-03-11	Paper
Every linear threshold function has a low-weight approximator	2008-02-22	Paper
Quantum algorithms for learning and testing juntas	2007-12-03	Paper
Learning intersections of halfspaces with a margin	2007-11-30	Paper
On PAC learning algorithms for rich Boolean function classes	2007-09-28	Paper
DNF Are Teachable in the Average Case	2007-09-14	Paper
PAC Learning Axis-Aligned Mixtures of Gaussians with No Separation Assumption	2007-09-14	Paper
Discriminative Learning Can Succeed Where Generative Learning Fails	2007-09-14	Paper
Theory and Applications of Models of Computation	2007-04-30	Paper
Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques	2006-07-07	Paper
Polynomial certificates for propositional classes	2006-06-30	Paper
Learning Theory	2006-06-22	Paper
Learning Theory	2006-06-22	Paper
Improved bounds on quantum learning algorithms	2006-05-29	Paper
On learning embedded midbit functions	2006-03-20	Paper
https://portal.mardi4nfdi.de/entity/Q5715719	2006-01-04	Paper
Learning DNF from random walks	2005-10-10	Paper
Boosting in the presence of noise	2005-10-10	Paper
Learning Random Log-Depth Decision Trees under Uniform Distribution	2005-09-16	Paper
Learning Theory	2005-06-13	Paper
Learning Theory	2005-06-13	Paper
Learning Theory	2005-06-13	Paper
Equivalences and Separations Between Quantum and Classical Learnability	2005-02-21	Paper
10.1162/153244304773936072	2004-11-23	Paper
Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)	2004-11-22	Paper
Learning functions of \(k\) relevant variables	2004-11-18	Paper
On learning monotone DNF under product distributions	2004-10-04	Paper
Monotone Boolean formulas can approximate monotone linear threshold functions	2004-08-19	Paper
Learning intersections and thresholds of halfspaces	2004-08-06	Paper
https://portal.mardi4nfdi.de/entity/Q4420741	2003-08-18	Paper
Boosting and hard-core set construction	2003-06-25	Paper
Perceptron, Winnow, and PAC Learning	2002-09-29	Paper
https://portal.mardi4nfdi.de/entity/Q3148821	2002-09-22	Paper
https://portal.mardi4nfdi.de/entity/Q3148827	2002-09-22	Paper
On the limits of efficient teachability	2002-07-14	Paper
https://portal.mardi4nfdi.de/entity/Q4535084	2002-06-12	Paper
PAC analogues of Perceptron and Winnow via boosting the margin	2002-04-11	Paper
Computational sample complexity and attribute-efficient learning	2000-07-27	Paper
https://portal.mardi4nfdi.de/entity/Q4863860	1996-06-05	Paper
Testing Sumsets is Hard	N/A	Paper

Research outcomes over time

This page was built for person: Rocco A. Servedio