Rocco A. Servedio

MaRDI QIDQ371199zbMATH OpenWikidataFDO

List of research outcomes

This list is not complete and representing at the moment only items from zbMATH Open and arXiv. We are working on additional sources - please check back here soon!

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
scientific article; zbMATH DE number 7829285 (Why is no real title available?) (available as arXiv preprint)	2024-04-09	Paper
scientific article; zbMATH DE number 7788343 (Why is no real title available?) (available as arXiv preprint)	2024-01-15	Paper
Deterministic Approximate Counting of Polynomial Threshold Functions via a Derandomized Regularity Lemma.	2023-11-20	Paper
scientific article; zbMATH DE number 7768398 (Why is no real title available?) (available as arXiv preprint)	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 ACM Transactions on Algorithms	2023-10-31	Paper
Testing Convex Truncation	2023-05-04	Paper
scientific article; zbMATH DE number 7650112 (Why is no real title available?)	2023-02-03	Paper
scientific article; zbMATH DE number 7650111 (Why is no real title available?) (available as arXiv preprint)	2023-02-03	Paper
Simple and efficient pseudorandom generators from gaussian processes	2022-07-27	Paper
Density estimation for shift-invariant multidimensional distributions (available as arXiv preprint)	2022-07-18	Paper
The Perils of Being Unhinged: On the Accuracy of Classifiers Minimizing a Noise-Robust Convex Loss Neural Computation	2022-06-13	Paper
Quantitative correlation inequalities via extremal power series Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete	2022-05-20	Paper
scientific article; zbMATH DE number 7528580 (Why is no real title available?) Theory of Computing	2022-05-18	Paper
Fooling Polytopes Journal of the ACM	2022-03-31	Paper
Luby-Veličković-Wigderson revisited: improved correlation bounds and pseudorandom generators for depth-two circuits (available as arXiv preprint)	2021-08-04	Paper
Adaptivity is exponentially powerful for testing monotonicity of halfspaces (available as arXiv preprint)	2021-07-28	Paper
Sample-based high-dimensional convexity testing (available as arXiv preprint)	2021-07-28	Paper
Approximating Sumset Size	2021-07-26	Paper
scientific article; zbMATH DE number 7307484 (Why is no real title available?) (available as arXiv preprint)	2021-02-08	Paper
scientific article; zbMATH DE number 7307484 (Why is no real title available?)	2021-02-08	Paper
A Lower Bound on Cycle-Finding in Sparse Digraphs Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms	2021-02-02	Paper
Learning from satisfying assignments under continuous distributions Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms	2021-02-02	Paper
Testing noisy linear functions for sparsity Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing	2021-01-19	Paper
Fooling Gaussian PTFs via local hyperconcentration Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing	2021-01-19	Paper
Quantitative Correlation Inequalities via Semigroup Interpolation	2020-12-22	Paper
Sharp bounds for population recovery Theory of Computing	2020-12-17	Paper
Reconstructing weighted voting schemes from partial information about their power indices	2020-07-19	Paper
Settling the query complexity of non-adaptive junta testing (available as arXiv preprint)	2020-05-26	Paper
Fooling polytopes Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing	2020-01-30	Paper
Kruskal-Katona for convex sets, with applications	2019-10-31	Paper
Pseudorandomness for read-\(k\) DNF formulas Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms	2019-10-15	Paper
Distribution-free junta testing Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing	2019-08-22	Paper
Efficient average-case population recovery in the presence of insertions and deletions (available as arXiv preprint)	2019-07-12	Paper
A polynomial-time approximation scheme for fault-tolerant distributed storage Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms	2019-06-20	Paper
Testing equivalence between distributions using conditional samples Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms	2019-06-20	Paper
Learning mixtures of structured distributions over discrete domains Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms	2019-05-15	Paper
Testing \(k\)-modal distributions: optimal algorithms via reductions Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms	2019-05-15	Paper
Exponentially improved algorithms and lower bounds for testing signed majorities Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms	2019-05-15	Paper
Private data release via learning thresholds (available as arXiv preprint)	2019-05-10	Paper
Private data release via learning thresholds	2019-05-10	Paper
Learning \(k\)-modal distributions via testing	2019-05-10	Paper
Testing halfspaces	2019-05-06	Paper
Optimal mean-based algorithms for trace reconstruction The Annals of Applied Probability	2019-04-24	Paper
Distribution-free junta testing ACM Transactions on Algorithms	2019-03-28	Paper
Settling the query complexity of non-adaptive junta testing Journal of the ACM	2019-02-25	Paper
A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete	2018-08-10	Paper
Learning Sums of Independent Random Variables with Sparse Collective Support (available as arXiv preprint)	2018-07-18	Paper
An average-case depth hierarchy theorem for Boolean circuits Journal of the ACM	2018-05-17	Paper
What circuit classes can be learned with non-trivial savings?	2018-05-03	Paper
The inverse Shapley value problem Games and Economic Behavior	2017-10-24	Paper
scientific article; zbMATH DE number 6789278 (Why is no real title available?)	2017-10-10	Paper
Learning from satisfying assignments Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms	2017-10-05	Paper
Hardness results for agnostically learning low-degree polynomial threshold functions	2017-09-29	Paper
Hardness results for agnostically learning low-degree polynomial threshold functions (available as arXiv preprint)	2017-09-29	Paper
Poly-logarithmic Frege depth lower bounds via an expander switching lemma Proceedings of the forty-eighth annual ACM symposium on Theory of Computing	2017-09-29	Paper
Near-optimal small-depth lower bounds for small distance connectivity Proceedings of the forty-eighth annual ACM symposium on Theory of Computing	2017-09-29	Paper
Learning circuits with few negations (available as arXiv preprint)	2017-08-31	Paper
Optimal mean-based algorithms for trace reconstruction Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing	2017-08-17	Paper
Addition is exponentially harder than counting for shallow monotone circuits Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing	2017-08-17	Paper
Low-weight halfspaces for sparse boolean vectors Proceedings of the 4th conference on Innovations in Theoretical Computer Science	2017-05-16	Paper
Computational sample complexity and attribute-efficient learning Proceedings of the thirty-first annual ACM symposium on Theory of Computing	2016-09-29	Paper
A robust Khintchine inequality, and algorithms for computing optimal constants in Fourier analysis and high-dimensional geometry SIAM Journal on Discrete Mathematics	2016-05-26	Paper
Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science	2016-04-15	Paper
scientific article; zbMATH DE number 6537946 (Why is no real title available?) Chicago Journal of Theoretical Computer Science	2016-02-01	Paper
Boolean function monotonicity testing requires (almost) \(n^{1/2}\) non-adaptive queries Proceedings of the forty-seventh annual ACM symposium on Theory of Computing	2015-08-21	Paper
Exponentially improved algorithms and lower bounds for testing signed majorities Algorithmica	2015-07-10	Paper
Efficient deterministic approximate counting for low-degree polynomial threshold functions Proceedings of the forty-sixth annual ACM symposium on Theory of computing	2015-06-26	Paper
Efficient density estimation via piecewise polynomial approximation Proceedings of the forty-sixth annual ACM symposium on Theory of computing	2015-06-26	Paper
Testing probability distributions using conditional samples SIAM Journal on Computing	2015-06-11	Paper
Learning Poisson binomial distributions Algorithmica	2015-05-21	Paper
Learning DNF in time Proceedings of the thirty-third annual ACM symposium on Theory of computing	2015-02-27	Paper
Learning \(k\)-modal distributions via testing Theory of Computing	2015-02-03	Paper
On the Weight of Halfspaces over Hamming Balls SIAM Journal on Discrete Mathematics	2014-12-22	Paper
scientific article; zbMATH DE number 6378047 (Why is no real title available?)	2014-12-08	Paper
A regularity lemma and low-weight approximators for low-degree polynomial threshold functions Theory of Computing	2014-10-06	Paper
Nearly optimal solutions for the Chow parameters problem and low-weight approximation of halfspaces Journal of the ACM	2014-09-12	Paper
Bounding the average sensitivity and noise sensitivity of polynomial threshold functions Proceedings of the forty-second ACM symposium on Theory of computing	2014-08-13	Paper
Bounded Independence Fools Halfspaces 2009 50th Annual IEEE Symposium on Foundations of Computer Science	2014-07-25	Paper
On DNF approximators for monotone Boolean functions Automata, Languages, and Programming	2014-07-01	Paper
Average sensitivity and noise sensitivity of polynomial threshold functions SIAM Journal on Computing	2014-06-04	Paper
Learning Poisson binomial distributions Proceedings of the forty-fourth annual ACM symposium on Theory of computing	2014-05-13	Paper
Nearly optimal solutions for the Chow parameters problem and low-weight approximation of halfspaces Proceedings of the forty-fourth annual ACM symposium on Theory of computing	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 Computational Complexity	2013-09-30	Paper
The inverse Shapley value problem Lecture Notes in Computer Science	2013-08-12	Paper
A robust Khintchine inequality, and algorithms for computing optimal constants in Fourier analysis and high-dimensional geometry Lecture Notes in Computer Science	2013-08-06	Paper
Learning halfspaces with malicious noise Journal of Machine Learning Research (JMLR)	2012-04-17	Paper
On the Distribution of the Fourier Spectrum of Halfspaces	2012-02-29	Paper
New degree bounds for polynomial threshold functions Combinatorica	2011-12-19	Paper
Testing Fourier dimensionality and sparsity SIAM Journal on Computing	2011-11-07	Paper
Efficiently testing sparse \(\text{GF}(2)\) polynomials Algorithmica	2011-11-07	Paper
Toward attribute efficient learning of decision lists and parities	2011-10-12	Paper
Maximum margin algorithms with Boolean kernels	2011-10-12	Paper
scientific article; zbMATH DE number 5957428 (Why is no real title available?)	2011-10-12	Paper
A canonical form for testing Boolean function properties Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques	2011-08-17	Paper
Distribution-free testing lower bound for basic Boolean functions Theory of Computing	2011-05-24	Paper
On learning random DNF formulas under the uniform distribution Theory of Computing	2011-05-24	Paper
Optimal cryptographic hardness of learning monotone functions Theory of Computing	2011-05-24	Paper
The Chow parameters problem SIAM Journal on Computing	2011-05-17	Paper
Bounded Independence Fools Halfspaces SIAM Journal on Computing	2011-04-04	Paper
Learning random monotone DNF Discrete Applied Mathematics	2011-03-10	Paper
Testing Halfspaces SIAM Journal on Computing	2010-11-04	Paper
Testing by implicit learning: a brief survey Property Testing	2010-10-12	Paper
Testing (Subclasses of) Halfspaces Property Testing	2010-10-12	Paper
Random classification noise defeats all convex potential boosters Machine Learning	2010-10-07	Paper
Learning and lower bounds for AC\(^{0}\) with threshold gates Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques	2010-09-10	Paper
Learning juntas Proceedings of the thirty-fifth annual ACM symposium on Theory of computing	2010-08-16	Paper
Boosting in the presence of noise Proceedings of the thirty-fifth annual ACM symposium on Theory of computing	2010-08-16	Paper
New degree bounds for polynomial threshold functions Proceedings of the thirty-fifth annual ACM symposium on Theory of computing	2010-08-16	Paper
Testing monotone high-dimensional distributions Proceedings of the thirty-seventh annual ACM symposium on Theory of computing	2010-08-16	Paper
Learnability beyond AC 0 Proceedings of the thiry-fourth annual ACM symposium on Theory of computing	2010-08-05	Paper
Discriminative learning can succeed where generative learning fails Information Processing Letters	2010-03-24	Paper
Learning random log-depth decision trees under the uniform distribution. Lecture Notes in Computer Science	2010-03-23	Paper
Polynomial certificates for propositional classes. Lecture Notes in Computer Science	2010-03-23	Paper
Maximum margin algorithms with Boolean kernels. Lecture Notes in Computer Science	2010-03-23	Paper
Computing sparse permanents faster Information Processing Letters	2009-12-18	Paper
Testing ±1-weight halfspace Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques	2009-10-28	Paper
Testing Fourier Dimensionality and Sparsity Automata, Languages and Programming	2009-07-14	Paper
Learning Halfspaces with Malicious Noise Automata, Languages and Programming	2009-07-14	Paper
DNF are teachable in the average case Machine Learning	2009-03-31	Paper
Testing monotone high‐dimensional distributions Random Structures & Algorithms	2009-03-04	Paper
Distribution-Free Testing Lower Bounds for Basic Boolean Functions Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques	2009-02-17	Paper
scientific article; zbMATH DE number 5485564 (Why is no real title available?)	2009-01-05	Paper
Agnostically Learning Halfspaces SIAM Journal on Computing	2008-12-22	Paper
LP Decoding Corrects a Constant Fraction of Errors IEEE Transactions on Information Theory	2008-12-21	Paper
Learning Random Monotone DNF Lecture Notes in Computer Science	2008-11-27	Paper
Learning Mixtures of Product Distributions over Discrete Domains SIAM Journal on Computing	2008-10-28	Paper
Learning unions of \(\omega(1)\)-dimensional rectangles Theoretical Computer Science	2008-10-22	Paper
Learning Unions of ω(1)-Dimensional Rectangles Lecture Notes in Computer Science	2008-09-04	Paper
Efficiently Testing Sparse GF(2) Polynomials Automata, Languages and Programming	2008-08-28	Paper
Optimal Cryptographic Hardness of Learning Monotone Functions Automata, Languages and Programming	2008-08-28	Paper
Editors’ Introduction Lecture Notes in Computer Science	2008-08-19	Paper
Learning Monotone Decision Trees in Polynomial Time SIAM Journal on Computing	2008-06-19	Paper
Extremal properties of polynomial threshold functions Journal of Computer and System Sciences	2008-03-11	Paper
Every linear threshold function has a low-weight approximator Computational Complexity	2008-02-22	Paper
Quantum algorithms for learning and testing juntas Quantum Information Processing	2007-12-03	Paper
Learning intersections of halfspaces with a margin Journal of Computer and System Sciences	2007-11-30	Paper
On PAC learning algorithms for rich Boolean function classes Theoretical Computer Science	2007-09-28	Paper
DNF Are Teachable in the Average Case Learning Theory	2007-09-14	Paper
PAC Learning Axis-Aligned Mixtures of Gaussians with No Separation Assumption Learning Theory	2007-09-14	Paper
Discriminative Learning Can Succeed Where Generative Learning Fails Learning Theory	2007-09-14	Paper
Theory and Applications of Models of Computation Lecture Notes in Computer Science	2007-04-30	Paper
Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques Lecture Notes in Computer Science	2006-07-07	Paper
Polynomial certificates for propositional classes Information and Computation	2006-06-30	Paper
Learning Theory Lecture Notes in Computer Science	2006-06-22	Paper
Learning Theory Lecture Notes in Computer Science	2006-06-22	Paper
Improved bounds on quantum learning algorithms Quantum Information Processing	2006-05-29	Paper
On learning embedded midbit functions Theoretical Computer Science	2006-03-20	Paper
scientific article; zbMATH DE number 2243402 (Why is no real title available?) (available as arXiv preprint)	2006-01-04	Paper
Boosting in the presence of noise Journal of Computer and System Sciences	2005-10-10	Paper
Learning DNF from random walks Journal of Computer and System Sciences	2005-10-10	Paper
Learning Random Log-Depth Decision Trees under Uniform Distribution SIAM Journal on Computing	2005-09-16	Paper
Learning Theory Lecture Notes in Computer Science	2005-06-13	Paper
Learning Theory Lecture Notes in Computer Science	2005-06-13	Paper
Learning Theory Lecture Notes in Computer Science	2005-06-13	Paper
Equivalences and Separations Between Quantum and Classical Learnability SIAM Journal on Computing	2005-02-21	Paper
10.1162/153244304773936072 CrossRef Listing of Deleted DOIs	2004-11-23	Paper
Learning DNF in time \(2^{\widetilde O(n^{1/3})}\) Journal of Computer and System Sciences	2004-11-22	Paper
Learning functions of \(k\) relevant variables Journal of Computer and System Sciences	2004-11-18	Paper
On learning monotone DNF under product distributions Information and Computation	2004-10-04	Paper
Monotone Boolean formulas can approximate monotone linear threshold functions Discrete Applied Mathematics	2004-08-19	Paper
Learning intersections and thresholds of halfspaces Journal of Computer and System Sciences	2004-08-06	Paper
scientific article; zbMATH DE number 1966607 (Why is no real title available?)	2003-08-18	Paper
Boosting and hard-core set construction Machine Learning	2003-06-25	Paper
Perceptron, Winnow, and PAC Learning SIAM Journal on Computing	2002-09-29	Paper
scientific article; zbMATH DE number 1804125 (Why is no real title available?)	2002-09-22	Paper
scientific article; zbMATH DE number 1804119 (Why is no real title available?)	2002-09-22	Paper
On the limits of efficient teachability Information Processing Letters	2002-07-14	Paper
scientific article; zbMATH DE number 1754656 (Why is no real title available?)	2002-06-12	Paper
PAC analogues of Perceptron and Winnow via boosting the margin Machine Learning	2002-04-11	Paper
Computational sample complexity and attribute-efficient learning Journal of Computer and System Sciences	2000-07-27	Paper
scientific article; zbMATH DE number 838639 (Why is no real title available?)	1996-06-05	Paper
Testing Sumsets is Hard (available as arXiv preprint)	N/A	Paper

Research outcomes over time

This page was built for person: Rocco A. Servedio