LIPIcs, Volume 107
ICALP 2018, July 9-13, 2018, Prague, Czech Republic
Editors: Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella. LIPIcs, Volume 107, ICALP'18, Complete Volume. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@Proceedings{chatzigiannakis_et_al:LIPIcs.ICALP.2018, title = {{LIPIcs, Volume 107, ICALP'18, Complete Volume}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018}, URN = {urn:nbn:de:0030-drops-92803}, doi = {10.4230/LIPIcs.ICALP.2018}, annote = {Keywords: Theory of computation} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella. Front Matter, Table of Contents, Preface, Conference Organization. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 0:i-0:xlviii, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{chatzigiannakis_et_al:LIPIcs.ICALP.2018.0, author = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {0:i--0:xlviii}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.0}, URN = {urn:nbn:de:0030-drops-90049}, doi = {10.4230/LIPIcs.ICALP.2018.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Theophanis Hadjistasi and Alexander A. Schwarzmann. Consistent Distributed Memory Services: Resilience and Efficiency (Invited Paper). In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 1:1-1:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{hadjistasi_et_al:LIPIcs.ICALP.2018.1, author = {Hadjistasi, Theophanis and Schwarzmann, Alexander A.}, title = {{Consistent Distributed Memory Services: Resilience and Efficiency}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {1:1--1:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.1}, URN = {urn:nbn:de:0030-drops-90050}, doi = {10.4230/LIPIcs.ICALP.2018.1}, annote = {Keywords: Atomicity, shared-memory, read/write objects, fault-tolerance, latency} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Jaroslav Nesetril. Sparsity - an Algorithmic Perspective (Invited Paper). In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, p. 2:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{nesetril:LIPIcs.ICALP.2018.2, author = {Nesetril, Jaroslav}, title = {{Sparsity - an Algorithmic Perspective}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {2:1--2:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.2}, URN = {urn:nbn:de:0030-drops-90062}, doi = {10.4230/LIPIcs.ICALP.2018.2}, annote = {Keywords: sparse structures, algorithm design} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Sam Staton. Probability Theory from a Programming Perspective (Invited Paper). In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, p. 3:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{staton:LIPIcs.ICALP.2018.3, author = {Staton, Sam}, title = {{Probability Theory from a Programming Perspective}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {3:1--3:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.3}, URN = {urn:nbn:de:0030-drops-90073}, doi = {10.4230/LIPIcs.ICALP.2018.3}, annote = {Keywords: correctness, complexity, statistics} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Richard Ryan Williams. Lower Bounds by Algorithm Design: A Progress Report (Invited Paper). In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, p. 4:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{williams:LIPIcs.ICALP.2018.4, author = {Williams, Richard Ryan}, title = {{Lower Bounds by Algorithm Design: A Progress Report}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {4:1--4:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.4}, URN = {urn:nbn:de:0030-drops-90088}, doi = {10.4230/LIPIcs.ICALP.2018.4}, annote = {Keywords: circuit complexity, satisfiability, derandomization} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Anders Aamand, Mathias Bæk Tejs Knudsen, and Mikkel Thorup. Power of d Choices with Simple Tabulation. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 5:1-5:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{aamand_et_al:LIPIcs.ICALP.2018.5, author = {Aamand, Anders and B{\ae}k Tejs Knudsen, Mathias and Thorup, Mikkel}, title = {{Power of d Choices with Simple Tabulation}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {5:1--5:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.5}, URN = {urn:nbn:de:0030-drops-90096}, doi = {10.4230/LIPIcs.ICALP.2018.5}, annote = {Keywords: Hashing, Load Balancing, Balls and Bins, Simple Tabulation} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Anders Aamand, Niklas Hjuler, Jacob Holm, and Eva Rotenberg. One-Way Trail Orientations. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 6:1-6:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{aamand_et_al:LIPIcs.ICALP.2018.6, author = {Aamand, Anders and Hjuler, Niklas and Holm, Jacob and Rotenberg, Eva}, title = {{One-Way Trail Orientations}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {6:1--6:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.6}, URN = {urn:nbn:de:0030-drops-90109}, doi = {10.4230/LIPIcs.ICALP.2018.6}, annote = {Keywords: Graph algorithms, Robbins' theorem, Graph orientation} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Moab Arar, Shiri Chechik, Sarel Cohen, Cliff Stein, and David Wajc. Dynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 7:1-7:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{arar_et_al:LIPIcs.ICALP.2018.7, author = {Arar, Moab and Chechik, Shiri and Cohen, Sarel and Stein, Cliff and Wajc, David}, title = {{Dynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {7:1--7:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.7}, URN = {urn:nbn:de:0030-drops-90112}, doi = {10.4230/LIPIcs.ICALP.2018.7}, annote = {Keywords: Dynamic, Worst-case, Maximum Matching, Maximum Weight Matching} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Amir Abboud and Karl Bringmann. Tighter Connections Between Formula-SAT and Shaving Logs. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 8:1-8:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{abboud_et_al:LIPIcs.ICALP.2018.8, author = {Abboud, Amir and Bringmann, Karl}, title = {{Tighter Connections Between Formula-SAT and Shaving Logs}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {8:1--8:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.8}, URN = {urn:nbn:de:0030-drops-90129}, doi = {10.4230/LIPIcs.ICALP.2018.8}, annote = {Keywords: Fine-Grained Complexity, Hardness in P, Formula-SAT, Longest Common Subsequence, Frechet Distance} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Anna Adamaszek, Matthias Mnich, and Katarzyna Paluch. New Approximation Algorithms for (1,2)-TSP. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 9:1-9:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{adamaszek_et_al:LIPIcs.ICALP.2018.9, author = {Adamaszek, Anna and Mnich, Matthias and Paluch, Katarzyna}, title = {{New Approximation Algorithms for (1,2)-TSP}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {9:1--9:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.9}, URN = {urn:nbn:de:0030-drops-90133}, doi = {10.4230/LIPIcs.ICALP.2018.9}, annote = {Keywords: Approximation algorithms, traveling salesperson problem, cycle cover} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Pankaj K. Agarwal, Haim Kaplan, and Micha Sharir. Union of Hypercubes and 3D Minkowski Sums with Random Sizes. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 10:1-10:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{agarwal_et_al:LIPIcs.ICALP.2018.10, author = {Agarwal, Pankaj K. and Kaplan, Haim and Sharir, Micha}, title = {{Union of Hypercubes and 3D Minkowski Sums with Random Sizes}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {10:1--10:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.10}, URN = {urn:nbn:de:0030-drops-90147}, doi = {10.4230/LIPIcs.ICALP.2018.10}, annote = {Keywords: Computational geometry, Minkowski sums, Axis-parallel cubes, Union of geometric objects, Objects with random sizes} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Rotem Arnon-Friedman and Henry Yuen. Noise-Tolerant Testing of High Entanglement of Formation. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 11:1-11:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{arnonfriedman_et_al:LIPIcs.ICALP.2018.11, author = {Arnon-Friedman, Rotem and Yuen, Henry}, title = {{Noise-Tolerant Testing of High Entanglement of Formation}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {11:1--11:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.11}, URN = {urn:nbn:de:0030-drops-90157}, doi = {10.4230/LIPIcs.ICALP.2018.11}, annote = {Keywords: device independence, quantum games, entanglement testing, noise tolerance} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Miriam Backens. A Complete Dichotomy for Complex-Valued Holant^c. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 12:1-12:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{backens:LIPIcs.ICALP.2018.12, author = {Backens, Miriam}, title = {{A Complete Dichotomy for Complex-Valued Holant^c}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {12:1--12:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.12}, URN = {urn:nbn:de:0030-drops-90168}, doi = {10.4230/LIPIcs.ICALP.2018.12}, annote = {Keywords: computational complexity, counting complexity, Holant problems, dichotomy, entanglement} }
Feedback for Dagstuhl Publishing