Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Dorna Abdolazimi, Kasper Lindberg, and Shayan Oveis Gharan. On Optimization and Counting of Non-Broken Bases of Matroids. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 40:1-40:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{abdolazimi_et_al:LIPIcs.APPROX/RANDOM.2023.40, author = {Abdolazimi, Dorna and Lindberg, Kasper and Gharan, Shayan Oveis}, title = {{On Optimization and Counting of Non-Broken Bases of Matroids}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {40:1--40:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-296-9}, ISSN = {1868-8969}, year = {2023}, volume = {275}, editor = {Megow, Nicole and Smith, Adam}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.40}, URN = {urn:nbn:de:0030-drops-188653}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.40}, annote = {Keywords: Complexity, Hardness, Optimization, Counting, Random walk, Local to Global, Matroids} }
Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Dorna Abdolazimi and Shayan Oveis Gharan. An Improved Trickle down Theorem for Partite Complexes. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 10:1-10:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{abdolazimi_et_al:LIPIcs.CCC.2023.10, author = {Abdolazimi, Dorna and Oveis Gharan, Shayan}, title = {{An Improved Trickle down Theorem for Partite Complexes}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {10:1--10:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-282-2}, ISSN = {1868-8969}, year = {2023}, volume = {264}, editor = {Ta-Shma, Amnon}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.10}, URN = {urn:nbn:de:0030-drops-182807}, doi = {10.4230/LIPIcs.CCC.2023.10}, annote = {Keywords: Simplicial complexes, High dimensional expanders, Trickle down theorem, Bounded degree high dimensional expanders, Locally testable codes, Random walks} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Anna R. Karlin. A (Slightly) Improved Approximation Algorithm for the Metric Traveling Salesperson Problem (Invited Talk). In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, p. 1:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{karlin:LIPIcs.ICALP.2023.1, author = {Karlin, Anna R.}, title = {{A (Slightly) Improved Approximation Algorithm for the Metric Traveling Salesperson Problem}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {1:1--1:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.1}, URN = {urn:nbn:de:0030-drops-180531}, doi = {10.4230/LIPIcs.ICALP.2023.1}, annote = {Keywords: Traveling Salesperson Problem, approximation algorithm} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Dorna Abdolazimi, Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan. Matroid Partition Property and the Secretary Problem. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 2:1-2:9, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{abdolazimi_et_al:LIPIcs.ITCS.2023.2, author = {Abdolazimi, Dorna and Karlin, Anna R. and Klein, Nathan and Oveis Gharan, Shayan}, title = {{Matroid Partition Property and the Secretary Problem}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {2:1--2:9}, 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.2}, URN = {urn:nbn:de:0030-drops-175051}, doi = {10.4230/LIPIcs.ITCS.2023.2}, annote = {Keywords: Online algorithms, Matroids, Matroid secretary problem} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Farzam Ebrahimnejad, Ansh Nagda, and Shayan Oveis Gharan. Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 61:1-61:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{ebrahimnejad_et_al:LIPIcs.ITCS.2022.61, author = {Ebrahimnejad, Farzam and Nagda, Ansh and Gharan, Shayan Oveis}, title = {{Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {61:1--61:12}, 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.61}, URN = {urn:nbn:de:0030-drops-156579}, doi = {10.4230/LIPIcs.ITCS.2022.61}, annote = {Keywords: perfect matchings, approximate sampling, approximate counting, expanders} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Kuikui Liu. From Coupling to Spectral Independence and Blackbox Comparison with the Down-Up Walk. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 32:1-32:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{liu:LIPIcs.APPROX/RANDOM.2021.32, author = {Liu, Kuikui}, title = {{From Coupling to Spectral Independence and Blackbox Comparison with the Down-Up Walk}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {32:1--32:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-207-5}, ISSN = {1868-8969}, year = {2021}, volume = {207}, editor = {Wootters, Mary and Sanit\`{a}, Laura}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.32}, URN = {urn:nbn:de:0030-drops-147259}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.32}, annote = {Keywords: Markov chains, Approximate counting, Spectral independence} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Vedat Levi Alev, Nima Anari, Lap Chi Lau, and Shayan Oveis Gharan. Graph Clustering using Effective Resistance. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 41:1-41:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{alev_et_al:LIPIcs.ITCS.2018.41, author = {Alev, Vedat Levi and Anari, Nima and Lau, Lap Chi and Oveis Gharan, Shayan}, title = {{Graph Clustering using Effective Resistance}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {41:1--41:16}, 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.41}, URN = {urn:nbn:de:0030-drops-83696}, doi = {10.4230/LIPIcs.ITCS.2018.41}, annote = {Keywords: Electrical Flows, Effective Resistance, Conductance, Graph Partitioning} }
Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Nima Anari, Shayan Oveis Gharan, Amin Saberi, and Mohit Singh. Nash Social Welfare, Matrix Permanent, and Stable Polynomials. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 36:1-36:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{anari_et_al:LIPIcs.ITCS.2017.36, author = {Anari, Nima and Oveis Gharan, Shayan and Saberi, Amin and Singh, Mohit}, title = {{Nash Social Welfare, Matrix Permanent, and Stable Polynomials}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, pages = {36:1--36:12}, 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.36}, URN = {urn:nbn:de:0030-drops-81489}, doi = {10.4230/LIPIcs.ITCS.2017.36}, annote = {Keywords: Nash Welfare, Permanent, Matching, Stable Polynomial, Randomized Algorithm, Saddle Point} }
Feedback for Dagstuhl Publishing