Santosh S. Vempala

Orcid: 0000-0002-3779-433X

Affiliations:
  • Georgia Institute of Technology, School of Computer Science, Atlanta, GA, USA


According to our database1, Santosh S. Vempala authored at least 232 papers between 1993 and 2023.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

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
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2023
Convergence of Gibbs Sampling: Coordinate Hit-and-Run Mixes Fast.
Discret. Comput. Geom., September, 2023

Calibrated Language Models Must Hallucinate.
CoRR, 2023

Efficiently Sampling the PSD Cone with the Metric Dikin Walk.
CoRR, 2023

Computation with Sequences in the Brain.
CoRR, 2023

Sampling with Barriers: Faster Mixing via Lewis Weights.
CoRR, 2023

Contrastive Moments: Unsupervised Halfspace Learning in Polynomial Time.
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

The Bit Complexity of Efficient Continuous Optimization.
Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

The k-Cap Process on Geometric Random Graphs.
Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

Is Planted Coloring Easier than Planted Clique?
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

Geodesic Walks in Polytopes.
SIAM J. Comput., 2022

Approximating sparse graphs: The random overlapping communities model.
Random Struct. Algorithms, 2022

A unified view of graph regularity via matrix decompositions.
Random Struct. Algorithms, 2022

Socially fair network design via iterative rounding.
Oper. Res. Lett., 2022

A Slightly Improved Bound for the KLS Constant.
CoRR, 2022

Constant-Factor Approximation Algorithms for Socially Fair k-Clustering.
CoRR, 2022

Convergence of the Riemannian Langevin Algorithm.
CoRR, 2022

Robustly learning mixtures of <i>k</i> arbitrary Gaussians.
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.
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).
Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Assemblies of neurons learn to classify well-separated distributions.
Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

A Unified Approach to Discrepancy Minimization.
Proceedings of the Approximation, 2022

The Mirror Langevin Algorithm Converges with Vanishing Bias.
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.
Proceedings of the International Conference on Artificial Intelligence and Statistics, 2022

Provable Lifelong Learning of Representations.
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

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

Sparse Regression Faster than d<sup>ω</sup>.
CoRR, 2021

Tutorial on the Robust Interior Point Method.
CoRR, 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

Solving Sparse Linear Systems Faster than Matrix Multiplication.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Socially Fair k-Means Clustering.
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

Robustly Learning Mixtures of k Arbitrary Gaussians.
CoRR, 2020

Reducing Isotropy and Volume to KLS: An O(n<sup>3</sup>ψ<sup>2</sup>) Volume Algorithm.
CoRR, 2020

Fair k-Means Clustering.
CoRR, 2020

Strong self-concordance and sampling.
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

The Communication Complexity of Optimization.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

2019
Brain Computation: A Computer Science Perspective.
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.
ACM Trans. Algorithms, 2019

Matrix Decompositions and Sparse Graph Regularity.
CoRR, 2019

Human-Usable Password Schemas: Beyond Information-Theoretic Security.
CoRR, 2019

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

Fair Dimensionality Reduction and Iterative Rounding for SDPs.
CoRR, 2019

Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices.
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.
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.
Proceedings of the 2019 ITU Kaleidoscope: ICT for Health: Networks, 2019

Random Projection in the Brain and Computation with Assemblies of Neurons.
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

Gaussian Cooling and O<sup>*(n<sup>3)</sup></sup> Algorithms for Volume and Gaussian Volume.
SIAM J. Comput., 2018

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

The Kannan-Lovász-Simonovits Conjecture.
CoRR, 2018

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

Stochastic localization + Stieltjes barrier = tight bound for log-Sobolev.
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

The Price of Fair PCA: One Extra dimension.
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.
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.
Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Usability of Humanly Computable Passwords.
Proceedings of the Sixth AAAI Conference on Human Computation and Crowdsourcing, 2018

Continuous Algorithms (Invited Paper).
Proceedings of the 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2018

Efficient Convex Optimization with Membership Oracles.
Proceedings of the Conference On Learning Theory, 2018

2017
Geometric random edge.
Math. Program., 2017

Statistical Algorithms and a Lower Bound for Detecting Planted Cliques.
J. ACM, 2017

Random Overlapping Communities: Approximating Motif Densities of Large Graphs.
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

Randomized algorithms in numerical linear algebra.
Acta Numer., 2017

Adaptive Matrix Vector Product.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

On the Complexity of Learning Neural Networks.
Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

Towards Human Computable Passwords.
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

The Hidden Hubs Problem.
Proceedings of the 30th Conference on Learning Theory, 2017

2016
A note on non-degenerate integer programs with small sub-determinants.
Oper. Res. Lett., 2016

A practical volume algorithm.
Math. Program. Comput., 2016

The Cutting Plane Method is Polynomial for Perfect Matchings.
Math. Oper. Res., 2016

Beyond Spectral: Tight Bounds for Planted Gaussians.
CoRR, 2016

Variable Binding through Assemblies in Spiking Neural Networks.
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

Accelerated Newton Iteration for Roots of Black Box Polynomials.
Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

Agnostic Estimation of Mean and Covariance.
Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

Cortical Computation via Iterative Constructions.
Proceedings of the 29th Conference on Learning Theory, 2016

2015
Visual Categorization with Random Projection.
Neural Comput., 2015

Stochastic Billiards for Sampling from the Boundary of a Convex Set.
Math. Oper. Res., 2015

Query Complexity of Sampling and Small Geometric Partitions.
Comb. Probab. Comput., 2015

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

Statistical Query Algorithms for Stochastic Convex Optimization.
CoRR, 2015

Bypassing KLS: Gaussian Cooling and an O^*(n3) Volume Algorithm.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Cortical Computation.
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.
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.
Proceedings of the Third AAAI Conference on Human Computation and Crowdsourcing, 2015

Max vs Min: Tensor Decomposition and ICA with nearly Linear Sample Complexity.
Proceedings of The 28th Conference on Learning Theory, 2015

Cortical Learning via Prediction.
Proceedings of The 28th Conference on Learning Theory, 2015

Efficient Representations for Lifelong Learning and Autoencoding.
Proceedings of The 28th Conference on Learning Theory, 2015

2014
Expanders via Random Spanning Trees.
SIAM J. Comput., 2014

On the Complexity of Random Satisfiability Problems with Planted Solutions.
Electron. Colloquium Comput. Complex., 2014

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

Unsupervised Learning through Prediction in a Model of Cortex.
CoRR, 2014

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

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

Efficient Representations for Life-Long Learning and Autoencoding.
CoRR, 2014

Fourier PCA and robust tensor decomposition.
Proceedings of the Symposium on Theory of Computing, 2014

A Cubic Algorithm for Computing Gaussian Volume.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Integer feasibility of random polytopes: random integer programs.
Proceedings of the Innovations in Theoretical Computer Science, 2014

Principal Component Analysis and Higher Correlations for Distributed Data.
Proceedings of The 27th Conference on Learning Theory, 2014

2013
Near-optimal deterministic algorithms for volume computation via M-ellipsoids.
Proc. Natl. Acad. Sci. USA, 2013

Nimble Algorithms for Cloud Computing
CoRR, 2013

Fourier PCA.
CoRR, 2013

The approximate rank of a matrix and its algorithmic applications: approximate rank.
Proceedings of the Symposium on Theory of Computing Conference, 2013

The Complexity of Approximating Vertex Expansion.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

Complexity of learning subspace juntas and ICA.
Proceedings of the 2013 Asilomar Conference on Signals, 2013

2012
A Deterministic Polynomial-Time Approximation Scheme for Counting Knapsack Solutions.
SIAM J. Comput., 2012

Local Versus Global Properties of Metric Spaces.
SIAM J. Comput., 2012

Statistical Algorithms and a Lower Bound for Planted Clique.
Electron. Colloquium Comput. Complex., 2012

The Approximate Rank of a Matrix and its Algorithmic Applications.
Electron. Colloquium Comput. Complex., 2012

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

The Complexity of Statistical Algorithms
CoRR, 2012

Modeling high-dimensional data: technical perspective.
Commun. ACM, 2012

Many sparse cuts via higher eigenvalues.
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

Effective Principal Component Analysis.
Proceedings of the Similarity Search and Applications - 5th International Conference, 2012

Randomly-oriented k-d Trees Adapt to Intrinsic Dimension.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2012

2011
A Discrepancy based Approach to Integer Programming
CoRR, 2011

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

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

Algorithms for Implicit Hitting Set Problems.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

LifeNet: a flexible ad hoc networking solution for transient environments.
Proceedings of the ACM SIGCOMM 2011 Conference on Applications, 2011

An FPTAS for #Knapsack and Related Counting Problems.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

Algorithmic Extensions of Cheeger's Inequality to Higher Eigenvalues and Partitions.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

Semantic Communication for Simple Goals Is Equivalent to On-line Learning.
Proceedings of the Algorithmic Learning Theory - 22nd International Conference, 2011

On Noise-Tolerant Learning of Sparse Parities and Related Problems.
Proceedings of the Algorithmic Learning Theory - 22nd International Conference, 2011

2010
A random-sampling-based algorithm for learning intersections of halfspaces.
J. ACM, 2010

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

Logconcave Random Graphs.
Electron. J. Comb., 2010

Chipping Away at Censorship Firewalls with User-Generated Content.
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

Circumventing censorship with collage.
Proceedings of the ACM SIGCOMM 2010 Conference on Applications, 2010

On Nash-Equilibria of Approximation-Stable Games.
Proceedings of the Algorithmic Game Theory - Third International Symposium, 2010

A New Approach to Strongly Polynomial Linear Programming.
Proceedings of the Innovations in Computer Science, 2010

Recent Progress and Open Problems in Algorithmic Convex Geometry.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2010

Learning Convex Concepts from Gaussian Distributions with PCA.
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

Corrigendum: A Random Sampling Algorithm for Learning an Intersection of Halfspaces.
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

2009
An Efficient Rescaled Perceptron Algorithm for Conic Systems.
Math. Oper. Res., 2009

Adaptive simulated annealing: A near-optimal connection between sampling and counting.
J. ACM, 2009

Spectral Algorithms.
Found. Trends Theor. Comput. Sci., 2009

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

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

Expanders via random spanning trees.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Design and deployment of a blood safety monitoring tool.
Proceedings of the 2009 International Conference on Information and Communication Technologies and Development, 2009

Design of a blood flow system.
Proceedings of the 2009 International Conference on Information and Communication Technologies and Development, 2009

Sampling s-Concave Functions: The Limit of Convexity Based Isoperimetry.
Proceedings of the Approximation, 2009

Random Tensors and Planted Cliques.
Proceedings of the Approximation, 2009

2008
The Spectral Method for General Mixture Models.
SIAM J. Comput., 2008

A simple polynomial-time rescaling algorithm for solving linear programs.
Math. Program., 2008

Algorithmic Prediction of Health-Care Costs.
Oper. Res., 2008

A discriminative framework for clustering via similarity functions.
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Path splicing.
Proceedings of the ACM SIGCOMM 2008 Conference on Applications, 2008

Isotropic PCA and Affine-Invariant Clustering.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007
The geometry of logconcave functions and sampling algorithms.
Random Struct. Algorithms, 2007

Nash equilibria in random games.
Random Struct. Algorithms, 2007

Path Splicing: Reliable Connectivity with Rapid Recovery.
Proceedings of the 6th ACM Workshop on Hot Topics in Networks, 2007

Life (and routing) on the Wireless Manifold.
Proceedings of the 6th ACM Workshop on Hot Topics in Networks, 2007

Spectral Algorithms for Learning and Clustering.
Proceedings of the Learning Theory, 20th Annual Conference on Learning Theory, 2007

An Efficient Re-scaled Perceptron Algorithm for Conic Systems.
Proceedings of the Learning Theory, 20th Annual Conference on Learning Theory, 2007

Filtering spam with behavioral blacklisting.
Proceedings of the 2007 ACM Conference on Computer and Communications Security, 2007

2006
A divide-and-merge methodology for clustering.
ACM Trans. Database Syst., 2006

Matrix Approximation and Projective Clustering via Volume Sampling.
Theory Comput., 2006

Hit-and-Run from a Corner.
SIAM J. Comput., 2006

Simulated Annealing for Convex Optimization.
Math. Oper. Res., 2006

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

An algorithmic theory of learning: Robust concepts and random projection.
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

Dispersion of Mass and the Complexity of Randomized Geometric Algorithms.
Electron. Colloquium Comput. Complex., 2006

Adaptive Sampling and Fast Low-Rank Matrix Approximation.
Electron. Colloquium Comput. Complex., 2006

On The Approximability Of The Traveling Salesman Problem.
Comb., 2006

Network Design Via Iterative Rounding Of Setpair Relaxations.
Comb., 2006

Symmetric network computation.
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
Efficient algorithms for online decision problems.
J. Comput. Syst. Sci., 2005

Tensor decomposition and approximation schemes for constraint satisfaction problems.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

2004
Flow metrics.
Theor. Comput. Sci., 2004

On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems.
Math. Program., 2004

Clustering Large Graphs via the Singular Value Decomposition.
Mach. Learn., 2004

A spectral algorithm for learning mixture models.
J. Comput. Syst. Sci., 2004

Optimal outlier removal in high-dimensional spaces.
J. Comput. Syst. Sci., 2004

On clusterings: Good, bad and spectral.
J. ACM, 2004

Fast monte-carlo algorithms for finding low-rank approximations.
J. ACM, 2004

Solving convex programs by random walks.
J. ACM, 2004

The Spectral Method for Mixture Models
Electron. Colloquium Comput. Complex., 2004

Testing Geometric Convexity.
Proceedings of the FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science, 2004

The Random Projection Method
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.
Proceedings of the Algorithmic Learning Theory, 15th International Conference, 2004

2003
An Approximation Algorithm for the Minimum-Cost k-Vertex Connected Subgraph.
SIAM J. Comput., 2003

Logconcave Functions: Geometry and Efficient Sampling Algorithms
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

Simulated Annealing in Convex Bodies and an 0*(n4) Volume Algorithm.
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

2002
Randomized metarounding.
Random Struct. Algorithms, 2002

Efficient Algorithms for Universal Portfolios.
J. Mach. Learn. Res., 2002

Approximation algorithms for minimum-cost k-vertex connected subgraphs.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

A Spectral Algorithm for Learning Mixtures of Distributions.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

2001
Random Sampling of Euler Tours.
Algorithmica, 2001

Optimal outlier removal in high-dimensional.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

On Euclidean Embeddings and Bandwidth Minimization.
Proceedings of the Approximation, 2001

Fences Are Futile: On Relaxations for the Linear Ordering Problem.
Proceedings of the Integer Programming and Combinatorial Optimization, 2001

Edge Covers of Setpairs and the Iterative Rounding Method.
Proceedings of the Integer Programming and Combinatorial Optimization, 2001

2000
Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems.
Theor. Comput. Sci., 2000

Latent Semantic Indexing: A Probabilistic Analysis.
J. Comput. Syst. Sci., 2000

On the approximability of the traveling salesman problem (extended abstract).
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Randomized metarounding (extended abstract).
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Towards a 4/3 approximation for the asymmetric traveling salesman problem.
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

Factor 4/3 approximations for minimum 2-connected subgraphs.
Proceedings of the Approximation Algorithms for Combinatorial Optimization, 2000

1999
Simple Markov-chain algorithms for generating bipartite graphs and tournaments.
Random Struct. Algorithms, 1999

A Constant-Factor Approximation Algorithm for the <i>k</i>-MST Problem.
J. Comput. Syst. Sci., 1999

A Convex Relaxation for the Asymmetric TSP.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Clustering in Large Graphs and Matrices.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Approximating Multicast Congestion.
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

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

Random Projection: A New Approach to VLSI Layout.
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.
Comb., 1997

Sampling Lattice Points.
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Locality-Preserving Hashing in Multidimensional Spaces.
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

A Random Sampling Based Algorithm for Learning the Intersection of Half-spaces.
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
A constant-factor approximation for the <i>k</i>-MST problem in the plane.
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
A Limited-Backtrack Greedy Schema for Approximation Algorithms.
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


  Loading...