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

  • 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, to appear.

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

  • 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.
    39th International Conference on Automata, Languages and Programming (ICALP), 2013.

  • Low-weight halfspaces for sparse Boolean vectors.
    P. Long and R. Servedio.
    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.

  • A near-optimal algorithm and lower bound for testing signed majorities.
    D. Ron and R. Servedio.
    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.
    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
    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.
    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
    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.

  • 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.

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

    V. Nabokov, Lolita

    "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

    Back to my home page