23 Search Results for "Chazelle, Bernard"

Document
DOI: 10.4230/LIPIcs.ESA.2024.4
Worst-Case to Expander-Case Reductions: Derandomized and Generalized

Authors: Amir Abboud and Nathan Wallheimer

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
A recent paper by Abboud and Wallheimer [ITCS 2023] presents self-reductions for various fundamental graph problems, which transform worst-case instances to expanders, thus proving that the complexity remains unchanged if the input is assumed to be an expander. An interesting corollary of their self-reductions is that if some problem admits such reduction, then the popular algorithmic paradigm based on expander-decompositions is useless against it. In this paper, we improve their core gadget, which augments a graph to make it an expander while retaining its important structure. Our new core construction has the benefit of being simple to analyze and generalize while obtaining the following results: - A derandomization of the self-reductions, showing that the equivalence between worst-case and expander-case holds even for deterministic algorithms, and ruling out the use of expander-decompositions as a derandomization tool. - An extension of the results to other models of computation, such as the Fully Dynamic model and the Congested Clique model. In the former, we either improve or provide an alternative approach to some recent hardness results for dynamic expander graphs by Henzinger, Paz, and Sricharan [ESA 2022]. In addition, we continue this line of research by designing new self-reductions for more problems, such as Max-Cut and dynamic Densest Subgraph, and demonstrating that the core gadget can be utilized to lift lower bounds based on the OMv Conjecture to expanders.
Cite as

Amir Abboud and Nathan Wallheimer. Worst-Case to Expander-Case Reductions: Derandomized and Generalized. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 4:1-4:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{abboud_et_al:LIPIcs.ESA.2024.4,
  author =	{Abboud, Amir and Wallheimer, Nathan},
  title =	{{Worst-Case to Expander-Case Reductions: Derandomized and Generalized}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{4:1--4:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.4},
  URN =		{urn:nbn:de:0030-drops-210751},
  doi =		{10.4230/LIPIcs.ESA.2024.4},
  annote =	{Keywords: Fine-grained complexity, expander graphs, self-reductions, worst-case to expander-case, expander decomposition, dynamic algorithms, exact and parameterized complexity, max-cut, maximum matching, k-clique detection, densest subgraph}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.18
Height-Bounded Lempel-Ziv Encodings

Authors: Hideo Bannai, Mitsuru Funakoshi, Diptarama Hendrian, Myuji Matsuda, and Simon J. Puglisi

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
We introduce height-bounded LZ encodings (LZHB), a new family of compressed representations that are variants of Lempel-Ziv parsings with a focus on bounding the worst-case access time to arbitrary positions in the text directly via the compressed representation. An LZ-like encoding is a partitioning of the string into phrases of length 1 which can be encoded literally, or phrases of length at least 2 which have a previous occurrence in the string and can be encoded by its position and length. An LZ-like encoding induces an implicit referencing forest on the set of positions of the string. An LZHB encoding is an LZ-like encoding where the height of the implicit referencing forest is bounded. An LZHB encoding with height constraint h allows access to an arbitrary position of the underlying text using O(h) predecessor queries. While computing the optimal (i.e., smallest) LZHB encoding efficiently seems to be difficult [Cicalese & Ugazio 2024, arXiv, to appear at DLT 2024], we give the first linear time algorithm for strings over a constant size alphabet that computes the greedy LZHB encoding, i.e., the string is processed from beginning to end, and the longest prefix of the remaining string that can satisfy the height constraint is taken as the next phrase. Our algorithms significantly improve both theoretically and practically, the very recently and independently proposed algorithms by Lipták et al. (CPM 2024). We also analyze the size of height bounded LZ encodings in the context of repetitiveness measures, and show that there exists a constant c such that the size ẑ_{HB(clog n)} of the optimal LZHB encoding whose height is bounded by clog n for any string of length n is O(ĝ_{rl}), where ĝ_{rl} is the size of the smallest run-length grammar. Furthermore, we show that there exists a family of strings such that ẑ_{HB(clog n)} = o(ĝ_{rl}), thus making ẑ_{HB(clog n)} one of the smallest known repetitiveness measures for which O(polylog n) time access is possible using linear (O(ẑ_{HB(clog n)})) space.
Cite as

Hideo Bannai, Mitsuru Funakoshi, Diptarama Hendrian, Myuji Matsuda, and Simon J. Puglisi. Height-Bounded Lempel-Ziv Encodings. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 18:1-18:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bannai_et_al:LIPIcs.ESA.2024.18,
  author =	{Bannai, Hideo and Funakoshi, Mitsuru and Hendrian, Diptarama and Matsuda, Myuji and Puglisi, Simon J.},
  title =	{{Height-Bounded Lempel-Ziv Encodings}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{18:1--18:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.18},
  URN =		{urn:nbn:de:0030-drops-210899},
  doi =		{10.4230/LIPIcs.ESA.2024.18},
  annote =	{Keywords: Lempel-Ziv parsing, data compression}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.27
Art Galleries and Mobile Guards: Revisiting O'Rourke’s Proof

Authors: Ahmad Biniaz

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
O'Rourke (1983) proved that every n-vertex polygon, with n ≥ 4, can be guarded by ⌊ n/4⌋ edges or diagonals - a variant of Chvátal’s theorem for sufficiency of ⌊ n/3⌋ vertices. We present a short proof for a somewhat stronger result that allows us to impose some constraints on the guards. We prove that for every given subset V of vertices, the polygon can be guarded by ⌊(n+2|V|)/4⌋ edges or diagonals that include at least one edge or diagonal incident to every vertex of V. This bound is the best achievable given the constraint for V. Our proof is by induction and suggests a simple linear-time algorithm after triangulating the polygon. The sufficiency of ⌊4⌋ guards is a special case of the new result where V is the empty set.
Cite as

Ahmad Biniaz. Art Galleries and Mobile Guards: Revisiting O'Rourke’s Proof. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 27:1-27:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{biniaz:LIPIcs.ESA.2024.27,
  author =	{Biniaz, Ahmad},
  title =	{{Art Galleries and Mobile Guards: Revisiting O'Rourke’s Proof}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{27:1--27:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.27},
  URN =		{urn:nbn:de:0030-drops-210989},
  doi =		{10.4230/LIPIcs.ESA.2024.27},
  annote =	{Keywords: Polygon guarding, Edge guarding, Short proof, Simple algorithm}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.28
A Faster Algorithm for the Fréchet Distance in 1D for the Imbalanced Case

Authors: Lotte Blank and Anne Driemel

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
The fine-grained complexity of computing the {Fréchet distance } has been a topic of much recent work, starting with the quadratic SETH-based conditional lower bound by Bringmann from 2014. Subsequent work established largely the same complexity lower bounds for the {Fréchet distance } in 1D. However, the imbalanced case, which was shown by Bringmann to be tight in dimensions d ≥ 2, was still left open. Filling in this gap, we show that a faster algorithm for the {Fréchet distance } in the imbalanced case is possible: Given two 1-dimensional curves of complexity n and n^{α} for some α ∈ (0,1), we can compute their {Fréchet distance } in O(n^{2α} log² n + n log n) time. This rules out a conditional lower bound of the form O((nm)^{1-ε}) that Bringmann showed for d ≥ 2 and any ε > 0 in turn showing a strict separation with the setting d = 1. At the heart of our approach lies a data structure that stores a 1-dimensional curve P of complexity n, and supports queries with a curve Q of complexity m for the continuous {Fréchet distance } between P and Q. The data structure has size in 𝒪(nlog n) and uses query time in 𝒪(m² log² n). Our proof uses a key lemma that is based on the concept of visiting orders and may be of independent interest. We demonstrate this by substantially simplifying the correctness proof of a clustering algorithm by Driemel, Krivošija and Sohler from 2015.
Cite as

Lotte Blank and Anne Driemel. A Faster Algorithm for the Fréchet Distance in 1D for the Imbalanced Case. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 28:1-28:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{blank_et_al:LIPIcs.ESA.2024.28,
  author =	{Blank, Lotte and Driemel, Anne},
  title =	{{A Faster Algorithm for the Fr\'{e}chet Distance in 1D for the Imbalanced Case}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{28:1--28:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.28},
  URN =		{urn:nbn:de:0030-drops-210999},
  doi =		{10.4230/LIPIcs.ESA.2024.28},
  annote =	{Keywords: \{Fr\'{e}chet distance\}, distance oracle, data structures, time series}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.31
String 2-Covers with No Length Restrictions

Authors: Itai Boneh, Shay Golan, and Arseny Shur

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
A λ-cover of a string S is a set of strings {C_i}₁^λ such that every index in S is contained in an occurrence of at least one string C_i. The existence of a 1-cover defines a well-known class of quasi-periodic strings. Quasi-periodicity can be decided in linear time, and all 1-covers of a string can be reported in linear time as well. Since in general it is NP-complete to decide whether a string has a λ-cover, the natural next step is the development of efficient algorithms for 2-covers. Radoszewski and Straszyński [ESA 2020] analysed the particular case where the strings in a 2-cover must be of the same length. They provided an algorithm that reports all such 2-covers of S in time near-linear in |S| and in the size of the output. In this work, we consider 2-covers in full generality. Since every length-n string has Ω(n²) trivial 2-covers (every prefix and suffix of total length at least n constitute such a 2-cover), we state the reporting problem as follows: given a string S and a number m, report all 2-covers {C₁,C₂} of S with length |C₁|+|C₂| upper bounded by m. We present an Õ(n + output) time algorithm solving this problem, with output being the size of the output. This algorithm admits a simpler modification that finds a 2-cover of minimum length. We also provide an Õ(n) time construction of a 2-cover oracle which, given two substrings C₁,C₂ of S, reports in poly-logarithmic time whether {C₁,C₂} is a 2-cover of S.
Cite as

Itai Boneh, Shay Golan, and Arseny Shur. String 2-Covers with No Length Restrictions. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 31:1-31:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{boneh_et_al:LIPIcs.ESA.2024.31,
  author =	{Boneh, Itai and Golan, Shay and Shur, Arseny},
  title =	{{String 2-Covers with No Length Restrictions}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{31:1--31:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.31},
  URN =		{urn:nbn:de:0030-drops-211029},
  doi =		{10.4230/LIPIcs.ESA.2024.31},
  annote =	{Keywords: Quasi-periodicity, String cover, Range query, Range stabbing}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.51
Better Diameter Algorithms for Bounded VC-Dimension Graphs and Geometric Intersection Graphs

Authors: Lech Duraj, Filip Konieczny, and Krzysztof Potępa

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
We develop a framework for algorithms finding the diameter in graphs of bounded distance Vapnik-Chervonenkis dimension, in (parameterized) subquadratic time complexity. The class of bounded distance VC-dimension graphs is wide, including, e.g. all minor-free graphs. We build on the work of Ducoffe et al. [SODA'20, SIGCOMP'22], improving their technique. With our approach the algorithms become simpler and faster, working in 𝒪{(k ⋅ n^{1-1/d} ⋅ m ⋅ polylog(n))} time complexity for the graph on n vertices and m edges, where k is the diameter and d is the distance VC-dimension of the graph. Furthermore, it allows us to use the improved technique in more general setting. In particular, we use this framework for geometric intersection graphs, i.e. graphs where vertices are identical geometric objects on a plane and the adjacency is defined by intersection. Applying our approach for these graphs, we partially answer a question posed by Bringmann et al. [SoCG'22], finding an 𝒪{(n^{7/4} ⋅ polylog(n))} parameterized diameter algorithm for unit square intersection graph of size n, as well as a more general algorithm for convex polygon intersection graphs.
Cite as

Lech Duraj, Filip Konieczny, and Krzysztof Potępa. Better Diameter Algorithms for Bounded VC-Dimension Graphs and Geometric Intersection Graphs. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 51:1-51:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{duraj_et_al:LIPIcs.ESA.2024.51,
  author =	{Duraj, Lech and Konieczny, Filip and Pot\k{e}pa, Krzysztof},
  title =	{{Better Diameter Algorithms for Bounded VC-Dimension Graphs and Geometric Intersection Graphs}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{51:1--51:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.51},
  URN =		{urn:nbn:de:0030-drops-211229},
  doi =		{10.4230/LIPIcs.ESA.2024.51},
  annote =	{Keywords: Graph Diameter, Geometric Intersection Graphs, Vapnik-Chervonenkis Dimension}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.37
Nearly Optimal Bounds for Sample-Based Testing and Learning of k-Monotone Functions

Authors: Hadley Black

Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)

Abstract
We study monotonicity testing of functions f : {0,1}^d → {0,1} using sample-based algorithms, which are only allowed to observe the value of f on points drawn independently from the uniform distribution. A classic result by Bshouty-Tamon (J. ACM 1996) proved that monotone functions can be learned with exp(Õ(min{(1/ε)√d,d})) samples and it is not hard to show that this bound extends to testing. Prior to our work the only lower bound for this problem was Ω(√{exp(d)/ε}) in the small ε parameter regime, when ε = O(d^{-3/2}), due to Goldreich-Goldwasser-Lehman-Ron-Samorodnitsky (Combinatorica 2000). Thus, the sample complexity of monotonicity testing was wide open for ε ≫ d^{-3/2}. We resolve this question, obtaining a nearly tight lower bound of exp(Ω(min{(1/ε)√d,d})) for all ε at most a sufficiently small constant. In fact, we prove a much more general result, showing that the sample complexity of k-monotonicity testing and learning for functions f : {0,1}^d → [r] is exp(Ω(min{(rk/ε)√d,d})). For testing with one-sided error we show that the sample complexity is exp(Ω(d)). Beyond the hypercube, we prove nearly tight bounds (up to polylog factors of d,k,r,1/ε in the exponent) of exp(Θ̃(min{(rk/ε)√d,d})) on the sample complexity of testing and learning measurable k-monotone functions f : ℝ^d → [r] under product distributions. Our upper bound improves upon the previous bound of exp(Õ(min{(k/ε²)√d,d})) by Harms-Yoshida (ICALP 2022) for Boolean functions (r = 2).
Cite as

Hadley Black. Nearly Optimal Bounds for Sample-Based Testing and Learning of k-Monotone Functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 37:1-37:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{black:LIPIcs.APPROX/RANDOM.2024.37,
  author =	{Black, Hadley},
  title =	{{Nearly Optimal Bounds for Sample-Based Testing and Learning of k-Monotone Functions}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{37:1--37:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.37},
  URN =		{urn:nbn:de:0030-drops-210308},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.37},
  annote =	{Keywords: Property testing, learning, Boolean functions, monotonicity, k-monotonicity}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.38
Approximating the Number of Relevant Variables in a Parity Implies Proper Learning

Authors: Nader H. Bshouty and George Haddad

Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)

Abstract
Consider the model where we can access a parity function through random uniform labeled examples in the presence of random classification noise. In this paper, we show that approximating the number of relevant variables in the parity function is as hard as properly learning parities. More specifically, let γ:ℝ^+ → ℝ^+, where γ(x) ≥ x, be any strictly increasing function. In our first result, we show that from any polynomial-time algorithm that returns a γ-approximation, D (i.e., γ^{-1}(d(f)) ≤ D ≤ γ(d(f))), of the number of relevant variables d(f) for any parity f, we can, in polynomial time, construct a solution to the long-standing open problem of polynomial-time learning k(n)-sparse parities (parities with k(n) ≤ n relevant variables), where k(n) = ω_n(1). In our second result, we show that from any T(n)-time algorithm that, for any parity f, returns a γ-approximation of the number of relevant variables d(f) of f, we can, in polynomial time, construct a poly(Γ(n))T(Γ(n)²)-time algorithm that properly learns parities, where Γ(x) = γ(γ(x)). If T(Γ(n)²) = exp({o(n/log n)}), this would resolve another long-standing open problem of properly learning parities in the presence of random classification noise in time exp(o(n/log n)).
Cite as

Nader H. Bshouty and George Haddad. Approximating the Number of Relevant Variables in a Parity Implies Proper Learning. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 38:1-38:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bshouty_et_al:LIPIcs.APPROX/RANDOM.2024.38,
  author =	{Bshouty, Nader H. and Haddad, George},
  title =	{{Approximating the Number of Relevant Variables in a Parity Implies Proper Learning}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{38:1--38:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.38},
  URN =		{urn:nbn:de:0030-drops-210316},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.38},
  annote =	{Keywords: PAC Learning, Random Classification Noise, Uniform Distribution, Parity, Sparcity Approximation}
}
Document
DOI: 10.4230/LIPIcs.TQC.2024.8
(Quantum) Complexity of Testing Signed Graph Clusterability

Authors: Kuo-Chin Chen, Simon Apers, and Min-Hsiu Hsieh

Published in: LIPIcs, Volume 310, 19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024)

Abstract
This study examines clusterability testing for a signed graph in the bounded-degree model. Our contributions are two-fold. First, we provide a quantum algorithm with query complexity Õ(N^{1/3}) for testing clusterability, which yields a polynomial speedup over the best classical clusterability tester known [Adriaens and Apers, 2023]. Second, we prove an Ω̃(√N) classical query lower bound for testing clusterability, which nearly matches the upper bound from [Adriaens and Apers, 2023]. This settles the classical query complexity of clusterability testing, and it shows that our quantum algorithm has an advantage over any classical algorithm.
Cite as

Kuo-Chin Chen, Simon Apers, and Min-Hsiu Hsieh. (Quantum) Complexity of Testing Signed Graph Clusterability. In 19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 310, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.TQC.2024.8,
  author =	{Chen, Kuo-Chin and Apers, Simon and Hsieh, Min-Hsiu},
  title =	{{(Quantum) Complexity of Testing Signed Graph Clusterability}},
  booktitle =	{19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024)},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-328-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{310},
  editor =	{Magniez, Fr\'{e}d\'{e}ric and Grilo, Alex Bredariol},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2024.8},
  URN =		{urn:nbn:de:0030-drops-206786},
  doi =		{10.4230/LIPIcs.TQC.2024.8},
  annote =	{Keywords: Quantum Algorithm, classical Query lower Bound, Graph Property testing}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2024.9
Quantum Algorithms for Hopcroft’s Problem

Authors: Vladimirs Andrejevs, Aleksandrs Belovs, and Jevgēnijs Vihrovs

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
In this work we study quantum algorithms for Hopcroft’s problem which is a fundamental problem in computational geometry. Given n points and n lines in the plane, the task is to determine whether there is a point-line incidence. The classical complexity of this problem is well-studied, with the best known algorithm running in O(n^{4/3}) time, with matching lower bounds in some restricted settings. Our results are two different quantum algorithms with time complexity Õ(n^{5/6}). The first algorithm is based on partition trees and the quantum backtracking algorithm. The second algorithm uses a quantum walk together with a history-independent dynamic data structure for storing line arrangement which supports efficient point location queries. In the setting where the number of points and lines differ, the quantum walk-based algorithm is asymptotically faster. The quantum speedups for the aforementioned data structures may be useful for other geometric problems.
Cite as

Vladimirs Andrejevs, Aleksandrs Belovs, and Jevgēnijs Vihrovs. Quantum Algorithms for Hopcroft’s Problem. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{andrejevs_et_al:LIPIcs.MFCS.2024.9,
  author =	{Andrejevs, Vladimirs and Belovs, Aleksandrs and Vihrovs, Jevg\={e}nijs},
  title =	{{Quantum Algorithms for Hopcroft’s Problem}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{9:1--9:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.9},
  URN =		{urn:nbn:de:0030-drops-205653},
  doi =		{10.4230/LIPIcs.MFCS.2024.9},
  annote =	{Keywords: Quantum algorithms, Quantum walks, Computational Geometry}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2024.68
Unweighted Geometric Hitting Set for Line-Constrained Disks and Related Problems

Authors: Gang Liu and Haitao Wang

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
Given a set P of n points and a set S of m disks in the plane, the disk hitting set problem asks for a smallest subset of P such that every disk of S contains at least one point in the subset. The problem is NP-hard. This paper considers a line-constrained version in which all disks have their centers on a line. We present an O(mlog²n+(n+m)log(n+m)) time algorithm for the problem. This improves the previous result of O(m²log m+(n+m)log(n+m)) time for the weighted case of the problem where every point of P has a weight and the objective is to minimize the total weight of the hitting set. Our algorithm also solves a more general line-separable problem with a single intersection property: The points of P and the disk centers are separated by a line 𝓁 and the boundary of every two disks intersect at most once on the side of 𝓁 containing P.
Cite as

Gang Liu and Haitao Wang. Unweighted Geometric Hitting Set for Line-Constrained Disks and Related Problems. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 68:1-68:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.MFCS.2024.68,
  author =	{Liu, Gang and Wang, Haitao},
  title =	{{Unweighted Geometric Hitting Set for Line-Constrained Disks and Related Problems}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{68:1--68:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.68},
  URN =		{urn:nbn:de:0030-drops-206240},
  doi =		{10.4230/LIPIcs.MFCS.2024.68},
  annote =	{Keywords: hitting set, line-constrained, line-separable, unit disks, half-planes, coverage}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2024.70
On Line-Separable Weighted Unit-Disk Coverage and Related Problems

Authors: Gang Liu and Haitao Wang

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
Given a set P of n points and a set S of n weighted disks in the plane, the disk coverage problem is to compute a subset of disks of smallest total weight such that the union of the disks in the subset covers all points of P. The problem is NP-hard. In this paper, we consider a line-separable unit-disk version of the problem where all disks have the same radius and their centers are separated from the points of P by a line 𝓁. We present an O(n^{3/2}log² n) time algorithm for the problem. This improves the previously best work of O(n²log n) time. Our result leads to an algorithm of O(n^{7/2}log² n) time for the halfplane coverage problem (i.e., using n weighted halfplanes to cover n points), an improvement over the previous O(n⁴log n) time solution. If all halfplanes are lower ones, our algorithm runs in O(n^{3/2}log² n) time, while the previous best algorithm takes O(n²log n) time. Using duality, the hitting set problems under the same settings can be solved with similar time complexities.
Cite as

Gang Liu and Haitao Wang. On Line-Separable Weighted Unit-Disk Coverage and Related Problems. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 70:1-70:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.MFCS.2024.70,
  author =	{Liu, Gang and Wang, Haitao},
  title =	{{On Line-Separable Weighted Unit-Disk Coverage and Related Problems}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{70:1--70:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.70},
  URN =		{urn:nbn:de:0030-drops-206265},
  doi =		{10.4230/LIPIcs.MFCS.2024.70},
  annote =	{Keywords: Line-separable, unit disks, halfplanes, geometric coverage, geometric hitting set}
}
Document
DOI: 10.4230/LIPIcs.SEA.2024.8
Practical Computation of Graph VC-Dimension

Authors: David Coudert, Mónika Csikós, Guillaume Ducoffe, and Laurent Viennot

Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)

Abstract
For any set system ℋ = (V,ℛ), ℛ ⊆ 2^V, a subset S ⊆ V is called shattered if every S' ⊆ S results from the intersection of S with some set in ℛ. The VC-dimension of ℋ is the size of a largest shattered set in V. In this paper, we focus on the problem of computing the VC-dimension of graphs. In particular, given a graph G = (V,E), the VC-dimension of G is defined as the VC-dimension of (V, N), where N contains each subset of V that can be obtained as the closed neighborhood of some vertex v ∈ V in G. Our main contribution is an algorithm for computing the VC-dimension of any graph, whose effectiveness is shown through experiments on various types of practical graphs, including graphs with millions of vertices. A key aspect of its efficiency resides in the fact that practical graphs have small VC-dimension, up to 8 in our experiments. As a side-product, we present several new bounds relating the graph VC-dimension to other classical graph theoretical notions. We also establish the W[1]-hardness of the graph VC-dimension problem by extending a previous result for arbitrary set systems.
Cite as

David Coudert, Mónika Csikós, Guillaume Ducoffe, and Laurent Viennot. Practical Computation of Graph VC-Dimension. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{coudert_et_al:LIPIcs.SEA.2024.8,
  author =	{Coudert, David and Csik\'{o}s, M\'{o}nika and Ducoffe, Guillaume and Viennot, Laurent},
  title =	{{Practical Computation of Graph VC-Dimension}},
  booktitle =	{22nd International Symposium on Experimental Algorithms (SEA 2024)},
  pages =	{8:1--8:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-325-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{301},
  editor =	{Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.8},
  URN =		{urn:nbn:de:0030-drops-203731},
  doi =		{10.4230/LIPIcs.SEA.2024.8},
  annote =	{Keywords: VC-dimension, graph, algorithm}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.27
The Discrepancy of Shortest Paths

Authors: Greg Bodwin, Chengyuan Deng, Jie Gao, Gary Hoppenworth, Jalaj Upadhyay, and Chen Wang

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
The hereditary discrepancy of a set system is a quantitative measure of the pseudorandom properties of the system. Roughly speaking, hereditary discrepancy measures how well one can 2-color the elements of the system so that each set contains approximately the same number of elements of each color. Hereditary discrepancy has numerous applications in computational geometry, communication complexity and derandomization. More recently, the hereditary discrepancy of the set system of shortest paths has found applications in differential privacy [Chen et al. SODA 23]. The contribution of this paper is to improve the upper and lower bounds on the hereditary discrepancy of set systems of unique shortest paths in graphs. In particular, we show that any system of unique shortest paths in an undirected weighted graph has hereditary discrepancy O(n^{1/4}), and we construct lower bound examples demonstrating that this bound is tight up to polylog n factors. Our lower bounds hold even for planar graphs and bipartite graphs, and improve a previous lower bound of Ω(n^{1/6}) obtained by applying the trace bound of Chazelle and Lvov [SoCG'00] to a classical point-line system of Erdős. As applications, we improve the lower bound on the additive error for differentially-private all pairs shortest distances from Ω(n^{1/6}) [Chen et al. SODA 23] to Ω̃(n^{1/4}), and we improve the lower bound on additive error for the differentially-private all sets range queries problem to Ω̃(n^{1/4}), which is tight up to polylog n factors [Deng et al. WADS 23].
Cite as

Greg Bodwin, Chengyuan Deng, Jie Gao, Gary Hoppenworth, Jalaj Upadhyay, and Chen Wang. The Discrepancy of Shortest Paths. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 27:1-27:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bodwin_et_al:LIPIcs.ICALP.2024.27,
  author =	{Bodwin, Greg and Deng, Chengyuan and Gao, Jie and Hoppenworth, Gary and Upadhyay, Jalaj and Wang, Chen},
  title =	{{The Discrepancy of Shortest Paths}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{27:1--27:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.27},
  URN =		{urn:nbn:de:0030-drops-201705},
  doi =		{10.4230/LIPIcs.ICALP.2024.27},
  annote =	{Keywords: Discrepancy, hereditary discrepancy, shortest paths, differential privacy}
}
Document
DOI: 10.4230/LIPIcs.SAND.2023.10
A Connectivity-Sensitive Approach to Consensus Dynamics

Authors: Bernard Chazelle and Kritkorn Karntikoon

Published in: LIPIcs, Volume 257, 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)

Abstract
The paper resolves a long-standing open question in network dynamics. Averaging-based consensus has long been known to exhibit an exponential gap in relaxation time between the connected and disconnected cases, but a satisfactory explanation has remained elusive. We provide one by deriving nearly tight bounds on the s-energy of disconnected systems. This in turn allows us to relate the convergence rate of consensus dynamics to the number of connected components. We apply our results to opinion formation in social networks and provide a theoretical validation of the concept of an Overton window as an attracting manifold of "viable" opinions.
Cite as

Bernard Chazelle and Kritkorn Karntikoon. A Connectivity-Sensitive Approach to Consensus Dynamics. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chazelle_et_al:LIPIcs.SAND.2023.10,
  author =	{Chazelle, Bernard and Karntikoon, Kritkorn},
  title =	{{A Connectivity-Sensitive Approach to Consensus Dynamics}},
  booktitle =	{2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)},
  pages =	{10:1--10:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-275-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{257},
  editor =	{Doty, David and Spirakis, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2023.10},
  URN =		{urn:nbn:de:0030-drops-179464},
  doi =		{10.4230/LIPIcs.SAND.2023.10},
  annote =	{Keywords: s-energy, dynamic networks, relaxation time, multiagent systems}
}
  • Refine by Author
  • 7 Chazelle, Bernard
  • 3 Alt, Helmut
  • 2 Liu, Gang
  • 2 Wang, Haitao
  • 2 Welzl, Emo
  • Show More...

  • Refine by Classification
  • 8 Theory of computation → Computational geometry
  • 3 Theory of computation → Design and analysis of algorithms
  • 3 Theory of computation → Graph algorithms analysis
  • 2 Theory of computation → Streaming, sublinear and near linear time algorithms
  • 1 Mathematics of computing → Combinatoric problems
  • Show More...

  • Refine by Keyword
  • 2 unit disks
  • 1 Boolean functions
  • 1 Computational Geometry
  • 1 Data Structures
  • 1 Discrepancy
  • Show More...

  • Refine by Type
  • 23 document

  • Refine by Publication Year
  • 14 2024
  • 2 2019
  • 1 1991
  • 1 1993
  • 1 1995
  • 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 Imprint Privacy Contact