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