154 Search Results for "Feige, Uriel"

Volume

LIPIcs, Volume 261

50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

ICALP 2023, July 10-14, 2023, Paderborn, Germany

Editors: Kousha Etessami, Uriel Feige, and Gabriele Puppis

Document
DOI: 10.4230/LIPIcs.SEA.2023.8
Noisy Sorting Without Searching: Data Oblivious Sorting with Comparison Errors

Authors: Ramtin Afshar, Michael Dillencourt, Michael T. Goodrich, and Evrim Ozel

Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)

Abstract
We provide and study several algorithms for sorting an array of n comparable distinct elements subject to probabilistic comparison errors. In this model, the comparison of two elements returns the wrong answer according to a fixed probability, p_e < 1/2, and otherwise returns the correct answer. The dislocation of an element is the distance between its position in a given (current or output) array and its position in a sorted array. There are various algorithms that can be utilized for sorting or near-sorting elements subject to probabilistic comparison errors, but these algorithms are not data oblivious because they all make heavy use of noisy binary searching. In this paper, we provide new methods for sorting with comparison errors that are data oblivious while avoiding the use of noisy binary search methods. In addition, we experimentally compare our algorithms and other sorting algorithms.
Cite as

Ramtin Afshar, Michael Dillencourt, Michael T. Goodrich, and Evrim Ozel. Noisy Sorting Without Searching: Data Oblivious Sorting with Comparison Errors. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 8:1-8:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{afshar_et_al:LIPIcs.SEA.2023.8,
  author =	{Afshar, Ramtin and Dillencourt, Michael and Goodrich, Michael T. and Ozel, Evrim},
  title =	{{Noisy Sorting Without Searching: Data Oblivious Sorting with Comparison Errors}},
  booktitle =	{21st International Symposium on Experimental Algorithms (SEA 2023)},
  pages =	{8:1--8: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.8},
  URN =		{urn:nbn:de:0030-drops-183585},
  doi =		{10.4230/LIPIcs.SEA.2023.8},
  annote =	{Keywords: sorting, algorithms, randomization, experimentation}
}
Document
DOI: 10.4230/LIPIcs.SEA.2023.21
Maximum Coverage in Sublinear Space, Faster

Authors: Stephen Jaud, Anthony Wirth, and Farhana Choudhury

Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)

Abstract
Given a collection of m sets from a universe 𝒰, the Maximum Set Coverage problem consists of finding k sets whose union has largest cardinality. This problem is NP-Hard, but the solution can be approximated by a polynomial time algorithm up to a factor 1-1/e. However, this algorithm does not scale well with the input size. In a streaming context, practical high-quality solutions are found, but with space complexity that scales linearly with respect to the size of the universe n = |𝒰|. However, one randomized streaming algorithm has been shown to produce a 1-1/e-ε approximation of the optimal solution with a space complexity that scales only poly-logarithmically with respect to m and n. In order to achieve such a low space complexity, the authors used two techniques in their multi-pass approach: - F₀-sketching, allows to determine with great accuracy the number of distinct elements in a set using less space than the set itself. - Subsampling, consists of only solving the problem on a subspace of the universe. It is implemented using γ-independent hash functions. This article focuses on the sublinear-space algorithm and highlights the time cost of these two techniques, especially subsampling. We present optimizations that significantly reduce the time complexity of the algorithm. Firstly, we give some optimizations that do not alter the space complexity, number of passes and approximation quality of the original algorithm. In particular, we reanalyze the error bounds to show that the original independence factor of Ω(ε^{-2} k log m) can be fine-tuned to Ω(k log m); we also show how F₀-sketching can be removed. Secondly, we derive a new lower bound for the probability of producing a 1-1/e-ε approximation using only pairwise independence: 1- (4/(c k log m)) compared to 1-(2e/(m^{ck/6})) with Ω(k log m)-independence. Although the theoretical guarantees are weaker, suggesting the approximation quality would suffer, for large streams, our algorithms perform well in practice. Finally, our experimental results show that even a pairwise-independent hash-function sampler does not produce worse solution than the original algorithm, while running significantly faster by several orders of magnitude.
Cite as

Stephen Jaud, Anthony Wirth, and Farhana Choudhury. Maximum Coverage in Sublinear Space, Faster. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 21:1-21:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{jaud_et_al:LIPIcs.SEA.2023.21,
  author =	{Jaud, Stephen and Wirth, Anthony and Choudhury, Farhana},
  title =	{{Maximum Coverage in Sublinear Space, Faster}},
  booktitle =	{21st International Symposium on Experimental Algorithms (SEA 2023)},
  pages =	{21:1--21:20},
  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.21},
  URN =		{urn:nbn:de:0030-drops-183715},
  doi =		{10.4230/LIPIcs.SEA.2023.21},
  annote =	{Keywords: streaming algorithms, subsampling, maximum set cover, k-wise independent hash functions}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.ICALP.2023
LIPIcs, Volume 261, ICALP 2023, Complete Volume

Authors: Kousha Etessami, Uriel Feige, and Gabriele Puppis

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
LIPIcs, Volume 261, ICALP 2023, Complete Volume
Cite as

50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 1-2486, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Proceedings{etessami_et_al:LIPIcs.ICALP.2023,
  title =	{{LIPIcs, Volume 261, ICALP 2023, Complete Volume}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{1--2486},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023},
  URN =		{urn:nbn:de:0030-drops-180517},
  doi =		{10.4230/LIPIcs.ICALP.2023},
  annote =	{Keywords: LIPIcs, Volume 261, ICALP 2023, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.ICALP.2023.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Kousha Etessami, Uriel Feige, and Gabriele Puppis

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

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

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

Copy BibTex To Clipboard

@InProceedings{etessami_et_al:LIPIcs.ICALP.2023.0,
  author =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{0:i--0:xxxviii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.0},
  URN =		{urn:nbn:de:0030-drops-180523},
  doi =		{10.4230/LIPIcs.ICALP.2023.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.ICALP.2023.1
A (Slightly) Improved Approximation Algorithm for the Metric Traveling Salesperson Problem (Invited Talk)

Authors: Anna R. Karlin

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
We describe recent joint work with Nathan Klein and Shayan Oveis Gharan showing that for any metric TSP instance, the max entropy algorithm studied by [Anna R. Karlin et al., 2021] returns a solution of expected cost at most 3/2-ε times the cost of the optimal solution to the subtour elimination LP and hence is a 3/2-ε approximation for the metric TSP problem. The research discussed comes from [Anna R. Karlin et al., 2021], [Anna R. Karlin et al., 2022] and [Anna R. Karlin et al., 2022].
Cite as

Anna R. Karlin. A (Slightly) Improved Approximation Algorithm for the Metric Traveling Salesperson Problem (Invited Talk). In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, p. 1:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{karlin:LIPIcs.ICALP.2023.1,
  author =	{Karlin, Anna R.},
  title =	{{A (Slightly) Improved Approximation Algorithm for the Metric Traveling Salesperson Problem}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{1:1--1:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.1},
  URN =		{urn:nbn:de:0030-drops-180531},
  doi =		{10.4230/LIPIcs.ICALP.2023.1},
  annote =	{Keywords: Traveling Salesperson Problem, approximation algorithm}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.ICALP.2023.2
An Almost-Linear Time Algorithm for Maximum Flow and More (Invited Talk)

Authors: Rasmus Kyng

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
In this talk, I will explain a new algorithm for computing exact maximum and minimum-cost flows in almost-linear time, settling the time complexity of these basic graph problems up to subpolynomial factors. Our algorithm uses a novel interior point method that builds the optimal flow as a sequence of approximate minimum-ratio cycles, each of which is computed and processed very efficiently using a new dynamic data structure. By well-known reductions, our result implies almost-linear time algorithms for several problems including bipartite matching, optimal transport, and undirected vertex connectivity. Our framework also extends to minimizing general edge-separable convex functions to high accuracy, yielding the first almost-linear time algorithms for many other problems including entropy-regularized optimal transport, matrix scaling, p-norm flows, and isotonic regression. This talk is based on joint work with Li Chen, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva [Chen et al., 2022]. Our result appeared in FOCS'22 and won the FOCS best paper award.
Cite as

Rasmus Kyng. An Almost-Linear Time Algorithm for Maximum Flow and More (Invited Talk). In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, p. 2:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kyng:LIPIcs.ICALP.2023.2,
  author =	{Kyng, Rasmus},
  title =	{{An Almost-Linear Time Algorithm for Maximum Flow and More}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.2},
  URN =		{urn:nbn:de:0030-drops-180543},
  doi =		{10.4230/LIPIcs.ICALP.2023.2},
  annote =	{Keywords: Maximum flow, Minimum cost flow, Data structures, Interior point methods, Convex optimization}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.ICALP.2023.3
Context-Bounded Analysis of Concurrent Programs (Invited Talk)

Authors: Pascal Baumann, Moses Ganardi, Rupak Majumdar, Ramanathan S. Thinniyam, and Georg Zetzsche

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
Context-bounded analysis of concurrent programs is a technique to compute a sequence of under-approximations of all behaviors of the program. For a fixed bound k, a context bounded analysis considers only those runs in which a single process is interrupted at most k times. As k grows, we capture more and more behaviors of the program. Practically, context-bounding has been very effective as a bug-finding tool: many bugs can be found even with small bounds. Theoretically, context-bounded analysis is decidable for a large number of programming models for which verification problems are undecidable. In this paper, we survey some recent work in context-bounded analysis of multithreaded programs. In particular, we show a general decidability result. We study context-bounded reachability in a language-theoretic setup. We fix a class of languages (satisfying some mild conditions) from which each thread is chosen. We show context-bounded safety and termination verification problems are decidable iff emptiness is decidable for the underlying class of languages and context-bounded boundedness is decidable iff finiteness is decidable for the underlying class.
Cite as

Pascal Baumann, Moses Ganardi, Rupak Majumdar, Ramanathan S. Thinniyam, and Georg Zetzsche. Context-Bounded Analysis of Concurrent Programs (Invited Talk). In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 3:1-3:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{baumann_et_al:LIPIcs.ICALP.2023.3,
  author =	{Baumann, Pascal and Ganardi, Moses and Majumdar, Rupak and Thinniyam, Ramanathan S. and Zetzsche, Georg},
  title =	{{Context-Bounded Analysis of Concurrent Programs}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{3:1--3:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.3},
  URN =		{urn:nbn:de:0030-drops-180559},
  doi =		{10.4230/LIPIcs.ICALP.2023.3},
  annote =	{Keywords: Context-bounded analysis, Multi-threaded programs, Decidability}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.ICALP.2023.4
Quantum Codes, Local Testability and Interactive Proofs: State of the Art and Open Questions (Invited Talk)

Authors: Thomas Vidick

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
The study of multiprover interactive proof systems, of locally testable codes, and of property testing are deeply linked, conceptually if not formally, through their role in the proof of the PCP theorem in complexity theory. Recently there has been substantial progress on an analogous research programme in quantum complexity theory. Two years ago we characterized the power of multiprover interactive proof systems with provers sharing entanglement, showing that MIP^* = RE [Ji et al., 2020], a hugely surprising increase in power from the classical result MIP = NEXP of [Babai et al., 1991]. The following year Panteleev and Kalachev gave the first construction of quantum low-density parity-check codes (QLDPC) [Panteleev and Kalachev, 2022], thus marking a major step towards the possible realization of good quantum locally testable codes - the classical analogue of which was only constructed quite recently [Dinur et al., 2022]. And finally, less than a year ago Anshu, Breuckmann and Nirkhe used facts evidenced in the construction of good decoders for the new QLDPC codes to resolve the NLTS conjecture [Anshu et al., 2022], widely viewed as a crucial step on the way to a possible quantum PCP theorem. In the talk I will survey these results, making an effort to motivate and present them to the non-expert. I will explain the connections between them and point to where, in my opinion, our understanding is currently lacking. Along the way I will highlight a number of open problems whose resolution could lead to further progress on one of the most important research programmes in quantum complexity theory.
Cite as

Thomas Vidick. Quantum Codes, Local Testability and Interactive Proofs: State of the Art and Open Questions (Invited Talk). In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, p. 4:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{vidick:LIPIcs.ICALP.2023.4,
  author =	{Vidick, Thomas},
  title =	{{Quantum Codes, Local Testability and Interactive Proofs: State of the Art and Open Questions}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{4:1--4:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.4},
  URN =		{urn:nbn:de:0030-drops-180569},
  doi =		{10.4230/LIPIcs.ICALP.2023.4},
  annote =	{Keywords: quantum interactive proofs, quantum codes}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.ICALP.2023.5
The Skolem Landscape (Invited Talk)

Authors: James Worrell

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
The Skolem Problem asks to determine whether a given integer linear recurrence sequence (LRS) has a zero term. This decision problem arises within a number of different topics in computer science, including loop termination, weighted automata, formal power series, and probabilistic model checking, among many other examples. Decidability of the problem is notoriously open, despite having been the subject of sustained interest over several decades [Halava et al., 2005]. More specifically, the problem is known to be decidable for recurrences of order at most 4 - a result obtained some 40 years ago [Mignotte et al., 1984; Vereshchagin, 1985] - while decidability is open already for recurrences of order 5. In this talk we take a wide-ranging view of the Skolem Problem. We survey its history and context, starting with the theorem of Skolem-Mahler-Lech characterising the set of zeros of a LRS over fields of characteristic zero. Here we explain the non-effective nature of the existing proofs of the theorem. Among modern developments, we overview versions of the Skolem-Mahler-Lech theorem for non-linear recurrences and for fields of non-zero characteristic. We also describe two recent directions of progress toward showing decidability of the Skolem Problem subject to classical number theoretic conjectures. The first new development concerns a recent algorithm [Y. Bilu et al., 2022] that decides the problem on the class of simple LRS (those with simple characteristic roots) subject to two classical conjectures about the exponential function. The algorithm is self-certifying: its output comes with a certificate of correctness that can be checked unconditionally. The two conjectures alluded to above are required for the proof of termination of the algorithm. A second new development concerns the notion of Universal Skolem Set [F. Luca et al., 2022]: a recursive set S of positive integers such that it is decidable whether a given non-degenerate linear recurrence sequence has a zero in S. Decidability of the Skolem Problem is equivalent to the assertion that ℕ is a Universal Skolem Set. In lieu of this one can ask whether there exists a Universal Skolem Set of density one. We will present a recent a construction of a Universal Skolem Set that has positive density unconditionally and has density one subject to the Bateman-Horn conjecture in number theory. The latter is a far-reaching generalisation of Hardy and Littlewood’s twin primes conjecture.
Cite as

James Worrell. The Skolem Landscape (Invited Talk). In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 5:1-5:2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{worrell:LIPIcs.ICALP.2023.5,
  author =	{Worrell, James},
  title =	{{The Skolem Landscape}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{5:1--5:2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.5},
  URN =		{urn:nbn:de:0030-drops-180573},
  doi =		{10.4230/LIPIcs.ICALP.2023.5},
  annote =	{Keywords: Automata, Formal Languages, Linear Recurrence Sequences}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.6
Optimal Decremental Connectivity in Non-Sparse Graphs

Authors: Anders Aamand, Adam Karczmarz, Jakub Łącki, Nikos Parotsidis, Peter M. R. Rasmussen, and Mikkel Thorup

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
We present a dynamic algorithm for maintaining the connected and 2-edge-connected components in an undirected graph subject to edge deletions. The algorithm is Monte-Carlo randomized and processes any sequence of edge deletions in O(m + n poly log n) total time. Interspersed with the deletions, it can answer queries whether any two given vertices currently belong to the same (2-edge-)connected component in constant time. Our result is based on a general Monte-Carlo randomized reduction from decremental c-edge-connectivity to a variant of fully-dynamic c-edge-connectivity on a sparse graph. For non-sparse graphs with Ω(n poly log n) edges, our connectivity and 2-edge-connectivity algorithms handle all deletions in optimal linear total time, using existing algorithms for the respective fully-dynamic problems. This improves upon an O(m log (n² / m) + n poly log n)-time algorithm of Thorup [J.Alg. 1999], which runs in linear time only for graphs with Ω(n²) edges. Our constant amortized cost for edge deletions in decremental connectivity in non-sparse graphs should be contrasted with an Ω(log n/log log n) worst-case time lower bound in the decremental setting [Alstrup, Husfeldt, and Rauhe FOCS'98] as well as an Ω(log n) amortized time lower-bound in the fully-dynamic setting [Patrascu and Demaine STOC'04].
Cite as

Anders Aamand, Adam Karczmarz, Jakub Łącki, Nikos Parotsidis, Peter M. R. Rasmussen, and Mikkel Thorup. Optimal Decremental Connectivity in Non-Sparse Graphs. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 6:1-6:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{aamand_et_al:LIPIcs.ICALP.2023.6,
  author =	{Aamand, Anders and Karczmarz, Adam and {\L}\k{a}cki, Jakub and Parotsidis, Nikos and Rasmussen, Peter M. R. and Thorup, Mikkel},
  title =	{{Optimal Decremental Connectivity in Non-Sparse Graphs}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{6:1--6:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.6},
  URN =		{urn:nbn:de:0030-drops-180581},
  doi =		{10.4230/LIPIcs.ICALP.2023.6},
  annote =	{Keywords: decremental connectivity, dynamic connectivity}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.7
On Range Summary Queries

Authors: Peyman Afshani, Pingan Cheng, Aniket Basu Roy, and Zhewei Wei

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
We study the query version of the approximate heavy hitter and quantile problems. In the former problem, the input is a parameter ε and a set P of n points in ℝ^d where each point is assigned a color from a set C, and the goal is to build a structure such that given any geometric range γ, we can efficiently find a list of approximate heavy hitters in γ∩P, i.e., colors that appear at least ε |γ∩P| times in γ∩P, as well as their frequencies with an additive error of ε |γ∩P|. In the latter problem, each point is assigned a weight from a totally ordered universe and the query must output a sequence S of 1+1/ε weights such that the i-th weight in S has approximate rank iε|γ∩P|, meaning, rank iε|γ∩P| up to an additive error of ε|γ∩P|. Previously, optimal results were only known in 1D [Wei and Yi, 2011] but a few sub-optimal methods were available in higher dimensions [Peyman Afshani and Zhewei Wei, 2017; Pankaj K. Agarwal et al., 2012]. We study the problems for two important classes of geometric ranges: 3D halfspace and 3D dominance queries. It is known that many other important queries can be reduced to these two, e.g., 1D interval stabbing or interval containment, 2D three-sided queries, 2D circular as well as 2D k-nearest neighbors queries. We consider the real RAM model of computation where integer registers of size w bits, w = Θ(log n), are also available. For dominance queries, we show optimal solutions for both heavy hitter and quantile problems: using linear space, we can answer both queries in time O(log n + 1/ε). Note that as the output size is 1/ε, after investing the initial O(log n) searching time, our structure takes on average O(1) time to find a heavy hitter or a quantile! For more general halfspace heavy hitter queries, the same optimal query time can be achieved by increasing the space by an extra log_w(1/ε) (resp. log log_w(1/ε)) factor in 3D (resp. 2D). By spending extra log^O(1)(1/ε) factors in both time and space, we can also support quantile queries. We remark that it is hopeless to achieve a similar query bound for dimensions 4 or higher unless significant advances are made in the data structure side of theory of geometric approximations.
Cite as

Peyman Afshani, Pingan Cheng, Aniket Basu Roy, and Zhewei Wei. On Range Summary Queries. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 7:1-7:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{afshani_et_al:LIPIcs.ICALP.2023.7,
  author =	{Afshani, Peyman and Cheng, Pingan and Basu Roy, Aniket and Wei, Zhewei},
  title =	{{On Range Summary Queries}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{7:1--7:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.7},
  URN =		{urn:nbn:de:0030-drops-180590},
  doi =		{10.4230/LIPIcs.ICALP.2023.7},
  annote =	{Keywords: Computational Geometry, Range Searching, Random Sampling, Geometric Approximation, Data Structures and Algorithms}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.8
Stable Matching: Choosing Which Proposals to Make

Authors: Ishan Agarwal and Richard Cole

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
To guarantee all agents are matched in general, the classic Deferred Acceptance algorithm needs complete preference lists. In practice, preference lists are short, yet stable matching still works well. This raises two questions: - Why does it work well? - Which proposals should agents include in their preference lists? We study these questions in a model, introduced by Lee [Lee, 2016], with preferences based on correlated cardinal utilities: these utilities are based on common public ratings of each agent together with individual private adjustments. Lee showed that for suitable utility functions, in large markets, with high probability, for most agents, all stable matchings yield similar valued utilities. By means of a new analysis, we strengthen Lee’s result, showing that in large markets, with high probability, for all but the agents with the lowest public ratings, all stable matchings yield similar valued utilities. We can then deduce that for all but the agents with the lowest public ratings, each agent has an easily identified length O(log n) preference list that includes all of its stable matches, addressing the second question above. We note that this identification uses an initial communication phase. We extend these results to settings where the two sides have unequal numbers of agents, to many-to-one settings, e.g. employers and workers, and we also show the existence of an ε-Bayes-Nash equilibrium in which every agent makes relatively few proposals. These results all rely on a new technique for sidestepping the conditioning between the tentative matching events that occur over the course of a run of the Deferred Acceptance algorithm. We complement these theoretical results with an experimental study.
Cite as

Ishan Agarwal and Richard Cole. Stable Matching: Choosing Which Proposals to Make. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 8:1-8:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.ICALP.2023.8,
  author =	{Agarwal, Ishan and Cole, Richard},
  title =	{{Stable Matching: Choosing Which Proposals to Make}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{8:1--8:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.8},
  URN =		{urn:nbn:de:0030-drops-180603},
  doi =		{10.4230/LIPIcs.ICALP.2023.8},
  annote =	{Keywords: Stable matching, randomized analysis}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.9
Expander Decomposition with Fewer Inter-Cluster Edges Using a Spectral Cut Player

Authors: Daniel Agassy, Dani Dorfman, and Haim Kaplan

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
A (ϕ,ε)-expander decomposition of a graph G (with n vertices and m edges) is a partition of V into clusters V₁,…,V_k with conductance Φ(G[V_i]) ≥ ϕ, such that there are at most ε m inter-cluster edges. Such a decomposition plays a crucial role in many graph algorithms. We give a randomized Õ(m/ϕ) time algorithm for computing a (ϕ, ϕlog²n)-expander decomposition. This improves upon the (ϕ, ϕlog³n)-expander decomposition also obtained in Õ(m/ϕ) time by [Saranurak and Wang, SODA 2019] (SW) and brings the number of inter-cluster edges within logarithmic factor of optimal. One crucial component of SW’s algorithm is a non-stop version of the cut-matching game of [Khandekar, Rao, Vazirani, JACM 2009] (KRV): The cut player does not stop when it gets from the matching player an unbalanced sparse cut, but continues to play on a trimmed part of the large side. The crux of our improvement is the design of a non-stop version of the cleverer cut player of [Orecchia, Schulman, Vazirani, Vishnoi, STOC 2008] (OSVV). The cut player of OSSV uses a more sophisticated random walk, a subtle potential function, and spectral arguments. Designing and analysing a non-stop version of this game was an explicit open question asked by SW.
Cite as

Daniel Agassy, Dani Dorfman, and Haim Kaplan. Expander Decomposition with Fewer Inter-Cluster Edges Using a Spectral Cut Player. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 9:1-9:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{agassy_et_al:LIPIcs.ICALP.2023.9,
  author =	{Agassy, Daniel and Dorfman, Dani and Kaplan, Haim},
  title =	{{Expander Decomposition with Fewer Inter-Cluster Edges Using a Spectral Cut Player}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{9:1--9:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.9},
  URN =		{urn:nbn:de:0030-drops-180619},
  doi =		{10.4230/LIPIcs.ICALP.2023.9},
  annote =	{Keywords: Exapander Decomposition, Cut-Matching Game}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.10
Locality in Online, Dynamic, Sequential, and Distributed Graph Algorithms

Authors: Amirreza Akbari, Navid Eslami, Henrik Lievonen, Darya Melnyk, Joona Särkijärvi, and Jukka Suomela

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
In this work, we give a unifying view of locality in four settings: distributed algorithms, sequential greedy algorithms, dynamic algorithms, and online algorithms. We introduce a new model of computing, called the online-LOCAL model: the adversary presents the nodes of the input graph one by one, in the same way as in classical online algorithms, but for each node we get to see its radius-T neighborhood before choosing the output. Instead of looking ahead in time, we have the power of looking around in space. We compare the online-LOCAL model with three other models: the LOCAL model of distributed computing, where each node produces its output based on its radius-T neighborhood, the SLOCAL model, which is the sequential counterpart of LOCAL, and the dynamic-LOCAL model, where changes in the dynamic input graph only influence the radius-T neighborhood of the point of change. The SLOCAL and dynamic-LOCAL models are sandwiched between the LOCAL and online-LOCAL models. In general, all four models are distinct, but we study in particular locally checkable labeling problems (LCLs), which is a family of graph problems extensively studied in the context of distributed graph algorithms. We prove that for LCL problems in paths, cycles, and rooted trees, all four models are roughly equivalent: the locality of any LCL problem falls in the same broad class - O(log* n), Θ(log n), or n^Θ(1) - in all four models. In particular, this result enables one to generalize prior lower-bound results from the LOCAL model to all four models, and it also allows one to simulate e.g. dynamic-LOCAL algorithms efficiently in the LOCAL model. We also show that this equivalence does not hold in two-dimensional grids or general bipartite graphs. We provide an online-LOCAL algorithm with locality O(log n) for the 3-coloring problem in bipartite graphs - this is a problem with locality Ω(n^{1/2}) in the LOCAL model and Ω(n^{1/10}) in the SLOCAL model.
Cite as

Amirreza Akbari, Navid Eslami, Henrik Lievonen, Darya Melnyk, Joona Särkijärvi, and Jukka Suomela. Locality in Online, Dynamic, Sequential, and Distributed Graph Algorithms. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 10:1-10:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{akbari_et_al:LIPIcs.ICALP.2023.10,
  author =	{Akbari, Amirreza and Eslami, Navid and Lievonen, Henrik and Melnyk, Darya and S\"{a}rkij\"{a}rvi, Joona and Suomela, Jukka},
  title =	{{Locality in Online, Dynamic, Sequential, and Distributed Graph Algorithms}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{10:1--10:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.10},
  URN =		{urn:nbn:de:0030-drops-180627},
  doi =		{10.4230/LIPIcs.ICALP.2023.10},
  annote =	{Keywords: Online computation, spatial advice, distributed algorithms, computational complexity}
}
  • Refine by Author
  • 8 Feige, Uriel
  • 3 Feldman, Michal
  • 3 Kothari, Pravesh K.
  • 3 Manurangsi, Pasin
  • 3 Ohlmann, Pierre
  • Show More...

  • Refine by Classification
  • 10 Theory of computation → Approximation algorithms analysis
  • 9 Theory of computation → Problems, reductions and completeness
  • 8 Mathematics of computing → Graph algorithms
  • 8 Theory of computation → Design and analysis of algorithms
  • 8 Theory of computation → Parameterized complexity and exact algorithms
  • Show More...

  • Refine by Keyword
  • 9 Approximation Algorithms
  • 5 approximation algorithms
  • 4 streaming algorithms
  • 3 Approximation
  • 3 Network Design
  • Show More...

  • Refine by Type
  • 153 document
  • 1 volume

  • Refine by Publication Year
  • 143 2023
  • 2 2008
  • 2 2018
  • 2 2019
  • 2 2022
  • 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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact