Rocco Servedio: Papers

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

• Random classification noise defeats all convex potential boosters.
  P. Long and R. Servedio.
  25th International Conference on Machine Learning (ICML), 2008.

• The Chow Parameters Problem.
  R. O'Donnell and R. Servedio.
  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.
  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.
  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.
  R. Servedio.
  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.
  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.
  To appear in SIAM Journal of Computing.
  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.
  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.
  To appear in Journal of Computer and System Sciences (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.
  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.

Back to my home page