Santosh S. Vempala

According to our database, Santosh S. Vempala authored at least 238 papers between 1993 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2024

Solving Sparse Linear Systems Faster than Matrix Multiplication.

Richard Peng, Santosh S. Vempala

Commun. ACM, July, 2024

Does GPT Really Get It? A Hierarchical Scale to Quantify Human vs AI's Understanding of Algorithms.

Mirabel Reid, Santosh S. Vempala

CoRR, 2024

Coin-Flipping In The Brain: Statistical Learning with Neuronal Assemblies.

Max Dabagia, Daniel Mitropolsky, Christos H. Papadimitriou, Santosh S. Vempala

CoRR, 2024

In-and-Out: Algorithmic Diffusion for Sampling Convex Bodies.

Yunbum Kook, Santosh S. Vempala, Matthew Shunshi Zhang

CoRR, 2024

Calibrated Language Models Must Hallucinate.

Adam Tauman Kalai, Santosh S. Vempala

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Gaussian Cooling and Dikin Walks: The Interior-Point Method for Logconcave Sampling.

Yunbum Kook, Santosh S. Vempala

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

Sampling Polytopes with Riemannian HMC: Faster Mixing via the Lewis Weights Barrier.

Khashayar Gatmiry, Jonathan A. Kelner, Santosh S. Vempala

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

Computation with Sequences of Assemblies in a Model of the Brain.

Max Dabagia, Christos H. Papadimitriou, Santosh S. Vempala

Proceedings of the International Conference on Algorithmic Learning Theory, 2024

2023

Convergence of Gibbs Sampling: Coordinate Hit-and-Run Mixes Fast.

Aditi Laddha, Santosh S. Vempala

Discret. Comput. Geom., September, 2023

Efficiently Sampling the PSD Cone with the Metric Dikin Walk.

Yunbum Kook, Santosh S. Vempala

CoRR, 2023

Computation with Sequences in the Brain.

Max Dabagia, Christos H. Papadimitriou, Santosh S. Vempala

CoRR, 2023

Sampling with Barriers: Faster Mixing via Lewis Weights.

Khashayar Gatmiry, Jonathan A. Kelner, Santosh S. Vempala

CoRR, 2023

Contrastive Moments: Unsupervised Halfspace Learning in Polynomial Time.

Xinyuan Cao, Santosh S. Vempala

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.

He Jia, Pravesh K. Kothari, Santosh S. Vempala

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

The Bit Complexity of Efficient Continuous Optimization.

Mehrdad Ghadiri, Richard Peng, Santosh S. Vempala

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

The k-Cap Process on Geometric Random Graphs.

Mirabel E. Reid, Santosh S. Vempala

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

Is Planted Coloring Easier than Planted Clique?

Pravesh Kothari, Santosh S. Vempala, Alexander S. Wein, Jeff Xu

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

Condition-number-independent Convergence Rate of Riemannian Hamiltonian Monte Carlo with Numerical Integrators.

Yunbum Kook, Yin Tat Lee, Ruoqi Shen, Santosh S. Vempala

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

2022

Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions.

Zongchen Chen, Santosh S. Vempala

Adv. Math. Commun., 2022

Geodesic Walks in Polytopes.

Yin Tat Lee, Santosh S. Vempala

SIAM J. Comput., 2022

Approximating sparse graphs: The random overlapping communities model.

Samantha Petti, Santosh S. Vempala

Random Struct. Algorithms, 2022

A unified view of graph regularity via matrix decompositions.

Greg Bodwin, Santosh S. Vempala

Random Struct. Algorithms, 2022

Socially fair network design via iterative rounding.

Aditi Laddha, Mohit Singh, Santosh S. Vempala

Oper. Res. Lett., 2022

A Slightly Improved Bound for the KLS Constant.

Arun Jambulapati, Yin Tat Lee, Santosh S. Vempala

CoRR, 2022

Constant-Factor Approximation Algorithms for Socially Fair k-Clustering.

Mehrdad Ghadiri, Mohit Singh, Santosh S. Vempala

CoRR, 2022

Convergence of the Riemannian Langevin Algorithm.

Khashayar Gatmiry, Santosh S. Vempala

CoRR, 2022

Robustly learning mixtures of <i>k</i> arbitrary Gaussians.

Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M. Kane, Pravesh K. Kothari, Santosh S. Vempala

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Sampling with Riemannian Hamiltonian Monte Carlo in a Constrained Space.

Yunbum Kook, Yin Tat Lee, Ruoqi Shen, Santosh S. Vempala

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

The Manifold Joys of Sampling (Invited Talk).

Yin Tat Lee, Santosh S. Vempala

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Assemblies of neurons learn to classify well-separated distributions.

Max Dabagia, Santosh S. Vempala, Christos H. Papadimitriou

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

A Unified Approach to Discrepancy Minimization.

Nikhil Bansal, Aditi Laddha, Santosh S. Vempala

Proceedings of the Approximation, 2022

The Mirror Langevin Algorithm Converges with Vanishing Bias.

Ruilin Li, Molei Tao, Santosh S. Vempala, Andre Wibisono

Proceedings of the International Conference on Algorithmic Learning Theory, 29 March, 2022

How and When Random Feedback Works: A Case Study of Low-Rank Matrix Factorization.

Shivam Garg, Santosh S. Vempala

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2022

Provable Lifelong Learning of Representations.

Xinyuan Cao, Weiyang Liu, Santosh S. Vempala

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2022

2021

Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization.

Vitaly Feldman, Cristóbal Guzmán, Santosh Srinivas Vempala

Math. Oper. Res., 2021

Assemblies of neurons can learn to classify well-separated distributions.

Max Dabagia, Christos H. Papadimitriou, Santosh S. Vempala

CoRR, 2021

Sparse Regression Faster than d^ω.

Mehrdad Ghadiri, Richard Peng, Santosh S. Vempala

CoRR, 2021

Tutorial on the Robust Interior Point Method.

Yin Tat Lee, Santosh S. Vempala

CoRR, 2021

Reducing isotropy and volume to KLS: an <i>o</i>*(<i>n</i>³<i>ψ</i>²) volume algorithm.

He Jia, Aditi Laddha, Yin Tat Lee, Santosh S. Vempala

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Socially Fair k-Means Clustering.

Mehrdad Ghadiri, Samira Samadi, Santosh S. Vempala

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.

Manuel Blum, Santosh S. Vempala

Proc. Natl. Acad. Sci. USA, 2020

Robustly Learning Mixtures of k Arbitrary Gaussians.

Ainesh Bakshi, Ilias Diakonikolas, He Jia, Daniel M. Kane, Pravesh K. Kothari, Santosh S. Vempala

CoRR, 2020

Reducing Isotropy and Volume to KLS: An O(n³ψ²) Volume Algorithm.

He Jia, Aditi Laddha, Yin Tat Lee, Santosh S. Vempala

CoRR, 2020

Fair k-Means Clustering.

Mehrdad Ghadiri, Samira Samadi, Santosh S. Vempala

CoRR, 2020

Strong self-concordance and sampling.

Aditi Laddha, Yin Tat Lee, Santosh S. Vempala

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

The Communication Complexity of Optimization.

Santosh S. Vempala, Ruosong Wang, David P. Woodruff

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

2019

Brain Computation: A Computer Science Perspective.

Wolfgang Maass, Christos H. Papadimitriou, Santosh S. Vempala, Robert Legenstein

Proceedings of the Computing and Software Science - State of the Art and Perspectives, 2019

A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Subgraph Problem.

Christoph Hunkenschröder, Santosh S. Vempala, Adrian Vetta

ACM Trans. Algorithms, 2019

Matrix Decompositions and Sparse Graph Regularity.

Greg Bodwin, Santosh S. Vempala

CoRR, 2019

Human-Usable Password Schemas: Beyond Information-Theoretic Security.

Elan Rosenfeld, Santosh S. Vempala, Manuel Blum

CoRR, 2019

Rapid Convergence of the Unadjusted Langevin Algorithm: Log-Sobolev Suffices.

Santosh S. Vempala, Andre Wibisono

CoRR, 2019

Fair Dimensionality Reduction and Iterative Rounding for SDPs.

Jamie Morgenstern, Samira Samadi, Mohit Singh, Uthaipon Tao Tantipongpipat, Santosh S. Vempala

CoRR, 2019

Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices.

Santosh S. Vempala, Andre Wibisono

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

Multi-Criteria Dimensionality Reduction with Applications to Fairness.

Uthaipon Tantipongpipat, Samira Samadi, Mohit Singh, Jamie Morgenstern, Santosh S. Vempala

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

Redesigning a Basic Laboratory Information System for the Global South.

Jung Wook Park, Aditi Shah, Rosa I. Arriaga, Santosh S. Vempala

Proceedings of the 2019 ITU Kaleidoscope: ICT for Health: Networks, 2019

Random Projection in the Brain and Computation with Assemblies of Neurons.

Christos H. Papadimitriou, Santosh S. Vempala

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.

Santosh S. Vempala, John Wilmes

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

Cristopher Moore, Santosh S. Vempala

SIAM J. Comput., 2018

On the Complexity of Random Satisfiability Problems with Planted Solutions.

Vitaly Feldman, Will Perkins, Santosh S. Vempala

SIAM J. Comput., 2018

Gaussian Cooling and O^*(n³⁾ Algorithms for Volume and Gaussian Volume.

Ben Cousins, Santosh S. Vempala

SIAM J. Comput., 2018

Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave Densities.

Yin Tat Lee, Zhao Song, Santosh S. Vempala

CoRR, 2018

The Kannan-Lovász-Simonovits Conjecture.

Yin Tat Lee, Santosh S. Vempala

CoRR, 2018

Polynomial Convergence of Gradient Descent for Training One-Hidden-Layer Neural Networks.

Santosh S. Vempala, John Wilmes

CoRR, 2018

Stochastic localization + Stieltjes barrier = tight bound for log-Sobolev.

Yin Tat Lee, Santosh S. Vempala

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.

Yin Tat Lee, Santosh S. Vempala

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

The Price of Fair PCA: One Extra dimension.

Samira Samadi, Uthaipon Tao Tantipongpipat, Jamie Morgenstern, Mohit Singh, Santosh S. Vempala

Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

Smoothed Analysis of Discrete Tensor Decomposition and Assemblies of Neurons.

Nima Anari, Constantinos Daskalakis, Wolfgang Maass, Christos H. Papadimitriou, Amin Saberi, Santosh S. Vempala

Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

Long Term Memory and the Densest K-Subgraph Problem.

Robert Legenstein, Wolfgang Maass, Christos H. Papadimitriou, Santosh S. Vempala

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Usability of Humanly Computable Passwords.

Samira Samadi, Santosh S. Vempala, Adam Tauman Kalai

Proceedings of the Sixth AAAI Conference on Human Computation and Crowdsourcing, 2018

Continuous Algorithms (Invited Paper).

Santosh S. Vempala

Proceedings of the 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2018

Efficient Convex Optimization with Membership Oracles.

Yin Tat Lee, Aaron Sidford, Santosh S. Vempala

Proceedings of the Conference On Learning Theory, 2018

2017

Geometric random edge.

Friedrich Eisenbrand, Santosh S. Vempala

Math. Program., 2017

Statistical Algorithms and a Lower Bound for Detecting Planted Cliques.

Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S. Vempala, Ying Xiao

J. ACM, 2017

Random Overlapping Communities: Approximating Motif Densities of Large Graphs.

Samantha Petti, Santosh S. Vempala

CoRR, 2017

The Complexity of Human Computation: A Concrete Model with an Application to Passwords.

Manuel Blum, Santosh S. Vempala

CoRR, 2017

CHRR: coordinate hit-and-run with rounding for uniform sampling of constraint-based models.

Hulda S. Haraldsdóttir, Ben Cousins, Ines Thiele, Ronan M. T. Fleming, Santosh S. Vempala

Bioinform., 2017

Randomized algorithms in numerical linear algebra.

Ravindran Kannan, Santosh S. Vempala

Acta Numer., 2017

Adaptive Matrix Vector Product.

Santosh S. Vempala, David P. Woodruff

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

On the Complexity of Learning Neural Networks.

Le Song, Santosh S. Vempala, John Wilmes, Bo Xie

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

Towards Human Computable Passwords.

Jeremiah Blocki, Manuel Blum, Anupam Datta, Santosh S. Vempala

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.

Yin Tat Lee, Santosh Srinivas Vempala

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

The Hidden Hubs Problem.

Ravindran Kannan, Santosh S. Vempala

Proceedings of the 30th Conference on Learning Theory, 2017

2016

A note on non-degenerate integer programs with small sub-determinants.

Stephan Artmann, Friedrich Eisenbrand, Christoph Glanzer, Timm Oertel, Santosh S. Vempala, Robert Weismantel

Oper. Res. Lett., 2016

A practical volume algorithm.

Ben Cousins, Santosh S. Vempala

Math. Program. Comput., 2016

The Cutting Plane Method is Polynomial for Perfect Matchings.

Karthekeyan Chandrasekaran, László A. Végh, Santosh S. Vempala

Math. Oper. Res., 2016

Beyond Spectral: Tight Bounds for Planted Gaussians.

Ravi Kannan, Santosh S. Vempala

CoRR, 2016

Variable Binding through Assemblies in Spiking Neural Networks.

Robert Legenstein, Christos H. Papadimitriou, Santosh S. Vempala, Wolfgang Maass

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.

Santosh S. Vempala, Naomi Chopra, Aishwarya Rajagopal, John Nkengasong, Sidney Akuro

Proceedings of the Eighth International Conference on Information and Communication Technologies and Development, 2016

Accelerated Newton Iteration for Roots of Black Box Polynomials.

Anand Louis, Santosh S. Vempala

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

Agnostic Estimation of Mean and Covariance.

Kevin A. Lai, Anup B. Rao, Santosh S. Vempala

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

Cortical Computation via Iterative Constructions.

Christos H. Papadimitriou, Samantha Petti, Santosh S. Vempala

Proceedings of the 29th Conference on Learning Theory, 2016

2015

Visual Categorization with Random Projection.

Rosa I. Arriaga, David Rutter, Maya Cakmak, Santosh S. Vempala

Neural Comput., 2015

Stochastic Billiards for Sampling from the Boundary of a Convex Set.

A. B. Dieker, Santosh S. Vempala

Math. Oper. Res., 2015

Query Complexity of Sampling and Small Geometric Partitions.

Navin Goyal, Luis Rademacher, Santosh S. Vempala

Comb. Probab. Comput., 2015

Accelerated Newton Iteration: Roots of Black Box Polynomials and Matrix Eigenvalues.

Anand Louis, Santosh S. Vempala

CoRR, 2015

Statistical Query Algorithms for Stochastic Convex Optimization.

Vitaly Feldman, Cristóbal Guzmán, Santosh S. Vempala

CoRR, 2015

Bypassing KLS: Gaussian Cooling and an O^*(n3) Volume Algorithm.

Benjamin Cousins, Santosh S. Vempala

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Cortical Computation.

Christos H. Papadimitriou, Santosh S. Vempala

Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, 2015

Subsampled Power Iteration: a Unified Algorithm for Block Models and Planted CSP's.

Vitaly Feldman, Will Perkins, Santosh S. Vempala

Proceedings of the Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, 2015

Publishable Humanly Usable Secure Password Creation Schemas.

Manuel Blum, Santosh Srinivas Vempala

Proceedings of the Third AAAI Conference on Human Computation and Crowdsourcing, 2015

Max vs Min: Tensor Decomposition and ICA with nearly Linear Sample Complexity.

Santosh S. Vempala, Ying Xiao

Proceedings of The 28th Conference on Learning Theory, 2015

Cortical Learning via Prediction.

Christos H. Papadimitriou, Santosh S. Vempala

Proceedings of The 28th Conference on Learning Theory, 2015

Efficient Representations for Lifelong Learning and Autoencoding.

Maria-Florina Balcan, Avrim Blum, Santosh S. Vempala

Proceedings of The 28th Conference on Learning Theory, 2015

2014

Expanders via Random Spanning Trees.

Alan M. Frieze, Navin Goyal, Luis Rademacher, Santosh S. Vempala

SIAM J. Comput., 2014

Max vs Min: Independent Component Analysis with nearly Linear Sample Complexity.

Santosh S. Vempala, Ying Xiao

CoRR, 2014

Unsupervised Learning through Prediction in a Model of Cortex.

Christos H. Papadimitriou, Santosh S. Vempala

CoRR, 2014

Subsampled Power Iteration: a New Algorithm for Block Models and Planted CSP's.

Vitaly Feldman, Will Perkins, Santosh S. Vempala

CoRR, 2014

Bypassing KLS: Gaussian Cooling and an O*(n^3) Volume Algorithm.

Ben Cousins, Santosh S. Vempala

CoRR, 2014

Efficient Representations for Life-Long Learning and Autoencoding.

Maria-Florina Balcan, Avrim Blum, Santosh S. Vempala

CoRR, 2014

Fourier PCA and robust tensor decomposition.

Navin Goyal, Santosh S. Vempala, Ying Xiao

Proceedings of the Symposium on Theory of Computing, 2014

A Cubic Algorithm for Computing Gaussian Volume.

Ben Cousins, Santosh S. Vempala

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Integer feasibility of random polytopes: random integer programs.

Karthekeyan Chandrasekaran, Santosh S. Vempala

Proceedings of the Innovations in Theoretical Computer Science, 2014

Principal Component Analysis and Higher Correlations for Distributed Data.

Ravi Kannan, Santosh S. Vempala, David P. Woodruff

Proceedings of The 27th Conference on Learning Theory, 2014

2013

Near-optimal deterministic algorithms for volume computation via M-ellipsoids.

Daniel Dadush, Santosh S. Vempala

Proc. Natl. Acad. Sci. USA, 2013

Nimble Algorithms for Cloud Computing

Ravindran Kannan, Santosh S. Vempala

CoRR, 2013

Fourier PCA.

Navin Goyal, Santosh S. Vempala, Ying Xiao

CoRR, 2013

The approximate rank of a matrix and its algorithmic applications: approximate rank.

Noga Alon, Troy Lee, Adi Shraibman, Santosh S. Vempala

Proceedings of the Symposium on Theory of Computing Conference, 2013

The Complexity of Approximating Vertex Expansion.

Anand Louis, Prasad Raghavendra, Santosh S. Vempala

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

Complexity of learning subspace juntas and ICA.

Santosh S. Vempala, Ying Xiao

Proceedings of the 2013 Asilomar Conference on Signals, 2013

2012

A Deterministic Polynomial-Time Approximation Scheme for Counting Knapsack Solutions.

Daniel Stefankovic, Santosh S. Vempala, Eric Vigoda

SIAM J. Comput., 2012

Local Versus Global Properties of Metric Spaces.

Sanjeev Arora, László Lovász, Ilan Newman, Yuval Rabani, Yuri Rabinovich, Santosh S. Vempala

SIAM J. Comput., 2012

Statistical Algorithms and a Lower Bound for Planted Clique.

Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S. Vempala, Ying Xiao

Electron. Colloquium Comput. Complex., 2012

The Approximate Rank of a Matrix and its Algorithmic Applications.

Noga Alon, Santosh S. Vempala

Electron. Colloquium Comput. Complex., 2012

Deterministic 2^{O(n)} Algorithms for M-Ellipsoids, Lattice Problems and Volume Estimation

Daniel Dadush, Santosh S. Vempala

CoRR, 2012

The Complexity of Statistical Algorithms

Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S. Vempala

CoRR, 2012

Modeling high-dimensional data: technical perspective.

Santosh S. Vempala

Commun. ACM, 2012

Many sparse cuts via higher eigenvalues.

Anand Louis, Prasad Raghavendra, Prasad Tetali, Santosh S. Vempala

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.

Daniel Dadush, Santosh S. Vempala

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Effective Principal Component Analysis.

Santosh S. Vempala

Proceedings of the Similarity Search and Applications - 5th International Conference, 2012

Randomly-oriented k-d Trees Adapt to Intrinsic Dimension.

Santosh S. Vempala

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2012

2011

A Discrepancy based Approach to Integer Programming

Karthekeyan Chandrasekaran, Santosh S. Vempala

CoRR, 2011

Structure from Local Optima: Learning Subspace Juntas via Higher Order PCA

Santosh S. Vempala, Ying Xiao

CoRR, 2011

Deterministic Construction of an Approximate M-Ellipsoid and its Application to Derandomizing Lattice Algorithms

Daniel Dadush, Santosh S. Vempala

CoRR, 2011

Algorithms for Implicit Hitting Set Problems.

Karthekeyan Chandrasekaran, Richard M. Karp, Erick Moreno-Centeno, Santosh S. Vempala

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

LifeNet: a flexible ad hoc networking solution for transient environments.

Hrushikesh Mehendale, Ashwin Paranjpe, Santosh S. Vempala

Proceedings of the ACM SIGCOMM 2011 Conference on Applications, 2011

An FPTAS for #Knapsack and Related Counting Problems.

Parikshit Gopalan, Adam R. Klivans, Raghu Meka, Daniel Stefankovic, Santosh S. Vempala, Eric Vigoda

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

Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings.

Daniel Dadush, Chris Peikert, Santosh S. Vempala

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

Algorithmic Extensions of Cheeger's Inequality to Higher Eigenvalues and Partitions.

Anand Louis, Prasad Raghavendra, Prasad Tetali, Santosh S. Vempala

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

Semantic Communication for Simple Goals Is Equivalent to On-line Learning.

Brendan Juba, Santosh S. Vempala

Proceedings of the Algorithmic Learning Theory - 22nd International Conference, 2011

On Noise-Tolerant Learning of Sparse Parities and Related Problems.

Elena Grigorescu, Lev Reyzin, Santosh S. Vempala

Proceedings of the Algorithmic Learning Theory - 22nd International Conference, 2011

2010

A random-sampling-based algorithm for learning intersections of halfspaces.

Santosh S. Vempala

J. ACM, 2010

Enumerative Algorithms for the Shortest and Closest Lattice Vector Problems in Any Norm via M-Ellipsoid Coverings

Daniel Dadush, Chris Peikert, Santosh S. Vempala

CoRR, 2010

Logconcave Random Graphs.

Alan M. Frieze, Santosh S. Vempala, Juan Vera

Electron. J. Comb., 2010

Chipping Away at Censorship Firewalls with User-Generated Content.

Sam Burnett, Nick Feamster, Santosh S. Vempala

Proceedings of the 19th USENIX Security Symposium, 2010

Thin Partitions: Isoperimetric Inequalities and a Sampling Algorithm for Star Shaped Bodies.

Karthekeyan Chandrasekaran, Daniel Dadush, Santosh S. Vempala

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Circumventing censorship with collage.

Sam Burnett, Nick Feamster, Santosh S. Vempala

Proceedings of the ACM SIGCOMM 2010 Conference on Applications, 2010

On Nash-Equilibria of Approximation-Stable Games.

Pranjal Awasthi, Maria-Florina Balcan, Avrim Blum, Or Sheffet, Santosh S. Vempala

Proceedings of the Algorithmic Game Theory - Third International Symposium, 2010

A New Approach to Strongly Polynomial Linear Programming.

Mihály Bárász, Santosh S. Vempala

Proceedings of the Innovations in Computer Science, 2010

Recent Progress and Open Problems in Algorithmic Convex Geometry.

Santosh S. Vempala

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2010

Learning Convex Concepts from Gaussian Distributions with PCA.

Santosh S. Vempala

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

Corrigendum: A Random Sampling Algorithm for Learning an Intersection of Halfspaces.

Santosh S. Vempala

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

2009

An Efficient Rescaled Perceptron Algorithm for Conic Systems.

Alexandre Belloni, Robert M. Freund, Santosh S. Vempala

Math. Oper. Res., 2009

Adaptive simulated annealing: A near-optimal connection between sampling and counting.

Daniel Stefankovic, Santosh S. Vempala, Eric Vigoda

J. ACM, 2009

Spectral Algorithms.

Ravi Kannan, Santosh S. Vempala

Found. Trends Theor. Comput. Sci., 2009

The Limit of Convexity Based Isoperimetry: Sampling Harmonic-Concave Functions

Karthekeyan Chandrasekaran, Amit Deshpande, Santosh S. Vempala

CoRR, 2009

Thin Partitions: Isoperimetric Inequalities and Sampling Algorithms for some Nonconvex Families

Karthekeyan Chandrasekaran, Daniel Dadush, Santosh S. Vempala

CoRR, 2009

Expanders via random spanning trees.

Navin Goyal, Luis Rademacher, Santosh S. Vempala

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Design and deployment of a blood safety monitoring tool.

Stephen Thomas, Adebola Osuntogun, John Pitman, Bright Mulenga, Santosh S. Vempala

Proceedings of the 2009 International Conference on Information and Communication Technologies and Development, 2009

Design of a blood flow system.

Adebola Osuntogun, Stephen Thomas, John Pitman, Sridhar Basavaraju, Bright Mulenga, Santosh S. Vempala

Proceedings of the 2009 International Conference on Information and Communication Technologies and Development, 2009

Sampling s-Concave Functions: The Limit of Convexity Based Isoperimetry.

Karthekeyan Chandrasekaran, Amit Deshpande, Santosh S. Vempala

Proceedings of the Approximation, 2009

Random Tensors and Planted Cliques.

S. Charles Brubaker, Santosh S. Vempala

Proceedings of the Approximation, 2009

2008

The Spectral Method for General Mixture Models.

Ravindran Kannan, Hadi Salmasian, Santosh S. Vempala

SIAM J. Comput., 2008

A simple polynomial-time rescaling algorithm for solving linear programs.

John Dunagan, Santosh S. Vempala

Math. Program., 2008

Algorithmic Prediction of Health-Care Costs.

Dimitris Bertsimas, Margrét V. Bjarnadóttir, Michael A. Kane, J. Christian Kryder, Rudra Pandey, Santosh S. Vempala, Grant Wang

Oper. Res., 2008

A discriminative framework for clustering via similarity functions.

Maria-Florina Balcan, Avrim Blum, Santosh S. Vempala

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

Path splicing.

Murtaza Motiwala, Megan Elmore, Nick Feamster, Santosh S. Vempala

Proceedings of the ACM SIGCOMM 2008 Conference on Applications, 2008

Isotropic PCA and Affine-Invariant Clustering.

S. Charles Brubaker, Santosh S. Vempala

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

2007

The geometry of logconcave functions and sampling algorithms.

László Lovász, Santosh S. Vempala

Random Struct. Algorithms, 2007

Nash equilibria in random games.

Imre Bárány, Santosh S. Vempala, Adrian Vetta

Random Struct. Algorithms, 2007

Path Splicing: Reliable Connectivity with Rapid Recovery.

Murtaza Motiwala, Nick Feamster, Santosh S. Vempala

Proceedings of the 6th ACM Workshop on Hot Topics in Networks, 2007

Life (and routing) on the Wireless Manifold.

Varun Kanade, Santosh S. Vempala

Proceedings of the 6th ACM Workshop on Hot Topics in Networks, 2007

Spectral Algorithms for Learning and Clustering.

Santosh S. Vempala

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

An Efficient Re-scaled Perceptron Algorithm for Conic Systems.

Alexandre Belloni, Robert M. Freund, Santosh S. Vempala

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

Filtering spam with behavioral blacklisting.

Anirudh Ramachandran, Nick Feamster, Santosh S. Vempala

Proceedings of the 2007 ACM Conference on Computer and Communications Security, 2007

2006

A divide-and-merge methodology for clustering.

David Cheng, Ravi Kannan, Santosh S. Vempala, Grant Wang

ACM Trans. Database Syst., 2006

Matrix Approximation and Projective Clustering via Volume Sampling.

Amit Deshpande, Luis Rademacher, Santosh S. Vempala, Grant Wang

Theory Comput., 2006

Hit-and-Run from a Corner.

László Lovász, Santosh S. Vempala

SIAM J. Comput., 2006

Simulated Annealing for Convex Optimization.

Adam Tauman Kalai, Santosh S. Vempala

Math. Oper. Res., 2006

Kernels as features: On kernels, margins, and low-dimensional mappings.

Maria-Florina Balcan, Avrim Blum, Santosh S. Vempala

Mach. Learn., 2006

An algorithmic theory of learning: Robust concepts and random projection.

Rosa I. Arriaga, Santosh S. Vempala

Mach. Learn., 2006

Simulated annealing in convex bodies and an <i>O</i>^*(<i>n</i>⁴) volume algorithm.

László Lovász, Santosh S. Vempala

J. Comput. Syst. Sci., 2006

Dispersion of Mass and the Complexity of Randomized Geometric Algorithms.

Luis Rademacher, Santosh S. Vempala

Electron. Colloquium Comput. Complex., 2006

Adaptive Sampling and Fast Low-Rank Matrix Approximation.

Amit Deshpande, Santosh S. Vempala

Electron. Colloquium Comput. Complex., 2006

On The Approximability Of The Traveling Salesman Problem.

Christos H. Papadimitriou, Santosh S. Vempala

Comb., 2006

Network Design Via Iterative Rounding Of Setpair Relaxations.

Joseph Cheriyan, Santosh S. Vempala, Adrian Vetta

Comb., 2006

Symmetric network computation.

David Pritchard, Santosh S. Vempala

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.

László Lovász, Santosh S. Vempala

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

2005

Efficient algorithms for online decision problems.

Adam Tauman Kalai, Santosh S. Vempala

J. Comput. Syst. Sci., 2005

Tensor decomposition and approximation schemes for constraint satisfaction problems.

Wenceslas Fernandez de la Vega, Marek Karpinski, Ravi Kannan, Santosh S. Vempala

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

2004

Flow metrics.

Claudson F. Bornstein, Santosh S. Vempala

Theor. Comput. Sci., 2004

On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems.

Robert D. Carr, Santosh S. Vempala

Math. Program., 2004

Clustering Large Graphs via the Singular Value Decomposition.

Petros Drineas, Alan M. Frieze, Ravi Kannan, Santosh S. Vempala, V. Vinay

Mach. Learn., 2004

A spectral algorithm for learning mixture models.

Santosh S. Vempala, Grant Wang

J. Comput. Syst. Sci., 2004

Optimal outlier removal in high-dimensional spaces.

John Dunagan, Santosh S. Vempala

J. Comput. Syst. Sci., 2004

On clusterings: Good, bad and spectral.

Ravi Kannan, Santosh S. Vempala, Adrian Vetta

J. ACM, 2004

Fast monte-carlo algorithms for finding low-rank approximations.

Alan M. Frieze, Ravi Kannan, Santosh S. Vempala

J. ACM, 2004

Solving convex programs by random walks.

Dimitris Bertsimas, Santosh S. Vempala

J. ACM, 2004

The Spectral Method for Mixture Models

Hadi Salmasian, Ravindran Kannan, Santosh S. Vempala

Electron. Colloquium Comput. Complex., 2004

Testing Geometric Convexity.

Luis Rademacher, Santosh S. Vempala

Proceedings of the FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science, 2004

The Random Projection Method

Santosh S. Vempala

DIMACS Series in Discrete Mathematics and Theoretical Computer Science 65, DIMACS/AMS, ISBN: 978-0-8218-3793-1, 2004

On Kernels, Margins, and Low-Dimensional Mappings.

Maria-Florina Balcan, Avrim Blum, Santosh S. Vempala

Proceedings of the Algorithmic Learning Theory, 15th International Conference, 2004

2003

An Approximation Algorithm for the Minimum-Cost k-Vertex Connected Subgraph.

Joseph Cheriyan, Santosh S. Vempala, Adrian Vetta

SIAM J. Comput., 2003

Logconcave Functions: Geometry and Efficient Sampling Algorithms

László Lovász, Santosh S. Vempala

Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

Simulated Annealing in Convex Bodies and an 0*(n4) Volume Algorithm.

László Lovász, Santosh S. Vempala

Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

2002

Randomized metarounding.

Robert D. Carr, Santosh S. Vempala

Random Struct. Algorithms, 2002

Efficient Algorithms for Universal Portfolios.

Adam Kalai, Santosh S. Vempala

J. Mach. Learn. Res., 2002

Approximation algorithms for minimum-cost k-vertex connected subgraphs.

Joseph Cheriyan, Santosh S. Vempala, Adrian Vetta

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

A Spectral Algorithm for Learning Mixtures of Distributions.

Santosh S. Vempala, Grant Wang

Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

2001

Random Sampling of Euler Tours.

Prasad Tetali, Santosh S. Vempala

Algorithmica, 2001

Optimal outlier removal in high-dimensional.

John Dunagan, Santosh S. Vempala

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

On Euclidean Embeddings and Bandwidth Minimization.

John Dunagan, Santosh S. Vempala

Proceedings of the Approximation, 2001

Fences Are Futile: On Relaxations for the Linear Ordering Problem.

Alantha Newman, Santosh S. Vempala

Proceedings of the Integer Programming and Combinatorial Optimization, 2001

Edge Covers of Setpairs and the Iterative Rounding Method.

Joseph Cheriyan, Santosh S. Vempala

Proceedings of the Integer Programming and Combinatorial Optimization, 2001

2000

Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems.

Avrim Blum, Goran Konjevod, R. Ravi, Santosh S. Vempala

Theor. Comput. Sci., 2000

Latent Semantic Indexing: A Probabilistic Analysis.

Christos H. Papadimitriou, Prabhakar Raghavan, Hisao Tamaki, Santosh S. Vempala

J. Comput. Syst. Sci., 2000

On the approximability of the traveling salesman problem (extended abstract).

Christos H. Papadimitriou, Santosh S. Vempala

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Randomized metarounding (extended abstract).

Robert D. Carr, Santosh S. Vempala

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Towards a 4/3 approximation for the asymmetric traveling salesman problem.

Robert D. Carr, Santosh S. Vempala, Jacques Mandler

Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

Factor 4/3 approximations for minimum 2-connected subgraphs.

Santosh S. Vempala, Adrian Vetta

Proceedings of the Approximation Algorithms for Combinatorial Optimization, 2000

1999

Simple Markov-chain algorithms for generating bipartite graphs and tournaments.

Ravi Kannan, Prasad Tetali, Santosh S. Vempala

Random Struct. Algorithms, 1999

A Constant-Factor Approximation Algorithm for the <i>k</i>-MST Problem.

Avrim Blum, R. Ravi, Santosh S. Vempala

J. Comput. Syst. Sci., 1999

A Convex Relaxation for the Asymmetric TSP.

Santosh S. Vempala, Mihalis Yannakakis

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Clustering in Large Graphs and Matrices.

Petros Drineas, Alan M. Frieze, Ravi Kannan, Santosh S. Vempala, V. Vinay

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Approximating Multicast Congestion.

Santosh S. Vempala, Berthold Vöcking

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.

Joseph S. B. Mitchell, Avrim Blum, Prasad Chalasani, Santosh S. Vempala

SIAM J. Comput., 1998

New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen.

Baruch Awerbuch, Yossi Azar, Avrim Blum, Santosh S. Vempala

SIAM J. Comput., 1998

A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions.

Avrim Blum, Alan M. Frieze, Ravi Kannan, Santosh S. Vempala

Algorithmica, 1998

Random Projection: A New Approach to VLSI Layout.

Santosh S. Vempala

Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

1997

The Colin de Verdière Number and Sphere Representations of a Graph.

Andrew Kotlov, László Lovász, Santosh S. Vempala

Comb., 1997

Sampling Lattice Points.

Ravi Kannan, Santosh S. Vempala

Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Locality-Preserving Hashing in Multidimensional Spaces.

Piotr Indyk, Rajeev Motwani, Prabhakar Raghavan, Santosh S. Vempala

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

Ravi Kannan, Prasad Tetali, Santosh S. Vempala

Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

A Random Sampling Based Algorithm for Learning the Intersection of Half-spaces.

Santosh S. Vempala

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

Avrim Blum, R. Ravi, Santosh S. Vempala

Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

1995

A constant-factor approximation for the <i>k</i>-MST problem in the plane.

Avrim Blum, Prasad Chalasani, Santosh S. Vempala

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.

Baruch Awerbuch, Yossi Azar, Avrim Blum, Santosh S. Vempala

Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

1994

A Limited-Backtrack Greedy Schema for Approximation Algorithms.

Vivek Arora, Santosh S. Vempala, Huzur Saran, Vijay V. Vazirani

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1994

1993

Improved Approximation Algorithms for Biconnected Subgraphs via Better Lower Bounding Techniques.

Naveen Garg, Santosh S. Vempala, Aman Singla

Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1993