All Publications (PDF files)

• Euclidean distance compression via deep random features. (Brett Leroux)
  To appear in NeurIPS 2024.
• On the Nystrom Approximation for Preconditioning in Kernel Machines. (Amirhesam Abedsoltan, Mikhail Belkin, Parthe Pandit)
  AISTATS 2024. Arxiv.
• Estranged facets and k-facets of Gaussian random point sets. (Brett Leroux)
  To appear in Journal of Applied Probability.
• Expansion of random 0/1 polytopes. (Brett Leroux)
  Random Structures & Algorithms, Arxiv, 2023.
• Improved bounds for the expected number of k-sets. (Brett Leroux)
  Discrete and Computational Geometry, Arxiv, 2023.
• The smoothed complexity of Frank-Wolfe methods via conditioning of random matrices and polytopes. (Chang Shu)
  Mathematical Statistics and Learning., 2022.
• Overcomplete order-3 tensor decomposition, blind deconvolution and Gaussian mixture models. (Haolin Chen)
  SIAM Journal on Mathematics of Data Science, 2022.
• Algebraic k-sets and generally neighborly embeddings. (Brett Leroux)
  Discrete and Computational Geometry, 2022.
• Efficiency of the floating body as a robust measure of dispersion. (Joseph Anderson)
  SODA 2020.
• The Minimum Euclidean-Norm Point in a Convex Polytope: Wolfe's Combinatorial Algorithm is Exponential. (Jesús De Loera, Jamie Haddock)
  SIAM Journal on Computing, 2020.
  STOC 2018, Arxiv.
• Eigenvectors of Orthogonally Decomposable Functions. (formerly "Basis learning as an algorithmic primitive") (Mikhail Belkin, James Voss)
  SIAM Journal on Computing, 2018.
  COLT 2016. Video and slides of talk at Simons Institute.
• Heavy-tailed analogues of the covariance matrix for ICA. (Joseph Anderson, Navin Goyal, Anupama Nandi)
  AAAI 2017.
• The hidden convexity of spectral clustering. (James Voss, Mikhail Belkin)
  AAAI 2016. Video and slides of talk at Simons Institute.
• On packing and covering polyhedra in infinite dimensions. (Alejandro Toriello, Juan Pablo Vielma)
  Operations Research Letters, 2016.
• A Pseudo-Euclidean Iteration for Optimal Recovery in Noisy ICA. (James Voss, Mikhail Belkin)
  NIPS 2015.
• Heavy-tailed Independent Component Analysis. (Joseph Anderson, Navin Goyal, Anupama Nandi)
  FOCS 2015.
• A simplicial polytope that maximizes the isotropic constant must be a simplex.
  Mathematika, 2015. Arxiv.
• Efficient volume sampling for row/column subset selection. (Amit Deshpande, Abhisek Kundu)
  In preparation, 2014.
• Expanders via random spanning trees. (Alan Frieze, Navin Goyal, Santosh Vempala)
  SIAM Journal on Computing, 2014.
  SODA 2009. Video of workshop talk.
• Lower bounds for the average and smoothed number of Pareto-optima. (Tobias Brunsch, Navin Goyal, Heiko Röglin)
  Theory of Computing, 2014.
• The more, the merrier: the blessing of dimensionality for learning large Gaussian mixtures. (Joseph Anderson, Mikhail Belkin, Navin Goyal, James Voss)
  COLT 2014. Video and slides of talk (by J. Anderson).
• Query complexity of sampling and small geometric partitions. (Navin Goyal, Santosh Vempala)
  Combinatorics, Probability and Computing. Arxiv. 2014.
• Fast algorithms for Gaussian noise invariant Independent Component Analysis. (Mikhail Belkin, James Voss)
  NIPS 2013. MATLAB implementation of GI-ICA.
• Efficient learning of simplices. (Joseph Anderson, Navin Goyal)
  COLT 2013. Video and slides of talk.
• Blind signal separation in the presence of Gaussian noise. (Mikhail Belkin, James Voss)
  COLT 2013. Arxiv. Video and slides of talk (by J. Voss).
• Lower bounds for the average and smoothed number of Pareto optima. (Navin Goyal)
  FSTTCS 2012. Arxiv.
• On the monotonicity of the expected volume of a random simplex.
  Mathematika, 2012. Arxiv. Presentation at Oberwolfach: PPTX, PDF.
  Computational experiments for the 3-dimensional case.
• Efficient volume sampling for row/column subset selection. (Amit Deshpande)
  FOCS 2010. Video of talk.
• Partitioning a planar graph of girth 10 into a forest and a matching. (A. Bassa, J. Burns, J. Campbell, A. Deshpande, J. Farley, M. Halsey, S.-Y. Ho, D. Kleitman, S. Michalakis, P.-O. Persson, P. Pylyavskyy, A. Riehl, M. Rios, J. Samuel, B. E. Tenner, A. Vijayasarathy, L. Zhao)
  Studies in Applied Mathematics, 2010.
• Optimization of a convex program with a polynomial perturbation. (Ravi Kannan)
  Operations Research Letters, 2009.
• Learning convex bodies is hard. (Navin Goyal) 
  COLT 2009. Video of workshop talk (by N. Goyal).
• Minimal Partitioning into Product Sets. (Xuancheng Shao) In preparation.
• Approximating the Centroid is Hard. PDF presentation.
  SOCG 2007.
• Dispersion of Mass and the Complexity of Geometric Problems. 
  PhD thesis, Department of Mathematics, MIT, 2007. Advisor: Santosh Vempala.
• Dispersion of Mass and the Complexity of Randomized Geometric Algorithms. (Santosh Vempala)
  Advances in Mathematics and FOCS 2006.
  PDF presentation of the volume lower bound.
• Computing Equilibrium Prices in Exchange Economies with Tax Distortions. (Bruno Codenotti, Kasturi Varadarajan)
  ICALP 2006.
• Matrix Approximation and Projective Clustering via Volume Sampling. (Amit Deshpande, Santosh Vempala, Grant Wang)
  Theory of Computing and SODA 2006. Short PDF presentation.
• Testing geometric convexity. (Santosh Vempala)
  FSTTCS 2004. Short PDF presentation.
  The Cross-Polytope with Peaks (java applet).
• Computation and Stability of Nash Equilibria and Applications to the Modeling of the Electrical Energy Generation Market (in Spanish).
  Math. Eng. Thesis, Department of Mathematical Engineering, University of Chile, Santiago, Chile, August 2002.