Adam Klivans's Publications

Time/Accuracy Tradeoffs for Learning a ReLU with respect to Gaussian Marginals
Surbhi Goel, Sushrut Karmalkar, Adam Klivans
To Appear, NeurIPS, 2019 (Spotlight).
We show that finding the best fitting ReLU with respect to squareloss, even when the marginal is Gaussian, is computationally hard, and we give the first efficient approximation algorithm.

ListDecodable Linear Regression
Sushrut Karmalkar, Adam Klivans, Pravesh Kothari
To Appear, NeurIPS, 2019 (Spotlight).
We give the first efficient algorithm for robust regression in the listdecodable setting where an adversary can corrupt a greater than 1/2 fraction of examples.

Learning Ising Models with Independent Failures
Surbhi Goel, Daniel Kane, Adam Klivans
To appear in COLT, 2019.
We give the first efficient algorithm for learning Ising
models when each entry is corrupted with some fixed
probability.
Learning Neural Networks with Two Nonlinear Layers in Polynomial Time
Surbhi Goel, Adam Klivans
To appear in COLT, 2019.
We give the first assumptionfree, provably efficient algorithm for learning neural networks with two nonlinear layers.

Preserving Randomness
for Adaptive Algorithms
William Hoza, Adam Klivans
In the proceedings of RANDOM, 2018.
For any randomized estimation algorithm that uses n random bits, we show how to run the algorithm on k adaptively chosen inputs using n + O(k) random bits, an essentially optimal bound.

Efficient Algorithms
for OutlierRobust Regression
Adam Klivans, Pravesh Kothari, Raghu Meka
In the proceedings of COLT, 2018.
We give the first efficient algorithm for performing
leastsquares regression resilient to adversarial corruptions in
both examples and labels.

Learning One
Convolutional Layer with Overlapping Patches
Surbhi Goel, Adam Klivans, Raghu Meka
In the proceedings of ICML, 2018 (full oral).
We give the first provably efficient algorithm for learning a one
layer CNN with respect to a broad class of overlapping patch structures.

Hyperparameter Optimzation: A Spectral
Approach
Elad Hazan, Adam Klivans, Yang Yuan
In the proceedings of ICLR, 2018.
Selected oral presentation, NIPS workshop on Deep Learning: Theory and
Practice, 2017.
We use techniques from the analysis of Boolean functions to give
improved algorithms for hyperparameter optimization.

Eigenvalue Decay Implies
PolynomialTime Learnability for Neural Networks
Surbhi Goel, Adam Klivans
In NIPS, 2017.
We give the first assumption on only the marginal distribution that implies efficient learnability for deep networks.

Learning Graphical Models Using Multiplicative
Weights
Adam Klivans, Raghu Meka
In FOCS 2017.
We give an algorithm, Sparsitron, that learns all undirected
graphical models (finite alphabet) with essentially optimal runtime and sample
complexity.

Reliably Learning the ReLU in Polynomial Time
Surbhi Goel, Varun Kanade, Adam Klivans, Justin Thaler
In COLT, 2017.
Selected Oral Presentation, NIPS 2016 Workshop on Optimization in ML (OptML).

Exact MAP Inference by Avoiding Fractional Vertices
Erik Lindgren, Alex Dimakis, Adam Klivans
In ICML, 2017.

2014, 2015: On Leave.

Sparse Polynomial Learning and Graph Sketching.
Alex Dimakis, Adam R. Klivans, Murat Kocaoglu, and Karthikeyan Shanmugam.
In NIPS, 2014 (oral presentation).

Embeddings Hard Learning Problems into Gaussian Space.
Adam R. Klivans and Pravesh Kothari.
In the Proceedings of RANDOM, 2014.

Learning Halfspaces under LogConcave Densities: Polynomial Approximations and MomentMatching
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.

MomentMatching Polynomials
Adam R. Klivans, Raghu Meka.
Manuscript, 2013.

An Explicit VCTheorem for LowDegree 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.

PolynomialTime 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 LogConcave 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 subexponentialtime 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 2page 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.

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

PerceptronLike Performance for Learning Intersections of Halfspaces, a 2page 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 ComplexityTheoretic 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 HardCore 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 PolynomialTime 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 CMUCS97136.
Some research supported by an NSF Mathematical Sciences Postdoctoral Fellowship