Rocco Servedio: Papers

"Man hath his daily work of body or mind
Appointed, which declares his dignity,
And the regard of Heaven on all his ways;
While other animals unactive range,
And of their doings God takes no account."

J. Milton, Paradise Lost

"These scientific products take of course some time to fructuate."

V. Nabokov, Lolita

  • Relative-error monotonicity testing.
    X. Chen and A. De and Y. Huang and Y. Li and S. Nadimpalli and R. Servedio and T. Yang.
    Symposium on Discrete Algorithms (SODA), 2025.

  • Lower Bounds for Convexity Testing.
    X. Chen and A. De and S. Nadimpalli and R. Servedio and E. Waingarten.
    Symposium on Discrete Algorithms (SODA), 2025.

  • Trace Reconstruction from Local Statistical Queries
    X. Chen and A. De and C.-H. Lee and R. Servedio.
    27th Intl. Workshop on Randomization and Computation (RANDOM), 2024.

  • Detecting Low-Degree Truncation.
    A. De and H. Li and S. Nadimpalli and R. Servedio
    56th Annual Symposium on Theory of Computing (STOC), 2024

  • Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity, Unateness, and Juntas
    X. Chen and A. De and Y. Li and S. Nadimpalli and R. Servedio.
    Symposium on Discrete Algorithms (SODA), 2024.

  • Testing Intersecting and Union-Closed Families.
    X. Chen and A. De and Y. Li and S. Nadimpalli and R. Servedio.
    Innovations in Theoretical Computer Science (ITCS), 2024.

  • Explicit orthogonal and unitary designs.
    R. O'Donnell and R. Servedio and P. Paredes. (*) Author ordering randomized
    64th Annual Symposium on Foundations of Computer Science (FOCS), 2023.

  • Subset Sum in Time $2^{n/2}/\poly(n)$.
    X. Chen and Y. Jin and T. Randolph and R. Servedio.
    27th Intl. Workshop on Randomization and Computation (RANDOM), 2023.

  • Approximate Trace Reconstruction from a Single Trace.
    X. Chen and A. De and C.-H. Lee and R. Servedio and S. Sinha.
    ACM-SIAM Symposium on Discrete Algorithms (SODA), 2023.

  • Testing Convex Truncation.
    A. De and S. Nadimpalli and R. Servedio.
    ACM-SIAM Symposium on Discrete Algorithms (SODA), 2023.

  • The perils of being unhinged: On the accuracy of classifiers minimizing a noise-robust convex loss.
    P. Long and R. Servedio.
    Neural Computation, 2022.

  • Near-Optimal Statistical Query Lower Bounds for Agnostically Learning Intersections of Halfspaces with Gaussian Marginals.
    D. Hsu and C. Sanford and R. Servedio and E.-V. Vlatakis-Gkaragkounis.
    35th Conference on Learning Theory (COLT), 2022.

  • Convex Influences.
    A. De and S. Nadimpalli and R. Servedio.
    Innovations in Theoretical Computer Science (ITCS), 2022.

  • Approximating Sumset Size.
    A. De and S. Nadimpalli and R. Servedio.
    ACM-SIAM Symposium on Discrete Algorithms (SODA), 2022.

  • Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces.
    X. Chen and A. De and C.-H. Lee and R. Servedio and S. Sinha.
    ACM-SIAM Symposium on Discrete Algorithms (SODA), 2022.

  • Average-Case Subset Balancing Problems.
    X. Chen and Y. Jin and T. Randolph and R. Servedio.
    ACM-SIAM Symposium on Discrete Algorithms (SODA), 2022.

  • Fourier growth of structured F_2-polynomials and applications.
    J. Błasiok and P. Ivanov and Y. Jin and C.-H. Lee and R. Servedio and E. Viola.
    25th Intl. Workshop on Randomization and Computation (RANDOM), 2021.

  • Deterministic approximate counting of polynomial threshold functions via a derandomized regularity lemma.
    R. Servedio and L.-Y. Tan. (*) Author ordering randomized
    25th Intl. Workshop on Randomization and Computation (RANDOM), 2021.

  • Weak learning convex sets under normal distributions.
    A. De and R. Servedio.
    34th Conference on Learning Theory (COLT), 2021.

  • On the Approximation Power of Two-Layer Networks of Random ReLUs.
    D. Hsu and C. Sanford and R. Servedio and E.-V. Vlatakis-Gkaragkounis.
    34th Conference on Learning Theory (COLT), 2021.

  • Learning sparse mixtures of permutations from noisy information.
    A. De and R. O'Donnell and R. Servedio.
    34th Conference on Learning Theory (COLT), 2021.

  • Reconstructing weighted voting schemes from partial information about their power indices.
    H. Bennett and A. De and R. Servedio and E.-V. Vlatakis-Gkaragkounis.
    34th Conference on Learning Theory (COLT), 2021.

  • Polynomial-time trace reconstruction in the low deletion rate regime.
    X. Chen and A. De and C.-H. Lee and R. Servedio and S. Sinha.
    Innovations in Theoretical Computer Science (ITCS), 2021.

  • Quantitative Correlation Inequalities via Semigroup Interpolation.
    A. De and S. Nadimpalli and R. Servedio.
    Innovations in Theoretical Computer Science (ITCS), 2021.

  • Polynomial-time trace reconstruction in the smoothed complexity model.
    X. Chen and A. De and C.-H. Lee and R. Servedio and S. Sinha.
    ACM-SIAM Symposium on Discrete Algorithms (SODA), 2021.

  • Sharp Bounds for Population Recovery.
    A. De and R. O'Donnell and R. Servedio.
    Theory of Computing, 16(6), 2020.

  • Fooling Gaussian PTFs via Local Hyperconcentration.
    R. O'Donnell and R. Servedio and L.-Y. Tan. (*) Author ordering randomized
    51th Annual Symposium on Theory of Computing (STOC), 2020.

  • Testing noisy linear functions for sparsity.
    X. Chen and A. De and R. Servedio.
    51th Annual Symposium on Theory of Computing (STOC), 2020.

  • Learning from satisfying assignments under continuous distributions.
    C. Canonne and A. De and R. Servedio.
    ACM-SIAM Symposium on Discrete Algorithms (SODA), 2020.

  • A lower bound on cycle finding in sparse digraphs.
    X. Chen and T. Randolph and R. Servedio and T. Sun.
    ACM-SIAM Symposium on Discrete Algorithms (SODA), 2020.

  • Beyond trace reconstruction: Population recovery from the deletion channel.
    F. Ban and X. Chen and A. Freilich and R. Servedio and S. Sinha.
    60th Annual Symposium on Foundations of Computer Science (FOCS), 2019.

  • Improved pseudorandom generators from pseudorandom multi-switching lemmas.
    R. Servedio and L.-Y. Tan.
    23rd Intl. Workshop on Randomization and Computation (RANDOM), 2019.

  • Efficient average-case population recovery in the presence of insertions and deletions.
    F. Ban and X. Chen and R. Servedio and S. Sinha.
    23rd Intl. Workshop on Randomization and Computation (RANDOM), 2019.

  • Simple and efficient pseudorandom generators from Gaussian processes.
    E. Chattopadhyay and A. De and R. Servedio.
    34th Computational Complexity Conference (CCC), 2019.

  • Fooling Polytopes.
    R. O'Donnell and R. Servedio and L.-Y. Tan.
    51th Annual Symposium on Theory of Computing (STOC), 2019.

  • Pseudorandomness for read-k DNF formulas.
    R. Servedio and L.-Y. Tan.
    ACM-SIAM Symposium on Discrete Algorithms (SODA), 2019.

  • Density estimation for shift-invariant multidimensional distributions.
    A. De and P. Long and R. Servedio.
    10th Innovations in Theoretical Computer Science Conference (ITCS), 2019.

  • Learning Sums of Independent Random Variables with Sparse Collective Support.
    A. De and P. Long and R. Servedio.
    59th Annual Symposium on Foundations of Computer Science (FOCS), 2018.

  • Luby-Velickovic-Wigderson revisited: Improved correlation bounds and pseudorandom generators for depth-two circuits.
    R. Servedio and L.-Y. Tan.
    22nd Intl. Workshop on Randomization and Computation (RANDOM), 2018.

  • Distribution-Free Junta Testing.
    Z. Liu and X. Chen and R.A. Servedio and Y. Sheng and J. Xie.
    50th Annual Symposium on Theory of Computing (STOC), 2018.

  • Deterministic search for CNF satisfying assignments in almost polynomial time.
    R. Servedio and L.-Y. Tan.
    58th Annual Symposium on Foundations of Computer Science (FOCS), 2017.

  • Fooling intersections of low-weight halfspaces.
    R. Servedio and L.-Y. Tan.
    58th Annual Symposium on Foundations of Computer Science (FOCS), 2017.

  • Sample-based high-dimensional convexity testing
    X. Chen and A. Freilich and R. Servedio and T. Sun.
    21st Intl. Workshop on Randomization and Computation (RANDOM), 2017.

  • Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces
    X. Chen and R. Servedio and L.-Y. Tan and E. Waingarten.
    21st Intl. Workshop on Randomization and Computation (RANDOM), 2017.

  • Settling the query complexity of non-adaptive junta testing
    X. Chen and R. Servedio and L.-Y. Tan and E. Waingarten and J. Xie.
    Computational Complexity Conference (CCC), 2017.
    Best Paper Award, CCC 2017.

  • Addition is exponentially harder than counting for shallow monotone circuits
    X. Chen and I. Oliveira and R. Servedio,
    49th Annual Symposium on Theory of Computing (STOC), 2017.

  • Optimal mean-based algorithms for trace reconstruction
    A. De and R. O'Donnell and R. Servedio,
    49th Annual Symposium on Theory of Computing (STOC), 2017.

  • What circuit classes can be learned with non-trivial savings?
    R. Servedio and L.-Y. Tan.
    8th Innovations in Theoretical Computer Science Conference (ITCS), 2017.

  • Degree and Sensitivity: Tails of Two Distributions.
    P. Gopalan and R. Servedio and A. Wigderson.
    IEEE Conference on Computational Complexity (CCC), 2016.

  • Poly-logarithmic Frege depth lower bounds via an expander switching lemma.
    T. Pitassi and B. Rossman and R. Servedio and L.-Y. Tan,
    48th Annual Symposium on Theory of Computing (STOC), 2016.

  • Near-optimal small-depth lower bounds for small distance connectivity.
    X. Chen and I. Oliveira and R. Servedio and L.-Y. Tan.
    48th Annual Symposium on Theory of Computing (STOC), 2016.

  • Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions.
    P. Gopalan and N. Nisan and R. Servedio and K. Talwar and A. Wigderson.
    7th Innovations in Theoretical Computer Science Conference (ITCS), 2016.

  • The Polynomial Hierarchy, Random Oracles, and Boolean Circuits
    B. Rossman and R. Servedio and L.-Y. Tan.
    SIGACT News Complexity Theory Column, 46(4), 2015.

  • An average-case depth hierarchy theorem for Boolean circuits.
    B. Rossman and R. Servedio and L.-Y. Tan.
    56th Annual Symposium on Foundations of Computer Science (FOCS), 2015.
    Best Paper Award, FOCS 2015.

  • Learning Circuits with Few Negations.
    E. Blais and C. Canonne and I. Oliveira and R. Servedio and L.-Y. Tan.
    19th Intl. Workshop on Randomization and Computation (RANDOM), 2015.

  • Adaptivity helps for testing juntas.
    R. Servedio and L.-Y. Tan and J. Wright.
    IEEE Conference on Computational Complexity (CCC), 2015.

  • Boolean function monotonicity testing requires (almost) n^{1/2} non-adaptive queries.
    X. Chen and A. De and R. Servedio and L.-Y. Tan.
    47th Annual Symposium on Theory of Computing (STOC), 2015.

  • Learning from Satisfying Assignments.
    A. De and I. Diakonikolas and R. Servedio.
    ACM-SIAM Symposium on Discrete Algorithms (SODA), 2015.

  • Noise stable halfspaces are close to very small juntas.
    I. Diakonikolas and R. Jaiswal and R. Servedio and L.-Y. Tan and A. Wan.
    Chicago Journal on Theoretical Computer Science, 2015.

  • Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms.
    S. Chan and I. Diakonikolas and R. Servedio and X. Sun.
    28th Annual Conference on Neural Information Processing Systems (NIPS), 2014.

  • New algorithms and lower bounds for monotonicity testing.
    X. Chen and R. Servedio and L.-Y. Tan.
    55th Annual Symposium on Foundations of Computer Science (FOCS), 2014.

  • On DNF Approximators for Monotone Boolean Functions.
    E. Blais and J. Håstad and R. Servedio and L.-Y. Tan.
    41st International Conference on Automata, Languages and Programming (ICALP), 2014.

  • Efficient Deterministic Approximate Counting for Low-Degree Polynomial Threshold Functions.
    A. De and R. Servedio.
    46th Annual Symposium on Theory of Computing (STOC), 2014.

  • Efficient Density Estimation via Piecewise Polynomial Approximation.
    S.O. Chan and I. Diakonikolas and R. Servedio and X. Sun,
    46th Annual Symposium on Theory of Computing (STOC), 2014.

  • Deterministic Approximate Counting for Juntas of Degree-2 Polynomial Threshold Functions.
    A. De and I. Diakonikolas and R. Servedio.
    IEEE Conference on Computational Complexity (CCC), 2014.

  • A polynomial time approximation scheme for fault-tolerant distributed storage.
    A. De and C. Daskalakis and I. Diakonikolas and A. Moitra and R. Servedio.
    ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014.

  • Testing equivalence between distributions using conditional samples.
    C. Canonne and D. Ron and R. Servedio.
    ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014.

  • Learning Sums of Independent Integer Random Variables.
    C. Daskalakis and I. Diakonikolas and R. O'Donnell and R. Servedio and L.-Y. Tan
    54th Annual Symposium on Foundations of Computer Science (FOCS), 2013.

  • A robust Khintchine inequality, and algorithms for computing optimal constants in Fourier analysis and high-dimensional geometry.
    A. De and I. Diakonikolas and R. Servedio.
    40th International Conference on Automata, Languages and Programming (ICALP), 2013.

  • Consistency versus Realizable $H$-Consistency for Multiclass Classification
    P. Long and R. Servedio.
    International Conference on Machine Learning (ICML), 2013.

  • On the Weight of Halfspaces over Hamming Balls.
    P. Long and R. Servedio.
    SIAM Journal on Discrete Math, 28(3), 2014.
    Preliminary version appeared as "Low-weight halfspaces for sparse Boolean vectors" in Innovations in Theoretical Computer Science (ITCS), 2013.

  • Learning mixtures of structured distributions over discrete domains.
    S. Chan and I. Diakonikolas and R. Servedio and X. Sun.
    ACM-SIAM Symposium on Discrete Algorithms (SODA), 2013.

  • Testing k-Modal Distributions: Optimal Algorithms via Reductions.
    C. Daskalakis and I. Diakonikolas and R. Servedio and G. Valiant and P. Valiant.
    ACM-SIAM Symposium on Discrete Algorithms (SODA), 2013.

  • Exponentially improved algorithms and lower bounds for testing signed majorities.
    D. Ron and R. Servedio.
    Algorithmica, December 2013.
    ACM-SIAM Symposium on Discrete Algorithms (SODA), 2013.

  • On a special case of rigidity.
    R. Servedio and E. Viola.
    ECCC Technical Report 144, 2012.

  • The Inverse Shapley Value Problem.
    A. De and I. Diakonikolas and R. Servedio.
    39th International Conference on Automata, Languages and Programming (ICALP), 2012.

  • Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial Threshold Functions.
    R. Servedio and L.-Y. Tan and J. Thaler.
    25th Annual Conference on Learning Theory (COLT), 2012.

  • Tight Bounds on Proper Equivalence Query Learning of DNF.
    L. Hellerstein and D. Kletenik and R. Servedio and L. Sellie.
    25th Annual Conference on Learning Theory (COLT), 2012.

  • Learning Poisson Binomial Distributions.
    C. Daskalakis and I. Diakonikolas and R. Servedio.
    44th Annual Symposium on Theory of Computing (STOC), 2012.

  • Nearly optimal solutions for the Chow Parameters Problem and low-weight approximation of halfspaces.
    A. De and I. Diakonikolas and V. Feldman and R. Servedio.
    J. ACM, 61(2), 2014.
    Preliminary version in 44th Annual Symposium on Theory of Computing (STOC), 2012.

  • Learning k-modal Distributions via Testing
    C. Daskalakis and I. Diakonikolas and R. Servedio.
    ACM-SIAM Symposium on Discrete Algorithms (SODA), 2012.

  • Private Data Release via Learning Thresholds
    M. Hardt and G. Rothblum and R. Servedio.
    ACM-SIAM Symposium on Discrete Algorithms (SODA), 2012.

  • Algorithms and hardness results for parallel large margin learning.
    P. Long and R. Servedio
    J. Machine Learning Research, 14(Oct), 2013.
    Preliminary version in 25th Annual Conference on Neural Information Processing Systems (NIPS), 2011.

  • Learning large-margin halfspaces with more malicious noise.
    P. Long and R. Servedio
    25th Annual Conference on Neural Information Processing Systems (NIPS), 2011.

  • A Canonical Form for Testing Boolean Function Properties.
    D. Dachman-Soled and R. Servedio.
    15th Intl. Workshop on Randomization and Computation (RANDOM), 2011.

  • Lower Bounds and Hardness Amplification for Learning Shallow Monotone Formulas.
    V. Feldman and H. Lee and R. Servedio.
    24th Annual Conference on Learning Theory (COLT), 2011.

  • Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions
    I. Diakonikolas and R. O'Donnell and R. Servedio and Y. Wu.
    ACM-SIAM Symposium on Discrete Algorithms (SODA), 2011.

  • Learning and Lower Bounds for AC0 Circuits with Threshold Gates.
    P. Gopalan and R. Servedio.
    14th Intl. Workshop on Randomization and Computation (RANDOM), 2010.

  • A Regularity Lemma, and Low-Weight Approximators, for Low-Degree Polynomial Threshold Functions.
    I. Diakonikolas and R. Servedio and L.-Y. Tan and A. Wan.
    Theory of Computing, 10(2), 2014.
    Preliminary version in 25th IEEE Conference on Computational Complexity (CCC), 2010.

  • Bounding the average sensitivity and noise sensitivity of polynomial threshold functions.
    I. Diakonikolas and P. Harsha and A. Klivans and R. Meka and P. Raghavendra and R. Servedio and L.-Y. Tan
    SIAM J. on Computing, 43(1), 2014.
    Preliminary version in 42nd Annual Symposium on Theory of Computing (STOC), 2010.

  • Restricted Boltzmann Machines are Hard to Approximately Evaluate or Simulate.
    P. Long and R. Servedio.
    27th International Conference on Machine Learning (ICML), 2010.

  • Testing by Implicit Learning: A Brief Survey.
    R. Servedio.
    Property Testing 2010.

  • Testing (Subclasses of) Halfspaces.
    K. Matulef and R. O'Donnell and R. Rubinfeld and R. Servedio.
    Property Testing 2010.

  • Bounded Independence Fools Halfspaces.
    I. Diakonikolas and P. Gopalan and R. Jaiswal and R. Servedio and E. Viola.
    SIAM Journal on Computing, 39(8), 2010.
    Preliminary version in 50th Annual Symposium on Foundations of Computer Science (FOCS), 2009.

  • Testing +1/-1 Weight Halfspaces.
    K. Matulef and R. O'Donnell and R. Rubinfeld and R. Servedio.
    13th International Workshop on Randomization and Computation (RANDOM), 2009.

  • Improved Approximation of Linear Threshold Functions.
    I. Diakonikolas and R. Servedio
    computational complexity, 2012.
    Preliminary version appeared in 24th Conference on Computational Complexity (CCC), 2009.

  • Learning Halfspaces with Malicious Noise.
    A. Klivans and P. Long and R. Servedio
    Journal of Machine Learning Research, 10(Dec), 2009.
    Preliminary version in 36th International Conference on Automata, Languages and Programming (ICALP), 2009.

  • Testing Fourier Dimensionality and Sparsity.
    P. Gopalan and R. O'Donnell and R. Servedio and A. Shpilka and K. Wimmer
    SIAM Journal on Computing, 40(4), 2011.
    Preliminary version in 36th International Conference on Automata, Languages and Programming (ICALP), 2009.

  • Testing Halfspaces.
    K. Matulef and R. Rubinfeld and R. O'Donnell and R. Servedio
    SIAM Journal on Computing, 39(5), 2010.
    Preliminary version in ACM-SIAM Symposium on Discrete Algorithms (SODA), 2009.

  • Adaptive Martingale Boosting.
    P. Long and R. Servedio
    22st Annual Conference on Neural Information Processing Systems (NIPS), 2008.

  • Learning Geometric Concepts via Gaussian Surface Area
    A. Klivans and R. O'Donnell and R. Servedio.
    49th Annual Symposium on Foundations of Computer Science (FOCS), 2008.

  • Learning Random Monotone DNF.
    J. Jackson and H. Lee and R. Servedio and A. Wan.
    Discrete Applied Mathematics, 159(5), 2011.
    Preliminary version in 12th International Workshop on Randomization and Computation (RANDOM), 2008.

  • Optimal Cryptographic Hardness of Learning Monotone Functions.
    D. Dachman-Soled and H. Lee and T. Malkin and R. Servedio and A. Wan and H. Wee.
    Theory of Computing, 5(1), 2009.
    Preliminary version in 35th International Conference on Automata, Languages and Programming (ICALP), 2008.

  • Efficiently Testing Sparse GF(2) Polynomials.
    I. Diakonikolas and H. Lee and K. Matulef and R. Servedio and A. Wan.
    Algorithmica, 61(3), 2011.
    Preliminary version in 35th International Conference on Automata, Languages and Programming (ICALP), 2008.

  • Random classification noise defeats all convex potential boosters.
    P. Long and R. Servedio.
    Machine Learning Journal, 78(3), 2010.
    Preliminary version in 25th International Conference on Machine Learning (ICML), 2008.

  • The Chow Parameters Problem.
    R. O'Donnell and R. Servedio.
    SIAM Journal on Computing, 40(1), 2011.
    Preliminary version in 40th Annual Symposium on Theory of Computing (STOC), 2008.

  • Testing for Concise Representations.
    I. Diakonikolas and H. Lee and K. Matulef and K. Onak and R. Rubinfeld and R. Servedio and A. Wan.
    48th Annual Symposium on Foundations of Computer Science (FOCS), 2007.

  • One-Pass Boosting.
    Z. Barutcuoglu and P. Long and R. Servedio.
    21st Annual Conference on Neural Information Processing Systems (NIPS), 2007.

  • Boosting the Area under the ROC Curve.
    P. Long and R. Servedio.
    21st Annual Conference on Neural Information Processing Systems (NIPS), 2007.

  • Distribution-Free Testing Lower Bounds for Basic Boolean Functions.
    D. Glasner and R. Servedio.
    Theory of Computing, 5(1), 2009.
    11th International Workshop on Randomization and Computation (RANDOM), 2007.

  • Quantum Algorithms for Learning and Testing Juntas.
    A. Atici and R. Servedio
    Quantum Information Processing 6(5), 2007.

  • Highly Efficient Secrecy-Preserving Proofs of Correctness of Computations and Applications.
    M. Rabin and R. Servedio and C. Thorpe.
    22nd IEEE Symposium on Logic in Computer Science (LICS), 2007.

  • Discriminative Learning can Succeed where Generative Learning Fails.
    P. Long, R. Servedio and H.-U. Simon
    Information Processing Letters, 103(4), 2007.

  • Attribute-efficient learning of decision lists and linear threshold functions under unconcentrated distributions.
    P. Long and R. Servedio.
    20th Annual Conference on Neural Information Processing Systems (NIPS), 2006.

  • Learning Unions of \omega(1)-Dimensional Rectangles.
    A. Atici and R. Servedio.
    Theoretical Computer Science, 405(3), 2008.
    Seventeenth International Conference on Algorithmic Learning Theory (ALT), 2006.
    Best Student Paper Award, ALT 2006.

  • DNF are Teachable in the Average Case.
    H. Lee and R. Servedio and A. Wan.
    Machine Learning, 69, 2007.
    Preliminary version in Nineteenth Annual Conference on Computational Learning Theory (COLT), 2006.

  • PAC Learning Mixtures of Axis-Aligned Gaussians with No Separation Assumption.
    J. Feldman and R. O'Donnell and R. Servedio.
    Nineteenth Annual Conference on Computational Learning Theory (COLT), 2006.

  • Learning Monotone Decision Trees in Polynomial Time.
    R. O'Donnell and R. Servedio.
    SIAM Journal on Computing, 37(3), 2007, pp. 827--844.
    Preliminary version in Eighteenth Annual Conference on Computational Complexity (CCC), 2006.

  • Every linear threshold function has a low-weight approximator.
    R. Servedio.
    computational complexity 16(2), 2007 (special issue for CCC 2006).
    Preliminary version in 21st Annual Conference on Computational Complexity (CCC), 2006.

  • On PAC learning algorithms for rich Boolean function classes.
    L. Hellerstein and R. Servedio.
    Theoretical Computer Science 384(1), 2007.
    Preliminary version in 3rd Annual Conference on Theory and Applications of Models of Computation (TAMC), 2006. (Invited paper.)

  • Improved Bounds on Quantum Learning Algorithms.
    A. Atici and R. Servedio.
    Quantum Information Processing, 4(5), 2005.

  • Agnostically Learning Halfspaces.
    A. Kalai and A. Klivans and Y. Mansour and R. Servedio.
    SIAM Journal on Computing, 37(6), 2008.
    46th Symposium on Foundations of Computer Science (FOCS), 2005.

  • Every decision tree has an influential variable.
    R. O'Donnell and M. Saks and O. Schramm and R. Servedio.
    46th Symposium on Foundations of Computer Science (FOCS), 2005.

  • Learning Mixtures of Product Distributions over Discrete Domains.
    J. Feldman and R. O'Donnell and R. Servedio.
    SIAM Journal of Computing, 37(5), 2008.
    Preliminary version in 46th Symposium on Foundations of Computer Science (FOCS), 2005.

  • On Learning Random DNF Formulas under the Uniform Distribution.
    J. Jackson and R. Servedio.
    Theory of Computing, 2, 2006.
    Preliminary version in 9th International Workshop on Randomness and Computation (RANDOM), 2005.

  • Unsupervised Evidence Integration.
    P. Long and V. Varadan and S. Gilman and M. Treshock and R. Servedio.
    22nd International Conference on Machine Learning (ICML), 2005.

  • Separating Models of Learning from Correlated and Uncorrelated Data.
    A. Elbaz and H. Lee and R. Servedio and A. Wan.
    Journal of Machine Learning Research 8(Feb), 2007.
    Preliminary version in Eighteenth Annual Conference on Computational Learning Theory (COLT), 2005.

  • Martingale Boosting.
    P. Long and R. Servedio.
    Eighteenth Annual Conference on Computational Learning Theory (COLT), 2005.

  • Testing Monotone High-Dimensional Distributions.
    R. Rubinfeld and R. Servedio.
    Random Structures and Algorithms, 34(1), 2009.
    Preliminary version in 37th Annual Symposium on Theory of Computing (STOC), 2005.

  • Computing Sparse Permanents Faster.
    R. Servedio and A. Wan.
    Information Processing Letters 96(5), 2005.

  • On the Capacity of Secure Network Coding.
    J. Feldman and T. Malkin and R. Servedio and C. Stein.
    42nd Annual Allerton Conference on Communication, Control, and Computing, 2004.

  • Toward Attribute-Efficient Learning of Decision Lists and Parities.
    A. Klivans and R. Servedio.
    Journal of Machine Learning Research 7(Apr), 2006.
    Preliminary version in Seventeenth Annual Conference on Computational Learning Theory (COLT), 2004.

  • Learning Intersections of Halfspaces with a Margin.
    A. Klivans and R. Servedio.
    Journal of Computer and System Sciences 74, 2008.
    Preliminary version in Seventeenth Annual Conference on Computational Learning Theory (COLT), 2004.

  • LP Decoding Corrects a Constant Fraction of Error.
    J. Feldman and T. Malkin and R. Servedio and C. Stein and M. Wainwright.
    IEEE Transactions on Information Theory 53(1), 2007.
    Preliminary version in IEEE International Symposium on Information Theory (ISIT), 2004.

  • Monotone Boolean Formulas can Approximate Monotone Linear Threshold Functions.
    R. Servedio.
    Discrete Applied Mathematics 142(1-3), 2004.

  • Learning DNF from Random Walks.
    N. Bshouty and E. Mossel and R. O'Donnell and R. Servedio.
    Journal of Computer and System Sciences 71(3), 2005 (special issue for STOC, FOCS, and COLT 2003).
    Preliminary version in 44th Annual Symposium on Foundations of Computer Science (FOCS), 2003.

  • Maximum Margin Algorithms with Boolean Kernels.
    R. Khardon and R. Servedio.
    Journal of Machine Learning Research 6(Sep), 2005.
    Preliminary version in Sixteenth Annual Conference on Computational Learning Theory (COLT), 2003.

  • Polynomial Certificates for Propositional Classes.
    M. Arias and A. Feigelson and R. Khardon and R. Servedio.
    Information and Computation, 204(5), 2006.
    Preliminary version in Sixteenth Annual Conference on Computational Learning Theory (COLT), 2003.

  • Learning Random Log-Depth Decision Trees under the Uniform Distribution.
    J. Jackson and R. Servedio.
    SIAM Journal on Computing 34(5), 2005.
    Preliminary version appeared in Sixteenth Annual Conference on Computational Learning Theory (COLT), 2003.

  • Extremal Properties of Polynomial Threshold Functions.
    R. O'Donnell and R. Servedio.
    Journal of Computer and System Sciences 74(3), 2008. (special issue for CCC 2003).
    Preliminary version appeared in Eighteenth Annual Conference on Computational Complexity (CCC), 2003.
    Best Paper award, CCC 2003.

  • New Degree Bounds for Polynomial Threshold Functions.
    R. O'Donnell and R. Servedio.
    Combinatorica 30(3), 2010.
    Preliminary version in 35th Annual Symposium on Theory of Computing (STOC), 2003.

  • Learning functions of k relevant variables.
    E. Mossel and R. O'Donnell and R. Servedio.
    Journal of Computer and System Sciences 69(3), 2004 (special issue for STOC 2003).
    Preliminary version "Learning Juntas" in 35th Annual Symposium on Theory of Computing (STOC), 2003.

  • Boosting in the Presence of Noise.
    A. Kalai and R. Servedio.
    Journal of Computer and System Sciences 71(3), 2005 (special issue for STOC, FOCS, and COLT 2003).
    Preliminary version in 35th Annual Symposium on Theory of Computing (STOC), 2003.

  • On Learning Embedded Midbit Functions.
    R. Servedio.
    Theoretical Computer Science 350(1), 2006 (special issue for ALT 2002).
    Preliminary version in Thirteenth International Conference on Algorithmic Learning Theory (ALT), 2002.

  • Learning Intersections and Thresholds of Halfspaces.
    A. Klivans and R. O'Donnell and R. Servedio.
    Journal of Computer and System Sciences 68(4), 2004 (special issue for FOCS 2002).
    Preliminary version in 43rd Annual Symposium on Foundations of Computer Science (FOCS), 2002.

  • Learnability Beyond AC^0.
    J. Jackson and A. Klivans and R. Servedio.
    34th Annual Symposium on Theory of Computing (STOC), 2002.
    One-page abstract also appeared in Seventeenth Annual Conference on Computational Complexity (CCC), 2002.

  • Efficiency versus Convergence of Boolean Kernels for Online Learning Algorithms.
    R. Khardon and D. Roth and R. Servedio.
    Journal of Artificial Intelligence Research 24(Sep), 2005.
    Preliminary version in Advances in Neural Information Processing Systems 14 (NIPS), 2001.

  • Learning DNF in Time 2^{O(n^{1/3})}.
    A. Klivans and R. Servedio.
    Journal of Computer and System Sciences 68(2), 2004 (special issue for STOC 2001).
    Preliminary version in 33rd Annual Symposium on Theory of Computing (STOC), 2001.
    Best Student Paper award, STOC 2001.

  • Efficient Algorithms in Computational Learning Theory.
    R. Servedio.
    Ph.D. thesis, Harvard University, May 2001.

  • On the Limits of Efficient Teachability.
    R. Servedio.
    Information Processing Letters 79(6), 2001.

  • On Learning Monotone DNF under Product Distributions.
    R. Servedio.
    Information and Computation 193, 2004.
    Preliminary version in Fourteenth Annual Conference on Computational Learning Theory (COLT), 2001.

  • Smooth Boosting and Learning with Malicious Noise.
    R. Servedio.
    Journal of Machine Learning Research, 4(Sep), 2003.
    Preliminary version in Fourteenth Annual Conference on Computational Learning Theory (COLT), 2001.

  • Separating Quantum and Classical Learning.
    R. Servedio.
    28th International Conference on Automata, Languages and Programming (ICALP), 2001.

  • Quantum versus Classical Learnability.
    S. Gortler and R. Servedio.
    Sixteenth Annual Conference on Computational Complexity (CCC), 2001.
    A combined version which also includes results from ICALP 01 paper appeared as Equivalences and Separations between Quantum and Classical Learnability in SIAM Journal on Computing 33(5), 2004.

  • PAC Analogues of Perceptron and Winnow via Boosting the Margin.
    R. Servedio.
    Machine Learning 47(2/3), 2002 (special issue for COLT 2000).
    Preliminary version in Thirteenth Annual Conference on Computational Learning Theory (COLT), 2000.
    Best Student Paper award, COLT 2000.

  • Computational Sample Complexity and Attribute-Efficient Learning.
    R. Servedio.
    Journal of Computer and System Sciences 60(1), 2000.
    Preliminary version in 31st Annual Symposium on Theory of Computing (STOC), 1999.

  • Boosting and Hard-Core Sets.
    A. Klivans and R. Servedio.
    Machine Learning 53(3), 2003 (special issue on Computational Learning Theory).
    Preliminary version in 40th Annual Symposium on Foundations of Computer Science (FOCS), 1999.

  • Perceptron, Winnow, and PAC Learning.
    R. Servedio.
    SIAM Journal on Computing 31(5), 2002.
    Preliminary version in Twelfth Annual Conference on Computational Learning Theory (COLT), 1999.

  • A Bijective Proof on Circular Compositions.
    R. Servedio and Y-N. Yeh.
    Bulletin of the Institute of Mathematics, Academia Sinica 23(4), 1995.

    "By day and night he measured and calculated; covered enormous quantities of paper with figures, letters, computations, algebraic symbols; his face, which was the face of an apparantly sound and vigorous man, wore the morose and visionary stare of a monomaniac; while his conversation, with consistent and fearful monotony, dealt with the proportional number pi...Everybody shunned the devoted Paravant like the plague"

    T. Mann, The Magic Mountain

    "If you can't understand it without an explanation, you can't understand it with an explanation."

    H. Murakami, 1Q84

    Back to my home page