LIPIcs, Volume 213
FSTTCS 2021, December 15-17, 2021, Virtual Conference
Editors: Mikołaj Bojańczyk and Chandra Chekuri
Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Karthekeyan Chandrasekaran and Weihang Wang. Approximating Submodular k-Partition via Principal Partition Sequence. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 3:1-3:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{chandrasekaran_et_al:LIPIcs.APPROX/RANDOM.2023.3, author = {Chandrasekaran, Karthekeyan and Wang, Weihang}, title = {{Approximating Submodular k-Partition via Principal Partition Sequence}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {3:1--3:16}, 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.3}, URN = {urn:nbn:de:0030-drops-188284}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.3}, annote = {Keywords: Approximation algorithms} }
Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Tanvi Bajpai and Chandra Chekuri. Bicriteria Approximation Algorithms for Priority Matroid Median. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 7:1-7:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{bajpai_et_al:LIPIcs.APPROX/RANDOM.2023.7, author = {Bajpai, Tanvi and Chekuri, Chandra}, title = {{Bicriteria Approximation Algorithms for Priority Matroid Median}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {7:1--7:22}, 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.7}, URN = {urn:nbn:de:0030-drops-188328}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.7}, annote = {Keywords: k-median, fair clustering, matroid} }
Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Chandra Chekuri and Kent Quanrud. Independent Sets in Elimination Graphs with a Submodular Objective. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 24:1-24:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{chekuri_et_al:LIPIcs.APPROX/RANDOM.2023.24, author = {Chekuri, Chandra and Quanrud, Kent}, title = {{Independent Sets in Elimination Graphs with a Submodular Objective}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {24:1--24:22}, 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.24}, URN = {urn:nbn:de:0030-drops-188490}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.24}, annote = {Keywords: elimination graphs, independent set, submodular maximization, primal-dual} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Elfarouk Harb, Kent Quanrud, and Chandra Chekuri. Convergence to Lexicographically Optimal Base in a (Contra)Polymatroid and Applications to Densest Subgraph and Tree Packing. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 56:1-56:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{harb_et_al:LIPIcs.ESA.2023.56, author = {Harb, Elfarouk and Quanrud, Kent and Chekuri, Chandra}, title = {{Convergence to Lexicographically Optimal Base in a (Contra)Polymatroid and Applications to Densest Subgraph and Tree Packing}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {56:1--56:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.56}, URN = {urn:nbn:de:0030-drops-187091}, doi = {10.4230/LIPIcs.ESA.2023.56}, annote = {Keywords: Polymatroid, lexicographically optimum base, densest subgraph, tree packing} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Chandra Chekuri and Rhea Jain. Approximation Algorithms for Network Design in Non-Uniform Fault Models. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 36:1-36:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{chekuri_et_al:LIPIcs.ICALP.2023.36, author = {Chekuri, Chandra and Jain, Rhea}, title = {{Approximation Algorithms for Network Design in Non-Uniform Fault Models}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {36:1--36:20}, 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.36}, URN = {urn:nbn:de:0030-drops-180885}, doi = {10.4230/LIPIcs.ICALP.2023.36}, annote = {Keywords: non-uniform faults, network design, approximation algorithm} }
Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)
Calvin Beideman, Karthekeyan Chandrasekaran, Chandra Chekuri, and Chao Xu. Approximate Representation of Symmetric Submodular Functions via Hypergraph Cut Functions. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 6:1-6:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{beideman_et_al:LIPIcs.FSTTCS.2022.6, author = {Beideman, Calvin and Chandrasekaran, Karthekeyan and Chekuri, Chandra and Xu, Chao}, title = {{Approximate Representation of Symmetric Submodular Functions via Hypergraph Cut Functions}}, booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)}, pages = {6:1--6:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-261-7}, ISSN = {1868-8969}, year = {2022}, volume = {250}, editor = {Dawar, Anuj and Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.6}, URN = {urn:nbn:de:0030-drops-173986}, doi = {10.4230/LIPIcs.FSTTCS.2022.6}, annote = {Keywords: Submodular Functions, Hypergraphs, Approximation, Representation} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Parinya Chalermsook, Chien-Chung Huang, Danupon Nanongkai, Thatchaphol Saranurak, Pattara Sukprasert, and Sorrachai Yingchareonthawornchai. Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 37:1-37:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{chalermsook_et_al:LIPIcs.ICALP.2022.37, author = {Chalermsook, Parinya and Huang, Chien-Chung and Nanongkai, Danupon and Saranurak, Thatchaphol and Sukprasert, Pattara and Yingchareonthawornchai, Sorrachai}, title = {{Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {37:1--37: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.37}, URN = {urn:nbn:de:0030-drops-163785}, doi = {10.4230/LIPIcs.ICALP.2022.37}, annote = {Keywords: Approximation Algorithms, Data Structures} }
Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
Mikołaj Bojańczyk and Chandra Chekuri. LIPIcs, Volume 213, FSTTCS 2021, Complete Volume. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 1-866, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@Proceedings{bojanczyk_et_al:LIPIcs.FSTTCS.2021, title = {{LIPIcs, Volume 213, FSTTCS 2021, Complete Volume}}, booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)}, pages = {1--866}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-215-0}, ISSN = {1868-8969}, year = {2021}, volume = {213}, editor = {Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021}, URN = {urn:nbn:de:0030-drops-155102}, doi = {10.4230/LIPIcs.FSTTCS.2021}, annote = {Keywords: LIPIcs, Volume 213, FSTTCS 2021, Complete Volume} }
Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
Mikołaj Bojańczyk and Chandra Chekuri. Front Matter, Table of Contents, Preface, Conference Organization. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 0:i-0:xvi, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{bojanczyk_et_al:LIPIcs.FSTTCS.2021.0, author = {Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)}, pages = {0:i--0:xvi}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-215-0}, ISSN = {1868-8969}, year = {2021}, volume = {213}, editor = {Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.0}, URN = {urn:nbn:de:0030-drops-155113}, doi = {10.4230/LIPIcs.FSTTCS.2021.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
Scott Aaronson. BQP After 28 Years (Invited Talk). In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, p. 1:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{aaronson:LIPIcs.FSTTCS.2021.1, author = {Aaronson, Scott}, title = {{BQP After 28 Years}}, booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)}, pages = {1:1--1:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-215-0}, ISSN = {1868-8969}, year = {2021}, volume = {213}, editor = {Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.1}, URN = {urn:nbn:de:0030-drops-155124}, doi = {10.4230/LIPIcs.FSTTCS.2021.1}, annote = {Keywords: quantum computing, complexity theory, oracle separations, circuit lower bounds} }
Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
Javier Esparza. State Complexity of Population Protocols (Invited Talk). In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, p. 2:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{esparza:LIPIcs.FSTTCS.2021.2, author = {Esparza, Javier}, title = {{State Complexity of Population Protocols}}, booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)}, pages = {2:1--2:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-215-0}, ISSN = {1868-8969}, year = {2021}, volume = {213}, editor = {Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.2}, URN = {urn:nbn:de:0030-drops-155139}, doi = {10.4230/LIPIcs.FSTTCS.2021.2}, annote = {Keywords: Population protocols, state complexity, Petri nets} }
Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
Leslie Ann Goldberg. Approximately Counting Graph Homomorphisms and Retractions (Invited Talk). In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, p. 3:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{goldberg:LIPIcs.FSTTCS.2021.3, author = {Goldberg, Leslie Ann}, title = {{Approximately Counting Graph Homomorphisms and Retractions}}, booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)}, pages = {3:1--3:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-215-0}, ISSN = {1868-8969}, year = {2021}, volume = {213}, editor = {Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.3}, URN = {urn:nbn:de:0030-drops-155146}, doi = {10.4230/LIPIcs.FSTTCS.2021.3}, annote = {Keywords: Graph homomorphisms, counting} }
Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
Huijia (Rachel) Lin. Indistinguishability Obfuscation from Well-Founded Assumptions (Invited Talk). In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, p. 4:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{lin:LIPIcs.FSTTCS.2021.4, author = {Lin, Huijia (Rachel)}, title = {{Indistinguishability Obfuscation from Well-Founded Assumptions}}, booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)}, pages = {4:1--4:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-215-0}, ISSN = {1868-8969}, year = {2021}, volume = {213}, editor = {Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.4}, URN = {urn:nbn:de:0030-drops-155154}, doi = {10.4230/LIPIcs.FSTTCS.2021.4}, annote = {Keywords: Cryptography, indistinguishability obfuscation} }
Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
Rahul Savani. The Complexity of Gradient Descent (Invited Talk). In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 5:1-5:2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{savani:LIPIcs.FSTTCS.2021.5, author = {Savani, Rahul}, title = {{The Complexity of Gradient Descent}}, booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)}, pages = {5:1--5:2}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-215-0}, ISSN = {1868-8969}, year = {2021}, volume = {213}, editor = {Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.5}, URN = {urn:nbn:de:0030-drops-155167}, doi = {10.4230/LIPIcs.FSTTCS.2021.5}, annote = {Keywords: Computational Complexity, Continuous Optimization, TFNP, PPAD, PLS, CLS, UEOPL} }
Feedback for Dagstuhl Publishing