LIPIcs, Volume 93
FSTTCS 2017, December 11-15, 2017, Kanpur, India
Editors: Satya Lokam and R. Ramanujam
Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Srinivasan Arunachalam, Sourav Chakraborty, Michal Koucký, Nitin Saurabh, and Ronald de Wolf. Improved Bounds on Fourier Entropy and Min-Entropy. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 45:1-45:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{arunachalam_et_al:LIPIcs.STACS.2020.45, author = {Arunachalam, Srinivasan and Chakraborty, Sourav and Kouck\'{y}, Michal and Saurabh, Nitin and de Wolf, Ronald}, title = {{Improved Bounds on Fourier Entropy and Min-Entropy}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {45:1--45:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-140-5}, ISSN = {1868-8969}, year = {2020}, volume = {154}, editor = {Paul, Christophe and Bl\"{a}ser, Markus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.45}, URN = {urn:nbn:de:0030-drops-119062}, doi = {10.4230/LIPIcs.STACS.2020.45}, annote = {Keywords: Fourier analysis of Boolean functions, FEI conjecture, query complexity, polynomial approximation, approximate degree, certificate complexity} }
Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)
37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@Proceedings{lokam_et_al:LIPIcs.FSTTCS.2017, title = {{LIPIcs, Volume 93, FSTTCS'17, Complete Volume}}, booktitle = {37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-055-2}, ISSN = {1868-8969}, year = {2018}, volume = {93}, editor = {Lokam, Satya and Ramanujam, R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017}, URN = {urn:nbn:de:0030-drops-85391}, doi = {10.4230/LIPIcs.FSTTCS.2017}, annote = {Keywords: Complexity Measures and Classes, Analysis of Algorithms and Problem Complexity, Logics and Meanings of Programs} }
Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)
37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 0:i-0:x, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{lokam_et_al:LIPIcs.FSTTCS.2017.0, author = {Lokam, Satya and Ramanujam, R.}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)}, pages = {0:i--0:x}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-055-2}, ISSN = {1868-8969}, year = {2018}, volume = {93}, editor = {Lokam, Satya and Ramanujam, R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.0}, URN = {urn:nbn:de:0030-drops-83720}, doi = {10.4230/LIPIcs.FSTTCS.2017.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization, External Reviewers} }
Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)
Edith Elkind. Justified Representation in Multiwinner Voting: Axioms and Algorithms. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 1:1-1:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{elkind:LIPIcs.FSTTCS.2017.1, author = {Elkind, Edith}, title = {{Justified Representation in Multiwinner Voting: Axioms and Algorithms}}, booktitle = {37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)}, pages = {1:1--1:10}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-055-2}, ISSN = {1868-8969}, year = {2018}, volume = {93}, editor = {Lokam, Satya and Ramanujam, R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.1}, URN = {urn:nbn:de:0030-drops-84179}, doi = {10.4230/LIPIcs.FSTTCS.2017.1}, annote = {Keywords: voting, committee selection, axioms, PAV} }
Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)
Prateek Jain, Sham M. Kakade, Rahul Kidambi, Praneeth Netrapalli, Venkata Krishna Pillutla, and Aaron Sidford. A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares). In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 2:1-2:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{jain_et_al:LIPIcs.FSTTCS.2017.2, author = {Jain, Prateek and Kakade, Sham M. and Kidambi, Rahul and Netrapalli, Praneeth and Pillutla, Venkata Krishna and Sidford, Aaron}, title = {{A Markov Chain Theory Approach to Characterizing the Minimax Optimality of Stochastic Gradient Descent (for Least Squares)}}, booktitle = {37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)}, pages = {2:1--2:10}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-055-2}, ISSN = {1868-8969}, year = {2018}, volume = {93}, editor = {Lokam, Satya and Ramanujam, R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.2}, URN = {urn:nbn:de:0030-drops-83941}, doi = {10.4230/LIPIcs.FSTTCS.2017.2}, annote = {Keywords: Stochastic Gradient Descent, Minimax Optimality, Least Squares Regression} }
Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)
Anca Muscholl. Automated Synthesis: a Distributed Viewpoint. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 3:1-3:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{muscholl:LIPIcs.FSTTCS.2017.3, author = {Muscholl, Anca}, title = {{Automated Synthesis: a Distributed Viewpoint}}, booktitle = {37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)}, pages = {3:1--3:5}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-055-2}, ISSN = {1868-8969}, year = {2018}, volume = {93}, editor = {Lokam, Satya and Ramanujam, R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.3}, URN = {urn:nbn:de:0030-drops-84151}, doi = {10.4230/LIPIcs.FSTTCS.2017.3}, annote = {Keywords: Synthesis, distributed program} }
Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)
Devavrat Shah. Matrix Estimation, Latent Variable Model and Collaborative Filtering. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 4:1-4:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{shah:LIPIcs.FSTTCS.2017.4, author = {Shah, Devavrat}, title = {{Matrix Estimation, Latent Variable Model and Collaborative Filtering}}, booktitle = {37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)}, pages = {4:1--4:8}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-055-2}, ISSN = {1868-8969}, year = {2018}, volume = {93}, editor = {Lokam, Satya and Ramanujam, R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.4}, URN = {urn:nbn:de:0030-drops-84193}, doi = {10.4230/LIPIcs.FSTTCS.2017.4}, annote = {Keywords: Matrix Estimation, Graphon Estimation, Collaborative Filtering} }
Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)
Vinod Vaikuntanathan. Some Open Problems in Information-Theoretic Cryptography. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 5:1-5:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{vaikuntanathan:LIPIcs.FSTTCS.2017.5, author = {Vaikuntanathan, Vinod}, title = {{Some Open Problems in Information-Theoretic Cryptography}}, booktitle = {37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)}, pages = {5:1--5:7}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-055-2}, ISSN = {1868-8969}, year = {2018}, volume = {93}, editor = {Lokam, Satya and Ramanujam, R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.5}, URN = {urn:nbn:de:0030-drops-84188}, doi = {10.4230/LIPIcs.FSTTCS.2017.5}, annote = {Keywords: Cryptography, Information-Theoretic Security, Private Information Retrieval, Secret Sharing, Multiparty Computation} }
Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)
Thomas Wilke. Backward Deterministic Büchi Automata on Infinite Words. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 6:1-6:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{wilke:LIPIcs.FSTTCS.2017.6, author = {Wilke, Thomas}, title = {{Backward Deterministic B\"{u}chi Automata on Infinite Words}}, booktitle = {37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)}, pages = {6:1--6:9}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-055-2}, ISSN = {1868-8969}, year = {2018}, volume = {93}, editor = {Lokam, Satya and Ramanujam, R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.6}, URN = {urn:nbn:de:0030-drops-84164}, doi = {10.4230/LIPIcs.FSTTCS.2017.6}, annote = {Keywords: finite automata, infinite words, determinism, backward automata, temporal logic, separated formulas} }
Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)
Luca Aceto, Antonis Achilleos, Adrian Francalanza, and Anna Ingólfsdóttir. Monitoring for Silent Actions. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{aceto_et_al:LIPIcs.FSTTCS.2017.7, author = {Aceto, Luca and Achilleos, Antonis and Francalanza, Adrian and Ing\'{o}lfsd\'{o}ttir, Anna}, title = {{Monitoring for Silent Actions}}, booktitle = {37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)}, pages = {7:1--7:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-055-2}, ISSN = {1868-8969}, year = {2018}, volume = {93}, editor = {Lokam, Satya and Ramanujam, R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.7}, URN = {urn:nbn:de:0030-drops-84023}, doi = {10.4230/LIPIcs.FSTTCS.2017.7}, annote = {Keywords: Runtime Verification, Monitorability, Hennessy-Milner Logic with Recursion, Silent Actions} }
Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)
Pankaj K. Agarwal, Kyle Fox, and Abhinandan Nath. Maintaining Reeb Graphs of Triangulated 2-Manifolds. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{agarwal_et_al:LIPIcs.FSTTCS.2017.8, author = {Agarwal, Pankaj K. and Fox, Kyle and Nath, Abhinandan}, title = {{Maintaining Reeb Graphs of Triangulated 2-Manifolds}}, booktitle = {37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)}, pages = {8:1--8:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-055-2}, ISSN = {1868-8969}, year = {2018}, volume = {93}, editor = {Lokam, Satya and Ramanujam, R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.8}, URN = {urn:nbn:de:0030-drops-84043}, doi = {10.4230/LIPIcs.FSTTCS.2017.8}, annote = {Keywords: Reeb graphs, 2-manifolds, topological graph theory} }
Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)
Akanksha Agrawal, R. Krithika, Daniel Lokshtanov, Amer E. Mouawad, and M. S. Ramanujan. On the Parameterized Complexity of Simultaneous Deletion Problems. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{agrawal_et_al:LIPIcs.FSTTCS.2017.9, author = {Agrawal, Akanksha and Krithika, R. and Lokshtanov, Daniel and Mouawad, Amer E. and Ramanujan, M. S.}, title = {{On the Parameterized Complexity of Simultaneous Deletion Problems}}, booktitle = {37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)}, pages = {9:1--9:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-055-2}, ISSN = {1868-8969}, year = {2018}, volume = {93}, editor = {Lokam, Satya and Ramanujam, R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.9}, URN = {urn:nbn:de:0030-drops-84128}, doi = {10.4230/LIPIcs.FSTTCS.2017.9}, annote = {Keywords: parameterized complexity, feedback vertex set, odd cycle transversal, edge-colored graphs, simultaneous deletion} }
Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)
Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, and Swagato Sanyal. A Composition Theorem for Randomized Query Complexity. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 10:1-10:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{anshu_et_al:LIPIcs.FSTTCS.2017.10, author = {Anshu, Anurag and Gavinsky, Dmitry and Jain, Rahul and Kundu, Srijita and Lee, Troy and Mukhopadhyay, Priyanka and Santha, Miklos and Sanyal, Swagato}, title = {{A Composition Theorem for Randomized Query Complexity}}, booktitle = {37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)}, pages = {10:1--10:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-055-2}, ISSN = {1868-8969}, year = {2018}, volume = {93}, editor = {Lokam, Satya and Ramanujam, R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.10}, URN = {urn:nbn:de:0030-drops-83967}, doi = {10.4230/LIPIcs.FSTTCS.2017.10}, annote = {Keywords: Query algorithms and complexity, Decision trees, Composition theorem, XOR lemma, Hardness amplification} }
Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)
Mohamed Faouzi Atig, Ahmed Bouajjani, K. Narayan Kumar, and Prakash Saivasan. Verification of Asynchronous Programs with Nested Locks. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{atig_et_al:LIPIcs.FSTTCS.2017.11, author = {Atig, Mohamed Faouzi and Bouajjani, Ahmed and Narayan Kumar, K. and Saivasan, Prakash}, title = {{Verification of Asynchronous Programs with Nested Locks}}, booktitle = {37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)}, pages = {11:1--11:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-055-2}, ISSN = {1868-8969}, year = {2018}, volume = {93}, editor = {Lokam, Satya and Ramanujam, R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.11}, URN = {urn:nbn:de:0030-drops-84106}, doi = {10.4230/LIPIcs.FSTTCS.2017.11}, annote = {Keywords: asynchronous programs locks concurrency multi-set pushdown systems, multi-threaded programs, reachability, model checking, verification, nested lockin} }
Feedback for Dagstuhl Publishing