Learning Theory, Computational Complexity, Pseudorandomness, Limit Theorems, and Gaussian Space.

Publications:

A Smoothed Analysis for Learning Sparse Polynomials
Alex Dimakis, Adam R. Klivans, Murat Kocaoglu, and Karthikeyan Shanmugam.
Submitted

Embedding Hard Learning Problems into Gaussian Space
Adam R. Klivans and Pravesh Kothari.
Submitted

Learning Halfspaces under Log-Concave Densities: Polynomial Approximations and Moment-Matching
Daniel Kane, Adam R. Klivans, and Raghu Meka.
In the Proceedings of the 26th Conference on Learning Theory (COLT), 2013.

Constructing Hard Functions from Learning Algorithms.
Adam R. Klivans, Igor C. Oliveira, and Pravesh Kothari.
In the Proceedings of the 28th Annual Conference on Computational Complexity (CCC), 2013.

Moment-Matching Polynomials
Adam R. Klivans, Raghu Meka.
Manuscript, 2013.

An Explicit VC-Theorem for Low-Degree Polynomials
Eshan Chattopadhyay, Adam R. Klivans, Pravesh Kothari.
In the Proceedings of RANDOM, 2012.

Learning Functions of Halfspaces Using Prefix Covers
Parikshit Gopalan, Adam R. Klivans, Raghu Meka.
In the Proceedings of the 25th Conference on Learning Theory (COLT), 2012.

Submodular Functions are Noise Stable
Mahdi Cheraghchi, Adam R. Klivans, Pravesh Kothari, Homin Lee.
In the Proceedings of the 23rd ACM Symposium on Discrete Algorithms (SODA), 2012.

An FPTAS for #Knapsack and Related Counting Problems
Parikshit Gopalan, Adam R. Klivans, Raghu Meka, Daniel Stefankovic, Santosh Vempala, Eric Vigoda.
In the Proceedings of the 52nd Foundations of Computer Science (FOCS), 2011.

Polynomial-Time Approximation Schemes for Knapsack and Related Counting Problems Using Branching Programs
Parikshit Gopalan, Adam R. Klivans, Raghu Meka.
Manuscript, 2011.

Mansour's Conjecture is True for Random DNF Formulas
Adam R. Klivans, Homin Lee, Andrew Wan.
In the Proceedings of the 23rd Conference on Learning Theory (COLT), 2010.

An Invariance Principle for Polytopes
Prahladh Harsha, Adam R. Klivans, Raghu Meka.
In the Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC), 2010.
To Appear in the Journal of the ACM.

Bounding the Sensitivity of Polynomial Threshold Functions
Prahladh Harsha, Adam R. Klivans, Raghu Meka.
Invited to appear in a special issue of Theory of Computing.
In the Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC), 2010.
(Conference version to be merged with this paper by Diakonikolas, Raghavendra, Servedio, and Tan)

Baum's Algorithm Learns Intersections of Halfspaces with respect to Log-Concave Distributions
Adam R. Klivans, Philip M. Long, Alex Tang.
In the Proceedings of RANDOM 2009.

Learning Halfspaces with Malicious Noise
Adam R. Klivans, Philip M. Long, Rocco A. Servedio.
In the Proceedings of ICALP 2009.

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.
In the Proceedings of the 49th Foundations of Computer Science (FOCS), 2008.

A Query Algorithm for Agnostically Learning DNF?, a 2-page open problem.
Parikshit Gopalan, Adam T. Kalai, Adam R. Klivans
In the Proceedings of the 21st Conference on Learning Theory (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.

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

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