Adam R. Klivans

Arsen Vasilyan

CoRR, 2023

An Efficient Tester-Learner for Halfspaces.

[BibT_eX]

[DOI]

Arsen Vasilyan

CoRR, 2023

A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity.

[BibT_eX]

[DOI]

Pravesh K. Kothari

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Learning Mixtures of Gaussians Using the DDPM Objective.

[BibT_eX]

[DOI]

Kulin Shah

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Tester-Learners for Halfspaces: Universal Algorithms.

[BibT_eX]

[DOI]

Arsen Vasilyan

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Agnostically Learning Single-Index Models using Omnipredictors.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Ambient Diffusion: Learning Clean Distributions from Corrupted Data.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

HotProtein: A Novel Framework for Protein Thermostability Prediction and Editing.

[BibT_eX]

[DOI]

Proceedings of the Eleventh International Conference on Learning Representations, 2023

One-Dimensional Deep Image Prior for Curve Fitting of S-Parameters from Electromagnetic Solvers.

[BibT_eX]

[DOI]

Proceedings of the IEEE/ACM International Conference on Computer Aided Design, 2023

Learning Narrow One-Hidden-Layer ReLU Networks.

[BibT_eX]

[DOI]

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

2022

Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

2021

Efficiently Learning Any One Hidden Layer ReLU Network From Queries.

[BibT_eX]

[DOI]

CoRR, 2021

Efficiently Learning One Hidden Layer ReLU Networks From Queries.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Tight Hardness Results for Training Depth-2 ReLU Networks.

[BibT_eX]

[DOI]

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Learning Deep ReLU Networks Is Fixed-Parameter Tractable.

[BibT_eX]

[DOI]

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

The Polynomial Method is Universal for Distribution-Free Correlational SQ Learning.

[BibT_eX]

[DOI]

Sushrut Karmalkar

CoRR, 2020

From Boltzmann Machines to Neural Networks and Back Again.

[BibT_eX]

[DOI]

Frederic Koehler

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Statistical-Query Lower Bounds via Functional Gradients.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Good Subnetworks Provably Exist: Pruning via Greedy Forward Selection.

[BibT_eX]

[DOI]

Proceedings of the 37th International Conference on Machine Learning, 2020

Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descent.

[BibT_eX]

[DOI]

Proceedings of the 37th International Conference on Machine Learning, 2020

Approximation Schemes for ReLU Regression.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2020

2019

List-decodable Linear Regression.

[BibT_eX]

[DOI]

Sushrut Karmalkar

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.

[BibT_eX]

[DOI]

Sushrut Karmalkar

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.

[BibT_eX]

[DOI]

Daniel M. Kane

Proceedings of the Conference on Learning Theory, 2019

Learning Neural Networks with Two Nonlinear Layers in Polynomial Time.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2019

2018

Learning One Convolutional Layer with Overlapping Patches.

[BibT_eX]

[DOI]

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

Hyperparameter optimization: a spectral approach.

[BibT_eX]

[DOI]

Elad Hazan

Yang Yuan

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

Efficient Algorithms for Outlier-Robust Regression.

[BibT_eX]

[DOI]

Pravesh K. Kothari

Proceedings of the Conference On Learning Theory, 2018

2017

Learning Depth-Three Neural Networks in Polynomial Time.

[BibT_eX]

[DOI]

CoRR, 2017

Eigenvalue Decay Implies Polynomial-Time Learnability for Neural Networks.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Erik M. Lindgren

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

Learning Graphical Models Using Multiplicative Weights.

[BibT_eX]

[DOI]

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

Reliably Learning the ReLU in Polynomial Time.

[BibT_eX]

[DOI]

Proceedings of the 30th Conference on Learning Theory, 2017

2016

Cryptographic Hardness of Learning.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Preserving Randomness for Adaptive Algorithms.

[BibT_eX]

[DOI]

William M. Hoza

Electron. Colloquium Comput. Complex., 2016

2014

Bounding the Sensitivity of Polynomial Threshold Functions.

[BibT_eX]

[DOI]

Prahladh Harsha

Theory Comput., 2014

Embedding Hard Learning Problems into Gaussian Space.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

A Smoothed Analysis for Learning Sparse Polynomials.

[BibT_eX]

[DOI]

Murat Kocaoglu

Karthikeyan Shanmugam

CoRR, 2014

Sparse Polynomial Learning and Graph Sketching.

[BibT_eX]

[DOI]

Murat Kocaoglu

Karthikeyan Shanmugam

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

2013

Moment-Matching Polynomials.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Constructing Hard Functions from Learning Algorithms.

[BibT_eX]

[DOI]

Igor C. Oliveira

Electron. Colloquium Comput. Complex., 2013

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

[BibT_eX]

[DOI]

Daniel M. Kane

Proceedings of the COLT 2013, 2013

Constructing Hard Functions Using Learning Algorithms.

[BibT_eX]

[DOI]

Igor C. Oliveira

Proceedings of the 28th Conference on Computational Complexity, 2013

2012

Learning Functions of Halfspaces using Prefix Covers.

[BibT_eX]

[DOI]

Proceedings of the COLT 2012, 2012

An invariance principle for polytopes.

[BibT_eX]

[DOI]

Prahladh Harsha

J. ACM, 2012

An Explicit VC-Theorem for Low-Degree Polynomials.

[BibT_eX]

[DOI]

Eshan Chattopadhyay

Electron. Colloquium Comput. Complex., 2012

2011

Submodular Functions Are Noise Stable.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

An FPTAS for #Knapsack and Related Counting Problems.

[BibT_eX]

[DOI]

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

2010

Mansour's Conjecture is True for Random DNF Formulas.

[BibT_eX]

[DOI]

Homin K. Lee

Andrew Wan

Electron. Colloquium Comput. Complex., 2010

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

Lower Bounds for Agnostic Learning via Approximate Rank.

[BibT_eX]

[DOI]

Comput. Complex., 2010

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

[BibT_eX]

[DOI]

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

2009

Learning Halfspaces with Malicious Noise.

[BibT_eX]

[DOI]

Philip M. Long

J. Mach. Learn. Res., 2009

Cryptographic hardness for learning intersections of halfspaces.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2009

Efficient learning algorithms yield circuit lower bounds.

[BibT_eX]

[DOI]

Lance Fortnow

J. Comput. Syst. Sci., 2009

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

[BibT_eX]

[DOI]

Philip M. Long

Alex K. Tang

Proceedings of the Approximation, 2009

2008

Cryptographic Hardness of Learning.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Agnostically Learning Halfspaces.

[BibT_eX]

[DOI]

SIAM J. Comput., 2008

Learning intersections of halfspaces with a margin.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2008

The complexity of properly learning simple concept classes.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2008

List-decoding reed-muller codes over small fields.

[BibT_eX]

[DOI]

David Zuckerman

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

Agnostically learning decision trees.

[BibT_eX]

[DOI]

Adam Tauman Kalai

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

Learning Geometric Concepts via Gaussian Surface Area.

[BibT_eX]

[DOI]

Ryan O'Donnell

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

A Query Algorithm for Agnostically Learning DNF?.

[BibT_eX]

[DOI]

Adam Kalai

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

2007

Unconditional lower bounds for learning intersections of halfspaces.

[BibT_eX]

[DOI]

Mach. Learn., 2007

A Lower Bound for Agnostically Learning Disjunctions.

[BibT_eX]

[DOI]

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

2006

Learning Restricted Models of Arithmetic Circuits.

[BibT_eX]

[DOI]

Amir Shpilka

Theory Comput., 2006

Toward Attribute Efficient Learning of Decision Lists and Parities.

[BibT_eX]

[DOI]

J. Mach. Learn. Res., 2006

Cryptographic Hardness Results for Learning Intersections of Halfspaces.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

Improved Lower Bounds for Learning Intersections of Halfspaces.

[BibT_eX]

[DOI]

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

2005

Linear Advice for Randomized Logarithmic Space

[BibT_eX]

[DOI]

Lance Fortnow

Electron. Colloquium Comput. Complex., 2005

2004

Learning DNF in time 2<sup>Õ(n<sup>1/3</sup>)</sup>.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2004

Learning intersections and thresholds of halfspaces.

[BibT_eX]

[DOI]

Ryan O'Donnell

J. Comput. Syst. Sci., 2004

NP with Small Advice

[BibT_eX]

[DOI]

Lance Fortnow

Electron. Colloquium Comput. Complex., 2004

Learnability and Automatizability.

[BibT_eX]

[DOI]

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

Perceptron-Like Performance for Intersections of Halfspaces.

[BibT_eX]

[DOI]

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

2003

Boosting and Hard-Core Set Construction.

[BibT_eX]

[DOI]

Mach. Learn., 2003

Toward Attribute Efficient Learning Algorithms

[BibT_eX]

[DOI]

CoRR, 2003

Learning Arithmetic Circuits via Partial Derivatives.

[BibT_eX]

[DOI]

Amir Shpilka

Proceedings of the Computational Learning Theory and Kernel Machines, 2003

2002

Learnability beyond AC0.

[BibT_eX]

[DOI]

Jeffrey C. Jackson

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

2001

Randomness efficient identity testing of multivariate polynomials.

[BibT_eX]

[DOI]

Daniel A. Spielman

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

On the Derandomization of Constant Depth Circuits.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2001

1999

Boosting and Hard-Core Sets.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]