Santosh S. Vempala
Orcid: 0000-0002-3779-433XAffiliations:
- Georgia Institute of Technology, School of Computer Science, Atlanta, GA, USA
According to our database1,
Santosh S. Vempala
authored at least 238 papers
between 1993 and 2024.
Collaborative distances:
Collaborative distances:
Awards
ACM Fellow
ACM Fellow 2015, "For contributions to algorithms for convex sets and probability distributions.".
Timeline
Legend:
Book In proceedings Article PhD thesis Dataset OtherLinks
Online presence:
-
on orcid.org
-
on id.loc.gov
-
on dl.acm.org
On csauthors.net:
Bibliography
2024
Commun. ACM, July, 2024
Does GPT Really Get It? A Hierarchical Scale to Quantify Human vs AI's Understanding of Algorithms.
CoRR, 2024
CoRR, 2024
Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024
Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024
Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024
Proceedings of the International Conference on Algorithmic Learning Theory, 2024
2023
Discret. Comput. Geom., September, 2023
Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023
Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error.
Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023
Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023
Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023
Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023
Condition-number-independent Convergence Rate of Riemannian Hamiltonian Monte Carlo with Numerical Integrators.
Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023
2022
Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions.
Theory Comput., 2022
Random Struct. Algorithms, 2022
Random Struct. Algorithms, 2022
Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022
Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022
Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022
Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022
Proceedings of the Approximation, 2022
Proceedings of the International Conference on Algorithmic Learning Theory, 29 March, 2022
Proceedings of the International Conference on Artificial Intelligence and Statistics, 2022
Proceedings of the International Conference on Artificial Intelligence and Statistics, 2022
2021
Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization.
Math. Oper. Res., 2021
Reducing isotropy and volume to KLS: an <i>o</i>*(<i>n</i><sup>3</sup><i>ψ</i><sup>2</sup>) volume algorithm.
Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021
Proceedings of the FAccT '21: 2021 ACM Conference on Fairness, 2021
2020
The complexity of human computation via a concrete model with an application to passwords.
Proc. Natl. Acad. Sci. USA, 2020
Reducing Isotropy and Volume to KLS: An O(n<sup>3</sup>ψ<sup>2</sup>) Volume Algorithm.
CoRR, 2020
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020
2019
Proceedings of the Computing and Software Science - State of the Art and Perspectives, 2019
ACM Trans. Algorithms, 2019
CoRR, 2019
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019
Proceedings of the 2019 ITU Kaleidoscope: ICT for Health: Networks, 2019
Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019
Gradient Descent for One-Hidden-Layer Neural Networks: Polynomial Convergence and SQ Lower Bounds.
Proceedings of the Conference on Learning Theory, 2019
2018
Special Section on the Fifty-Sixth Annual IEEE Symposium on Foundations of Computer Science (FOCS 2015).
SIAM J. Comput., 2018
SIAM J. Comput., 2018
Gaussian Cooling and O<sup>*(n<sup>3)</sup></sup> Algorithms for Volume and Gaussian Volume.
SIAM J. Comput., 2018
CoRR, 2018
Polynomial Convergence of Gradient Descent for Training One-Hidden-Layer Neural Networks.
CoRR, 2018
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018
Convergence rate of riemannian Hamiltonian Monte Carlo and faster polytope volume computation.
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018
Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018
Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018
Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018
Proceedings of the Sixth AAAI Conference on Human Computation and Crowdsourcing, 2018
Proceedings of the 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2018
Proceedings of the Conference On Learning Theory, 2018
2017
CoRR, 2017
The Complexity of Human Computation: A Concrete Model with an Application to Passwords.
CoRR, 2017
CHRR: coordinate hit-and-run with rounding for uniform sampling of constraint-based models.
Bioinform., 2017
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017
Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017
Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017
Eldan's Stochastic Localization and the KLS Hyperplane Conjecture: An Improved Lower Bound for Expansion.
Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017
2016
Oper. Res. Lett., 2016
Proceedings of the Workshop on Cognitive Computation: Integrating neural and symbolic approaches 2016 co-located with the 30th Annual Conference on Neural Information Processing Systems (NIPS 2016), 2016
C4G BLIS: Health Care Delivery via Iterative Collaborative Design in Resource-constrained Settings.
Proceedings of the Eighth International Conference on Information and Communication Technologies and Development, 2016
Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016
Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016
Proceedings of the 29th Conference on Learning Theory, 2016
2015
Math. Oper. Res., 2015
Comb. Probab. Comput., 2015
CoRR, 2015
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015
Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, 2015
Proceedings of the Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, 2015
Proceedings of the Third AAAI Conference on Human Computation and Crowdsourcing, 2015
Proceedings of The 28th Conference on Learning Theory, 2015
Proceedings of The 28th Conference on Learning Theory, 2015
Proceedings of The 28th Conference on Learning Theory, 2015
2014
CoRR, 2014
CoRR, 2014
Proceedings of the Symposium on Theory of Computing, 2014
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014
Proceedings of the Innovations in Theoretical Computer Science, 2014
Proceedings of The 27th Conference on Learning Theory, 2014
2013
Proc. Natl. Acad. Sci. USA, 2013
Proceedings of the Symposium on Theory of Computing Conference, 2013
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013
Proceedings of the 2013 Asilomar Conference on Signals, 2013
2012
A Deterministic Polynomial-Time Approximation Scheme for Counting Knapsack Solutions.
SIAM J. Comput., 2012
Electron. Colloquium Comput. Complex., 2012
Electron. Colloquium Comput. Complex., 2012
Deterministic 2^{O(n)} Algorithms for M-Ellipsoids, Lattice Problems and Volume Estimation
CoRR, 2012
Proceedings of the 44th Symposium on Theory of Computing Conference, 2012
Deterministic construction of an approximate M-ellipsoid and its applications to derandomizing lattice algorithms.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012
Proceedings of the Similarity Search and Applications - 5th International Conference, 2012
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2012
2011
CoRR, 2011
Deterministic Construction of an Approximate M-Ellipsoid and its Application to Derandomizing Lattice Algorithms
CoRR, 2011
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011
Proceedings of the ACM SIGCOMM 2011 Conference on Applications, 2011
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011
Proceedings of the Algorithmic Learning Theory - 22nd International Conference, 2011
Proceedings of the Algorithmic Learning Theory - 22nd International Conference, 2011
2010
J. ACM, 2010
Enumerative Algorithms for the Shortest and Closest Lattice Vector Problems in Any Norm via M-Ellipsoid Coverings
CoRR, 2010
Proceedings of the 19th USENIX Security Symposium, 2010
Thin Partitions: Isoperimetric Inequalities and a Sampling Algorithm for Star Shaped Bodies.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010
Proceedings of the ACM SIGCOMM 2010 Conference on Applications, 2010
Proceedings of the Algorithmic Game Theory - Third International Symposium, 2010
Proceedings of the Innovations in Computer Science, 2010
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2010
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010
2009
Adaptive simulated annealing: A near-optimal connection between sampling and counting.
J. ACM, 2009
CoRR, 2009
Thin Partitions: Isoperimetric Inequalities and Sampling Algorithms for some Nonconvex Families
CoRR, 2009
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009
Proceedings of the 2009 International Conference on Information and Communication Technologies and Development, 2009
Proceedings of the 2009 International Conference on Information and Communication Technologies and Development, 2009
Proceedings of the Approximation, 2009
2008
Math. Program., 2008
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008
2007
Random Struct. Algorithms, 2007
Proceedings of the 6th ACM Workshop on Hot Topics in Networks, 2007
Proceedings of the 6th ACM Workshop on Hot Topics in Networks, 2007
Proceedings of the Learning Theory, 20th Annual Conference on Learning Theory, 2007
Proceedings of the Learning Theory, 20th Annual Conference on Learning Theory, 2007
Proceedings of the 2007 ACM Conference on Computer and Communications Security, 2007
2006
Theory Comput., 2006
Mach. Learn., 2006
Mach. Learn., 2006
Simulated annealing in convex bodies and an <i>O</i><sup>*</sup>(<i>n</i><sup>4</sup>) volume algorithm.
J. Comput. Syst. Sci., 2006
Electron. Colloquium Comput. Complex., 2006
Electron. Colloquium Comput. Complex., 2006
Proceedings of the SPAA 2006: Proceedings of the 18th Annual ACM Symposium on Parallelism in Algorithms and Architectures, Cambridge, Massachusetts, USA, July 30, 2006
Fast Algorithms for Logconcave Functions: Sampling, Rounding, Integration and Optimization.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006
2005
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005
2004
On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems.
Math. Program., 2004
Proceedings of the FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science, 2004
DIMACS Series in Discrete Mathematics and Theoretical Computer Science 65, DIMACS/AMS, ISBN: 978-0-8218-3793-1, 2004
Proceedings of the Algorithmic Learning Theory, 15th International Conference, 2004
2003
SIAM J. Comput., 2003
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003
2002
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002
2001
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001
Proceedings of the Approximation, 2001
Proceedings of the Integer Programming and Combinatorial Optimization, 2001
Proceedings of the Integer Programming and Combinatorial Optimization, 2001
2000
Theor. Comput. Sci., 2000
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000
Proceedings of the Approximation Algorithms for Combinatorial Optimization, 2000
1999
Random Struct. Algorithms, 1999
J. Comput. Syst. Sci., 1999
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999
Proceedings of the Algorithms and Computation, 10th International Symposium, 1999
1998
A Constant-Factor Approximation Algorithm for the Geometric k-MST Problem in the Plane.
SIAM J. Comput., 1998
New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen.
SIAM J. Comput., 1998
Algorithmica, 1998
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998
1997
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997
Simple Markov-Chain Algorithms for Generating Bipartite Graphs and Tournaments (Extended Abstract).
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997
1996
A Constant-factor Approximation Algorithm for the <i>k</i> MST Problem (Extended Abstract).
Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996
1995
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995
Improved approximation guarantees for minimum-weight <i>k</i>-trees and prize-collecting salesmen.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995
1994
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1994
1993
Improved Approximation Algorithms for Biconnected Subgraphs via Better Lower Bounding Techniques.
Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1993