Adam Klivans's Publications

    Back to my homepage


  • Learning Geometric Concepts via Gaussian Surface Area
    (In this paper we give a subexponential-time algorithm for learning all convex sets with respect to Gaussian distributions.)
    Adam R. Klivans, Ryan O'Donnell, Rocco Servedio.
    To Appear in FOCS 2008.

  • A Query Algorithm for Agnostically Learning DNF?, a 2-page open problem.
    Parikshit Gopalan, Adam T. Kalai, Adam R. Klivans
    To Appear in COLT 2008.

  • Agnostically Learning Decision Trees
    Parikshit Gopalan, Adam T. Kalai, Adam R. Klivans.
    In the Proceedings of the 40th ACM Symposium on Theory of Computing (STOC), 2008.

  • List-Decoding Reed Muller Codes over Small Fields
    Parikshit Gopalan, Adam R. Klivans, David Zuckerman.
    In the Proceedings of the 40th ACM Symposium on Theory of Computing (STOC), 2008.

  • A Lower Bound for Agnostically Learning Disjunctions
    Adam R. Klivans, Alexander A. Sherstov.
    In the Proceedings of the 20th Conference on Learning Theory (COLT), 2007.

  • Cryptographic Hardness for Learning Intersections of Halfspaces
    Adam R. Klivans, Alexander A. Sherstov.
    In the Proceedings of the 47th Foundations of Computer Science (FOCS), 2006.
    Invited to appear in a special issue of the Journal of Computer and System Sciences.

  • Improved Lower Bounds for Learning Intersections of Halfspaces
    Adam R. Klivans, Alexander A. Sherstov.
    In the Proceedings of the 19th Conference on Learning Theory (COLT), 2006.
    Invited to appear in a special issue of Machine Learning Journal.

  • Efficient Learning Algorithms Yield Circuit Lower Bounds
    Lance Fortnow, Adam R. Klivans.
    In the Proceedings of the 19th Conference on Learning Theory (COLT), 2006.
    Invited to appear in a special issue of the Journal of Computer and System Sciences.

  • Linear Advice for Randomized Logarithmic Space
    Lance Fortnow, Adam R. Klivans.
    In the Proceedings of the 23rd International Symposium on Theoretical Aspects of Computer Science (STACS), 2006.

  • Agnostically Learning Halfspaces
    Adam Kalai, Adam R. Klivans, Yishay Mansour, Rocco Servedio
    In the Proceedings of the 46th Foundations of Computer Science (FOCS), 2005.
    Invited to appear in a special issue of SICOMP Journal on Computing.

  • NP with Small Advice
    Lance Fortnow, Adam R. Klivans.
    To Appear in the Proceedings of the 20th Annual Conference on Computational Complexity (CCC), 2005.

  • Learnability and Automatizability
    Misha Alekhnovich, Mark Braverman, Vitaly Feldman, Adam Klivans, Toniann Pitassi.
    Proceedings of the 45th Foundations of Computer Science (FOCS), 2004.
    Invited to appear in a special issue of the Journal of Computer and System Sciences.

  • Perceptron-Like Performance for Learning Intersections of Halfspaces, a 2-page open problem.
    Adam R. Klivans, Rocco Servedio.
    Proceedings of the 17th Annual Conference on Learning Theory (COLT), 2004.

  • Learning Intersections of Halfspaces with a Margin
    Adam R. Klivans, Rocco Servedio.
    Proceedings of the 17th Annual Conference on Learning Theory (COLT), 2004.
    Invited to appear in a a special issue of the Journal of Computer and System Sciences.

  • Toward Attribute Efficient Learning Algorithms
    Adam R. Klivans, Rocco Servedio.
    Proceedings of the 17th Annual Conference on Learning Theory (COLT), 2004.

  • Learning Arithmetic Circuits
    Adam R. Klivans, Amir Shpilka.
    Proceedings of the 16th Annual Conference on Learning Theory (COLT), 2003.

  • Learning Intersections and Thresholds of Halfspaces
    Adam R. Klivans, Ryan O'Donnell, Rocco Servedio.
    Proceedings of the 43rd Foundations of Computer Science (FOCS), 2002.
    Invited to appear in a special issue of the Journal of Computer and System Sciences.

  • A Complexity-Theoretic Approach to Learning
    Adam R. Klivans
    Ph.D. Thesis, MIT, 2002. [Abstract]

  • Learnability Beyond AC^0
    Jeff Jackson, Adam R. Klivans, Rocco Servedio.
    Proceedings of the 34th Symposium on Theory of Computing (STOC) and the 17th Conference on Computational Complexity (CCC), 2002.

  • On the Derandomization of Constant Depth Circuits
    Adam R. Klivans
    Proceedings of the 5th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), 2001.

  • Learning DNF in Time $2^{O(n^{1/3})}$
    Adam R. Klivans, Rocco A. Servedio.
    Proceedings of the 33rd Symposium on Theory of Computing (STOC), 2001.
    Winner, Best Student Paper.
    Invited to appear in a special issue of the Journal of Computer and System Sciences.

  • Randomness Efficient Identity Testing
    Adam R. Klivans, Daniel A. Spielman.
    Proceedings of the 33rd Symposium on Theory of Computing (STOC), 2001.

  • Boosting and Hard-Core Sets
    Adam R. Klivans, Rocco A. Servedio.
    Proceedings of 40th Foundations of Computer Science (FOCS), 1999.
    Invited to appear in a special issue of Machine Learning Journal.

  • Graph NonIsomorphism has Subexponential Size Proofs unless the Polynomial-Time Hierarchy Collapses
    Adam R. Klivans, Dieter van Melkebeek.
    Proceedings of 31st Symposium on the Theory of Computing (STOC), 1999.
    In SIAM Journal on Computing 2002. Journal Version.

  • Factoring Polynomials Modulo Composites
    Adam R. Klivans.
    Master's Thesis, CMU CS Technical Report CMU-CS-97-136.

    Some research supported by an NSF Mathematical Sciences Postdoctoral Fellowship