Laddha, Aditi; Vempala, Santosh S. Convergence of Gibbs sampling: coordinate hit-and-run mixes fast. (English) Zbl 1526.60042 Discrete Comput. Geom. 70, No. 2, 406-425 (2023). MSC: 60J05 PDFBibTeX XMLCite \textit{A. Laddha} and \textit{S. S. Vempala}, Discrete Comput. Geom. 70, No. 2, 406--425 (2023; Zbl 1526.60042) Full Text: DOI arXiv
Cao, Xinyuan; Vempala, Santosh S. Contrastive Moments: Unsupervised Halfspace Learning in Polynomial Time. arXiv:2311.01435 Preprint, arXiv:2311.01435 [cs.LG] (2023). BibTeX Cite \textit{X. Cao} and \textit{S. S. Vempala}, ``Contrastive Moments: Unsupervised Halfspace Learning in Polynomial Time'', Preprint, arXiv:2311.01435 [cs.LG] (2023) Full Text: arXiv OA License
Kook, Yunbum; Vempala, Santosh S. Gaussian Cooling and Dikin Walks: The Interior-Point Method for Logconcave Sampling. arXiv:2307.12943 Preprint, arXiv:2307.12943 [cs.DS] (2023). BibTeX Cite \textit{Y. Kook} and \textit{S. S. Vempala}, ``Gaussian Cooling and Dikin Walks: The Interior-Point Method for Logconcave Sampling'', Preprint, arXiv:2307.12943 [cs.DS] (2023) Full Text: arXiv OA License
Ghadiri, Mehrdad; Peng, Richard; Vempala, Santosh S. The Bit Complexity of Efficient Continuous Optimization. arXiv:2304.02124 Preprint, arXiv:2304.02124 [cs.DS] (2023). MSC: 62J05 BibTeX Cite \textit{M. Ghadiri} et al., ``The Bit Complexity of Efficient Continuous Optimization'', Preprint, arXiv:2304.02124 [cs.DS] (2023) Full Text: arXiv OA License
Gatmiry, Khashayar; Kelner, Jonathan; Vempala, Santosh S. Sampling with Barriers: Faster Mixing via Lewis Weights. arXiv:2303.00480 Preprint, arXiv:2303.00480 [cs.DS] (2023). BibTeX Cite \textit{K. Gatmiry} et al., ``Sampling with Barriers: Faster Mixing via Lewis Weights'', Preprint, arXiv:2303.00480 [cs.DS] (2023) Full Text: arXiv OA License
Bakshi, Ainesh; Diakonikolas, Ilias; Jia, He; Kane, Daniel M.; Kothari, Pravesh K.; Vempala, Santosh S. Robustly learning mixtures of \(k\) arbitrary Gaussians. (English) Zbl 07774413 Leonardi, Stefano (ed.) et al., Proceedings of the 54th annual ACM SIGACT symposium on theory of computing, STOC ’22, Rome, Italy June 20–24, 2022. New York, NY: Association for Computing Machinery (ACM). 1234-1247 (2022). MSC: 68Qxx PDFBibTeX XMLCite \textit{A. Bakshi} et al., in: Proceedings of the 54th annual ACM SIGACT symposium on theory of computing, STOC '22, Rome, Italy June 20--24, 2022. New York, NY: Association for Computing Machinery (ACM). 1234--1247 (2022; Zbl 07774413) Full Text: DOI arXiv
Petti, Samantha; Vempala, Santosh S. Approximating sparse graphs: the random overlapping communities model. (English) Zbl 07751093 Random Struct. Algorithms 61, No. 4, 844-908 (2022). MSC: 05-XX 68-XX PDFBibTeX XMLCite \textit{S. Petti} and \textit{S. S. Vempala}, Random Struct. Algorithms 61, No. 4, 844--908 (2022; Zbl 07751093) Full Text: DOI arXiv
Bodwin, Greg; Vempala, Santosh A unified view of graph regularity via matrix decompositions. (English) Zbl 1522.05464 Random Struct. Algorithms 61, No. 1, 62-83 (2022). MSC: 05C85 05C42 68W25 68Q25 68R10 PDFBibTeX XMLCite \textit{G. Bodwin} and \textit{S. Vempala}, Random Struct. Algorithms 61, No. 1, 62--83 (2022; Zbl 1522.05464) Full Text: DOI arXiv
Laddha, Aditi; Singh, Mohit; Vempala, Santosh S. Socially fair network design via iterative rounding. (English) Zbl 1525.90095 Oper. Res. Lett. 50, No. 5, 536-540 (2022). MSC: 90B10 90C27 90C29 PDFBibTeX XMLCite \textit{A. Laddha} et al., Oper. Res. Lett. 50, No. 5, 536--540 (2022; Zbl 1525.90095) Full Text: DOI
Chen, Zongchen; Vempala, Santosh S. Optimal convergence rate of Hamiltonian Monte Carlo for strongly logconcave distributions. (English) Zbl 07528585 Theory Comput. 18, Paper No. 9, 18 p. (2022). MSC: 68Qxx 60J05 60J25 68W20 PDFBibTeX XMLCite \textit{Z. Chen} and \textit{S. S. Vempala}, Theory Comput. 18, Paper No. 9, 18 p. (2022; Zbl 07528585) Full Text: DOI arXiv
Lee, Yin Tat; Vempala, Santosh Geodesic walks in polytopes. (English) Zbl 07516622 SIAM J. Comput. 51, No. 2, STOC17-400-STOC17-488 (2022). MSC: 68W20 65C05 58D17 PDFBibTeX XMLCite \textit{Y. T. Lee} and \textit{S. Vempala}, SIAM J. Comput. 51, No. 2, STOC17--400-STOC17--488 (2022; Zbl 07516622) Full Text: DOI
Kook, Yunbum; Lee, Yin Tat; Shen, Ruoqi; Vempala, Santosh S. Condition-number-independent convergence rate of Riemannian Hamiltonian Monte Carlo with numerical integrators. arXiv:2210.07219 Preprint, arXiv:2210.07219 [cs.DS] (2022). BibTeX Cite \textit{Y. Kook} et al., ``Condition-number-independent convergence rate of Riemannian Hamiltonian Monte Carlo with numerical integrators'', Preprint, arXiv:2210.07219 [cs.DS] (2022) Full Text: arXiv OA License
Jambulapati, Arun; Lee, Yin Tat; Vempala, Santosh S. A Slightly Improved Bound for the KLS Constant. arXiv:2208.11644 Preprint, arXiv:2208.11644 [math.FA] (2022). BibTeX Cite \textit{A. Jambulapati} et al., ``A Slightly Improved Bound for the KLS Constant'', Preprint, arXiv:2208.11644 [math.FA] (2022) Full Text: arXiv OA License
Gatmiry, Khashayar; Vempala, Santosh S. Convergence of the Riemannian Langevin Algorithm. arXiv:2204.10818 Preprint, arXiv:2204.10818 [cs.LG] (2022). MSC: 58D17 BibTeX Cite \textit{K. Gatmiry} and \textit{S. S. Vempala}, ``Convergence of the Riemannian Langevin Algorithm'', Preprint, arXiv:2204.10818 [cs.LG] (2022) Full Text: arXiv OA License
Reid, Mirabel; Vempala, Santosh S. The \(k\)-Cap Process on Geometric Random Graphs. arXiv:2203.12680 Preprint, arXiv:2203.12680 [math.PR] (2022). MSC: 37E05 37E25 BibTeX Cite \textit{M. Reid} and \textit{S. S. Vempala}, ``The $k$-Cap Process on Geometric Random Graphs'', Preprint, arXiv:2203.12680 [math.PR] (2022) Full Text: arXiv OA License
Peng, Richard; Vempala, Santosh Solving sparse linear systems faster than matrix multiplication. (English) Zbl 07788369 Marx, Dániel (ed.), Proceedings of the 32nd annual ACM-SIAM symposium on discrete algorithms, SODA 2021, Alexandria, VA, USA, virtual, January 10–13, 2021. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 504-521 (2021). MSC: 68Wxx PDFBibTeX XMLCite \textit{R. Peng} and \textit{S. Vempala}, in: Proceedings of the 32nd annual ACM-SIAM symposium on discrete algorithms, SODA 2021, Alexandria, VA, USA, virtual, January 10--13, 2021. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 504--521 (2021; Zbl 07788369) Full Text: DOI arXiv
Jia, He; Laddha, Aditi; Lee, Yin Tat; Vempala, Santosh Reducing isotropy and volume to KLS: an \(O*(n^3\psi^2)\) volume algorithm. (English) Zbl 07765224 Khuller, Samir (ed.) et al., Proceedings of the 53rd annual ACM SIGACT symposium on theory of computing, STOC ’21, virtual, Italy, June 21–25, 2021. New York, NY: Association for Computing Machinery (ACM). 961-974 (2021). MSC: 68Qxx PDFBibTeX XMLCite \textit{H. Jia} et al., in: Proceedings of the 53rd annual ACM SIGACT symposium on theory of computing, STOC '21, virtual, Italy, June 21--25, 2021. New York, NY: Association for Computing Machinery (ACM). 961--974 (2021; Zbl 07765224) Full Text: DOI arXiv
Feldman, Vitaly; Guzmán, Cristóbal; Vempala, Santosh Statistical query algorithms for mean vector estimation and stochastic convex optimization. (English) Zbl 1477.90046 Math. Oper. Res. 46, No. 3, 912-945 (2021). MSC: 90C15 90C25 68Q32 PDFBibTeX XMLCite \textit{V. Feldman} et al., Math. Oper. Res. 46, No. 3, 912--945 (2021; Zbl 1477.90046) Full Text: DOI arXiv
Lee, Yin Tat; Vempala, Santosh S. Tutorial on the Robust Interior Point Method. arXiv:2108.04734 Preprint, arXiv:2108.04734 [cs.DS] (2021). BibTeX Cite \textit{Y. T. Lee} and \textit{S. S. Vempala}, ``Tutorial on the Robust Interior Point Method'', Preprint, arXiv:2108.04734 [cs.DS] (2021) Full Text: arXiv OA License
Vempala, Santosh S.; Wang, Ruosong; Woodruff, David P. The communication complexity of optimization. (English) Zbl 07304129 Chawla, Shuchi (ed.), Proceedings of the 31st annual ACM-SIAM symposium on discrete algorithms, SODA 2020, Salt Lake City, UT, USA, January 5–8, 2020. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1733-1752 (2020). MSC: 68Wxx PDFBibTeX XMLCite \textit{S. S. Vempala} et al., in: Proceedings of the 31st annual ACM-SIAM symposium on discrete algorithms, SODA 2020, Salt Lake City, UT, USA, January 5--8, 2020. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1733--1752 (2020; Zbl 07304129) Full Text: DOI arXiv
Laddha, Aditi; Lee, Yin Tat; Vempala, Santosh Strong self-concordance and sampling. (English) Zbl 07298322 Makarychev, Konstantin (ed.) et al., Proceedings of the 52nd annual ACM SIGACT symposium on theory of computing, STOC ’20, Chicago, IL, USA, June 22–26, 2020. New York, NY: Association for Computing Machinery (ACM). 1212-1222 (2020). MSC: 68Qxx PDFBibTeX XMLCite \textit{A. Laddha} et al., in: Proceedings of the 52nd annual ACM SIGACT symposium on theory of computing, STOC '20, Chicago, IL, USA, June 22--26, 2020. New York, NY: Association for Computing Machinery (ACM). 1212--1222 (2020; Zbl 07298322) Full Text: DOI arXiv
Jiang, Haotian; Lee, Yin Tat; Vempala, Santosh S. A generalized central limit conjecture for convex bodies. (English) Zbl 1448.52004 Klartag, Bo’az (ed.) et al., Geometric aspects of functional analysis. Israel seminar (GAFA) 2017–2019. Volume II. Cham: Springer. Lect. Notes Math. 2266, 1-41 (2020). Reviewer: Fraser Daly (Edinburgh) MSC: 52A22 60F05 PDFBibTeX XMLCite \textit{H. Jiang} et al., Lect. Notes Math. 2266, 1--41 (2020; Zbl 1448.52004) Full Text: DOI arXiv
Chen, Zongchen; Vempala, Santosh S. Optimal convergence rate of Hamiltonian Monte Carlo for strongly logconcave distributions. (English) Zbl 07650131 Achlioptas, Dimitris (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques, 22nd international conference, APPROX 2019, and 23rd international conference, RANDOM 2019, Massachusetts Institute of Technology, Cambridge, MA, USA, September 20–22, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 145, Article 64, 12 p. (2019). MSC: 68W20 68W25 90C27 PDFBibTeX XMLCite \textit{Z. Chen} and \textit{S. S. Vempala}, LIPIcs -- Leibniz Int. Proc. Inform. 145, Article 64, 12 p. (2019; Zbl 07650131) Full Text: DOI
Papadimitriou, Christos H.; Vempala, Santosh S. Random projection in the brain and computation with assemblies of neurons. (English) Zbl 07559100 Blum, Avrim (ed.), 10th innovations in theoretical computer science conference, ITCS 2019, January 10–12, 2019, San Diego, CA, USA. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 124, Article 57, 19 p. (2019). MSC: 68Qxx PDFBibTeX XMLCite \textit{C. H. Papadimitriou} and \textit{S. S. Vempala}, LIPIcs -- Leibniz Int. Proc. Inform. 124, Article 57, 19 p. (2019; Zbl 07559100) Full Text: DOI
Lee, Yin Tat; Sidford, Aaron; Vempala, Santosh S. Efficient convex optimization with oracles. (English) Zbl 1452.68272 Bárány, Imre (ed.) et al., Building bridges II. Mathematics of László Lovász. Conference in celebration of László Lovász’ 70th birthday, Budapest, Hungary, July 2–6, 2018. Berlin: Springer. Bolyai Soc. Math. Stud. 28, 317-335 (2019). MSC: 68W20 68W40 90C25 PDFBibTeX XMLCite \textit{Y. T. Lee} et al., Bolyai Soc. Math. Stud. 28, 317--335 (2019; Zbl 1452.68272) Full Text: DOI
Hunkenschröder, Christoph; Vempala, Santosh; Vetta, Adrian A 4/3-approximation algorithm for the minimum 2-edge connected subgraph problem. (English) Zbl 1454.68184 ACM Trans. Algorithms 15, No. 4, Article No. 55, 28 p. (2019). MSC: 68W25 05C40 05C85 68R10 PDFBibTeX XMLCite \textit{C. Hunkenschröder} et al., ACM Trans. Algorithms 15, No. 4, Article No. 55, 28 p. (2019; Zbl 1454.68184) Full Text: DOI
Lee, Yin Tat; Vempala, Santosh S. The Kannan-Lovász-Simonovits conjecture. (English) Zbl 1474.52005 Jerison, David (ed.) et al., Current developments in mathematics 2017. Papers based on selected lectures given at the current development mathematics conference, Harvard University, Cambridge, MA, USA, November 2017. Somerville, MA: International Press. 1-36 (2019). MSC: 52A20 52A22 60D05 60F05 PDFBibTeX XMLCite \textit{Y. T. Lee} and \textit{S. S. Vempala}, in: Current developments in mathematics 2017. Papers based on selected lectures given at the current development mathematics conference, Harvard University, Cambridge, MA, USA, November 2017. Somerville, MA: International Press. 1--36 (2019; Zbl 1474.52005) Full Text: DOI arXiv
Vempala, Santosh S.; Wibisono, Andre Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices. arXiv:1903.08568 Preprint, arXiv:1903.08568 [cs.DS] (2019). BibTeX Cite \textit{S. S. Vempala} and \textit{A. Wibisono}, ``Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices'', Preprint, arXiv:1903.08568 [cs.DS] (2019) Full Text: arXiv OA License
Tantipongpipat, Uthaipon; Samadi, Samira; Singh, Mohit; Morgenstern, Jamie; Vempala, Santosh Multi-Criteria Dimensionality Reduction with Applications to Fairness. arXiv:1902.11281 Preprint, arXiv:1902.11281 [cs.DM] (2019). MSC: 90C22 90C27 90C29 90C49 68Q25 BibTeX Cite \textit{U. Tantipongpipat} et al., ``Multi-Criteria Dimensionality Reduction with Applications to Fairness'', Preprint, arXiv:1902.11281 [cs.DM] (2019) Full Text: arXiv OA License
Legenstein, Robert; Maass, Wolfgang; Papadimitriou, Christos H.; Vempala, Santosh S. Long term memory and the densest K-subgraph problem. (English) Zbl 1462.68041 Karlin, Anna R. (ed.), 9th innovations in theoretical computer science conference, ITCS 2018, Cambridge, MA, USA, January 11–14, 2018. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 94, Article 57, 15 p. (2018). MSC: 68Q07 05C80 68W20 92C20 PDFBibTeX XMLCite \textit{R. Legenstein} et al., LIPIcs -- Leibniz Int. Proc. Inform. 94, Article 57, 15 p. (2018; Zbl 1462.68041) Full Text: DOI
Lee, Yin Tat; Vempala, Santosh S. Stochastic localization + Stieltjes barrier = tight bound for log-Sobolev. (English) Zbl 1429.65028 Diakonikolas, Ilias (ed.) et al., Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, STOC ’18, Los Angeles, CA, USA, June 25–29, 2018. New York, NY: Association for Computing Machinery (ACM). 1122-1129 (2018). MSC: 65C40 60E15 PDFBibTeX XMLCite \textit{Y. T. Lee} and \textit{S. S. Vempala}, in: Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, STOC '18, Los Angeles, CA, USA, June 25--29, 2018. New York, NY: Association for Computing Machinery (ACM). 1122--1129 (2018; Zbl 1429.65028) Full Text: DOI arXiv
Lee, Yin Tat; Vempala, Santosh S. Convergence rate of Riemannian Hamiltonian Monte Carlo and faster polytope volume computation. (English) Zbl 1429.65009 Diakonikolas, Ilias (ed.) et al., Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, STOC ’18, Los Angeles, CA, USA, June 25–29, 2018. New York, NY: Association for Computing Machinery (ACM). 1115-1121 (2018). MSC: 65C05 65D18 65Y20 PDFBibTeX XMLCite \textit{Y. T. Lee} and \textit{S. S. Vempala}, in: Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, STOC '18, Los Angeles, CA, USA, June 25--29, 2018. New York, NY: Association for Computing Machinery (ACM). 1115--1121 (2018; Zbl 1429.65009) Full Text: DOI arXiv
Moore, Cris (ed.); Vempala, Santosh (ed.) Special section on the fifty-sixth annual IEEE Symposium on Foundations of Computer Science (FOCS 2015). (English) Zbl 1405.00057 SIAM J. Comput. 47, No. 6, 2237 (2018). MSC: 00B25 68-06 PDFBibTeX XMLCite \textit{C. Moore} (ed.) and \textit{S. Vempala} (ed.), SIAM J. Comput. 47, No. 6, 2237 (2018; Zbl 1405.00057) Full Text: DOI
Feldman, Vitaly; Perkins, Will; Vempala, Santosh On the complexity of random satisfiability problems with planted solutions. (English) Zbl 1396.68057 SIAM J. Comput. 47, No. 4, 1294-1338 (2018). MSC: 68Q25 05C65 05C70 05C80 68Q17 68Q87 PDFBibTeX XMLCite \textit{V. Feldman} et al., SIAM J. Comput. 47, No. 4, 1294--1338 (2018; Zbl 1396.68057) Full Text: DOI
Cousins, Ben; Vempala, Santosh Gaussian cooling and \(O^\ast(n^3)\) algorithms for volume and Gaussian volume. (English) Zbl 1397.68217 SIAM J. Comput. 47, No. 3, 1237-1273 (2018). MSC: 68W20 52A38 65C40 68Q25 PDFBibTeX XMLCite \textit{B. Cousins} and \textit{S. Vempala}, SIAM J. Comput. 47, No. 3, 1237--1273 (2018; Zbl 1397.68217) Full Text: DOI
Vempala, Santosh S.; Woodruff, David P. Adaptive matrix vector product. (English) Zbl 1410.68179 Klein, Philip N. (ed.), Proceedings of the 28th annual ACM-SIAM symposium on discrete algorithms, SODA 2017, Barcelona, Spain, January 16–19, 2017. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 2044-2060 (2017). MSC: 68Q25 65F30 68W27 PDFBibTeX XMLCite \textit{S. S. Vempala} and \textit{D. P. Woodruff}, in: Proceedings of the 28th annual ACM-SIAM symposium on discrete algorithms, SODA 2017, Barcelona, Spain, January 16--19, 2017. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 2044--2060 (2017; Zbl 1410.68179) Full Text: DOI
Feldman, Vitaly; Guzmán, Cristóbal; Vempala, Santosh Statistical query algorithms for mean vector estimation and stochastic convex optimization. (English) Zbl 1422.90031 Klein, Philip N. (ed.), Proceedings of the 28th annual ACM-SIAM symposium on discrete algorithms, SODA 2017, Barcelona, Spain, January 16–19, 2017. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1265-1277 (2017). MSC: 90C15 90C25 68Q17 PDFBibTeX XMLCite \textit{V. Feldman} et al., in: Proceedings of the 28th annual ACM-SIAM symposium on discrete algorithms, SODA 2017, Barcelona, Spain, January 16--19, 2017. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1265--1277 (2017; Zbl 1422.90031) Full Text: DOI arXiv
Feldman, Vitaly; Grigorescu, Elena; Reyzin, Lev; Vempala, Santosh S.; Xiao, Ying Statistical algorithms and a lower bound for detecting planted cliques. (English) Zbl 1397.68085 J. ACM 64, No. 2, Article No. 8, 37 p. (2017). MSC: 68Q17 05C69 05C80 68Q87 68T05 PDFBibTeX XMLCite \textit{V. Feldman} et al., J. ACM 64, No. 2, Article No. 8, 37 p. (2017; Zbl 1397.68085) Full Text: DOI arXiv
Blocki, Jeremiah; Blum, Manuel; Datta, Anupam; Vempala, Santosh Towards human computable passwords. (English) Zbl 1402.94073 Papadimitriou, Christos H. (ed.), 8th innovations in theoretical computer science conference, ITCS 2017, Berkeley, CA, USA, January 9–11, 2017. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-029-3). LIPIcs – Leibniz International Proceedings in Informatics 67, Article 10, 47 p. (2017). MSC: 94A62 68Q17 68Q25 94A60 PDFBibTeX XMLCite \textit{J. Blocki} et al., LIPIcs -- Leibniz Int. Proc. Inform. 67, Article 10, 47 p. (2017; Zbl 1402.94073) Full Text: DOI arXiv
Kannan, Ravindran; Vempala, Santosh Randomized algorithms in numerical linear algebra. (English) Zbl 1378.65084 Acta Numerica 26, 95-135 (2017). Reviewer: Constantin Popa (Constanţa) MSC: 65F10 65F08 68W20 15A69 62J05 65-02 PDFBibTeX XMLCite \textit{R. Kannan} and \textit{S. Vempala}, Acta Numerica 26, 95--135 (2017; Zbl 1378.65084) Full Text: DOI
Jansen, Klaus (ed.); Rolim, José D. P. (ed.); Williamson, David P. (ed.); Vempala, Santosh S. (ed.) Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 20th international workshop, APPROX 2017 and 21st international workshop, RANDOM 2017, Berkeley, CA, USA, August 16–18, 2017. Proceedings. (English) Zbl 1372.68012 LIPIcs – Leibniz International Proceedings in Informatics 81. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-044-6). xvi, 49 articles, not consecutively paged, electronic only, open access (2017). MSC: 68-06 68W20 68W25 90C27 00B25 PDFBibTeX XMLCite \textit{K. Jansen} (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 20th international workshop, APPROX 2017 and 21st international workshop, RANDOM 2017, Berkeley, CA, USA, August 16--18, 2017. Proceedings. Wadern: Schloss Dagstuhl -- Leibniz Zentrum für Informatik (2017; Zbl 1372.68012) Full Text: DOI Link
Lee, Yin Tat; Vempala, Santosh S. Geodesic walks in polytopes. (English) Zbl 1370.90146 Hatami, Hamed (ed.) et al., Proceedings of the 49th annual ACM SIGACT symposium on theory of computing, STOC ’17, Montreal, QC, Canada, June 19–23, 2017. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4528-6). 927-940 (2017). MSC: 90C08 60G50 PDFBibTeX XMLCite \textit{Y. T. Lee} and \textit{S. S. Vempala}, in: Proceedings of the 49th annual ACM SIGACT symposium on theory of computing, STOC '17, Montreal, QC, Canada, June 19--23, 2017. New York, NY: Association for Computing Machinery (ACM). 927--940 (2017; Zbl 1370.90146) Full Text: DOI arXiv
Eisenbrand, Friedrich; Vempala, Santosh Geometric random edge. (English) Zbl 1373.90071 Math. Program. 164, No. 1-2 (A), 325-339 (2017). MSC: 90C05 60J10 68W20 PDFBibTeX XMLCite \textit{F. Eisenbrand} and \textit{S. Vempala}, Math. Program. 164, No. 1--2 (A), 325--339 (2017; Zbl 1373.90071) Full Text: DOI arXiv
Petti, Samantha; Vempala, Santosh Random Overlapping Communities: Approximating Motif Densities of Large Graphs. arXiv:1709.09477 Preprint, arXiv:1709.09477 [cs.DM] (2017). BibTeX Cite \textit{S. Petti} and \textit{S. Vempala}, ``Random Overlapping Communities: Approximating Motif Densities of Large Graphs'', Preprint, arXiv:1709.09477 [cs.DM] (2017) Full Text: arXiv OA License
Lee, Yin Tat; Sidford, Aaron; Vempala, Santosh S. Efficient Convex Optimization with Membership Oracles. arXiv:1706.07357 Preprint, arXiv:1706.07357 [cs.DS] (2017). BibTeX Cite \textit{Y. T. Lee} et al., ``Efficient Convex Optimization with Membership Oracles'', Preprint, arXiv:1706.07357 [cs.DS] (2017) Full Text: arXiv OA License
Artmann, S.; Eisenbrand, F.; Glanzer, C.; Oertel, T.; Vempala, S.; Weismantel, R. A note on non-degenerate integer programs with small sub-determinants. (English) Zbl 1408.90186 Oper. Res. Lett. 44, No. 5, 635-639 (2016). MSC: 90C10 90C39 PDFBibTeX XMLCite \textit{S. Artmann} et al., Oper. Res. Lett. 44, No. 5, 635--639 (2016; Zbl 1408.90186) Full Text: DOI arXiv
Cousins, Ben; Vempala, Santosh A practical volume algorithm. (English) Zbl 1341.65007 Math. Program. Comput. 8, No. 2, 133-160 (2016). MSC: 65D18 52A38 90C27 PDFBibTeX XMLCite \textit{B. Cousins} and \textit{S. Vempala}, Math. Program. Comput. 8, No. 2, 133--160 (2016; Zbl 1341.65007) Full Text: DOI
Chandrasekaran, Karthekeyan; Végh, László A.; Vempala, Santosh S. The cutting plane method is polynomial for perfect matchings. (English) Zbl 1334.90077 Math. Oper. Res. 41, No. 1, 23-48 (2016). MSC: 90C10 90C35 68Q25 68R10 68W40 PDFBibTeX XMLCite \textit{K. Chandrasekaran} et al., Math. Oper. Res. 41, No. 1, 23--48 (2016; Zbl 1334.90077) Full Text: DOI arXiv Link
Lee, Yin Tat; Vempala, Santosh S. Eldan’s Stochastic Localization and the KLS Conjecture: Isoperimetry, Concentration and Mixing. arXiv:1612.01507 Preprint, arXiv:1612.01507 [math.FA] (2016). BibTeX Cite \textit{Y. T. Lee} and \textit{S. S. Vempala}, ``Eldan's Stochastic Localization and the KLS Conjecture: Isoperimetry, Concentration and Mixing'', Preprint, arXiv:1612.01507 [math.FA] (2016) Full Text: arXiv OA License
Arriaga, Rosa I.; Rutter, David; Cakmak, Maya; Vempala, Santosh S. Visual categorization with random projection. (English) Zbl 1472.92008 Neural Comput. 27, No. 10, 2132-2147 (2015). MSC: 92B20 PDFBibTeX XMLCite \textit{R. I. Arriaga} et al., Neural Comput. 27, No. 10, 2132--2147 (2015; Zbl 1472.92008) Full Text: DOI
Goyal, Navin; Rademacher, Luis; Vempala, Santosh Query complexity of sampling and small geometric partitions. (English) Zbl 1371.68097 Comb. Probab. Comput. 24, No. 5, 733-753 (2015). MSC: 68Q17 51E20 68R05 PDFBibTeX XMLCite \textit{N. Goyal} et al., Comb. Probab. Comput. 24, No. 5, 733--753 (2015; Zbl 1371.68097) Full Text: DOI arXiv
Dieker, A. B.; Vempala, Santosh S. Stochastic billiards for sampling from the boundary of a convex set. (English) Zbl 1331.60152 Math. Oper. Res. 40, No. 4, 888-901 (2015). MSC: 60J22 65C05 65C40 PDFBibTeX XMLCite \textit{A. B. Dieker} and \textit{S. S. Vempala}, Math. Oper. Res. 40, No. 4, 888--901 (2015; Zbl 1331.60152) Full Text: DOI arXiv
Cousins, Benjamin; Vempala, Santosh Bypassing KLS: Gaussian cooling and an \(O^\ast(n^3)\) volume algorithm. (English) Zbl 1321.68434 Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 539-548 (2015). MSC: 68U05 68W20 68Q25 PDFBibTeX XMLCite \textit{B. Cousins} and \textit{S. Vempala}, in: Proceedings of the 47th annual ACM symposium on theory of computing, STOC '15, Portland, OR, USA, June 14--17, 2015. New York, NY: Association for Computing Machinery (ACM). 539--548 (2015; Zbl 1321.68434) Full Text: DOI arXiv
Feldman, Vitaly; Perkins, Will; Vempala, Santosh On the complexity of random satisfiability problems with planted solutions (extended abstract). (English) Zbl 1321.68280 Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 77-86 (2015). MSC: 68Q17 68Q25 PDFBibTeX XMLCite \textit{V. Feldman} et al., in: Proceedings of the 47th annual ACM symposium on theory of computing, STOC '15, Portland, OR, USA, June 14--17, 2015. New York, NY: Association for Computing Machinery (ACM). 77--86 (2015; Zbl 1321.68280) Full Text: DOI arXiv
Cousins, Ben; Vempala, Santosh A cubic algorithm for computing Gaussian volume. (English) Zbl 1421.68186 Chekuri, Chandra (ed.), Proceedings of the 25th annual ACM-SIAM symposium on discrete algorithms, SODA 2014, Portland, OR, USA, January 5–7, 2014. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1215-1228 (2014). MSC: 68W20 68Q25 PDFBibTeX XMLCite \textit{B. Cousins} and \textit{S. Vempala}, in: Proceedings of the 25th annual ACM-SIAM symposium on discrete algorithms, SODA 2014, Portland, OR, USA, January 5--7, 2014. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1215--1228 (2014; Zbl 1421.68186) Full Text: DOI arXiv
Chandrasekaran, Karthekeyan; Vempala, Santosh S. Integer feasibility of random polytopes: random integer programs. (English) Zbl 1364.90221 Proceedings of the 5th conference on innovations in theoretical computer science, ITCS’14, Princeton, NJ, USA, January 11–14, 2014. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2243-0). 449-458 (2014). MSC: 90C10 52B12 90C15 PDFBibTeX XMLCite \textit{K. Chandrasekaran} and \textit{S. S. Vempala}, in: Proceedings of the 5th conference on innovations in theoretical computer science, ITCS'14, Princeton, NJ, USA, January 11--14, 2014. New York, NY: Association for Computing Machinery (ACM). 449--458 (2014; Zbl 1364.90221) Full Text: DOI arXiv
Goyal, Navin; Vempala, Santosh; Xiao, Ying Fourier PCA and robust tensor decomposition. (English) Zbl 1315.68209 Proceedings of the 46th annual ACM symposium on theory of computing, STOC ’14, New York, NY, USA, May 31 – June 3, 2014. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2710-7). 584-593 (2014). MSC: 68T05 15A69 65F30 PDFBibTeX XMLCite \textit{N. Goyal} et al., in: Proceedings of the 46th annual ACM symposium on theory of computing, STOC '14, New York, NY, USA, May 31 -- June 3, 2014. New York, NY: Association for Computing Machinery (ACM). 584--593 (2014; Zbl 1315.68209) Full Text: DOI arXiv
Frieze, Alan; Goyal, Navin; Rademacher, Luis; Vempala, Santosh Expanders via random spanning trees. (English) Zbl 1297.68186 SIAM J. Comput. 43, No. 2, 497-513 (2014). MSC: 68R05 68R10 68W20 PDFBibTeX XMLCite \textit{A. Frieze} et al., SIAM J. Comput. 43, No. 2, 497--513 (2014; Zbl 1297.68186) Full Text: DOI Link
Feldman, Vitaly; Perkins, Will; Vempala, Santosh Subsampled Power Iteration: a Unified Algorithm for Block Models and Planted CSP’s. arXiv:1407.2774 Preprint, arXiv:1407.2774 [cs.DS] (2014). BibTeX Cite \textit{V. Feldman} et al., ``Subsampled Power Iteration: a Unified Algorithm for Block Models and Planted CSP's'', Preprint, arXiv:1407.2774 [cs.DS] (2014) Full Text: arXiv OA License
Alon, Noga; Lee, Troy; Shraibman, Adi; Vempala, Santosh The approximate rank of a matrix and its algorithmic applications: approximate rank. (English) Zbl 1293.68136 Proceedings of the 45th annual ACM symposium on theory of computing, STOC ’13. Palo Alto, CA, USA, June 1–4, 2013. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2029-0). 675-684 (2013). MSC: 68Q17 05C22 15A15 65F30 68U05 68W25 91A05 PDFBibTeX XMLCite \textit{N. Alon} et al., in: Proceedings of the 45th annual ACM symposium on theory of computing, STOC '13. Palo Alto, CA, USA, June 1--4, 2013. New York, NY: Association for Computing Machinery (ACM). 675--684 (2013; Zbl 1293.68136) Full Text: DOI
Feldman, Vitaly; Grigorescu, Elena; Reyzin, Lev; Vempala, Santosh; Xiao, Ying Statistical algorithms and a lower bound for detecting planted cliques. (English) Zbl 1293.68142 Proceedings of the 45th annual ACM symposium on theory of computing, STOC ’13. Palo Alto, CA, USA, June 1–4, 2013. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2029-0). 655-664 (2013). MSC: 68Q17 05C69 PDFBibTeX XMLCite \textit{V. Feldman} et al., in: Proceedings of the 45th annual ACM symposium on theory of computing, STOC '13. Palo Alto, CA, USA, June 1--4, 2013. New York, NY: Association for Computing Machinery (ACM). 655--664 (2013; Zbl 1293.68142) Full Text: DOI
Dadush, Daniel; Vempala, Santosh S. Near-optimal deterministic algorithms for volume computation via M-ellipsoids. (English) Zbl 1292.52018 Proc. Natl. Acad. Sci. USA 110, No. 48, 19237-19245 (2013). MSC: 52C17 52C45 68Q25 90C25 PDFBibTeX XMLCite \textit{D. Dadush} and \textit{S. S. Vempala}, Proc. Natl. Acad. Sci. USA 110, No. 48, 19237--19245 (2013; Zbl 1292.52018) Full Text: DOI arXiv Link
Dadush, Daniel; Vempala, Santosh Deterministic construction of an approximate M-ellipsoid and its applications to derandomizing lattice algorithms. (English) Zbl 1421.68209 Rabani, Yuval (ed.), Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA 2012, Kyoto, Japan, January 17–19, 2012. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1445-1456 (2012). MSC: 68W25 11H06 11Y16 52C07 68Q25 68W20 PDFBibTeX XMLCite \textit{D. Dadush} and \textit{S. Vempala}, in: Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA 2012, Kyoto, Japan, January 17--19, 2012. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1445--1456 (2012; Zbl 1421.68209) Full Text: arXiv Link
Vempala, Santosh S. Randomly-oriented \(k\)-\(d\) trees adapt to intrinsic dimension. (English) Zbl 1354.68067 D’Souza, Deepak (ed.) et al., IARCS annual conference on foundations of software technology and theoretical computer science (FSTTCS 2012). Selected papers based on the presentations at the 32nd conference, Hyderabad, India, December 15–17, 2012. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-47-7). LIPIcs – Leibniz International Proceedings in Informatics 18, 48-57 (2012). MSC: 68P05 PDFBibTeX XMLCite \textit{S. S. Vempala}, LIPIcs -- Leibniz Int. Proc. Inform. 18, 48--57 (2012; Zbl 1354.68067) Full Text: DOI
Louis, Anand; Raghavendra, Prasad; Tetali, Prasad; Vempala, Santosh Many sparse cuts via higher eigenvalues. (English) Zbl 1286.05095 Karloff, Howard J. (ed.) et al., Proceedings of the 44th annual ACM symposium on theory of computing, STOC 2012. New York, NY, USA, May 19–22, 2012. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-1245-5). 1131-1140 (2012). MSC: 05C50 PDFBibTeX XMLCite \textit{A. Louis} et al., in: Proceedings of the 44th annual ACM symposium on theory of computing, STOC 2012. New York, NY, USA, May 19--22, 2012. New York, NY: Association for Computing Machinery (ACM). 1131--1140 (2012; Zbl 1286.05095) Full Text: DOI arXiv
Štefankovič, Daniel; Vempala, Santosh; Vigoda, Eric A deterministic polynomial-time approximation scheme for counting knapsack solutions. (English) Zbl 1253.68182 SIAM J. Comput. 41, No. 2, 356-366 (2012). MSC: 68Q25 90C39 PDFBibTeX XMLCite \textit{D. Štefankovič} et al., SIAM J. Comput. 41, No. 2, 356--366 (2012; Zbl 1253.68182) Full Text: DOI arXiv
Arora, Sanjeev; Lovász, László; Newman, Ilan; Rabani, Yuval; Rabinovich, Yuri; Vempala, Santosh Local versus global properties of metric spaces. (English) Zbl 1291.90195 SIAM J. Comput. 41, No. 1, 250-271 (2012). MSC: 90C27 05C85 46B85 PDFBibTeX XMLCite \textit{S. Arora} et al., SIAM J. Comput. 41, No. 1, 250--271 (2012; Zbl 1291.90195) Full Text: DOI Link
Chandrasekaran, Karthekeyan; Karp, Richard; Moreno-Centeno, Erick; Vempala, Santosh Algorithms for implicit hitting set problems. (English) Zbl 1375.68214 Randall, Dana (ed.), Proceedings of the 22nd annual ACM-SIAM symposium on discrete algorithms, SODA 2011, San Francisco, CA, USA, January 23–25, 2011. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 614-629 (2011). MSC: 68W25 05C80 05C85 68Q25 68W27 90C27 PDFBibTeX XMLCite \textit{K. Chandrasekaran} et al., in: Proceedings of the 22nd annual ACM-SIAM symposium on discrete algorithms, SODA 2011, San Francisco, CA, USA, January 23--25, 2011. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 614--629 (2011; Zbl 1375.68214) Full Text: Link
Gopalan, Parikshit; Klivans, Adam; Meka, Raghu; Štefankovič, Daniel; Vempala, Santosh; Vigoda, Eric An FPTAS for #knapsack and related counting problems. (English) Zbl 1292.68167 Ostrovsky, Rafail (ed.), Proceedings of the 2011 IEEE 52nd annual symposium on foundations of computer science – FOCS 2011, Palm Springs, CA, USA, October 22–25. Los Alamitos, CA: IEEE Computer Society (ISBN 978-0-7695-4571-4; 978-1-4577-1843-4/ebook). 817-826 (2011). MSC: 68W25 68Q15 90C27 PDFBibTeX XMLCite \textit{P. Gopalan} et al., in: Proceedings of the 2011 IEEE 52nd annual symposium on foundations of computer science -- FOCS 2011, Palm Springs, CA, USA, October 22--25. Los Alamitos, CA: IEEE Computer Society. 817--826 (2011; Zbl 1292.68167) Full Text: DOI
Dadush, Daniel; Peikert, Chris; Vempala, Santosh Enumerative lattice algorithms in any norm via \(M\)-ellipsoid coverings. (English) Zbl 1292.68091 Ostrovsky, Rafail (ed.), Proceedings of the 2011 IEEE 52nd annual symposium on foundations of computer science – FOCS 2011, Palm Springs, CA, USA, October 22–25. Los Alamitos, CA: IEEE Computer Society (ISBN 978-0-7695-4571-4; 978-1-4577-1843-4/ebook). 580-589 (2011). MSC: 68Q25 52B20 90C10 94B75 PDFBibTeX XMLCite \textit{D. Dadush} et al., in: Proceedings of the 2011 IEEE 52nd annual symposium on foundations of computer science -- FOCS 2011, Palm Springs, CA, USA, October 22--25. Los Alamitos, CA: IEEE Computer Society. 580--589 (2011; Zbl 1292.68091) Full Text: DOI arXiv
Grigorescu, Elena; Reyzin, Lev; Vempala, Santosh On noise-tolerant learning of sparse parities and related problems. (English) Zbl 1348.68194 Kivinen, Jyrki (ed.) et al., Algorithmic learning theory. 22nd international conference, ALT 2011, Espoo, Finland, October 5–7, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-24411-7/pbk). Lecture Notes in Computer Science 6925. Lecture Notes in Artificial Intelligence, 413-424 (2011). MSC: 68T05 PDFBibTeX XMLCite \textit{E. Grigorescu} et al., Lect. Notes Comput. Sci. 6925, 413--424 (2011; Zbl 1348.68194) Full Text: DOI
Juba, Brendan; Vempala, Santosh Semantic communication for simple goals is equivalent to on-line learning. (English) Zbl 1350.68220 Kivinen, Jyrki (ed.) et al., Algorithmic learning theory. 22nd international conference, ALT 2011, Espoo, Finland, October 5–7, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-24411-7/pbk). Lecture Notes in Computer Science 6925. Lecture Notes in Artificial Intelligence, 277-291 (2011). MSC: 68T05 68Q32 68W27 PDFBibTeX XMLCite \textit{B. Juba} and \textit{S. Vempala}, Lect. Notes Comput. Sci. 6925, 277--291 (2011; Zbl 1350.68220) Full Text: DOI
Louis, Anand; Raghavendra, Prasad; Tetali, Prasad; Vempala, Santosh Algorithmic extensions of Cheeger’s inequality to higher eigenvalues and partitions. (English) Zbl 1321.05152 Goldberg, Leslie Ann (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 14th international workshop, APPROX 2011, and 15th international workshop, RANDOM 2011, Princeton, NJ, USA, August 17–19, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-22934-3/pbk). Lecture Notes in Computer Science 6845, 315-326 (2011). MSC: 05C50 05C70 05C85 PDFBibTeX XMLCite \textit{A. Louis} et al., Lect. Notes Comput. Sci. 6845, 315--326 (2011; Zbl 1321.05152) Full Text: DOI
Vempala, Santosh S.; Xiao, Ying Structure from Local Optima: Learning Subspace Juntas via Higher Order PCA. arXiv:1108.3329 Preprint, arXiv:1108.3329 [cs.CC] (2011). MSC: 68Q32 15A69 90C26 BibTeX Cite \textit{S. S. Vempala} and \textit{Y. Xiao}, ``Structure from Local Optima: Learning Subspace Juntas via Higher Order PCA'', Preprint, arXiv:1108.3329 [cs.CC] (2011) Full Text: arXiv OA License
Chandrasekaran, Karthekeyan; Dadush, Daniel; Vempala, Santosh Thin partitions, isoperimetric inequalities and a sampling algorithm for star shaped bodies. (English) Zbl 1288.90062 Charikar, Moses (ed.), Proceedings of the 21st annual ACM-SIAM symposium on discrete algorithms, SODA 2010, Austin, TX, USA, January 17–19, 2010. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-0-89871-698-6/CD-ROM). 1630-1645 (2010). MSC: 90C25 68W05 68Q17 PDFBibTeX XMLCite \textit{K. Chandrasekaran} et al., in: Proceedings of the 21st annual ACM-SIAM symposium on discrete algorithms, SODA 2010, Austin, TX, USA, January 17--19, 2010. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1630--1645 (2010; Zbl 1288.90062) Full Text: arXiv
Vempala, Santosh S. Recent progress and open problems in algorithmic convex geometry. (English) Zbl 1245.52005 Lodaya, Kamal (ed.) et al., IARCS annual conference on foundations of software technology and theoretical computer science (FSTTCS 2010), December 15–18, 2010, Chennai, India. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-23-1). LIPIcs – Leibniz International Proceedings in Informatics 8, 42-64, electronic only (2010). MSC: 52B55 90C25 90C05 68U05 52-02 PDFBibTeX XMLCite \textit{S. S. Vempala}, LIPIcs -- Leibniz Int. Proc. Inform. 8, 42--64 (2010; Zbl 1245.52005) Full Text: DOI Link
Vempala, Santosh A random-sampling-based algorithm for learning intersections of halfspaces. (English) Zbl 1327.68200 J. ACM 57, No. 6, Article No. 32, 14 p. (2010). MSC: 68T05 PDFBibTeX XMLCite \textit{S. Vempala}, J. ACM 57, No. 6, Article No. 32, 14 p. (2010; Zbl 1327.68200) Full Text: DOI
Awasthi, Pranjal; Balcan, Maria-Florina; Blum, Avrim; Sheffet, Or; Vempala, Santosh On Nash-equilibria of approximation-stable games. (English) Zbl 1310.91009 Kontogiannis, Spyros (ed.) et al., Algorithmic game theory. Third international symposium, SAGT 2010, Athens, Greece, October 18–20, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-16169-8/pbk). Lecture Notes in Computer Science 6386, 78-89 (2010). MSC: 91A10 68Q25 PDFBibTeX XMLCite \textit{P. Awasthi} et al., Lect. Notes Comput. Sci. 6386, 78--89 (2010; Zbl 1310.91009) Full Text: DOI
Frieze, Alan; Vempala, Santosh; Vera, Juan Logconcave random graphs. (English) Zbl 1193.05145 Electron. J. Comb. 17, No. 1, Research Paper R108, 31 p. (2010). MSC: 05C80 52A23 PDFBibTeX XMLCite \textit{A. Frieze} et al., Electron. J. Comb. 17, No. 1, Research Paper R108, 31 p. (2010; Zbl 1193.05145) Full Text: arXiv EuDML EMIS
Goyal, Navin; Rademacher, Luis; Vempala, Santosh Expanders via random spanning trees. (English) Zbl 1421.68100 Mathieu, Claire (ed.), Proceedings of the 20th annual ACM-SIAM symposium on discrete algorithms, SODA 2009, New York, NY, USA, January 4–6, 2009. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 576-585 (2009). MSC: 68R05 68R10 68W20 PDFBibTeX XMLCite \textit{N. Goyal} et al., in: Proceedings of the 20th annual ACM-SIAM symposium on discrete algorithms, SODA 2009, New York, NY, USA, January 4--6, 2009. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 576--585 (2009; Zbl 1421.68100) Full Text: Link
Štefankovič, Daniel; Vempala, Santosh; Vigoda, Eric Adaptive simulated annealing: a near-optimal connection between sampling and counting. (English) Zbl 1325.68198 J. ACM 56, No. 3, Article No. 18, 36 p. (2009). MSC: 68T05 60C05 62D05 PDFBibTeX XMLCite \textit{D. Štefankovič} et al., J. ACM 56, No. 3, Article No. 18, 36 p. (2009; Zbl 1325.68198) Full Text: DOI Link
Belloni, Alexandre; Freund, Robert M.; Vempala, Santosh An efficient rescaled perceptron algorithm for conic systems. (English) Zbl 1220.90086 Math. Oper. Res. 34, No. 3, 621-641 (2009). MSC: 90C25 52A20 90C60 PDFBibTeX XMLCite \textit{A. Belloni} et al., Math. Oper. Res. 34, No. 3, 621--641 (2009; Zbl 1220.90086) Full Text: DOI Link
Chandrasekaran, Karthekeyan; Deshpande, Amit; Vempala, Santosh Sampling \(s\)-concave functions: the limit of convexity based isoperimetry. (English) Zbl 1255.90091 Dinur, Irit (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 12th international workshop, APPROX 2009, and 13th international workshop, RANDOM 2009, Berkeley, CA, USA, August 21–23, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-03684-2/pbk). Lecture Notes in Computer Science 5687, 420-433 (2009). MSC: 90C25 26B25 60G50 PDFBibTeX XMLCite \textit{K. Chandrasekaran} et al., Lect. Notes Comput. Sci. 5687, 420--433 (2009; Zbl 1255.90091) Full Text: DOI
Brubaker, S. Charles; Vempala, Santosh S. Random tensors and planted cliques. (English) Zbl 1254.05180 Dinur, Irit (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 12th international workshop, APPROX 2009, and 13th international workshop, RANDOM 2009, Berkeley, CA, USA, August 21–23, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-03684-2/pbk). Lecture Notes in Computer Science 5687, 406-419 (2009). MSC: 05C80 05C05 05C69 PDFBibTeX XMLCite \textit{S. C. Brubaker} and \textit{S. S. Vempala}, Lect. Notes Comput. Sci. 5687, 406--419 (2009; Zbl 1254.05180) Full Text: DOI arXiv
Kannan, Ravindran; Vempala, Santosh Spectral algorithms. (English) Zbl 1191.68852 Found. Trends Theor. Comput. Sci. 4, No. 3-4, 157-288 (2008). MSC: 68W20 68W25 68W40 68-02 PDFBibTeX XMLCite \textit{R. Kannan} and \textit{S. Vempala}, Found. Trends Theor. Comput. Sci. 4, No. 3--4, 157--288 (2008; Zbl 1191.68852) Full Text: DOI Link
Bertsimas, Dimitris; Bjarnadóttir, Margrét V.; Kane, Michael A.; Kryder, J. Christian; Pandey, Rudra; Vempala, Santosh; Wang, Grant Algorithmic prediction of health-care costs. (English) Zbl 1167.91406 Oper. Res. 56, No. 6, 1382-1392 (2008). MSC: 91B84 92C50 62P10 PDFBibTeX XMLCite \textit{D. Bertsimas} et al., Oper. Res. 56, No. 6, 1382--1392 (2008; Zbl 1167.91406) Full Text: DOI
Kannan, Ravindran; Salmasian, Hadi; Vempala, Santosh The spectral method for general mixture models. (English) Zbl 1274.62424 SIAM J. Comput. 38, No. 3, 1141-1156 (2008). MSC: 62H30 68T05 68Q32 PDFBibTeX XMLCite \textit{R. Kannan} et al., SIAM J. Comput. 38, No. 3, 1141--1156 (2008; Zbl 1274.62424) Full Text: DOI
Bubraker, S. Charles; Vempala, Santosh S. Isotropic PCA and affine-invariant clustering. (English) Zbl 1159.68542 Grötschel, Martin (ed.) et al., Building bridges. Between mathematics and computer science. Selected papers of the conferences held in Budapest, Hungary, August 5–9, 2008 and Keszthely, Hungary, August 11–15, 2008 and other research papers dedicated to László Lovász on the occasion of his 60th birthday. Berlin: Springer (ISBN 978-3-540-85218-6/hbk). Bolyai Society Mathematical Studies 19, 241-281 (2008). MSC: 68T10 PDFBibTeX XMLCite \textit{S. C. Bubraker} and \textit{S. S. Vempala}, Bolyai Soc. Math. Stud. 19, 241--281 (2008; Zbl 1159.68542) Full Text: DOI Link
Frieze, Alan; Vempala, Santosh; Vera, Juan Logconcave random graphs. (English) Zbl 1231.68180 STOC’08. Proceedings of the 40th annual ACM symposium on theory of computing 2008, Victoria, Canada, May 17–20, 2008. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-60558-047-0). 779-788 (2008). MSC: 68R10 05C80 PDFBibTeX XMLCite \textit{A. Frieze} et al., in: Proceedings of the 40th annual ACM symposium on theory of computing, STOC 2008. Victoria, Canada, May 17--20, 2008. New York, NY: Association for Computing Machinery (ACM). 779--788 (2008; Zbl 1231.68180)
Balcan, Maria-Florina; Blum, Avrim; Vempala, Santosh A discriminative framework for clustering via similarity functions. (English) Zbl 1231.68192 STOC’08. Proceedings of the 40th annual ACM symposium on theory of computing 2008, Victoria, Canada, May 17–20, 2008. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-60558-047-0). 671-680 (2008). MSC: 68T05 62H30 PDFBibTeX XMLCite \textit{M.-F. Balcan} et al., in: Proceedings of the 40th annual ACM symposium on theory of computing, STOC 2008. Victoria, Canada, May 17--20, 2008. New York, NY: Association for Computing Machinery (ACM). 671--680 (2008; Zbl 1231.68192)
Rademacher, Luis; Vempala, Santosh Dispersion of mass and the complexity of randomized geometric algorithms. (English) Zbl 1149.68079 Adv. Math. 219, No. 3, 1037-1069 (2008). MSC: 68W20 68Q25 65Y20 68U05 PDFBibTeX XMLCite \textit{L. Rademacher} and \textit{S. Vempala}, Adv. Math. 219, No. 3, 1037--1069 (2008; Zbl 1149.68079) Full Text: DOI arXiv
Dunagan, John; Vempala, Santosh A simple polynomial-time rescaling algorithm for solving linear programs. (English) Zbl 1157.90007 Math. Program. 114, No. 1 (A), 101-114 (2008). Reviewer: Prabhat Kumar Mahanti (Saint John) MSC: 90C05 68Q32 68T05 PDFBibTeX XMLCite \textit{J. Dunagan} and \textit{S. Vempala}, Math. Program. 114, No. 1 (A), 101--114 (2008; Zbl 1157.90007) Full Text: DOI
Bárány, Imre; Vempala, Santosh; Vetta, Adrian Nash equilibria in random games. (English) Zbl 1130.91312 Random Struct. Algorithms 31, No. 4, 391-405 (2007). MSC: 91A60 91A15 PDFBibTeX XMLCite \textit{I. Bárány} et al., Random Struct. Algorithms 31, No. 4, 391--405 (2007; Zbl 1130.91312) Full Text: DOI
Belloni, Alexandre; Freund, Robert M.; Vempala, Santosh S. An efficient re-scaled perceptron algorithm for conic systems. (English) Zbl 1203.68137 Bshouty, Nader H. (ed.) et al., Learning theory. 20th annual conference on learning theory, COLT 2007, San Diego, CA, USA, June 13–15, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-72925-9). Lecture Notes in Computer Science 4539. Lecture Notes in Artificial Intelligence, 393-408 (2007). MSC: 68T05 90C05 PDFBibTeX XMLCite \textit{A. Belloni} et al., Lect. Notes Comput. Sci. 4539, 393--408 (2007; Zbl 1203.68137) Full Text: DOI Link
Lovász, László; Vempala, Santosh The geometry of logconcave functions and sampling algorithms. (English) Zbl 1122.65012 Random Struct. Algorithms 30, No. 3, 307-358 (2007). Reviewer: R. E. Maiboroda (Kyïv) MSC: 65C40 65C10 60J22 PDFBibTeX XMLCite \textit{L. Lovász} and \textit{S. Vempala}, Random Struct. Algorithms 30, No. 3, 307--358 (2007; Zbl 1122.65012) Full Text: DOI
Deshpande, Amit; Rademacher, Luis; Vempala, Santosh; Wang, Grant Matrix approximation and projective clustering via volume sampling. (English) Zbl 1213.68702 Theory Comput. 2, Paper No. 12, 225-247 (2006). MSC: 68W25 65F15 PDFBibTeX XMLCite \textit{A. Deshpande} et al., Theory Comput. 2, Paper No. 12, 225--247 (2006; Zbl 1213.68702) Full Text: DOI
Arora, Sanjeev; Lovász, László; Newman, Ilan; Rabani, Yuval; Rabinovich, Yuri; Vempala, Santosh Local versus global properties of metric spaces (extended abstract). (English) Zbl 1192.90155 Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, January 22–24, 2006. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 0-89871-605-5). 41-50 (2006). MSC: 90C27 05C85 PDFBibTeX XMLCite \textit{S. Arora} et al., in: Proceedings of the seventeenth annual ACM-SIAM symposium on discrete algorithms, SODA 2006, Miami, FL, January 22--24, 2006. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). 41--50 (2006; Zbl 1192.90155) Full Text: DOI
Deshpande, Amit; Rademacher, Luis; Vempala, Santosh; Wang, Grant Matrix approximation and projective clustering via volume sampling. (English) Zbl 1192.68889 Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, January 22–24, 2006. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 0-89871-605-5). 1117-1126 (2006). MSC: 68W25 15A03 62H30 PDFBibTeX XMLCite \textit{A. Deshpande} et al., in: Proceedings of the seventeenth annual ACM-SIAM symposium on discrete algorithms, SODA 2006, Miami, FL, January 22--24, 2006. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). 1117--1126 (2006; Zbl 1192.68889) Full Text: DOI
Kalai, Adam Tauman; Vempala, Santosh Simulated annealing for convex optimization. (English) Zbl 1278.90311 Math. Oper. Res. 31, No. 2, 253-266 (2006). MSC: 90C25 90C59 90C05 PDFBibTeX XMLCite \textit{A. T. Kalai} and \textit{S. Vempala}, Math. Oper. Res. 31, No. 2, 253--266 (2006; Zbl 1278.90311) Full Text: DOI Link
Deshpande, Amit; Vempala, Santosh Adaptive sampling and fast low-rank matrix approximation. (English) Zbl 1155.68575 Díaz, Josep (ed.) et al., Approximation, randomization and combinatorial optimization. Algorithms and techniques. 9th international workshop on approximation algorithms for combinatorial optimization problems, APPROX 2006, and 10th international workshop on randomization and computation, RANDOM 2006, Barcelona, Spain, August 28–30, 2006. Proceedings. Berlin: Springer (ISBN 3-540-38044-2/pbk). Lecture Notes in Computer Science 4110, 292-303 (2006). MSC: 68W25 68W20 15A03 PDFBibTeX XMLCite \textit{A. Deshpande} and \textit{S. Vempala}, Lect. Notes Comput. Sci. 4110, 292--303 (2006; Zbl 1155.68575) Full Text: DOI