LIPIcs, Volume 81
APPROX/RANDOM 2017, August 16-18, 2017, Berkeley, CA, USA
Editors: Klaus Jansen, José D. P. Rolim, David P. Williamson, and Santosh S. Vempala
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Prayaag Venkat. Efficient Algorithms for Certifying Lower Bounds on the Discrepancy of Random Matrices. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 98:1-98:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{venkat:LIPIcs.ITCS.2023.98, author = {Venkat, Prayaag}, title = {{Efficient Algorithms for Certifying Lower Bounds on the Discrepancy of Random Matrices}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {98:1--98:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.98}, URN = {urn:nbn:de:0030-drops-176015}, doi = {10.4230/LIPIcs.ITCS.2023.98}, annote = {Keywords: Average-case discrepancy theory, lattices, shortest vector problem} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Nikhil Bansal, Aditi Laddha, and Santosh Vempala. A Unified Approach to Discrepancy Minimization. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 1:1-1:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{bansal_et_al:LIPIcs.APPROX/RANDOM.2022.1, author = {Bansal, Nikhil and Laddha, Aditi and Vempala, Santosh}, title = {{A Unified Approach to Discrepancy Minimization}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {1:1--1:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.1}, URN = {urn:nbn:de:0030-drops-171238}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.1}, annote = {Keywords: Discrepancy theory, smoothed analysis} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Yin Tat Lee and Santosh S. Vempala. The Manifold Joys of Sampling (Invited Talk). In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 4:1-4:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{lee_et_al:LIPIcs.ICALP.2022.4, author = {Lee, Yin Tat and Vempala, Santosh S.}, title = {{The Manifold Joys of Sampling}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {4:1--4:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.4}, URN = {urn:nbn:de:0030-drops-163459}, doi = {10.4230/LIPIcs.ICALP.2022.4}, annote = {Keywords: Sampling, Diffusion, Optimization, High Dimension} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Nima Anari, Michał Dereziński, Thuy-Duong Vuong, and Elizabeth Yang. Domain Sparsification of Discrete Distributions Using Entropic Independence. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 5:1-5:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{anari_et_al:LIPIcs.ITCS.2022.5, author = {Anari, Nima and Derezi\'{n}ski, Micha{\l} and Vuong, Thuy-Duong and Yang, Elizabeth}, title = {{Domain Sparsification of Discrete Distributions Using Entropic Independence}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {5:1--5:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-217-4}, ISSN = {1868-8969}, year = {2022}, volume = {215}, editor = {Braverman, Mark}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.5}, URN = {urn:nbn:de:0030-drops-156013}, doi = {10.4230/LIPIcs.ITCS.2022.5}, annote = {Keywords: Domain Sparsification, Markov Chains, Sampling, Entropic Independence} }
Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)
Aditi Laddha and Santosh S. Vempala. Convergence of Gibbs Sampling: Coordinate Hit-And-Run Mixes Fast. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 51:1-51:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{laddha_et_al:LIPIcs.SoCG.2021.51, author = {Laddha, Aditi and Vempala, Santosh S.}, title = {{Convergence of Gibbs Sampling: Coordinate Hit-And-Run Mixes Fast}}, booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)}, pages = {51:1--51:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-184-9}, ISSN = {1868-8969}, year = {2021}, volume = {189}, editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.51}, URN = {urn:nbn:de:0030-drops-138503}, doi = {10.4230/LIPIcs.SoCG.2021.51}, annote = {Keywords: Gibbs Sampler, Coordinate Hit and run, Mixing time of Markov Chain} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Nima Anari, Nathan Hu, Amin Saberi, and Aaron Schild. Sampling Arborescences in Parallel. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 83:1-83:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{anari_et_al:LIPIcs.ITCS.2021.83, author = {Anari, Nima and Hu, Nathan and Saberi, Amin and Schild, Aaron}, title = {{Sampling Arborescences in Parallel}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {83:1--83:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.83}, URN = {urn:nbn:de:0030-drops-136225}, doi = {10.4230/LIPIcs.ITCS.2021.83}, annote = {Keywords: parallel algorithms, arborescences, spanning trees, random sampling} }
Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)
Haim Kaplan, Micha Sharir, and Uri Stemmer. How to Find a Point in the Convex Hull Privately. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 52:1-52:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{kaplan_et_al:LIPIcs.SoCG.2020.52, author = {Kaplan, Haim and Sharir, Micha and Stemmer, Uri}, title = {{How to Find a Point in the Convex Hull Privately}}, booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}, pages = {52:1--52:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-143-6}, ISSN = {1868-8969}, year = {2020}, volume = {164}, editor = {Cabello, Sergio and Chen, Danny Z.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.52}, URN = {urn:nbn:de:0030-drops-122107}, doi = {10.4230/LIPIcs.SoCG.2020.52}, annote = {Keywords: Differential privacy, Tukey depth, Convex hull} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Zongchen Chen and Santosh S. Vempala. Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 64:1-64:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{chen_et_al:LIPIcs.APPROX-RANDOM.2019.64, author = {Chen, Zongchen and Vempala, Santosh S.}, title = {{Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {64:1--64:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.64}, URN = {urn:nbn:de:0030-drops-112790}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.64}, annote = {Keywords: logconcave distribution, sampling, Hamiltonian Monte Carlo, spectral gap, strong convexity} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Ke Chen, Adrian Dumitrescu, Wolfgang Mulzer, and Csaba D. Tóth. On the Stretch Factor of Polygonal Chains. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 56:1-56:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{chen_et_al:LIPIcs.MFCS.2019.56, author = {Chen, Ke and Dumitrescu, Adrian and Mulzer, Wolfgang and T\'{o}th, Csaba D.}, title = {{On the Stretch Factor of Polygonal Chains}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {56:1--56:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.56}, URN = {urn:nbn:de:0030-drops-110005}, doi = {10.4230/LIPIcs.MFCS.2019.56}, annote = {Keywords: polygonal chain, vertex dilation, Koch curve, recursive construction} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Ryan O'Donnell and Tselil Schramm. Sherali - Adams Strikes Back. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 8:1-8:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{odonnell_et_al:LIPIcs.CCC.2019.8, author = {O'Donnell, Ryan and Schramm, Tselil}, title = {{Sherali - Adams Strikes Back}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {8:1--8:30}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-116-0}, ISSN = {1868-8969}, year = {2019}, volume = {137}, editor = {Shpilka, Amir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.8}, URN = {urn:nbn:de:0030-drops-108309}, doi = {10.4230/LIPIcs.CCC.2019.8}, annote = {Keywords: Linear programming, Sherali, Adams, max-cut, graph eigenvalues, Sum-of-Squares} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Christos H. Papadimitriou and Santosh S. Vempala. Random Projection in the Brain and Computation with Assemblies of Neurons. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 57:1-57:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{papadimitriou_et_al:LIPIcs.ITCS.2019.57, author = {Papadimitriou, Christos H. and Vempala, Santosh S.}, title = {{Random Projection in the Brain and Computation with Assemblies of Neurons}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {57:1--57:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-095-8}, ISSN = {1868-8969}, year = {2019}, volume = {124}, editor = {Blum, Avrim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.57}, URN = {urn:nbn:de:0030-drops-101506}, doi = {10.4230/LIPIcs.ITCS.2019.57}, annote = {Keywords: Brain computation, random projection, assemblies, plasticity, memory, association} }
Published in: LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)
Santosh Vempala. Continuous Algorithms (Invited Paper). In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, p. 4:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{vempala:LIPIcs.FSTTCS.2018.4, author = {Vempala, Santosh}, title = {{Continuous Algorithms}}, booktitle = {38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)}, pages = {4:1--4:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-093-4}, ISSN = {1868-8969}, year = {2018}, volume = {122}, editor = {Ganguly, Sumit and Pandya, Paritosh}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.4}, URN = {urn:nbn:de:0030-drops-99037}, doi = {10.4230/LIPIcs.FSTTCS.2018.4}, annote = {Keywords: Algorithms} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Robert Legenstein, Wolfgang Maass, Christos H. Papadimitriou, and Santosh S. Vempala. Long Term Memory and the Densest K-Subgraph Problem. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 57:1-57:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{legenstein_et_al:LIPIcs.ITCS.2018.57, author = {Legenstein, Robert and Maass, Wolfgang and Papadimitriou, Christos H. and Vempala, Santosh S.}, title = {{Long Term Memory and the Densest K-Subgraph Problem}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {57:1--57:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-060-6}, ISSN = {1868-8969}, year = {2018}, volume = {94}, editor = {Karlin, Anna R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.57}, URN = {urn:nbn:de:0030-drops-83593}, doi = {10.4230/LIPIcs.ITCS.2018.57}, annote = {Keywords: Brain computation, long term memory, assemblies, association} }
Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Jeremiah Blocki, Manuel Blum, Anupam Datta, and Santosh Vempala. Towards Human Computable Passwords. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 10:1-10:47, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{blocki_et_al:LIPIcs.ITCS.2017.10, author = {Blocki, Jeremiah and Blum, Manuel and Datta, Anupam and Vempala, Santosh}, title = {{Towards Human Computable Passwords}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, pages = {10:1--10:47}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-029-3}, ISSN = {1868-8969}, year = {2017}, volume = {67}, editor = {Papadimitriou, Christos H.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.10}, URN = {urn:nbn:de:0030-drops-81847}, doi = {10.4230/LIPIcs.ITCS.2017.10}, annote = {Keywords: Passwords, Cognitive Authentication, Human Computation, Planted Constraint Satisfaction Problem, Statistical Dimension} }
Feedback for Dagstuhl Publishing