# Adam R. Klivans

According to our database

Collaborative distances:

^{1}, Adam R. Klivans authored at least 63 papers between 1998 and 2019.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### Homepages:

#### On csauthors.net:

## Bibliography

2019

List-decodable Linear Regression.

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Time/Accuracy Tradeoffs for Learning a ReLU with respect to Gaussian Marginals.

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Learning Ising Models with Independent Failures.

Proceedings of the Conference on Learning Theory, 2019

Learning Neural Networks with Two Nonlinear Layers in Polynomial Time.

Proceedings of the Conference on Learning Theory, 2019

2018

Learning One Convolutional Layer with Overlapping Patches.

Proceedings of the 35th International Conference on Machine Learning, 2018

Hyperparameter optimization: a spectral approach.

Proceedings of the 6th International Conference on Learning Representations, 2018

Efficient Algorithms for Outlier-Robust Regression.

Proceedings of the Conference On Learning Theory, 2018

2017

Learning Depth-Three Neural Networks in Polynomial Time.

CoRR, 2017

Eigenvalue Decay Implies Polynomial-Time Learnability for Neural Networks.

Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

Exact MAP Inference by Avoiding Fractional Vertices.

Proceedings of the 34th International Conference on Machine Learning, 2017

Learning Graphical Models Using Multiplicative Weights.

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Reliably Learning the ReLU in Polynomial Time.

Proceedings of the 30th Conference on Learning Theory, 2017

2016

Cryptographic Hardness of Learning.

Encyclopedia of Algorithms, 2016

Preserving Randomness for Adaptive Algorithms.

Electronic Colloquium on Computational Complexity (ECCC), 2016

2014

Bounding the Sensitivity of Polynomial Threshold Functions.

Theory of Computing, 2014

Embedding Hard Learning Problems into Gaussian Space.

Electronic Colloquium on Computational Complexity (ECCC), 2014

A Smoothed Analysis for Learning Sparse Polynomials.

CoRR, 2014

Sparse Polynomial Learning and Graph Sketching.

Proceedings of the Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, 2014

2013

Moment-Matching Polynomials.

Electronic Colloquium on Computational Complexity (ECCC), 2013

Constructing Hard Functions from Learning Algorithms.

Electronic Colloquium on Computational Complexity (ECCC), 2013

Learning Halfspaces Under Log-Concave Densities: Polynomial Approximations and Moment Matching.

Proceedings of the COLT 2013, 2013

Constructing Hard Functions Using Learning Algorithms.

Proceedings of the 28th Conference on Computational Complexity, CCC 2013, K.lo Alto, 2013

2012

Learning Functions of Halfspaces using Prefix Covers.

Proceedings of the COLT 2012, 2012

An invariance principle for polytopes.

J. ACM, 2012

An Explicit VC-Theorem for Low-Degree Polynomials.

Electronic Colloquium on Computational Complexity (ECCC), 2012

2011

Submodular Functions Are Noise Stable.

Electronic Colloquium on Computational Complexity (ECCC), 2011

An FPTAS for #Knapsack and Related Counting Problems.

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010

Mansour's Conjecture is True for Random DNF Formulas.

Electronic Colloquium on Computational Complexity (ECCC), 2010

Polynomial-Time Approximation Schemes for Knapsack and Related Counting Problems using Branching Programs.

Electronic Colloquium on Computational Complexity (ECCC), 2010

Lower Bounds for Agnostic Learning via Approximate Rank.

Computational Complexity, 2010

Bounding the average sensitivity and noise sensitivity of polynomial threshold functions.

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

2009

Learning Halfspaces with Malicious Noise.

J. Mach. Learn. Res., 2009

Cryptographic hardness for learning intersections of halfspaces.

J. Comput. Syst. Sci., 2009

Efficient learning algorithms yield circuit lower bounds.

J. Comput. Syst. Sci., 2009

Baum's Algorithm Learns Intersections of Halfspaces with Respect to Log-Concave Distributions.

Proceedings of the Approximation, 2009

2008

Cryptographic Hardness of Learning.

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Agnostically Learning Halfspaces.

SIAM J. Comput., 2008

Learning intersections of halfspaces with a margin.

J. Comput. Syst. Sci., 2008

The complexity of properly learning simple concept classes.

J. Comput. Syst. Sci., 2008

List-decoding reed-muller codes over small fields.

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Agnostically learning decision trees.

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Learning Geometric Concepts via Gaussian Surface Area.

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

A Query Algorithm for Agnostically Learning DNF?.

Proceedings of the 21st Annual Conference on Learning Theory, 2008

2007

Unconditional lower bounds for learning intersections of halfspaces.

Machine Learning, 2007

A Lower Bound for Agnostically Learning Disjunctions.

Proceedings of the Learning Theory, 20th Annual Conference on Learning Theory, 2007

2006

Learning Restricted Models of Arithmetic Circuits.

Theory of Computing, 2006

Toward Attribute Efficient Learning of Decision Lists and Parities.

J. Mach. Learn. Res., 2006

Cryptographic Hardness Results for Learning Intersections of Halfspaces.

Electronic Colloquium on Computational Complexity (ECCC), 2006

Improved Lower Bounds for Learning Intersections of Halfspaces.

Proceedings of the Learning Theory, 19th Annual Conference on Learning Theory, 2006

2005

Linear Advice for Randomized Logarithmic Space

Electronic Colloquium on Computational Complexity (ECCC), 2005

2004

Learning DNF in time 2

^{Õ(n1/3)}.
J. Comput. Syst. Sci., 2004

Learning intersections and thresholds of halfspaces.

J. Comput. Syst. Sci., 2004

NP with Small Advice

Electronic Colloquium on Computational Complexity (ECCC), 2004

Learnability and Automatizability.

Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

Perceptron-Like Performance for Intersections of Halfspaces.

Proceedings of the Learning Theory, 17th Annual Conference on Learning Theory, 2004

2003

Boosting and Hard-Core Set Construction.

Machine Learning, 2003

Toward Attribute Efficient Learning Algorithms

CoRR, 2003

Learning Arithmetic Circuits via Partial Derivatives.

Proceedings of the Computational Learning Theory and Kernel Machines, 2003

2002

Learnability beyond AC0.

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

2001

Randomness efficient identity testing of multivariate polynomials.

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

On the Derandomization of Constant Depth Circuits.

Proceedings of the Approximation, 2001

1999

Boosting and Hard-Core Sets.

Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

1998

Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses.

Electronic Colloquium on Computational Complexity (ECCC), 1998