DROPS

Volume

LIPIcs, Volume 107

45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

ICALP 2018, July 9-13, 2018, Prague, Czech Republic

Editors: Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella

Document

Complete Volume

DOI: 10.4230/LIPIcs.ICALP.2018

LIPIcs, Volume 107, ICALP'18, Complete Volume

Authors: 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)

Abstract

LIPIcs, Volume 107, ICALP'18, Complete Volume

Cite as

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)

Copy BibTex To Clipboard

@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}
}

Document

Front Matter

DOI: 10.4230/LIPIcs.ICALP.2018.0

Front Matter, Table of Contents, Preface, Conference Organization

Authors: 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)

Abstract

Front Matter, Table of Contents, Preface, Conference Organization

Cite as

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)

Copy BibTex To Clipboard

@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}
}

Document

Invited Paper

DOI: 10.4230/LIPIcs.ICALP.2018.1

Consistent Distributed Memory Services: Resilience and Efficiency (Invited Paper)

Authors: Theophanis Hadjistasi and Alexander A. Schwarzmann

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract

Reading, 'Riting, and 'Rithmetic, the three R's underlying much of human intellectual activity, not surprisingly, also stand as a venerable foundation of modern computing technology. Indeed, both the Turing machine and von Neumann machine models operate by reading, writing, and computing, and all practical uniprocessor implementations are based on performing activities structured in terms of the three R's. With the advance of networking technology, communication became an additional major systemic activity. However, at a high level of abstraction, it is apparently still more natural to think in terms of reading, writing, and computing. While it is hard to imagine distributed systems - such as those implementing the World-Wide Web - without communication, we often imagine browser-based applications that operate by retrieving (i.e., reading) data, performing computation, and storing (i.e., writing) the results. In this article, we deal with the storage of shared readable and writable data in distributed systems that are subject to perturbations in the underlying distributed platforms composed of computers and networks that interconnect them. The perturbations may include permanent failures (or crashes) of individual computers, transient failures, and delays in the communication medium. The focus of this paper is on the implementations of distributed atomic memory services. Atomicity is a venerable notion of consistency, introduced in 1979 by Lamport [Lamport, 1979]. To this day atomicity remains the most natural type of consistency because it provides an illusion of equivalence with the serial object type that software designers expect. We define the overall setting, models of computation, definition of atomic consistency, and measures of efficiency. We then present algorithms for single-writer settings in the static models. Then we move to presenting algorithms for multi-writer settings. For both static settings we discuss design issues, correctness, efficiency, and trade-offs. Lastly we survey the implementation issues in dynamic settings, where the universe of participants may completely change over time. Here the expectation is that solutions are found by integrating static algorithms with a reconfiguration framework so that during periods of relative stability one benefits from the efficiency of static algorithms, and where during the more turbulent times performance degrades gracefully when reconfigurations are needed. We describe the most important approaches and provide examples.

Cite as

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)

Copy BibTex To Clipboard

@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}
}

Document

Invited Paper

DOI: 10.4230/LIPIcs.ICALP.2018.2

Sparsity - an Algorithmic Perspective (Invited Paper)

Authors: Jaroslav Nesetril

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract

It is a well known experience that for sparse structures one can find fast algorithm for some problems which seem to be otherwise complex. The recently developed theory of sparse classes of graphs (and structures) formalizes this. Particularly the dichotomy Nowhere vs Somewhere Dense presents a very robust tool to study and design algorithms and algorithmic metatheorems. This dichotomy can be characterized in many different ways leading tp broad applications. We survey some of the recent highlights. This is a joint work with Patrice Ossona de Mendez (EHESS Paris and Charles University Prague).

Cite as

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)

Copy BibTex To Clipboard

@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}
}

Document

Invited Paper

DOI: 10.4230/LIPIcs.ICALP.2018.3

Probability Theory from a Programming Perspective (Invited Paper)

Authors: Sam Staton

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract

A leading idea is to apply techniques from verification and programming theory to machine learning and statistics, to deal with things like compositionality and various notions of correctness and complexity. Probabilistic programming is an example of this. Moreover, this approach leads to new foundational methods in probability theory. This is particularly true in the "non-parametric" aspects, for example in higher-order functions and infinite random graph models.

Cite as

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)

Copy BibTex To Clipboard

@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}
}

Document

Invited Paper

DOI: 10.4230/LIPIcs.ICALP.2018.4

Lower Bounds by Algorithm Design: A Progress Report (Invited Paper)

Authors: Richard Ryan Williams

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract

In 2010, the author proposed a program for proving lower bounds in circuit complexity, via faster algorithms for circuit satisfiability and related problems. This talk will give an overview of how the program works, report on the successes of this program so far, and outline open frontiers that have yet to be resolved.

Cite as

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)

Copy BibTex To Clipboard

@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}
}

Document

DOI: 10.4230/LIPIcs.ICALP.2018.5

Power of d Choices with Simple Tabulation

Authors: Anders Aamand, Mathias Bæk Tejs Knudsen, and Mikkel Thorup

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract

We consider the classic d-choice paradigm of Azar et al. [STOC'94] in which m balls are put into n bins sequentially as follows: For each ball we are given a choice of d bins chosen according to d hash functions and the ball is placed in the least loaded of these bins, breaking ties arbitrarily. The interest is in the number of balls in the fullest bin after all balls have been placed. In this paper we suppose that the d hash functions are simple tabulation hash functions which are easy to implement and can be evaluated in constant time. Generalising a result by Dahlgaard et al. [SODA'16] we show that for an arbitrary constant d >= 2 the expected maximum load is at most (lg lg n)/(lg d) + O(1). We further show that by using a simple tie-breaking algorithm introduced by Vöcking [J.ACM'03] the expected maximum load is reduced to (lg lg n)/(d lg phi_d) + O(1) where phi_d is the rate of growth of the d-ary Fibonacci numbers. Both of these expected bounds match those known from the fully random setting. The analysis by Dahlgaard et al. relies on a proof by Patrascu and Thorup [J.ACM'11] concerning the use of simple tabulation for cuckoo hashing. We require a generalisation to d>2 hash functions, but the original proof is an 8-page tour de force of ad-hoc arguments that do not appear to generalise. Our main technical contribution is a shorter, simpler and more accessible proof of the result by Patrascu and Thorup, where the relevant parts generalise nicely to the analysis of d choices.

Cite as

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)

Copy BibTex To Clipboard

@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}
}

Document

DOI: 10.4230/LIPIcs.ICALP.2018.6

One-Way Trail Orientations

Authors: Anders Aamand, Niklas Hjuler, Jacob Holm, and Eva Rotenberg

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract

Given a graph, does there exist an orientation of the edges such that the resulting directed graph is strongly connected? Robbins' theorem [Robbins, Am. Math. Monthly, 1939] asserts that such an orientation exists if and only if the graph is 2-edge connected. A natural extension of this problem is the following: Suppose that the edges of the graph are partitioned into trails. Can the trails be oriented consistently such that the resulting directed graph is strongly connected? We show that 2-edge connectivity is again a sufficient condition and we provide a linear time algorithm for finding such an orientation. The generalised Robbins' theorem [Boesch, Am. Math. Monthly, 1980] for mixed multigraphs asserts that the undirected edges of a mixed multigraph can be oriented to make the resulting directed graph strongly connected exactly when the mixed graph is strongly connected and the underlying graph is bridgeless. We consider the natural extension where the undirected edges of a mixed multigraph are partitioned into trails. It turns out that in this case the condition of the generalised Robbin's Theorem is not sufficient. However, we show that as long as each cut either contains at least 2 undirected edges or directed edges in both directions, there exists an orientation of the trails such that the resulting directed graph is strongly connected. Moreover, if the condition is satisfied, we may start by orienting an arbitrary trail in an arbitrary direction. Using this result one obtains a very simple polynomial time algorithm for finding a strong trail orientation if it exists, both in the undirected and the mixed setting.

Cite as

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)

Copy BibTex To Clipboard

@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}
}

Document

DOI: 10.4230/LIPIcs.ICALP.2018.7

Dynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms

Authors: Moab Arar, Shiri Chechik, Sarel Cohen, Cliff Stein, and David Wajc

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract

We present a simple randomized reduction from fully-dynamic integral matching algorithms to fully-dynamic "approximately-maximal" fractional matching algorithms. Applying this reduction to the recent fractional matching algorithm of Bhattacharya, Henzinger, and Nanongkai (SODA 2017), we obtain a novel result for the integral problem. Specifically, our main result is a randomized fully-dynamic (2+epsilon)-approximate integral matching algorithm with small polylog worst-case update time. For the (2+epsilon)-approximation regime only a fractional fully-dynamic (2+epsilon)-matching algorithm with worst-case polylog update time was previously known, due to Bhattacharya et al. (SODA 2017). Our algorithm is the first algorithm that maintains approximate matchings with worst-case update time better than polynomial, for any constant approximation ratio. As a consequence, we also obtain the first constant-approximate worst-case polylogarithmic update time maximum weight matching algorithm.

Cite as

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)

Copy BibTex To Clipboard

@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}
}

Document

DOI: 10.4230/LIPIcs.ICALP.2018.8

Tighter Connections Between Formula-SAT and Shaving Logs

Authors: Amir Abboud and Karl Bringmann

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract

A noticeable fraction of Algorithms papers in the last few decades improve the running time of well-known algorithms for fundamental problems by logarithmic factors. For example, the {O}(n^2) dynamic programming solution to the Longest Common Subsequence problem (LCS) was improved to O(n^2/log^{2}n) in several ways and using a variety of ingenious tricks. This line of research, also known as the art of shaving log factors, lacks a tool for proving negative results. Specifically, how can we show that it is unlikely that LCS can be solved in time O(n^2/log^3n)? Perhaps the only approach for such results was suggested in a recent paper of Abboud, Hansen, Vassilevska W. and Williams (STOC'16). The authors blame the hardness of shaving logs on the hardness of solving satisfiability on boolean formulas (Formula-SAT) faster than exhaustive search. They show that an O(n^2/log^{1000} n) algorithm for LCS would imply a major advance in circuit lower bounds. Whether this approach can lead to tighter barriers was unclear. In this paper, we push this approach to its limit and, in particular, prove that a well-known barrier from complexity theory stands in the way for shaving five additional log factors for fundamental combinatorial problems. For LCS, regular expression pattern matching, as well as the Fréchet distance problem from Computational Geometry, we show that an O(n^2/log^{7+epsilon}{n}) runtime would imply new Formula-SAT algorithms. Our main result is a reduction from SAT on formulas of size s over n variables to LCS on sequences of length N=2^{n/2} * s^{1+o(1)}. Our reduction is essentially as efficient as possible, and it greatly improves the previously known reduction for LCS with N=2^{n/2} * s^c, for some c >= 100.

Cite as

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)

Copy BibTex To Clipboard

@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}
}

Document

DOI: 10.4230/LIPIcs.ICALP.2018.9

New Approximation Algorithms for (1,2)-TSP

Authors: Anna Adamaszek, Matthias Mnich, and Katarzyna Paluch

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract

We give faster and simpler approximation algorithms for the (1,2)-TSP problem, a well-studied variant of the traveling salesperson problem where all distances between cities are either 1 or 2. Our main results are two approximation algorithms for (1,2)-TSP, one with approximation factor 8/7 and run time O(n^3) and the other having an approximation guarantee of 7/6 and run time O(n^{2.5}). The 8/7-approximation matches the best known approximation factor for (1,2)-TSP, due to Berman and Karpinski (SODA 2006), but considerably improves the previous best run time of O(n^9). Thus, ours is the first improvement for the (1,2)-TSP problem in more than 10 years. The algorithm is based on combining three copies of a minimum-cost cycle cover of the input graph together with a relaxed version of a minimum weight matching, which allows using "half-edges". The resulting multigraph is then edge-colored with four colors so that each color class yields a collection of vertex-disjoint paths. The paths from one color class can then be extended to an 8/7-approximate traveling salesperson tour. Our algorithm, and in particular its analysis, is simpler than the previously best 8/7-approximation. The 7/6-approximation algorithm is similar and even simpler, and has the advantage of not using Hartvigsen's complicated algorithm for computing a minimum-cost triangle-free cycle cover.

Cite as

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)

Copy BibTex To Clipboard

@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}
}

Document

DOI: 10.4230/LIPIcs.ICALP.2018.10

Union of Hypercubes and 3D Minkowski Sums with Random Sizes

Authors: Pankaj K. Agarwal, Haim Kaplan, and Micha Sharir

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract

Let T={triangle_1,...,triangle_n} be a set of of n pairwise-disjoint triangles in R^3, and let B be a convex polytope in R^3 with a constant number of faces. For each i, let C_i = triangle_i oplus r_i B denote the Minkowski sum of triangle_i with a copy of B scaled by r_i>0. We show that if the scaling factors r_1, ..., r_n are chosen randomly then the expected complexity of the union of C_1, ..., C_n is O(n^{2+epsilon), for any epsilon > 0; the constant of proportionality depends on epsilon and the complexity of B. The worst-case bound can be Theta(n^3). We also consider a special case of this problem in which T is a set of points in R^3 and B is a unit cube in R^3, i.e., each C_i is a cube of side-length 2r_i. We show that if the scaling factors are chosen randomly then the expected complexity of the union of the cubes is O(n log^2 n), and it improves to O(n log n) if the scaling factors are chosen randomly from a "well-behaved" probability density function (pdf). We also extend the latter results to higher dimensions. For any fixed odd value of d, we show that the expected complexity of the union of the hypercubes is O(n^floor[d/2] log n) and the bound improves to O(n^floor[d/2]) if the scaling factors are chosen from a "well-behaved" pdf. The worst-case bounds are Theta(n^2) in R^3, and Theta(n^{ceil[d/2]}) in higher dimensions.

Cite as

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)

Copy BibTex To Clipboard

@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}
}

Document

DOI: 10.4230/LIPIcs.ICALP.2018.11

Noise-Tolerant Testing of High Entanglement of Formation

Authors: Rotem Arnon-Friedman and Henry Yuen

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract

In this work we construct tests that allow a classical user to certify high dimensional entanglement in uncharacterized and possibly noisy quantum devices. We present a family of non-local games {G_n} that for all n certify states with entanglement of formation Omega(n). These tests can be derived from any bipartite non-local game with a classical-quantum gap. Furthermore, our tests are noise-tolerant in the sense that fault tolerant technologies are not needed to play the games; entanglement distributed over noisy channels can pass with high probability, making our tests relevant for realistic experimental settings. This is in contrast to, e.g., results on self-testing of high dimensional entanglement, which are only relevant when the noise rate goes to zero with the system's size n. As a corollary of our result, we supply a lower-bound on the entanglement cost of any state achieving a quantum advantage in a bipartite non-local game. Our proof techniques heavily rely on ideas from the work on classical and quantum parallel repetition theorems.

Cite as

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)

Copy BibTex To Clipboard

@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}
}

Document

DOI: 10.4230/LIPIcs.ICALP.2018.12

A Complete Dichotomy for Complex-Valued Holant^c

Authors: Miriam Backens

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract

Holant problems are a family of counting problems on graphs, parametrised by sets of complex-valued functions of Boolean inputs. Holant^c denotes a subfamily of those problems, where any function set considered must contain the two unary functions pinning inputs to values 0 or 1. The complexity classification of Holant problems usually takes the form of dichotomy theorems, showing that for any set of functions in the family, the problem is either #P-hard or it can be solved in polynomial time. Previous such results include a dichotomy for real-valued Holant^c and one for Holant^c with complex symmetric functions, i.e. functions which only depend on the Hamming weight of the input. Here, we derive a dichotomy theorem for Holant^c with complex-valued, not necessarily symmetric functions. The tractable cases are the complex-valued generalisations of the tractable cases of the real-valued Holant^c dichotomy. The proof uses results from quantum information theory, particularly about entanglement. This full dichotomy for Holant^c answers a question that has been open for almost a decade.

Cite as

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)

Copy BibTex To Clipboard

@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}
}

168 Search Results for "Sannella, Donald"

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Thanks for your feedback!

Could not send message