LIPIcs, Volume 250
FSTTCS 2022, December 18-20, 2022, IIT Madras, Chennai, India
Editors: Anuj Dawar and Venkatesan Guruswami
Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Venkatesan Guruswami and Shilun Li. A Deterministic Construction of a Large Distance Code from the Wozencraft Ensemble. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 50:1-50:10, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{guruswami_et_al:LIPIcs.APPROX/RANDOM.2023.50, author = {Guruswami, Venkatesan and Li, Shilun}, title = {{A Deterministic Construction of a Large Distance Code from the Wozencraft Ensemble}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {50:1--50:10}, 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.50}, URN = {urn:nbn:de:0030-drops-188751}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.50}, annote = {Keywords: Algebraic codes, Pseudorandomness, Explicit Construction, Wozencraft Ensemble, Sidon Sets} }
Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)
Anuj Dawar and Venkatesan Guruswami. LIPIcs, Volume 250, FSTTCS 2022, Complete Volume. 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. 1-792, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@Proceedings{dawar_et_al:LIPIcs.FSTTCS.2022, title = {{LIPIcs, Volume 250, FSTTCS 2022, Complete Volume}}, booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)}, pages = {1--792}, 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}, URN = {urn:nbn:de:0030-drops-173910}, doi = {10.4230/LIPIcs.FSTTCS.2022}, annote = {Keywords: LIPIcs, Volume 250, FSTTCS 2022, Complete Volume} }
Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)
Anuj Dawar and Venkatesan Guruswami. Front Matter, Table of Contents, Preface, Conference Organization. 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. 0:i-0:xvi, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{dawar_et_al:LIPIcs.FSTTCS.2022.0, author = {Dawar, Anuj and Guruswami, Venkatesan}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)}, pages = {0:i--0:xvi}, 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.0}, URN = {urn:nbn:de:0030-drops-173928}, doi = {10.4230/LIPIcs.FSTTCS.2022.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)
Anupam Gupta. Algorithms for Uncertain Environments: Going Beyond the Worst-Case (Invited Talk). In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, p. 1:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{gupta:LIPIcs.FSTTCS.2022.1, author = {Gupta, Anupam}, title = {{Algorithms for Uncertain Environments: Going Beyond the Worst-Case}}, booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)}, pages = {1:1--1:1}, 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.1}, URN = {urn:nbn:de:0030-drops-173933}, doi = {10.4230/LIPIcs.FSTTCS.2022.1}, annote = {Keywords: Optimization under Uncertainty, Online Algorithms, Beyond Worst Case Analysis} }
Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)
Rahul Santhanam. Why MCSP Is a More Important Problem Than SAT (Invited Talk). In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, p. 2:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{santhanam:LIPIcs.FSTTCS.2022.2, author = {Santhanam, Rahul}, title = {{Why MCSP Is a More Important Problem Than SAT}}, booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)}, pages = {2:1--2:1}, 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.2}, URN = {urn:nbn:de:0030-drops-173943}, doi = {10.4230/LIPIcs.FSTTCS.2022.2}, annote = {Keywords: Minimum Circuit Size Problem, Satisfiability, Cryptography, Learning, Approximation} }
Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)
Patricia Bouyer, Mickael Randour, and Pierre Vandenhove. The True Colors of Memory: A Tour of Chromatic-Memory Strategies in Zero-Sum Games on Graphs (Invited Talk). 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. 3:1-3:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{bouyer_et_al:LIPIcs.FSTTCS.2022.3, author = {Bouyer, Patricia and Randour, Mickael and Vandenhove, Pierre}, title = {{The True Colors of Memory: A Tour of Chromatic-Memory Strategies in Zero-Sum Games on Graphs}}, booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)}, pages = {3:1--3: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.3}, URN = {urn:nbn:de:0030-drops-173957}, doi = {10.4230/LIPIcs.FSTTCS.2022.3}, annote = {Keywords: two-player games on graphs, finite-memory strategies, chromatic memory, parity automata, \omega-regularity} }
Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)
Irit Dinur. Expanders in Higher Dimensions (Invited Talk). In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, p. 4:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{dinur:LIPIcs.FSTTCS.2022.4, author = {Dinur, Irit}, title = {{Expanders in Higher Dimensions}}, booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)}, pages = {4:1--4:1}, 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.4}, URN = {urn:nbn:de:0030-drops-173967}, doi = {10.4230/LIPIcs.FSTTCS.2022.4}, annote = {Keywords: Expanders} }
Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)
Jasine Babu, R. Krithika, and Deepak Rajendraprasad. Packing Arc-Disjoint 4-Cycles in Oriented Graphs. 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. 5:1-5:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{babu_et_al:LIPIcs.FSTTCS.2022.5, author = {Babu, Jasine and Krithika, R. and Rajendraprasad, Deepak}, title = {{Packing Arc-Disjoint 4-Cycles in Oriented Graphs}}, booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)}, pages = {5:1--5:16}, 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.5}, URN = {urn:nbn:de:0030-drops-173979}, doi = {10.4230/LIPIcs.FSTTCS.2022.5}, annote = {Keywords: arc-disjoint cycles, bipartite digraphs, oriented graphs, parameterized complexity} }
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 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)
Gianfranco Bilardi and Lorenzo De Stefani. The DAG Visit Approach for Pebbling and I/O Lower Bounds. 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. 7:1-7:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{bilardi_et_al:LIPIcs.FSTTCS.2022.7, author = {Bilardi, Gianfranco and De Stefani, Lorenzo}, title = {{The DAG Visit Approach for Pebbling and I/O Lower Bounds}}, booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)}, pages = {7:1--7:23}, 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.7}, URN = {urn:nbn:de:0030-drops-173999}, doi = {10.4230/LIPIcs.FSTTCS.2022.7}, annote = {Keywords: Pebbling, Directed Acyclic Graph, Pebbling number, I/O complexity} }
Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)
Arijit Bishnu, Arijit Ghosh, Gopinath Mishra, and Manaswi Paraashar. Counting and Sampling from Substructures Using Linear Algebraic Queries. 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. 8:1-8:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{bishnu_et_al:LIPIcs.FSTTCS.2022.8, author = {Bishnu, Arijit and Ghosh, Arijit and Mishra, Gopinath and Paraashar, Manaswi}, title = {{Counting and Sampling from Substructures Using Linear Algebraic Queries}}, booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)}, pages = {8:1--8:20}, 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.8}, URN = {urn:nbn:de:0030-drops-174009}, doi = {10.4230/LIPIcs.FSTTCS.2022.8}, annote = {Keywords: Query complexity, Bilinear form, Uniform sampling, Weighted graphs} }
Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)
Pranav Bisht and Nitin Saxena. Derandomization via Symmetric Polytopes: Poly-Time Factorization of Certain Sparse Polynomials. 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. 9:1-9:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{bisht_et_al:LIPIcs.FSTTCS.2022.9, author = {Bisht, Pranav and Saxena, Nitin}, title = {{Derandomization via Symmetric Polytopes: Poly-Time Factorization of Certain Sparse Polynomials}}, booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)}, pages = {9:1--9:19}, 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.9}, URN = {urn:nbn:de:0030-drops-174012}, doi = {10.4230/LIPIcs.FSTTCS.2022.9}, annote = {Keywords: Multivariate polynomial factorization, derandomization, sparse polynomials, symmetric polynomials, factor-sparsity, convex polytopes} }
Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)
Pranav Bisht and Ilya Volkovich. On Solving Sparse Polynomial Factorization Related Problems. 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. 10:1-10:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{bisht_et_al:LIPIcs.FSTTCS.2022.10, author = {Bisht, Pranav and Volkovich, Ilya}, title = {{On Solving Sparse Polynomial Factorization Related Problems}}, booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)}, pages = {10:1--10:22}, 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.10}, URN = {urn:nbn:de:0030-drops-174023}, doi = {10.4230/LIPIcs.FSTTCS.2022.10}, annote = {Keywords: Sparse Polynomials, Identity Testing, Derandomization, Factor-Sparsity, Multivariate Polynomial Factorization} }
Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)
Krishnendu Chatterjee, Rasmus Ibsen-Jensen, Ismaël Jecker, and Jakub Svoboda. Complexity of Spatial Games. 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. 11:1-11:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{chatterjee_et_al:LIPIcs.FSTTCS.2022.11, author = {Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus and Jecker, Isma\"{e}l and Svoboda, Jakub}, title = {{Complexity of Spatial Games}}, booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)}, pages = {11:1--11:14}, 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.11}, URN = {urn:nbn:de:0030-drops-174038}, doi = {10.4230/LIPIcs.FSTTCS.2022.11}, annote = {Keywords: spatial games, computational complexity, prisoner’s dilemma, dynamical systems} }
Feedback for Dagstuhl Publishing