| Publication | Date of Publication | Type |
|---|
| The quest for mathematical understanding of deep learning (invited talk) | 2026-03-23 | Paper |
Mathematics of machine learning: an introduction
Proceedings of the International Congress of Mathematicians (ICM 2018) | 2020-09-22 | Paper |
| scientific article; zbMATH DE number 6970825 (Why is no real title available?) | 2018-11-02 | Paper |
Subexponential algorithms for unique games and related problems
Journal of the ACM | 2018-08-02 | Paper |
A combinatorial, primal-dual approach to semidefinite programs
Journal of the ACM | 2018-08-02 | Paper |
| The work of Subhash Khot | 2017-10-25 | Paper |
Provable learning of noisy-OR networks
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
Message-Passing Algorithms and Improved LP Decoding
IEEE Transactions on Information Theory | 2017-06-08 | Paper |
Approximation schemes for minimum latency problems
Proceedings of the thirty-first annual ACM symposium on Theory of Computing | 2016-09-29 | Paper |
Computing a nonnegative matrix factorization -- provably
SIAM Journal on Computing | 2016-09-02 | Paper |
Simulating quadratic dynamical systems is PSPACE-complete (preliminary version)
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 | 2016-09-01 | Paper |
Expander flows, geometric embeddings and graph partitioning
Journal of the ACM | 2015-11-11 | Paper |
Provable ICA with unknown Gaussian noise, and implications for Gaussian mixtures and autoencoders
Algorithmica | 2015-05-21 | Paper |
Message passing algorithms and improved LP decoding
Proceedings of the forty-first annual ACM symposium on Theory of computing | 2015-02-04 | Paper |
New approximation guarantee for chromatic number
Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing | 2014-11-25 | Paper |
Computing a nonnegative matrix factorization -- provably
Proceedings of the forty-fourth annual ACM symposium on Theory of computing | 2014-05-13 | Paper |
Testing permanent oracles -- revisited
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2012-11-02 | Paper |
The multiplicative weights update method: a meta-algorithm and applications
Theory of Computing | 2012-09-27 | Paper |
Towards strong nonapproximability results in the Lovász-Schrijver hierarchy
Computational Complexity | 2012-06-26 | Paper |
Local versus global properties of metric spaces
SIAM Journal on Computing | 2012-05-30 | Paper |
Semidefinite programming and approximation algorithms: a survey
Algorithms and Computation | 2011-12-16 | Paper |
New tools for graph coloring
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2011-08-17 | Paper |
New Algorithms for Learning in Presence of Errors
Automata, Languages and Programming | 2011-07-06 | Paper |
Proving integrality gaps without knowing the linear program
Theory of Computing | 2011-05-24 | Paper |
\(O(\sqrt{\log n})\) approximation to sparsest cut in \(\tilde{O}(n^2)\) time
SIAM Journal on Computing | 2010-11-04 | Paper |
Euclidean distortion and the sparsest cut (extended abstract)
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Local versus global properties of metric spaces
Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 | 2010-08-16 | Paper |
Expander flows, geometric embeddings and graph partitioning
Proceedings of the thirty-sixth annual ACM symposium on Theory of computing | 2010-08-15 | Paper |
Fitting algebraic curves to noisy data
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing | 2010-08-05 | Paper |
| Computational Complexity | 2009-07-22 | Paper |
Towards a Study of Low-Complexity Graphs
Automata, Languages and Programming | 2009-07-14 | Paper |
| scientific article; zbMATH DE number 5485455 (Why is no real title available?) | 2009-01-05 | Paper |
| Unique games on expanding constraint graphs are easy (extended abstract) | 2009-01-05 | Paper |
Fréchet embeddings of negative type metrics
Discrete & Computational Geometry | 2008-02-18 | Paper |
A randomized online algorithm for bandwidth utilization
Journal of Scheduling | 2007-12-20 | Paper |
Euclidean distortion and the sparsest cut
Journal of the American Mathematical Society | 2007-11-01 | Paper |
A Fast Random Sampling Algorithm for Sparsifying Matrices
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2007-08-28 | Paper |
Improved low-degree testing and its applications
Combinatorica | 2006-06-27 | Paper |
A \(2+\varepsilon\) approximation algorithm for the \(k\)-MST problem
Mathematical Programming. Series A. Series B | 2006-06-14 | Paper |
Learning mixtures of separated nonspherical Gaussians
The Annals of Applied Probability | 2005-04-29 | Paper |
| scientific article; zbMATH DE number 2134902 (Why is no real title available?) | 2005-02-18 | Paper |
Approximation schemes for degree-restricted MST and red-blue separation problems
Algorithmica | 2005-02-11 | Paper |
Proof verification and the hardness of approximation problems
Journal of the ACM | 2005-01-25 | Paper |
Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
Journal of the ACM | 2005-01-25 | Paper |
| scientific article; zbMATH DE number 2119708 (Why is no real title available?) | 2004-11-29 | Paper |
Fitting algebraic curves to noisy data
Journal of Computer and System Sciences | 2004-11-18 | Paper |
| scientific article; zbMATH DE number 2081090 (Why is no real title available?) | 2004-08-04 | Paper |
| scientific article; zbMATH DE number 2064408 (Why is no real title available?) | 2004-05-18 | Paper |
| scientific article; zbMATH DE number 2038709 (Why is no real title available?) | 2004-02-08 | Paper |
Approximation Schemes for Minimum Latency Problems
SIAM Journal on Computing | 2003-09-28 | Paper |
Approximation schemes for NP-hard geometric optimization problems: a survey
Mathematical Programming. Series A. Series B | 2003-09-01 | Paper |
| scientific article; zbMATH DE number 1789920 (Why is no real title available?) | 2002-10-06 | Paper |
| scientific article; zbMATH DE number 1775394 (Why is no real title available?) | 2002-09-17 | Paper |
| scientific article; zbMATH DE number 1775419 (Why is no real title available?) | 2002-08-01 | Paper |
A new rounding procedure for the assignment problem with applications to dense graph arrangement problems
Mathematical Programming. Series A. Series B | 2002-06-12 | Paper |
| scientific article; zbMATH DE number 1256636 (Why is no real title available?) | 2002-01-17 | Paper |
| scientific article; zbMATH DE number 1670523 (Why is no real title available?) | 2001-11-11 | Paper |
| scientific article; zbMATH DE number 1263204 (Why is no real title available?) | 2001-08-27 | Paper |
| scientific article; zbMATH DE number 1559564 (Why is no real title available?) | 2001-02-28 | Paper |
| scientific article; zbMATH DE number 1256635 (Why is no real title available?) | 2000-05-28 | Paper |
| scientific article; zbMATH DE number 1445374 (Why is no real title available?) | 2000-05-10 | Paper |
| scientific article; zbMATH DE number 1306873 (Why is no real title available?) | 2000-04-26 | Paper |
| scientific article; zbMATH DE number 1305389 (Why is no real title available?) | 2000-04-13 | Paper |
Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
Journal of Computer and System Sciences | 2000-02-17 | Paper |
| scientific article; zbMATH DE number 1303538 (Why is no real title available?) | 1999-06-17 | Paper |
| scientific article; zbMATH DE number 1163704 (Why is no real title available?) | 1999-05-05 | Paper |
Probabilistic checking of proofs
Journal of the ACM | 1998-10-25 | Paper |
On winning strategies in Ehrenfeucht-Fraïssé games
Theoretical Computer Science | 1998-10-22 | Paper |
The hardness of approximate optima in lattices, codes, and systems of linear equations
Journal of Computer and System Sciences | 1997-12-08 | Paper |
On-Line Algorithms for Path Selection in a Nonblocking Network
SIAM Journal on Computing | 1996-11-26 | Paper |
