621 Search Results for "Chatzigiannakis, Ioannis"

Volume

LIPIcs, Volume 132

46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

ICALP 2019, July 9-12, 2019, Patras, Greece

Editors: Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi

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

Volume

LIPIcs, Volume 80

44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

ICALP 2017, July 10-14, 2017, Warsaw, Poland

Editors: Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl

Volume

LIPIcs, Volume 55

43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

ICALP 2016, July 11-15, 2016, Rome, Italy

Editors: Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi

Document
DOI: 10.4230/DagRep.13.2.183
Algorithmic Foundations of Programmable Matter (Dagstuhl Seminar 23091)

Authors: Aaron Becker, Sándor Fekete, Irina Kostitsyna, Matthew J. Patitz, Damien Woods, and Ioannis Chatzigiannakis

Published in: Dagstuhl Reports, Volume 13, Issue 2 (2023)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 23091, "Algorithmic Foundations of Programmable Matter", a new and emerging field that combines theoretical work on algorithms with a wide spectrum of practical applications that reach all the way from small-scale embedded systems to cyber-physical structures at nano-scale. The aim of this seminar was to bring together researchers from computational geometry, distributed computing, DNA computing, and swarm robotics who have worked on programmable matter to inform one another about the newest developments in each area and to discuss future models, approaches, and directions for new research. Similar to the first two Dagstuhl Seminars on programmable matter (16271 and 18331), we did focus on some basic problems, but also considered new problems that were now within reach to be studied.
Cite as

Aaron Becker, Sándor Fekete, Irina Kostitsyna, Matthew J. Patitz, Damien Woods, and Ioannis Chatzigiannakis. Algorithmic Foundations of Programmable Matter (Dagstuhl Seminar 23091). In Dagstuhl Reports, Volume 13, Issue 2, pp. 183-198, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{becker_et_al:DagRep.13.2.183,
  author =	{Becker, Aaron and Fekete, S\'{a}ndor and Kostitsyna, Irina and Patitz, Matthew J. and Woods, Damien and Chatzigiannakis, Ioannis},
  title =	{{Algorithmic Foundations of Programmable Matter (Dagstuhl Seminar 23091)}},
  pages =	{183--198},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2023},
  volume =	{13},
  number =	{2},
  editor =	{Becker, Aaron and Fekete, S\'{a}ndor and Kostitsyna, Irina and Patitz, Matthew J. and Woods, Damien and Chatzigiannakis, Ioannis},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.13.2.183},
  URN =		{urn:nbn:de:0030-drops-191848},
  doi =		{10.4230/DagRep.13.2.183},
  annote =	{Keywords: computational geometry, distributed algorithms, DNA computing, programmable matter, swarm robotics}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.ICALP.2019
LIPIcs, Volume 132, ICALP'19, Complete Volume

Authors: Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
LIPIcs, Volume 132, ICALP'19, Complete Volume
Cite as

46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Proceedings{baier_et_al:LIPIcs.ICALP.2019,
  title =	{{LIPIcs, Volume 132, ICALP'19, Complete Volume}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019},
  URN =		{urn:nbn:de:0030-drops-108644},
  doi =		{10.4230/LIPIcs.ICALP.2019},
  annote =	{Keywords: Theory of computation}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.ICALP.2019.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 0:i-0:xxxviii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{baier_et_al:LIPIcs.ICALP.2019.0,
  author =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{0:i--0:xxxviii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.0},
  URN =		{urn:nbn:de:0030-drops-105765},
  doi =		{10.4230/LIPIcs.ICALP.2019.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.ICALP.2019.1
Auction Design under Interdependent Values (Invited Talk)

Authors: Michal Feldman

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
We study combinatorial auctions with interdependent valuations. In such settings, every agent has a private signal, and every agent has a valuation function that depends on the private signals of all the agents. Interdependent valuations capture settings where agents lack information to determine their own valuations. Examples include auctions for artwork or oil drilling rights. For single item auctions and assume some restrictive conditions (the so-called single-crossing condition), full welfare can be achieved. However, in general, there are strong impossibility results on welfare maximization in the interdependent setting. This is in contrast to settings where agents are aware of their own valuations, where the optimal welfare can always be obtained by an incentive compatible mechanism. Motivated by these impossibility results, we study welfare maximization for interdependent valuations through the lens of approximation. We introduce two valuation properties that enable positive results. The first is a relaxed, parameterized version of single crossing; the second is a submodularity condition over the signals. We obtain a host of approximation guarantees under these two notions for various scenarios. Related publications: [Alon Eden et al., 2018; Alon Eden et al., 2019]
Cite as

Michal Feldman. Auction Design under Interdependent Values (Invited Talk). In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{feldman:LIPIcs.ICALP.2019.1,
  author =	{Feldman, Michal},
  title =	{{Auction Design under Interdependent Values}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{1:1--1:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.1},
  URN =		{urn:nbn:de:0030-drops-105778},
  doi =		{10.4230/LIPIcs.ICALP.2019.1},
  annote =	{Keywords: Combinatorial auctions, Interdependent values, Welfare approximation}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.ICALP.2019.2
Symmetry and Similarity (Invited Talk)

Authors: Martin Grohe

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
Deciding if two graphs are isomorphic, or equivalently, computing the symmetries of a graph, is a fundamental algorithmic problem. It has many interesting applications, and it is one of the few natural problems in the class NP whose complexity status is still unresolved. Three years ago, Babai (STOC 2016) gave a quasi-polynomial time isomorphism algorithm. Despite of this breakthrough, the question for a polynomial algorithm remains wide open. Related to the isomorphism problem is the problem of determining the similarity between graphs. Variations of this problems are known as robust graph isomorphism or graph matching (the latter in the machine learning and computer vision literature). This problem is significantly harder than the isomorphism problem, both from a complexity theoretical and from a practical point of view, but for many applications it is the more relevant problem. My talk will be a survey of recent progress on the isomorphism and on the similarity problem. I will focus on generic algorithmic strategies (as opposed to algorithms tailored towards specific graph classes) that have proved to be useful and interesting in various context, both theoretical and practical.
Cite as

Martin Grohe. Symmetry and Similarity (Invited Talk). In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{grohe:LIPIcs.ICALP.2019.2,
  author =	{Grohe, Martin},
  title =	{{Symmetry and Similarity}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.2},
  URN =		{urn:nbn:de:0030-drops-105787},
  doi =		{10.4230/LIPIcs.ICALP.2019.2},
  annote =	{Keywords: Graph Isomorphism, Graph Similarity, Graph Matching}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.ICALP.2019.3
Approximately Good and Modern Matchings (Invited Talk)

Authors: Ola Svensson

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
The matching problem is one of our favorite benchmark problems. Work on it has contributed to the development of many core concepts of computer science, including the equation of efficiency with polynomial time computation in the groundbreaking work by Edmonds in 1965. However, half a century later, we still do not have full understanding of the complexity of the matching problem in several models of computation such as parallel, online, and streaming algorithms. In this talk we survey some of the major challenges and report some recent progress.
Cite as

Ola Svensson. Approximately Good and Modern Matchings (Invited Talk). In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{svensson:LIPIcs.ICALP.2019.3,
  author =	{Svensson, Ola},
  title =	{{Approximately Good and Modern Matchings}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{3:1--3:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.3},
  URN =		{urn:nbn:de:0030-drops-105797},
  doi =		{10.4230/LIPIcs.ICALP.2019.3},
  annote =	{Keywords: Algorithms, Matchings, Computational Complexity}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.ICALP.2019.4
Automata Learning and Galois Connections (Invited Talk)

Authors: Frits Vaandrager

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
Automata learning is emerging as an effective technique for obtaining state machine models of software and hardware systems. I will present an overview of recent work in which we used active automata learning to find standard violations and security vulnerabilities in implementations of network protocols such as TCP and SSH. Also, I will discuss applications of automata learning to support refactoring of legacy control software and identifying job patterns in manufacturing systems. As a guiding theme in my presentation, I will show how Galois connections (adjunctions) help us to scale the application of learning algorithms to practical problems.
Cite as

Frits Vaandrager. Automata Learning and Galois Connections (Invited Talk). In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, p. 4:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{vaandrager:LIPIcs.ICALP.2019.4,
  author =	{Vaandrager, Frits},
  title =	{{Automata Learning and Galois Connections}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{4:1--4:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.4},
  URN =		{urn:nbn:de:0030-drops-105800},
  doi =		{10.4230/LIPIcs.ICALP.2019.4},
  annote =	{Keywords: Automaton Learning, Model Learning, Protocol Verification, Applications of Automata Learning, Galois Connections}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.ICALP.2019.5
Fixed Point Computation Problems and Facets of Complexity (Invited Talk)

Authors: Mihalis Yannakakis

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
Many problems from a wide variety of areas can be formulated mathematically as the problem of computing a fixed point of a suitable given multivariate function. Examples include a variety of problems from game theory, economics, optimization, stochastic analysis, verification, and others. In some problems there is a unique fixed point (for example if the function is a contraction); in others there may be multiple fixed points and any one of them is an acceptable solution; while in other cases the desired object is a specific fixed point (for example the least fixed point or greatest fixed point of a monotone function). In this talk we will discuss several types of fixed point computation problems, their complexity, and some of the common themes that have emerged: classes of problems for which there are efficient algorithms, and other classes for which there seem to be serious obstacles.
Cite as

Mihalis Yannakakis. Fixed Point Computation Problems and Facets of Complexity (Invited Talk). In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, p. 5:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{yannakakis:LIPIcs.ICALP.2019.5,
  author =	{Yannakakis, Mihalis},
  title =	{{Fixed Point Computation Problems and Facets of Complexity}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{5:1--5:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.5},
  URN =		{urn:nbn:de:0030-drops-105812},
  doi =		{10.4230/LIPIcs.ICALP.2019.5},
  annote =	{Keywords: Fixed Point, Polynomial Time Algorithm, Computational Complexity}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.6
Complexity-Theoretic Limitations on Blind Delegated Quantum Computation

Authors: Scott Aaronson, Alexandru Cojocaru, Alexandru Gheorghiu, and Elham Kashefi

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
Blind delegation protocols allow a client to delegate a computation to a server so that the server learns nothing about the input to the computation apart from its size. For the specific case of quantum computation we know, from work over the past decade, that blind delegation protocols can achieve information-theoretic security (provided the client and the server exchange some amount of quantum information). In this paper we prove, provided certain complexity-theoretic conjectures are true, that the power of information-theoretically secure blind delegation protocols for quantum computation (ITS-BQC protocols) is in a number of ways constrained. In the first part of our paper we provide some indication that ITS-BQC protocols for delegating polynomial-time quantum computations in which the client and the server interact only classically are unlikely to exist. We first show that having such a protocol in which the client and the server exchange O(n^d) bits of communication, implies that BQP subset MA/O(n^d). We conjecture that this containment is unlikely by proving that there exists an oracle relative to which BQP not subset MA/O(n^d). We then show that if an ITS-BQC protocol exists in which the client and the server interact only classically and which allows the client to delegate quantum sampling problems to the server (such as BosonSampling) then there exist non-uniform circuits of size 2^{n - Omega(n/log(n))}, making polynomially-sized queries to an NP^{NP} oracle, for computing the permanent of an n x n matrix. The second part of our paper concerns ITS-BQC protocols in which the client and the server engage in one round of quantum communication and then exchange polynomially many classical messages. First, we provide a complexity-theoretic upper bound on the types of functions that could be delegated in such a protocol by showing that they must be contained in QCMA/qpoly cap coQCMA/qpoly. Then, we show that having such a protocol for delegating NP-hard functions implies coNP^{NP^{NP}} subseteq NP^{NP^{PromiseQMA}}.
Cite as

Scott Aaronson, Alexandru Cojocaru, Alexandru Gheorghiu, and Elham Kashefi. Complexity-Theoretic Limitations on Blind Delegated Quantum Computation. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{aaronson_et_al:LIPIcs.ICALP.2019.6,
  author =	{Aaronson, Scott and Cojocaru, Alexandru and Gheorghiu, Alexandru and Kashefi, Elham},
  title =	{{Complexity-Theoretic Limitations on Blind Delegated Quantum Computation}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{6:1--6:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.6},
  URN =		{urn:nbn:de:0030-drops-105826},
  doi =		{10.4230/LIPIcs.ICALP.2019.6},
  annote =	{Keywords: Quantum cryptography, Complexity theory, Delegated quantum computation, Computing on encrypted data}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.7
Faster Algorithms for All-Pairs Bounded Min-Cuts

Authors: Amir Abboud, Loukas Georgiadis, Giuseppe F. Italiano, Robert Krauthgamer, Nikos Parotsidis, Ohad Trabelsi, Przemysław Uznański, and Daniel Wolleb-Graf

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
The All-Pairs Min-Cut problem (aka All-Pairs Max-Flow) asks to compute a minimum s-t cut (or just its value) for all pairs of vertices s,t. We study this problem in directed graphs with unit edge/vertex capacities (corresponding to edge/vertex connectivity). Our focus is on the k-bounded case, where the algorithm has to find all pairs with min-cut value less than k, and report only those. The most basic case k=1 is the Transitive Closure (TC) problem, which can be solved in graphs with n vertices and m edges in time O(mn) combinatorially, and in time O(n^{omega}) where omega<2.38 is the matrix-multiplication exponent. These time bounds are conjectured to be optimal. We present new algorithms and conditional lower bounds that advance the frontier for larger k, as follows: - A randomized algorithm for vertex capacities that runs in time {O}((nk)^{omega}). This is only a factor k^omega away from the TC bound, and nearly matches it for all k=n^{o(1)}. - Two deterministic algorithms for edge capacities (which is more general) that work in DAGs and further reports a minimum cut for each pair. The first algorithm is combinatorial (does not involve matrix multiplication) and runs in time {O}(2^{{O}(k^2)}* mn). The second algorithm can be faster on dense DAGs and runs in time {O}((k log n)^{4^{k+o(k)}}* n^{omega}). Previously, Georgiadis et al. [ICALP 2017], could match the TC bound (up to n^{o(1)} factors) only when k=2, and now our two algorithms match it for all k=o(sqrt{log n}) and k=o(log log n). - The first super-cubic lower bound of n^{omega-1-o(1)} k^2 time under the 4-Clique conjecture, which holds even in the simplest case of DAGs with unit vertex capacities. It improves on the previous (SETH-based) lower bounds even in the unbounded setting k=n. For combinatorial algorithms, our reduction implies an n^{2-o(1)} k^2 conditional lower bound. Thus, we identify new settings where the complexity of the problem is (conditionally) higher than that of TC. Our three sets of results are obtained via different techniques. The first one adapts the network coding method of Cheung, Lau, and Leung [SICOMP 2013] to vertex-capacitated digraphs. The second set exploits new insights on the structure of latest cuts together with suitable algebraic tools. The lower bounds arise from a novel reduction of a different structure than the SETH-based constructions.
Cite as

Amir Abboud, Loukas Georgiadis, Giuseppe F. Italiano, Robert Krauthgamer, Nikos Parotsidis, Ohad Trabelsi, Przemysław Uznański, and Daniel Wolleb-Graf. Faster Algorithms for All-Pairs Bounded Min-Cuts. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{abboud_et_al:LIPIcs.ICALP.2019.7,
  author =	{Abboud, Amir and Georgiadis, Loukas and Italiano, Giuseppe F. and Krauthgamer, Robert and Parotsidis, Nikos and Trabelsi, Ohad and Uzna\'{n}ski, Przemys{\l}aw and Wolleb-Graf, Daniel},
  title =	{{Faster Algorithms for All-Pairs Bounded Min-Cuts}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{7:1--7:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.7},
  URN =		{urn:nbn:de:0030-drops-105833},
  doi =		{10.4230/LIPIcs.ICALP.2019.7},
  annote =	{Keywords: All-pairs min-cut, k-reachability, network coding, Directed graphs, fine-grained complexity}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.8
Fine-Grained Reductions and Quantum Speedups for Dynamic Programming

Authors: Amir Abboud

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
This paper points at a connection between certain (classical) fine-grained reductions and the question: Do quantum algorithms offer an advantage for problems whose (classical) best solution is via dynamic programming? A remarkable recent result of Ambainis et al. [SODA 2019] indicates that the answer is positive for some fundamental problems such as Set-Cover and Travelling Salesman. They design a quantum O^*(1.728^n) time algorithm whereas the dynamic programming O^*(2^n) time algorithms are conjectured to be classically optimal. In this paper, fine-grained reductions are extracted from their algorithms giving the first lower bounds for problems in P that are based on the intriguing Set-Cover Conjecture (SeCoCo) of Cygan et al. [CCC 2010]. In particular, the SeCoCo implies: - a super-linear Omega(n^{1.08}) lower bound for 3-SUM on n integers, - an Omega(n^{k/(c_k)-epsilon}) lower bound for k-SUM on n integers and k-Clique on n-node graphs, for any integer k >= 3, where c_k <= log_2{k}+1.4427. While far from being tight, these lower bounds are significantly stronger than what is known to follow from the Strong Exponential Time Hypothesis (SETH); the well-known n^{Omega(k)} ETH-based lower bounds for k-Clique and k-SUM are vacuous when k is constant. Going in the opposite direction, this paper observes that some "sequential" problems with previously known fine-grained reductions to a "parallelizable" core also enjoy quantum speedups over their classical dynamic programming solutions. Examples include RNA Folding and Least-Weight Subsequence.
Cite as

Amir Abboud. Fine-Grained Reductions and Quantum Speedups for Dynamic Programming. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 8:1-8:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{abboud:LIPIcs.ICALP.2019.8,
  author =	{Abboud, Amir},
  title =	{{Fine-Grained Reductions and Quantum Speedups for Dynamic Programming}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{8:1--8:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.8},
  URN =		{urn:nbn:de:0030-drops-105846},
  doi =		{10.4230/LIPIcs.ICALP.2019.8},
  annote =	{Keywords: Fine-Grained Complexity, Set-Cover, 3-SUM, k-Clique, k-SUM, Dynamic Programming, Quantum Algorithms}
}
  • Refine by Author
  • 10 Chatzigiannakis, Ioannis
  • 10 Lokshtanov, Daniel
  • 10 Saurabh, Saket
  • 9 Woodruff, David P.
  • 9 Worrell, James
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 18 approximation algorithms
  • 13 Approximation Algorithms
  • 12 lower bounds
  • 11 Approximation algorithms
  • 11 communication complexity
  • Show More...

  • Refine by Type
  • 617 document
  • 4 volume

  • Refine by Publication Year
  • 168 2018
  • 154 2019
  • 153 2016
  • 144 2017
  • 1 2010
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact