LIPIcs, Volume 185
ITCS 2021, January 6-8, 2021, Virtual Conference
Editors: James R. Lee
Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)
Ömer Burak Onar, Tınaz Ekim, and Z. Caner Taşkın. Integer Programming Formulations and Cutting Plane Algorithms for the Maximum Selective Tree Problem. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 13:1-13:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{onar_et_al:LIPIcs.SEA.2023.13, author = {Onar, \"{O}mer Burak and Ekim, T{\i}naz and Ta\c{s}k{\i}n, Z. Caner}, title = {{Integer Programming Formulations and Cutting Plane Algorithms for the Maximum Selective Tree Problem}}, booktitle = {21st International Symposium on Experimental Algorithms (SEA 2023)}, pages = {13:1--13:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-279-2}, ISSN = {1868-8969}, year = {2023}, volume = {265}, editor = {Georgiadis, Loukas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.13}, URN = {urn:nbn:de:0030-drops-183634}, doi = {10.4230/LIPIcs.SEA.2023.13}, annote = {Keywords: maximum induced tree, selective tree, cutting plane, separation algorithm, mixed integer programming} }
Published in: LITES, Volume 8, Issue 2 (2022): Special Issue on Distributed Hybrid Systems. Leibniz Transactions on Embedded Systems, Volume 8, Issue 2
Pierre Courtieu, Lionel Rieg, Sébastien Tixeuil, and Xavier Urbain. Swarms of Mobile Robots: Towards Versatility with Safety. In LITES, Volume 8, Issue 2 (2022): Special Issue on Distributed Hybrid Systems. Leibniz Transactions on Embedded Systems, Volume 8, Issue 2, pp. 02:1-02:36, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@Article{courtieu_et_al:LITES.8.2.2, author = {Courtieu, Pierre and Rieg, Lionel and Tixeuil, S\'{e}bastien and Urbain, Xavier}, title = {{Swarms of Mobile Robots: Towards Versatility with Safety}}, booktitle = {LITES, Volume 8, Issue 2 (2022): Special Issue on Distributed Hybrid Systems}, pages = {02:1--02:36}, journal = {Leibniz Transactions on Embedded Systems}, ISSN = {2199-2002}, year = {2022}, volume = {8}, number = {2}, editor = {Courtieu, Pierre and Rieg, Lionel and Tixeuil, S\'{e}bastien and Urbain, Xavier}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LITES.8.2.2}, doi = {10.4230/LITES.8.2.2}, annote = {Keywords: distributed algorithm, mobile autonomous robots, formal proof} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Zhao Song and Ruizhe Zhang. Hyperbolic Concentration, Anti-Concentration, and Discrepancy. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 10:1-10:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{song_et_al:LIPIcs.APPROX/RANDOM.2022.10, author = {Song, Zhao and Zhang, Ruizhe}, title = {{Hyperbolic Concentration, Anti-Concentration, and Discrepancy}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {10:1--10:19}, 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.10}, URN = {urn:nbn:de:0030-drops-171324}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.10}, annote = {Keywords: Hyperbolic polynomial, Chernoff bound, Concentration, Discrepancy theory, Anti-concentration} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Farzam Ebrahimnejad and James R. Lee. Multiscale Entropic Regularization for MTS on General Metric Spaces. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 60:1-60:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{ebrahimnejad_et_al:LIPIcs.ITCS.2022.60, author = {Ebrahimnejad, Farzam and Lee, James R.}, title = {{Multiscale Entropic Regularization for MTS on General Metric Spaces}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {60:1--60:21}, 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.60}, URN = {urn:nbn:de:0030-drops-156568}, doi = {10.4230/LIPIcs.ITCS.2022.60}, annote = {Keywords: Metrical task systems, online algorithms, metric embeddings, convex optimization} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Adam Kurpisz, Aaron Potechin, and Elias Samuel Wirth. SoS Certification for Symmetric Quadratic Functions and Its Connection to Constrained Boolean Hypercube Optimization. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 90:1-90:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{kurpisz_et_al:LIPIcs.ICALP.2021.90, author = {Kurpisz, Adam and Potechin, Aaron and Wirth, Elias Samuel}, title = {{SoS Certification for Symmetric Quadratic Functions and Its Connection to Constrained Boolean Hypercube Optimization}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {90:1--90:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.90}, URN = {urn:nbn:de:0030-drops-141595}, doi = {10.4230/LIPIcs.ICALP.2021.90}, annote = {Keywords: symmetric quadratic functions, SoS certificate, hypercube optimization, semidefinite programming} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Emanuele Viola. Fourier Conjectures, Correlation Bounds, and Majority. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 111:1-111:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{viola:LIPIcs.ICALP.2021.111, author = {Viola, Emanuele}, title = {{Fourier Conjectures, Correlation Bounds, and Majority}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {111:1--111:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.111}, URN = {urn:nbn:de:0030-drops-141806}, doi = {10.4230/LIPIcs.ICALP.2021.111}, annote = {Keywords: Fourier analysis, polynomials, Majority, correlation, lower bound, conjectures} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
James R. Lee. LIPIcs, Volume 185, ITCS 2021, Complete Volume. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 1-1550, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@Proceedings{lee:LIPIcs.ITCS.2021, title = {{LIPIcs, Volume 185, ITCS 2021, Complete Volume}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {1--1550}, 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}, URN = {urn:nbn:de:0030-drops-135381}, doi = {10.4230/LIPIcs.ITCS.2021}, annote = {Keywords: LIPIcs, Volume 185, ITCS 2021, Complete Volume} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
James R. Lee. Front Matter, Table of Contents, Preface, Conference Organization. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 0:i-0:xiv, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{lee:LIPIcs.ITCS.2021.0, author = {Lee, James R.}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {0:i--0:xiv}, 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.0}, URN = {urn:nbn:de:0030-drops-135397}, doi = {10.4230/LIPIcs.ITCS.2021.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Yuval Dagan, Yuval Filmus, Daniel Kane, and Shay Moran. The Entropy of Lies: Playing Twenty Questions with a Liar. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 1:1-1:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{dagan_et_al:LIPIcs.ITCS.2021.1, author = {Dagan, Yuval and Filmus, Yuval and Kane, Daniel and Moran, Shay}, title = {{The Entropy of Lies: Playing Twenty Questions with a Liar}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {1:1--1:16}, 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.1}, URN = {urn:nbn:de:0030-drops-135400}, doi = {10.4230/LIPIcs.ITCS.2021.1}, annote = {Keywords: entropy, twenty questions, algorithms, sorting} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Russell Impagliazzo and Sam McGuire. Comparing Computational Entropies Below Majority (Or: When Is the Dense Model Theorem False?). In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 2:1-2:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{impagliazzo_et_al:LIPIcs.ITCS.2021.2, author = {Impagliazzo, Russell and McGuire, Sam}, title = {{Comparing Computational Entropies Below Majority (Or: When Is the Dense Model Theorem False?)}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {2:1--2:20}, 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.2}, URN = {urn:nbn:de:0030-drops-135417}, doi = {10.4230/LIPIcs.ITCS.2021.2}, annote = {Keywords: Computational entropy, dense model theorem, coin problem} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Martin Hoefer, Pasin Manurangsi, and Alexandros Psomas. Algorithmic Persuasion with Evidence. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 3:1-3:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{hoefer_et_al:LIPIcs.ITCS.2021.3, author = {Hoefer, Martin and Manurangsi, Pasin and Psomas, Alexandros}, title = {{Algorithmic Persuasion with Evidence}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {3:1--3:20}, 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.3}, URN = {urn:nbn:de:0030-drops-135420}, doi = {10.4230/LIPIcs.ITCS.2021.3}, annote = {Keywords: Bayesian Persuasion, Semidefinite Programming, Approximation Algorithms} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Ishay Haviv. The Complexity of Finding Fair Independent Sets in Cycles. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 4:1-4:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{haviv:LIPIcs.ITCS.2021.4, author = {Haviv, Ishay}, title = {{The Complexity of Finding Fair Independent Sets in Cycles}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {4:1--4:14}, 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.4}, URN = {urn:nbn:de:0030-drops-135431}, doi = {10.4230/LIPIcs.ITCS.2021.4}, annote = {Keywords: Fair independent sets in cycles, the complexity class \{PPA\}, Schrijver graphs} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Venkatesan Guruswami, Jonathan Mosheiff, Nicolas Resch, Shashwat Silas, and Mary Wootters. Sharp Threshold Rates for Random Codes. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 5:1-5:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{guruswami_et_al:LIPIcs.ITCS.2021.5, author = {Guruswami, Venkatesan and Mosheiff, Jonathan and Resch, Nicolas and Silas, Shashwat and Wootters, Mary}, title = {{Sharp Threshold Rates for Random Codes}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {5:1--5:20}, 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.5}, URN = {urn:nbn:de:0030-drops-135446}, doi = {10.4230/LIPIcs.ITCS.2021.5}, annote = {Keywords: Coding theory, Random codes, Sharp thresholds} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Cameron Musco, Christopher Musco, and David P. Woodruff. Simple Heuristics Yield Provable Algorithms for Masked Low-Rank Approximation. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 6:1-6:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{musco_et_al:LIPIcs.ITCS.2021.6, author = {Musco, Cameron and Musco, Christopher and Woodruff, David P.}, title = {{Simple Heuristics Yield Provable Algorithms for Masked Low-Rank Approximation}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {6:1--6:20}, 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.6}, URN = {urn:nbn:de:0030-drops-135452}, doi = {10.4230/LIPIcs.ITCS.2021.6}, annote = {Keywords: low-rank approximation, communication complexity, weighted low-rank approximation, bicriteria approximation algorithms} }
Feedback for Dagstuhl Publishing