DROPS

Volume

LIPIcs, Volume 77

33rd International Symposium on Computational Geometry (SoCG 2017)

SoCG 2017, July 4-7, 2017, Brisbane, Australia

Editors: Boris Aronov and Matthew J. Katz

Document

DOI: 10.4230/LIPIcs.SoCG.2026.4

Dynamic Nearest-Neighbor Searching Under General Metrics in ℝ³ and Its Applications

Authors: Pankaj K. Agarwal, Matthew J. Katz, and Micha Sharir

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract

Let K be a compact, centrally-symmetric, strictly-convex region in ℝ³, which is a semi-algebraic set of constant complexity, i.e. the unit ball of a corresponding metric, denoted as ‖⋅‖_K. Let 𝒦 be a set of n homothetic copies of K. This paper contains two main sets of results: (i) For a storage parameter s ∈ [n,n³], 𝒦 can be preprocessed in O^*(s) expected time into a data structure of size O^*(s), so that for a query homothet K₀ of K, an intersection-detection query (determine whether K₀ intersects any member of 𝒦, and if so, report such a member) or a nearest-neighbor query (return the member of 𝒦 whose ‖⋅‖_K-distance from K₀ is smallest) can be answered in O^*(n/s^{1/3}) time; all k homothets of 𝒦 intersecting K₀ can be reported in additional O(k) time. In addition, the data structure supports insertions/deletions in O^*(s/n) amortized expected time per operation. Here the O^*(⋅) notation hides factors of the form n^ε, where ε > 0 is an arbitrarily small constant, and the constant of proportionality depends on ε. (ii) Let 𝒢(𝒦) denote the intersection graph of 𝒦. Using the above data structure, breadth-first or depth-first search on 𝒢(𝒦) can be performed in O^*(n^{3/2}) expected time. Combining this result with the so-called shrink-and-bifurcate technique, the reverse-shortest-path problem in a suitably defined proximity graph of 𝒦 can be solved in O^*(n^{62/39}) expected time. Dijkstra’s shortest-path algorithm, as well as Prim’s MST algorithm, on a ‖⋅‖_K-proximity graph on n points in ℝ³, with edges weighted by ‖⋅‖_K, can also be performed in O^*(n^{3/2}) time.

Cite as

Pankaj K. Agarwal, Matthew J. Katz, and Micha Sharir. Dynamic Nearest-Neighbor Searching Under General Metrics in ℝ³ and Its Applications. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.SoCG.2026.4,
  author =	{Agarwal, Pankaj K. and Katz, Matthew J. and Sharir, Micha},
  title =	{{Dynamic Nearest-Neighbor Searching Under General Metrics in \mathbb{R}³ and Its Applications}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{4:1--4:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.4},
  URN =		{urn:nbn:de:0030-drops-258102},
  doi =		{10.4230/LIPIcs.SoCG.2026.4},
  annote =	{Keywords: Homothets, Minkowski metric, Shallow cuttings, Nearest-neighbor searching, Intersection and proximity graphs, Reverse-shortest-path problem}
}

Document

DOI: 10.4230/LIPIcs.STACS.2026.81

Counting Unit Circular Arc Intersections

Authors: Haitao Wang

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract

Given a set of n circular arcs of the same radius in the plane, we consider the problem of computing the number of intersections among the arcs. The problem was studied before and the previously best algorithm solves the problem in O(n^{4/3+ε}) time [Agarwal, Pellegrini, and Sharir, SIAM J. Comput., 1993], for any constant ε > 0. No progress has been made on the problem for more than 30 years. We present a new algorithm of O(n^{4/3}log^{16/3} n) time and improve it to O(n^{1+ε}+K^{1/3}n^{2/3}((n²)/(n+K))^{ε}log^{16/3}n) time for small K, where K is the number of intersections of all arcs.

Cite as

Haitao Wang. Counting Unit Circular Arc Intersections. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 81:1-81:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{wang:LIPIcs.STACS.2026.81,
  author =	{Wang, Haitao},
  title =	{{Counting Unit Circular Arc Intersections}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{81:1--81:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.81},
  URN =		{urn:nbn:de:0030-drops-255707},
  doi =		{10.4230/LIPIcs.STACS.2026.81},
  annote =	{Keywords: circular arc intersections, unit circles, arrangements, cuttings, segment intersections}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.19

Limitations to Computing Quadratic Functions on Reed-Solomon Encoded Data

Authors: Keller Blackwell and Mary Wootters

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

We study the problem of low-bandwidth non-linear computation on Reed-Solomon encoded data. Given an [n,k] Reed-Solomon encoding of a message vector 𝐟 ∈ 𝔽_q^k, and a polynomial g ∈ 𝔽_q[X₁, X₂, …, X_k], a user wishing to evaluate g(𝐟) is given local query access to each codeword symbol. The query response is allowed to be the output of an arbitrary function evaluated locally on the codeword symbol, and the user’s aim is to minimize the total information downloaded in order to compute g(𝐟). This problem has been studied before for linear functions g; in this work we initiate the study of non-linear functions by starting with quadratic monomials. For q = p^e and distinct i,j ∈ [k], we show that any scheme evaluating the quadratic monomial g_{i,j} := X_i X_j must download at least 2 log₂(q-1) - 3 bits of information when p is an odd prime, and at least 2log₂(q-2) -4 bits when p = 2. When k = 2, our result shows that one cannot do significantly better than the naive bound of k log₂(q) bits, which is enough to recover all of 𝐟. This contrasts sharply with prior work for low-bandwidth evaluation of linear functions g(𝐟) over Reed-Solomon encoded data, for which it is possible to substantially improve upon this bound [Venkatesan Guruswami and Mary Wootters, 2016; Tamo et al., 2018; Shutty and Wootters, 2021; Kiah et al., 2024; Con and Tamo, 2022]. Some proofs have been omitted from this extended abstract; the full version can be found at [Keller Blackwell and Mary Wootters, 2025].

Cite as

Keller Blackwell and Mary Wootters. Limitations to Computing Quadratic Functions on Reed-Solomon Encoded Data. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 19:1-19:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{blackwell_et_al:LIPIcs.ITCS.2026.19,
  author =	{Blackwell, Keller and Wootters, Mary},
  title =	{{Limitations to Computing Quadratic Functions on Reed-Solomon Encoded Data}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{19:1--19:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.19},
  URN =		{urn:nbn:de:0030-drops-253064},
  doi =		{10.4230/LIPIcs.ITCS.2026.19},
  annote =	{Keywords: Distributed computation, Reed-Solomon codes}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.65

Characterizing Off-Chain Influence Proof Transaction Fee Mechanisms

Authors: Aadityan Ganesh, Clayton Thomas, and S. Matthew Weinberg

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

Roughgarden [Roughgarden, 2020] initiates the study of Transaction Fee Mechanisms (TFMs), and posits that the on-chain game of a "good" TFM should be on-chain simple (OnC-S), i.e., incentive compatible for both the users and the miner. Recent work of Ganesh, Thomas an Weinberg [Ganesh et al., 2024] posit that they should additionally be Off-Chain Influence-Proof (OffC-IP), which means that the miner cannot achieve any additional revenue by separately conducting an off-chain auction to determine on-chain inclusion. They observe that a cryptographic second-price auction satisfies both properties, but leave open the question of whether other mechanisms (such as those not dependent on cryptography) satisfy these properties. In this paper, we characterize OffC-IP TFMs: They are those satisfying a burn identity relating the burn rule to the allocation rule. In particular, we show that auction is OffC-IP if and only if its (induced direct-revelation) allocation rule X̄(⋅) and burn rule B̅(⋅) (both of which take as input users' values v₁, … , v_n) are truthful when viewing (X̄(⋅), B̅(⋅)) as the allocation and pricing rule of a multi-item auction for a single additive buyer with values (φ(v₁),…, φ(v_n)) equal to the users' virtual values. Building on this burn identity, we characterize OffC-IP and OnC-S TFMs that are deterministic and do not use cryptography: They are posted-price mechanisms with specially-tuned burns. As a corollary, we show that such TFMs can only exist with infinite supply and prior-dependence. However, we show that for randomized TFMs, there are additional OnC-S and OffC-IP auctions that do not use cryptography (even when there is {finite} supply, under prior-dependence with a bounded prior distribution). Holistically, our results show that while OffC-IP is a fairly stringent requirement, families of OffC-IP mechanisms can be found for a variety of settings.

Cite as

Aadityan Ganesh, Clayton Thomas, and S. Matthew Weinberg. Characterizing Off-Chain Influence Proof Transaction Fee Mechanisms. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 65:1-65:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ganesh_et_al:LIPIcs.ITCS.2026.65,
  author =	{Ganesh, Aadityan and Thomas, Clayton and Weinberg, S. Matthew},
  title =	{{Characterizing Off-Chain Influence Proof Transaction Fee Mechanisms}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{65:1--65:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.65},
  URN =		{urn:nbn:de:0030-drops-253527},
  doi =		{10.4230/LIPIcs.ITCS.2026.65},
  annote =	{Keywords: Transaction Fee Mechanism Design, Off-Chain Influence Proofness, Blockchain, Decentralized Finance, Simple Auctions}
}

Document

Invited Paper

DOI: 10.4230/OASIcs.RW.2024/2025.6

Explaining Reasoning Results for Description Logic Ontologies (Invited Paper)

Authors: Patrick Koopmann

Published in: OASIcs, Volume 138, Joint Proceedings of the 20th and 21st Reasoning Web Summer Schools (RW 2024 & RW 2025)

Abstract

The Web Ontology Language (OWL), grounded in description logics, enables reasoning systems to infer implicit knowledge in a transparent manner. However, the expressivity of description logics and the complexity of large ontologies often results in reasoning outcomes that are hard to understand without additional tool support. Explanations of these outcomes are essential for users to understand ontology content, communicate its structure and behavior effectively, and debug undesired or missing inferences. This chapter provides an overview of the central explanation techniques that have been developed for explaining reasoning with description logic ontologies. Here, we consider both explanations for positive entailments (explaining why something can be deduced), as well as negative entailments (why something cannot be deduced). More specifically, we discuss justifications, proofs and interpolation as a means to explain positive entailments, and abduction for explaining negative entailments, where we also have a closer look at practical algorithms as well as practical and theoretical challenges.

Cite as

Patrick Koopmann. Explaining Reasoning Results for Description Logic Ontologies (Invited Paper). In Joint Proceedings of the 20th and 21st Reasoning Web Summer Schools (RW 2024 & RW 2025). Open Access Series in Informatics (OASIcs), Volume 138, pp. 6:1-6:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{koopmann:OASIcs.RW.2024/2025.6,
  author =	{Koopmann, Patrick},
  title =	{{Explaining Reasoning Results for Description Logic Ontologies}},
  booktitle =	{Joint Proceedings of the 20th and 21st Reasoning Web Summer Schools (RW 2024 \& RW 2025)},
  pages =	{6:1--6:29},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-405-5},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{138},
  editor =	{Artale, Alessandro and Bienvenu, Meghyn and Garc{\'\i}a, Yazm{\'\i}n Ib\'{a}\~{n}ez and Murlak, Filip},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.RW.2024/2025.6},
  URN =		{urn:nbn:de:0030-drops-250514},
  doi =		{10.4230/OASIcs.RW.2024/2025.6},
  annote =	{Keywords: Explanations, Justifications, Proofs, Craig Interpolation, Contrastive Explanations}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2025.6

A Dimension-Reducing Fréchet Simplification Oracle

Authors: Boris Aronov, Tsuri Farhana, Matthew J. Katz, and Indu Ramesh

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract

Let P be a polygonal curve with n vertices in the plane. We construct a data structure of size O(n log n) suited for simplification queries of the following kind. Given a query line 𝓁 and an integer k ≥ 1, find a curve Q on 𝓁 with at most k vertices that minimizes the discrete Fréchet distance to P, among all such curves. Using our data structure, a query can be handled in O(k² log³ n + k log⁴n) time. More generally, a geometric tree T on n vertices in the plane can be preprocessed into a near-linear-size structure so that, given a pair u, v of its vertices, a line 𝓁, and an integer k ≥ 1, one can find a curve Q on 𝓁 with at most k vertices that minimizes the discrete Fréchet distance to the path from u to v in T, in time O(k² polylog n). For the general dimension-reduction problem, where P is a curve in ℝ^d (d ≥ 3), 0 < ε₀ < 1 is a real parameter, and a query specifies a g-flat h (1 ≤ g ≤ d-1) and an integer k ≥ 1, we construct a data structure of size O(nlog n + f(ε₀) n), where f(ε₀) = (1+1/ε₀)^{(d-1)/2}, that allows us to find a curve Q on h with at most k vertices, whose discrete Fréchet distance to P is at most 1+ε₀ times the distance of Q^* to P, where Q^* is such a curve that minimizes the distance to P. The query handling time is O(f(ε₀) k² log² n).

Cite as

Boris Aronov, Tsuri Farhana, Matthew J. Katz, and Indu Ramesh. A Dimension-Reducing Fréchet Simplification Oracle. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 6:1-6:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{aronov_et_al:LIPIcs.ISAAC.2025.6,
  author =	{Aronov, Boris and Farhana, Tsuri and Katz, Matthew J. and Ramesh, Indu},
  title =	{{A Dimension-Reducing Fr\'{e}chet Simplification Oracle}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{6:1--6:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.6},
  URN =		{urn:nbn:de:0030-drops-249149},
  doi =		{10.4230/LIPIcs.ISAAC.2025.6},
  annote =	{Keywords: Computational geometry, discrete Fr\'{e}chet distance, curve simplification oracle, restricted minimum enclosing disk queries}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2025.46

Realizing Metric Spaces with Convex Obstacles

Authors: Sándor Kisfaludi-Bak and Leonidas Theocharous

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract

The presence of obstacles has a significant impact on distance computation, motion-planning, and visibility. These problems have been studied extensively in the planar setting, while our understanding of these problems in 3- and higher-dimensional spaces is still rudimentary. In this paper, we study the impact of different types of obstacles on the induced geodesic metric in 3-dimensional Euclidean space. We say that a finite metric space (X, dist_X) is approximately realizable by a collection 𝒯 of obstacles in ℝ³ if for any ε > 0 it can be embedded into (ℝ³⧵⋃_{T∈𝒯} T, dist_𝒯) with worst-case multiplicative distortion 1+ε, where dist_𝒯 denotes the geodesic distance in the free space induced by 𝒯. We focus on three key geometric properties of obstacles -convexity, disjointness, and fatness- and examine how dropping each one of them affects the existence of such embeddings. Our main result concerns dropping the fatness property: we demonstrate that any finite metric space is realizable with 1+ε worst-case multiplicative distortion using a collection of convex and pairwise disjoint obstacles in ℝ³, even if the obstacles are congruent and equilateral triangles. Based on the same construction, we can also show that if we require fatness but drop any of the other two properties instead, then we can still approximately realize any finite metric space. Our results have important implications on the approximability of tsp with obstacles, a natural variant of tsp introduced recently by Alkema et al. (ESA 2022). Specifically, we use the recent results of Banerjee et al. on tsp in doubling spaces (FOCS 2024) and of Chew et al. on distances among obstacles (Inf. Process. Lett. 2002) to show that tsp with obstacles admits a PTAS if the obstacles are convex, fat, and pairwise disjoint. If any of these three properties is dropped, then our results, combined with the APX-hardness of Metric tsp, demonstrate that tsp with obstacles is APX-hard.

Cite as

Sándor Kisfaludi-Bak and Leonidas Theocharous. Realizing Metric Spaces with Convex Obstacles. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 46:1-46:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kisfaludibak_et_al:LIPIcs.ISAAC.2025.46,
  author =	{Kisfaludi-Bak, S\'{a}ndor and Theocharous, Leonidas},
  title =	{{Realizing Metric Spaces with Convex Obstacles}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{46:1--46:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.46},
  URN =		{urn:nbn:de:0030-drops-249545},
  doi =		{10.4230/LIPIcs.ISAAC.2025.46},
  annote =	{Keywords: traveling salesman, geodesic distance}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2025.45

BFS and Reverse Shortest Paths for Ball Intersection Graphs in Three and Higher Dimensions

Authors: Matthew J. Katz, Rachel Saban, and Micha Sharir

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract

Let ℬ be a collection of n arbitrary balls in ℝ³, and let G₀(ℬ) be their intersection graph. We provide an algorithm for performing BFS on G₀(ℬ), which runs in O^*(n^{4/3}) time, where the O^*(⋅) notation hides subpolynomial factors. For r ≥ 0, let G_r(ℬ) be the intersection graph of the set ℬ_r = {B+r ∣ B ∈ ℬ}, where B+r is the ball concentric with B whose radius is larger by r than the radius of B. We provide an efficient algorithm for the reverse shortest path (RSP) problem, where we are given two designated balls B_s, B_t of ℬ and a parameter 0 < λ < n, and seek the smallest value r^* for which G_{r^*}(ℬ) contains a path from B_s to B_t of at most λ edges. For the special case of congruent balls (equivalently, for points in ℝ³), the algorithm runs in O^*(n^{29/21}) ≈ O^*(n^{1.381}) time. For the general case, the algorithm runs in O^*(n^{56/39}) ≈ O^*(n^{1.436}) time. We also extend the technique to handle other measures of expansion and higher dimensions.

Cite as

Matthew J. Katz, Rachel Saban, and Micha Sharir. BFS and Reverse Shortest Paths for Ball Intersection Graphs in Three and Higher Dimensions. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 45:1-45:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{katz_et_al:LIPIcs.ISAAC.2025.45,
  author =	{Katz, Matthew J. and Saban, Rachel and Sharir, Micha},
  title =	{{BFS and Reverse Shortest Paths for Ball Intersection Graphs in Three and Higher Dimensions}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{45:1--45:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.45},
  URN =		{urn:nbn:de:0030-drops-249535},
  doi =		{10.4230/LIPIcs.ISAAC.2025.45},
  annote =	{Keywords: Computational geometry, reverse shortest paths, breadth-first search, shrink-and-bifurcate, intersection graphs}
}

Document

DOI: 10.4230/LIPIcs.AFT.2025.1

Cache Timing Leakages in Zero-Knowledge Protocols

Authors: Shibam Mukherjee, Christian Rechberger, and Markus Schofnegger

Published in: LIPIcs, Volume 354, 7th Conference on Advances in Financial Technologies (AFT 2025)

Abstract

The area of modern zero-knowledge proof systems has seen a significant rise in popularity over the last couple of years, with new techniques and optimized constructions emerging on a regular basis. As the field matures, the aspect of implementation attacks becomes more relevant, however side-channel attacks on zero-knowledge proof systems have seen surprisingly little treatment so far. In this paper, we give an overview of potential attack vectors and show that some of the underlying finite field libraries, and implementations of heavily used components like hash functions using them, are vulnerable w.r.t. cache attacks on CPUs. On the positive side, we demonstrate that the computational overhead to protect against these attacks is relatively small.

Cite as

Shibam Mukherjee, Christian Rechberger, and Markus Schofnegger. Cache Timing Leakages in Zero-Knowledge Protocols. In 7th Conference on Advances in Financial Technologies (AFT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 354, pp. 1:1-1:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{mukherjee_et_al:LIPIcs.AFT.2025.1,
  author =	{Mukherjee, Shibam and Rechberger, Christian and Schofnegger, Markus},
  title =	{{Cache Timing Leakages in Zero-Knowledge Protocols}},
  booktitle =	{7th Conference on Advances in Financial Technologies (AFT 2025)},
  pages =	{1:1--1:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-400-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{354},
  editor =	{Avarikioti, Zeta and Christin, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2025.1},
  URN =		{urn:nbn:de:0030-drops-247201},
  doi =		{10.4230/LIPIcs.AFT.2025.1},
  annote =	{Keywords: zero-knowledge, protocol, cache timing, side-channel, leakage}
}

Document

DOI: 10.4230/LIPIcs.AFT.2025.16

Nakamoto Consensus from Multiple Resources

Authors: Mirza Ahad Baig, Christoph U. Günther, and Krzysztof Pietrzak

Published in: LIPIcs, Volume 354, 7th Conference on Advances in Financial Technologies (AFT 2025)

Abstract

The blocks in the Bitcoin blockchain "record" the amount of work W that went into creating them through proofs of work. When honest parties control a majority of the work, consensus is achieved by picking the chain with the highest recorded weight. Resources other than work have been considered to secure such longest-chain blockchains. In Chia, blocks record the amount of disk-space S (via a proof of space) and sequential computational steps V (through a VDF). In this paper, we ask what weight functions Γ(S,V,W) (that assign a weight to a block as a function of the recorded space, speed, and work) are secure in the sense that whenever the weight of the resources controlled by honest parties is larger than the weight of adversarial parties, the blockchain is secure against private double-spending attacks. We completely classify such functions in an idealized "continuous" model: Γ(S,V,W) is secure against private double-spending attacks if and only if it is homogeneous of degree one in the "timed" resources V and W, i.e., αΓ(S,V,W) = Γ(S,α V, α W). This includes the Bitcoin rule Γ(S,V,W) = W and the Chia rule Γ(S,V,W) = S ⋅ V. In a more realistic model where blocks are created at discrete time-points, one additionally needs some mild assumptions on the dependency on S (basically, the weight should not grow too much if S is slightly increased, say linear as in Chia). Our classification is more general and allows various instantiations of the same resource. It provides a powerful tool for designing new longest-chain blockchains. E.g., consider combining different PoWs to counter centralization, say the Bitcoin PoW W₁ and a memory-hard PoW W₂. Previous work suggested to use W₁+W₂ as weight. Our results show that using e.g., √{W₁}⋅ √{W₂} or min{W₁,W₂} are also secure, and we argue that in practice these are much better choices.

Cite as

Mirza Ahad Baig, Christoph U. Günther, and Krzysztof Pietrzak. Nakamoto Consensus from Multiple Resources. In 7th Conference on Advances in Financial Technologies (AFT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 354, pp. 16:1-16:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{baig_et_al:LIPIcs.AFT.2025.16,
  author =	{Baig, Mirza Ahad and G\"{u}nther, Christoph U. and Pietrzak, Krzysztof},
  title =	{{Nakamoto Consensus from Multiple Resources}},
  booktitle =	{7th Conference on Advances in Financial Technologies (AFT 2025)},
  pages =	{16:1--16:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-400-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{354},
  editor =	{Avarikioti, Zeta and Christin, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2025.16},
  URN =		{urn:nbn:de:0030-drops-247353},
  doi =		{10.4230/LIPIcs.AFT.2025.16},
  annote =	{Keywords: Nakamoto Consensus, Heaviest-chain Rule, Resource Theory}
}

Document

DOI: 10.4230/LIPIcs.ESA.2025.31

An Optimal Algorithm for Shortest Paths in Unweighted Disk Graphs

Authors: Bruce W. Brewer and Haitao Wang

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract

Given in the plane a set S of n points and a set of disks centered at these points, the disk graph G(S) induced by these disks has vertex set S and an edge between two vertices if their disks intersect. Note that the disks may have different radii. We consider the problem of computing shortest paths from a source point s ∈ S to all vertices in G(S) where the length of a path in G(S) is defined as the number of edges in the path. The previously best algorithm solves the problem in O(nlog² n) time. A lower bound of Ω(nlog n) is also known for this problem under the algebraic decision tree model. In this paper, we present an O(nlog n) time algorithm, which matches the lower bound and thus is optimal. Another virtue of our algorithm is that it is quite simple.

Cite as

Bruce W. Brewer and Haitao Wang. An Optimal Algorithm for Shortest Paths in Unweighted Disk Graphs. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 31:1-31:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{brewer_et_al:LIPIcs.ESA.2025.31,
  author =	{Brewer, Bruce W. and Wang, Haitao},
  title =	{{An Optimal Algorithm for Shortest Paths in Unweighted Disk Graphs}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{31:1--31:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian 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.2025.31},
  URN =		{urn:nbn:de:0030-drops-244997},
  doi =		{10.4230/LIPIcs.ESA.2025.31},
  annote =	{Keywords: disk graphs, weighted Voronoi diagrams, shortest paths}
}

Document

DOI: 10.4230/LIPIcs.ESA.2025.67

Compact Representation of Semilinear and Terrain-Like Graphs

Authors: Jean Cardinal and Yelena Yuditsky

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract

We consider the existence and construction of biclique covers of graphs, consisting of coverings of their edge sets by complete bipartite graphs. The size of such a cover is the sum of the sizes of the bicliques. Small-size biclique covers of graphs are ubiquitous in computational geometry, and have been shown to be useful compact representations of graphs. We give a brief survey of classical and recent results on biclique covers and their applications, and give new families of graphs having biclique covers of near-linear size. In particular, we show that semilinear graphs, whose edges are defined by linear relations in bounded dimensional space, always have biclique covers of size O(npolylog n). This generalizes many previously known results on special classes of graphs including interval graphs, permutation graphs, and graphs of bounded boxicity, but also new classes such as intersection graphs of L-shapes in the plane. It also directly implies the bounds for Zarankiewicz’s problem derived by Basit, Chernikov, Starchenko, Tao, and Tran (Forum Math. Sigma, 2021). We also consider capped graphs, also known as terrain-like graphs, defined as ordered graphs forbidding a certain ordered pattern on four vertices. Terrain-like graphs contain the induced subgraphs of terrain visibility graphs. We give an elementary proof that these graphs admit biclique partitions of size O(nlog³ n). This provides a simple combinatorial analogue of a classical result from Agarwal, Alon, Aronov, and Suri on polygon visibility graphs (Discrete Comput. Geom. 1994). Finally, we prove that there exists families of unit disk graphs on n vertices that do not admit biclique coverings of size o(n^{4/3}), showing that we are unlikely to improve on Szemerédi-Trotter type incidence bounds for higher-degree semialgebraic graphs.

Cite as

Jean Cardinal and Yelena Yuditsky. Compact Representation of Semilinear and Terrain-Like Graphs. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 67:1-67:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cardinal_et_al:LIPIcs.ESA.2025.67,
  author =	{Cardinal, Jean and Yuditsky, Yelena},
  title =	{{Compact Representation of Semilinear and Terrain-Like Graphs}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{67:1--67:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian 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.2025.67},
  URN =		{urn:nbn:de:0030-drops-245359},
  doi =		{10.4230/LIPIcs.ESA.2025.67},
  annote =	{Keywords: Biclique covers, intersection graphs, visibility graphs, Zarankiewicz’s problem}
}

Document

DOI: 10.4230/LIPIcs.ESA.2025.44

Near-Optimal Vertex Fault-Tolerant Labels for Steiner Connectivity

Authors: Koustav Bhanja and Asaf Petruschka

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract

We present a compact labeling scheme for determining whether a designated set of terminals in a graph remains connected after any f (or less) vertex failures occur. An f-FT Steiner connectivity labeling scheme for an n-vertex graph G = (V,E) with terminal set U ⊆ V provides labels to the vertices of G, such that given only the labels of any subset F ⊆ V with |F| ≤ f, one can determine if U remains connected in G-F. The main complexity measure is the maximum label length. The special case U = V of global connectivity has been recently studied by Jiang, Parter, and Petruschka [Yonggang Jiang et al., 2025], who provided labels of n^{1-1/f} ⋅ poly(f,log n) bits. This is near-optimal (up to poly(f,log n) factors) by a lower bound of Long, Pettie and Saranurak [Yaowei Long et al., 2025]. Our scheme achieves labels of |U|^{1-1/f} ⋅ poly(f, log n) for general U ⊆ V, which is near-optimal for any given size |U| of the terminal set. To handle terminal sets, our approach differs from [Yonggang Jiang et al., 2025]. We use a well-structured Steiner tree for U produced by a decomposition theorem of Duan and Pettie [Ran Duan and Seth Pettie, 2020], and bypass the need for Nagamochi-Ibaraki sparsification [Hiroshi Nagamochi and Toshihide Ibaraki, 1992].

Cite as

Koustav Bhanja and Asaf Petruschka. Near-Optimal Vertex Fault-Tolerant Labels for Steiner Connectivity. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 44:1-44:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bhanja_et_al:LIPIcs.ESA.2025.44,
  author =	{Bhanja, Koustav and Petruschka, Asaf},
  title =	{{Near-Optimal Vertex Fault-Tolerant Labels for Steiner Connectivity}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{44:1--44:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian 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.2025.44},
  URN =		{urn:nbn:de:0030-drops-245123},
  doi =		{10.4230/LIPIcs.ESA.2025.44},
  annote =	{Keywords: Fault Tolerance, Labeling Schemes, Steiner Connectivity}
}

Document

DOI: 10.4230/LIPIcs.ESA.2025.42

(Multivariate) k-SUM as Barrier to Succinct Computation

Authors: Geri Gokaj, Marvin Künnemann, Sabine Storandt, and Carina Truschel

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract

How does the time complexity of a problem change when the input is given succinctly rather than explicitly? We study this question for several geometric problems defined on a set X of N points in ℤ^d. As succinct representation, we choose a sumset (or Minkowski sum) representation: Instead of receiving X explicitly, we are given sets A,B of n points that define X as A+B = {a+b∣ a ∈ A,b ∈ B}. We investigate the fine-grained complexity of this succinct version for several Õ(N)-time computable geometric primitives. Remarkably, we can tie their complexity tightly to the complexity of corresponding k-SUM problems. Specifically, we introduce as All-ints 3-SUM(n,n,k) the following multivariate, multi-output variant of 3-SUM: given sets A,B of size n and set C of size k, determine for all c ∈ C whether there are a ∈ A and b ∈ B with a+b = c. We obtain the following results: 1) Succinct closest L_∞-pair requires time N^{1-o(1)} under the 3-SUM hypothesis, while succinct furthest L_∞-pair can be solved in time Õ(n). 2) Succinct bichromatic closest L_∞-Pair requires time N^{1-o(1)} iff the 4-SUM hypothesis holds. 3) The following problems are fine-grained equivalent to All-ints 3-SUM(n,n,k): succinct skyline computation in 2D with output size k and succinct batched orthogonal range search with k given ranges. This establishes conditionally tight Õ(min{nk, N})-time algorithms for these problems. We obtain further connections with All-ints 3-SUM(n,n,k) for succinctly computing independent sets in unit interval graphs. Thus, (Multivariate) k-SUM problems precisely capture the barrier for enabling sumset-succinct computation for various geometric primitives.

Cite as

Geri Gokaj, Marvin Künnemann, Sabine Storandt, and Carina Truschel. (Multivariate) k-SUM as Barrier to Succinct Computation. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 42:1-42:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gokaj_et_al:LIPIcs.ESA.2025.42,
  author =	{Gokaj, Geri and K\"{u}nnemann, Marvin and Storandt, Sabine and Truschel, Carina},
  title =	{{(Multivariate) k-SUM as Barrier to Succinct Computation}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{42:1--42:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian 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.2025.42},
  URN =		{urn:nbn:de:0030-drops-245101},
  doi =		{10.4230/LIPIcs.ESA.2025.42},
  annote =	{Keywords: Fine-grained complexity theory, sumsets, additive combinatorics, succinct inputs, computational geometry}
}

136 Search Results for "Katz, Matthew J."

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Thanks for your feedback!

Could not send message