32 Search Results for "Fox, Kyle"

Document
DOI: 10.4230/LIPIcs.SWAT.2026.16
Online Hitting Set for Axis-Aligned Squares

Authors: Minati De, Satyam Singh, and Csaba D. Tóth

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
Given a set P of n points in the plane and a sequence of axis-aligned squares that arrive in an online fashion, the online hitting set problem consists of maintaining, by adding new points from P if necessary, a hitting set H ⊆ P, which contains at least one point in every input square that has already arrived. We present an O(log n)-competitive deterministic algorithm for this problem. The competitive ratio is the best possible, apart from constant factors. In fact, this is the first O(log n)-competitive algorithm for the online hitting set problem that works for geometric objects of arbitrary sizes (i.e., unbounded scaling factors) in the plane. We further generalize this result to positive homothets of a polygon with k ≥ 3 vertices in the plane and provide an O(k²log n)-competitive algorithm.
Cite as

Minati De, Satyam Singh, and Csaba D. Tóth. Online Hitting Set for Axis-Aligned Squares. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{de_et_al:LIPIcs.SWAT.2026.16,
  author =	{De, Minati and Singh, Satyam and T\'{o}th, Csaba D.},
  title =	{{Online Hitting Set for Axis-Aligned Squares}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{16:1--16:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.16},
  URN =		{urn:nbn:de:0030-drops-260528},
  doi =		{10.4230/LIPIcs.SWAT.2026.16},
  annote =	{Keywords: axis-aligned squares, hitting set, homothets of a polygon, online algorithm}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.3
Lower Bounding the Gromov-Hausdorff Distance in Metric Graphs

Authors: Henry Adams, Sushovan Majhi, Fedor Manin, Žiga Virk, and Nicolò Zava

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

Abstract
Let G be a finite, connected metric graph and let X be a subset of G. If X is sufficiently dense in G, we show that the Gromov-Hausdorff distance matches the Hausdorff distance, namely d_GH(G,X) = d_H(G,X). When the metric graph is the circle G = S¹ with circumference 2π, a recent study established the equality d_GH(S¹,X) = d_H(S¹,X) whenever d_GH(S¹,X) < π/6. Our results relax this hypothesis to d_GH(S¹,X) < π/3, and furthermore, we show that the constant π/3 is the best possible. We lower bound the Gromov-Hausdorff distance d_GH(G,X) by the Hausdorff distance d_H(G,X) via a simple topological obstruction: the existence of a possibly discontinuous function f: G → X with too small distortion contradicts the connectedness of G.
Cite as

Henry Adams, Sushovan Majhi, Fedor Manin, Žiga Virk, and Nicolò Zava. Lower Bounding the Gromov-Hausdorff Distance in Metric Graphs. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{adams_et_al:LIPIcs.SoCG.2026.3,
  author =	{Adams, Henry and Majhi, Sushovan and Manin, Fedor and Virk, \v{Z}iga and Zava, Nicol\`{o}},
  title =	{{Lower Bounding the Gromov-Hausdorff Distance in Metric Graphs}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{3:1--3:16},
  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.3},
  URN =		{urn:nbn:de:0030-drops-258099},
  doi =		{10.4230/LIPIcs.SoCG.2026.3},
  annote =	{Keywords: Gromov-Hausdorff distance, distortion, connectedness, Borsuk-Ulam theorem}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.35
On Computing the (Exact) Fréchet Distance with a Frog

Authors: Jacobus Conradi, Ivor van der Hoog, and Eva Rotenberg

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

Abstract
The continuous Fréchet distance 𝒟_F(π,σ) between two polygonal curves π and σ is classically computed by exploring the free space diagram over the two curves. [SoCG'25] recently proposed a radically different approach: they approximate 𝒟_F(π,σ) by computing paths in a discrete graph that models a joint traversal of π and σ, recursively bisecting edges until the discrete distance converges to the continuous one. They implement their "frog-based" technique, and claim that it yields substantial practical speedups compared to the state-of-the-art implementations. In this paper, we revisit this technique. We observe that, in its current form, it has three limitations: (i) it does not use exact arithmetic, (ii) its recursive bisection introduces the required monotonicity events to realise the Fréchet distance only in the limit, and (iii) it applies a heuristic simplification technique which is overly conservative. Motivated by theoretical interest, we develop new techniques that guarantee exactness, polynomial-time convergence and near-optimal lossless simplifications. We provide an open-source C++ implementation of our variant. Our primary contribution is an extensive empirical evaluation on a broad, publically available, suite of real-world and synthetic data sets. Among the frog-based variants, exact computation indeed introduces overhead and increases median runtime. Yet, our new approach is often faster in the worst case, worst ten percent, or even the average runtime due to its worst-case convergence guarantees. More surprisingly, the implementation of [SoCG'19] dominates all frog-based implementations in performance - this finding contrasts previously published claims. These results provide a much-needed nuanced perspective on the capabilities and limitations of frog-based techniques: we showcase its theoretical appeal, but highlight its limited practical feasibility.
Cite as

Jacobus Conradi, Ivor van der Hoog, and Eva Rotenberg. On Computing the (Exact) Fréchet Distance with a Frog. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 35:1-35:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{conradi_et_al:LIPIcs.SoCG.2026.35,
  author =	{Conradi, Jacobus and van der Hoog, Ivor and Rotenberg, Eva},
  title =	{{On Computing the (Exact) Fr\'{e}chet Distance with a Frog}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{35:1--35:20},
  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.35},
  URN =		{urn:nbn:de:0030-drops-258414},
  doi =		{10.4230/LIPIcs.SoCG.2026.35},
  annote =	{Keywords: Algorithms engineering, Fr\'{e}chet distance}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.79
D-GRIL: End-To-End Topological Learning with 2-Parameter Persistence

Authors: Soham Mukherjee, Shreyas N. Samaga, Cheng Xin, Steve Oudot, and Tamal K. Dey

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

Abstract
End-to-end topological learning using 1-parameter persistence is well-known. We show that the framework can be enhanced using 2-parameter persistence by adopting a recently introduced 2-parameter persistence based vectorization technique called Gril. We establish a theory for gradient descent on Gril producing D-Gril. We show that D-Gril can be used to learn a bifiltration function on benchmark graph datasets. Further, we exhibit that this framework can be applied in the context of bio-activity prediction in drug discovery.
Cite as

Soham Mukherjee, Shreyas N. Samaga, Cheng Xin, Steve Oudot, and Tamal K. Dey. D-GRIL: End-To-End Topological Learning with 2-Parameter Persistence. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 79:1-79:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{mukherjee_et_al:LIPIcs.SoCG.2026.79,
  author =	{Mukherjee, Soham and Samaga, Shreyas N. and Xin, Cheng and Oudot, Steve and Dey, Tamal K.},
  title =	{{D-GRIL: End-To-End Topological Learning with 2-Parameter Persistence}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{79:1--79:17},
  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.79},
  URN =		{urn:nbn:de:0030-drops-258865},
  doi =		{10.4230/LIPIcs.SoCG.2026.79},
  annote =	{Keywords: Topological Data Analysis, Persistent Homology, Multiparameter Persistence, Graph Learning, Graph Neural Networks}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.87
Robustness of Persistent Topological Features and Minimum Homological Cuts

Authors: Pepijn Roos Hoefgeest and Lucas Slot

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

Abstract
Persistent homology is a popular method for computing topological features of (metric) data. Standard approaches based on the Čech or Rips filtration are stable under small perturbations of the data, but highly sensitive to outliers. This lack of robustness has been frequently addressed in the literature. In this paper, we take a novel perspective by asking the following question: When can we guarantee that an observed persistent feature (a bar) is inherent to the underlying data in the presence of a limited number of unknown, arbitrary outliers. We formalize this question by introducing the notion of adversarial robustness, and study the problem of deciding whether a given bar in the barcode of a filtered simplicial complex is adversarially robust. We show that this problem is essentially equivalent to a homological variant of the minimum cut problem in simplicial complexes, which we believe to be of independent interest. As our main technical contribution, we provide the first computational complexity results for this problem, consisting of an efficient algorithm in 0-dimensional homology, NP-hardness for the general problem, and an efficient algorithm for codimension-1 in n-dimensional complexes embedded in ℝⁿ. We also analyze its natural linear programming relaxation, whose dual defines a homological analog of the max-flow problem in graphs. We show that a max-flow/min-cut theorem does not hold in our setting, implying that the LP relaxation is not tight in general. Finally, in the special case of the Rips filtration, we provide a global heuristic based on the Hausdorff distance that guarantees adversarial robustness of sufficiently long bars. This connects adversarial robustness to standard stability theorems in persistent homology.
Cite as

Pepijn Roos Hoefgeest and Lucas Slot. Robustness of Persistent Topological Features and Minimum Homological Cuts. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 87:1-87:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{rooshoefgeest_et_al:LIPIcs.SoCG.2026.87,
  author =	{Roos Hoefgeest, Pepijn and Slot, Lucas},
  title =	{{Robustness of Persistent Topological Features and Minimum Homological Cuts}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{87:1--87: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.87},
  URN =		{urn:nbn:de:0030-drops-258636},
  doi =		{10.4230/LIPIcs.SoCG.2026.87},
  annote =	{Keywords: Topological Data Analysis, Persistent Homology, Min-cut Max-flow, Robustness, Vietoris-Rips Filtration}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.17
Fréchet Distance in the Imbalanced Case

Authors: Lotte Blank

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

Abstract
Given two polygonal curves P and Q defined by n and m vertices with m ≤ n, we show that the discrete Fréchet distance in 1D cannot be approximated within a factor of 2-ε in 𝒪((nm)^{1-δ}) time for any ε, δ > 0 unless OVH fails. Using a similar construction, we extend this bound for curves in 2D under the continuous or discrete Fréchet distance and increase the approximation factor to 1+√2-ε (resp. 3-ε) if the curves lie in the Euclidean space (resp. in the L_∞-space). This strengthens the lower bound by Buchin, Ophelders, and Speckmann to the case where m = n^α for α ∈ (0,1) and increases the approximation factor of 1.001 by Bringmann. For the discrete Fréchet distance in 1D, we provide an approximation algorithm with optimal approximation factor and almost optimal running time. Further, for curves in any dimension embedded in any L_p space, we present a (3+ε)-approximation algorithm for the continuous and discrete Fréchet distance using 𝒪((n+m²)log n) time, which almost matches the approximation factor of the lower bound for the L_∞ metric.
Cite as

Lotte Blank. Fréchet Distance in the Imbalanced Case. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 17:1-17:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{blank:LIPIcs.SoCG.2026.17,
  author =	{Blank, Lotte},
  title =	{{Fr\'{e}chet Distance in the Imbalanced Case}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{17:1--17:17},
  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.17},
  URN =		{urn:nbn:de:0030-drops-258232},
  doi =		{10.4230/LIPIcs.SoCG.2026.17},
  annote =	{Keywords: Fr\'{e}chet distance, SETH, Orthogonal Vectors, Lower Bounds, distance oracle, data structures}
}
Document
DOI: 10.4230/LIPIcs.FUN.2026.5
Token Positional Games

Authors: Guillaume Bagan, Quentin Deschamps, Florian Galliot, Mirjana Mikalački, and Nacim Oijid

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract
The classical Maker-Breaker positional game is played on a board which is a hypergraph ℋ, with two players, Maker and Breaker, alternately claiming vertices of ℋ until all the vertices are claimed. When the game ends, Maker wins if she has claimed all the vertices of some edge of ℋ; otherwise, Breaker wins. Playing this game in real life can be done by placing tokens on the vertices of the board. In this paper, we study the unfortunate case in which one or both players do not have enough tokens to cover all the vertices and, as such, will have to move their tokens around at some point instead of placing new ones. There may be a bias, in that Maker and Breaker do not necessarily have the same amount of tokens. The present paper initiates the study of this generalization of positional games, called token positional games. A particularly interesting case is when Maker has a winning strategy in the classical game: what is the lowest number of tokens with which she still wins against Breaker’s unlimited stock? We notably show that, for k-uniform hypergraphs on an arbitrarily large number n of vertices, this number equals k if k ∈ {2,3} but can vary from k to Ω(n) if k ≥ 4. From an algorithmic point of view, PSPACE-hardness in general is inherited from classical positional games, but we get a polynomial-time algorithm to solve the case where Breaker only has one token. We also establish EXPTIME-completeness for a "token sliding" variation of the game.
Cite as

Guillaume Bagan, Quentin Deschamps, Florian Galliot, Mirjana Mikalački, and Nacim Oijid. Token Positional Games. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 5:1-5:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bagan_et_al:LIPIcs.FUN.2026.5,
  author =	{Bagan, Guillaume and Deschamps, Quentin and Galliot, Florian and Mikala\v{c}ki, Mirjana and Oijid, Nacim},
  title =	{{Token Positional Games}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{5:1--5:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.5},
  URN =		{urn:nbn:de:0030-drops-257240},
  doi =		{10.4230/LIPIcs.FUN.2026.5},
  annote =	{Keywords: positional games, token games, hypergraphs, algorithmic complexity}
}
Document
DOI: 10.4230/OASIcs.NINeS.2026.10
Scalable Routing in a City-Scale Wi-Fi Network for Disaster Recovery

Authors: Ziqian Liu, Om Chabra, James Lynch, Aaron Martin, Chenning Li, and Hari Balakrishnan

Published in: OASIcs, Volume 139, 1st New Ideas in Networked Systems (NINeS 2026)

Abstract
This paper presents CityMesh, a city-scale decentralized mesh network designed for disaster recovery and emergency scenarios. When wide-area Internet connectivity is unavailable or severely degraded, CityMesh leverages both static access points and mobile devices equipped with Wi-Fi to provide intra-city connectivity and reach opportunistic gateways to the Internet (e.g., via satellite links). The main contribution of this paper is a scalable routing protocol that supports millions of devices, addressing a long-standing limitation of wireless mesh and mobile ad hoc networks. Unlike prior approaches, CityMesh exploits rich building-location and building-geometry data from widely available city maps to guide route computation, improving packet delivery while significantly reducing transmission overhead. Simulation results from 70 cities show that CityMesh improves packet delivery rates by 88% over WEAVE (a state-of-the-art geographic routing protocol). A campus-scale deployment of 300 Wi-Fi devices across 31 buildings shows the practical deployability of CityMesh. These results demonstrate the promise of map-aware routing as a foundation for scalable, resilient city-wide Wi-Fi networks.
Cite as

Ziqian Liu, Om Chabra, James Lynch, Aaron Martin, Chenning Li, and Hari Balakrishnan. Scalable Routing in a City-Scale Wi-Fi Network for Disaster Recovery. In 1st New Ideas in Networked Systems (NINeS 2026). Open Access Series in Informatics (OASIcs), Volume 139, pp. 10:1-10:31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:OASIcs.NINeS.2026.10,
  author =	{Liu, Ziqian and Chabra, Om and Lynch, James and Martin, Aaron and Li, Chenning and Balakrishnan, Hari},
  title =	{{Scalable Routing in a City-Scale Wi-Fi Network for Disaster Recovery}},
  booktitle =	{1st New Ideas in Networked Systems (NINeS 2026)},
  pages =	{10:1--10:31},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-414-7},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{139},
  editor =	{Argyraki, Katerina and Panda, Aurojit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.NINeS.2026.10},
  URN =		{urn:nbn:de:0030-drops-255954},
  doi =		{10.4230/OASIcs.NINeS.2026.10},
  annote =	{Keywords: mesh networking, disaster recovery, geographic routing, scalability, Wi-Fi}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.34
Testing Classical Properties from Quantum Data

Authors: Matthias C. Caro, Preksha Naik, and Joseph Slote

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

Abstract
Many properties of Boolean functions can be tested far more efficiently than the function itself can be learned. However, this dramatic advantage often disappears when testers are limited to random samples of f instead of adaptively chosen queries to f. In this work we investigate the quantum version of this restriction: quantum algorithms that test properties of a Boolean function f solely from copies of either the function state |f⟩∝ ∑_x|x,f(x)⟩ or the phase state |(-1)^f⟩∝ ∑_x (-1)^{f(x)}|x⟩. Quantum advantage in testing from data. For monotonicity, symmetry, and triangle-freeness, we show passive quantum testers are unboundedly or super-polynomially better than their classical passive testing counterparts. They are competitive with classic query-based testers in each case. Inadequacy of Fourier sampling. Our new testers use techniques beyond quantum Fourier sampling, and it turns out this is necessary: we show a certain class of bent functions can be tested from 𝒪(1) function states but has a sample complexity lower bound of 2^{Ω(n)} for any tester relying exclusively on Fourier and classical samples. Classical queries vs. quantum data. Our passive quantum testers are competitive with classical query-based testers, but this isn't universal: we exhibit a testing problem that can be solved from 𝒪(1) classical queries but requires Ω(2^{n/2}) function state copies. The Forrelation problem provides a separation of the same magnitude in the opposite direction, so we conclude that quantum data and classical queries are "maximally incomparable" resources for testing. Towards lower bounds. We also begin the study of lower bounds for testing from quantum data. For quantum monotonicity testing, we prove that the ensembles of [Goldreich et al., 2000; Black, 2024], which give exponential lower bounds for classical sample-based testing, do not yield any nontrivial lower bounds for testing from quantum data. New insights specific to quantum data will be required for proving copy complexity lower bounds for testing in this model.
Cite as

Matthias C. Caro, Preksha Naik, and Joseph Slote. Testing Classical Properties from Quantum Data. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 34:1-34:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{caro_et_al:LIPIcs.ITCS.2026.34,
  author =	{Caro, Matthias C. and Naik, Preksha and Slote, Joseph},
  title =	{{Testing Classical Properties from Quantum Data}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{34:1--34:26},
  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.34},
  URN =		{urn:nbn:de:0030-drops-253213},
  doi =		{10.4230/LIPIcs.ITCS.2026.34},
  annote =	{Keywords: Quantum Property Testing, Quantum Data, Boolean Functions}
}
Document
Poster Abstract
DOI: 10.4230/LIPIcs.GD.2025.51
Graph Tiles (Poster Abstract)

Authors: Oswin Aichholzer, Robert Ganian, Phillip Keldenich, Maarten Löffler, Gert Meijer, Alexandra Weinberger, and Carola Wenk

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
We define a graph tile to be a unit square (or more generally, a polygon) on which a piece of a graph has been drawn/embedded; in particular, it may have vertices in its interior, edges connecting those vertices, or half-edges that extend to the boundary of the tile. In a graph tiling problem, we are given as input a set of graph tiles, with multiplicities, and the output is an arrangement of those tiles forming a graph of larger area. We focus on a simple tile set: unit square tiles with a central vertex and either a half-edge or no half-edge on each side. Up to symmetry this gives us six different types. We characterize which multiplicities are compatible for sets of at most three different tiles.
Cite as

Oswin Aichholzer, Robert Ganian, Phillip Keldenich, Maarten Löffler, Gert Meijer, Alexandra Weinberger, and Carola Wenk. Graph Tiles (Poster Abstract). In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 51:1-51:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{aichholzer_et_al:LIPIcs.GD.2025.51,
  author =	{Aichholzer, Oswin and Ganian, Robert and Keldenich, Phillip and L\"{o}ffler, Maarten and Meijer, Gert and Weinberger, Alexandra and Wenk, Carola},
  title =	{{Graph Tiles}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{51:1--51:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.51},
  URN =		{urn:nbn:de:0030-drops-250371},
  doi =		{10.4230/LIPIcs.GD.2025.51},
  annote =	{Keywords: graph tiles}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.12
Subtrajectory Clustering and Coverage Maximization in Cubic Time, or Better

Authors: Jacobus Conradi and Anne Driemel

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

Abstract
Many application areas collect unstructured trajectory data. In subtrajectory clustering, one is interested to find patterns in this data using a hybrid combination of segmentation and clustering. We analyze two variants of this problem based on the well-known SetCover and CoverageMaximization problems. In both variants the set system is induced by metric balls under the Fréchet distance centered at polygonal curves. Our algorithms focus on improving the running time of the update step of the generic greedy algorithm by means of a careful combination of sweeps through a candidate space. In the first variant, we are given a polygonal curve P of complexity n, distance threshold Δ and complexity bound 𝓁 and the goal is to identify a minimum-size set of center curves 𝒞, where each center curve is of complexity at most 𝓁 and every point p on P is covered. A point p on P is covered if it is part of a subtrajectory π_p of P such that there is a center c ∈ 𝒞 whose Fréchet distance to π_p is at most Δ. We present an approximation algorithm for this problem with a running time of 𝒪((n²𝓁 + √{k_Δ}n^{5/2})log²n), where k_Δ is the size of an optimal solution. The algorithm gives a bicriterial approximation guarantee that relaxes the Fréchet distance threshold by a constant factor and the size of the solution by a factor of 𝒪(log n). The second problem variant asks for the maximum fraction of the input curve P that can be covered using k center curves, where k ≤ n is a parameter to the algorithm. For the second problem variant, our techniques lead to an algorithm with a running time of 𝒪((k+𝓁)n²log²n) and similar approximation guarantees. Note that in both algorithms k,k_Δ ∈ O(n) and hence the running time is cubic, or better if k ≪ n.
Cite as

Jacobus Conradi and Anne Driemel. Subtrajectory Clustering and Coverage Maximization in Cubic Time, or Better. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 12:1-12:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{conradi_et_al:LIPIcs.ESA.2025.12,
  author =	{Conradi, Jacobus and Driemel, Anne},
  title =	{{Subtrajectory Clustering and Coverage Maximization in Cubic Time, or Better}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{12:1--12:18},
  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.12},
  URN =		{urn:nbn:de:0030-drops-244806},
  doi =		{10.4230/LIPIcs.ESA.2025.12},
  annote =	{Keywords: Clustering, Set cover, Fr\'{e}chet distance, Approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.35
The Geodesic Fréchet Distance Between Two Curves Bounding a Simple Polygon

Authors: Thijs van der Horst, Marc van Kreveld, Tim Ophelders, and Bettina Speckmann

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

Abstract
The Fréchet distance is a popular similarity measure that is well-understood for polygonal curves in ℝ^d: near-quadratic time algorithms exist, and conditional lower bounds suggest that these results cannot be improved significantly, even in one dimension and when approximating with a factor less than three. We consider the special case where the curves bound a simple polygon and distances are measured via geodesics inside this simple polygon. Here the conditional lower bounds do not apply; Efrat et al. (2002) were able to give a near-linear time 2-approximation algorithm. In this paper, we significantly improve upon their result: we present a (1+ε)-approximation algorithm, for any ε > 0, that runs in 𝒪(1/(ε) (n+m log n) log nm log 1/(ε)) time for a simple polygon bounded by two curves with n and m vertices, respectively. To do so, we show how to compute the reachability of specific groups of points in the free space at once, by interpreting the free space as one between separated one-dimensional curves. We solve this one-dimensional problem in near-linear time, generalizing a result by Bringmann and Künnemann (2015). Finally, we give a linear time exact algorithm if the two curves bound a convex polygon.
Cite as

Thijs van der Horst, Marc van Kreveld, Tim Ophelders, and Bettina Speckmann. The Geodesic Fréchet Distance Between Two Curves Bounding a Simple Polygon. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 35:1-35:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{vanderhorst_et_al:LIPIcs.ESA.2025.35,
  author =	{van der Horst, Thijs and van Kreveld, Marc and Ophelders, Tim and Speckmann, Bettina},
  title =	{{The Geodesic Fr\'{e}chet Distance Between Two Curves Bounding a Simple Polygon}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{35:1--35:16},
  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.35},
  URN =		{urn:nbn:de:0030-drops-245038},
  doi =		{10.4230/LIPIcs.ESA.2025.35},
  annote =	{Keywords: Fr\'{e}chet distance, approximation, geodesic, simple polygon}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.90
Separating Two Points with Obstacles in the Plane: Improved Upper and Lower Bounds

Authors: Jack Spalding-Jamieson and Anurag Murty Naredla

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

Abstract
Given two points in the plane, and a set of "obstacles" given as curves through the plane with assigned weights, we consider the point-separation problem, which asks for a minimum-weight subset of the obstacles separating the two points. A few computational models for this problem have been previously studied. We give a unified approach to this problem in all models via a reduction to a particular shortest-path problem, and obtain improved running times in essentially all cases. In addition, we also give fine-grained lower bounds for many cases.
Cite as

Jack Spalding-Jamieson and Anurag Murty Naredla. Separating Two Points with Obstacles in the Plane: Improved Upper and Lower Bounds. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 90:1-90:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{spaldingjamieson_et_al:LIPIcs.ESA.2025.90,
  author =	{Spalding-Jamieson, Jack and Naredla, Anurag Murty},
  title =	{{Separating Two Points with Obstacles in the Plane: Improved Upper and Lower Bounds}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{90:1--90:18},
  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.90},
  URN =		{urn:nbn:de:0030-drops-245598},
  doi =		{10.4230/LIPIcs.ESA.2025.90},
  annote =	{Keywords: obstacle separation, point separation, geometric intersection graph, Z₂-homology, fine-grained lower bounds}
}
Document
DOI: 10.4230/LIPIcs.SAT.2025.32
Efficient Certified Reasoning for Binarized Neural Networks

Authors: Jiong Yang, Yong Kiam Tan, Mate Soos, Magnus O. Myreen, and Kuldeep S. Meel

Published in: LIPIcs, Volume 341, 28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025)

Abstract
Neural networks have emerged as essential components in safety-critical applications - these use cases demand complex, yet trustworthy computations. Binarized Neural Networks (BNNs) are a type of neural network where each neuron is constrained to a Boolean value; they are particularly well-suited for safety-critical tasks because they retain much of the computational capacities of full-scale (floating-point or quantized) deep neural networks, but remain compatible with satisfiability solvers for qualitative verification and with model counters for quantitative reasoning. However, existing methods for BNN analysis suffer from either limited scalability or susceptibility to soundness errors, which hinders their applicability in real-world scenarios. In this work, we present a scalable and trustworthy approach for both qualitative and quantitative verification of BNNs. Our approach introduces a native representation of BNN constraints in a custom-designed solver for qualitative reasoning, and in an approximate model counter for quantitative reasoning. We further develop specialized proof generation and checking pipelines with native support for BNN constraint reasoning, ensuring trustworthiness for all of our verification results. Empirical evaluations on a BNN robustness verification benchmark suite demonstrate that our certified solving approach achieves a 9× speedup over prior certified CNF and PB-based approaches, and our certified counting approach achieves a 218× speedup over the existing CNF-based baseline. In terms of coverage, our pipeline produces fully certified results for 99% and 86% of the qualitative and quantitative reasoning queries on BNNs, respectively. This is in sharp contrast to the best existing baselines which can fully certify only 62% and 4% of the queries, respectively.
Cite as

Jiong Yang, Yong Kiam Tan, Mate Soos, Magnus O. Myreen, and Kuldeep S. Meel. Efficient Certified Reasoning for Binarized Neural Networks. In 28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 341, pp. 32:1-32:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{yang_et_al:LIPIcs.SAT.2025.32,
  author =	{Yang, Jiong and Tan, Yong Kiam and Soos, Mate and Myreen, Magnus O. and Meel, Kuldeep S.},
  title =	{{Efficient Certified Reasoning for Binarized Neural Networks}},
  booktitle =	{28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025)},
  pages =	{32:1--32:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-381-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{341},
  editor =	{Berg, Jeremias and Nordstr\"{o}m, Jakob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2025.32},
  URN =		{urn:nbn:de:0030-drops-237665},
  doi =		{10.4230/LIPIcs.SAT.2025.32},
  annote =	{Keywords: Neural network verification, proof certification, SAT solving, approximate model counting}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.133
Faster, Deterministic and Space Efficient Subtrajectory Clustering

Authors: Ivor van der Hoog, Thijs van der Horst, and Tim Ophelders

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Given a trajectory T and a distance Δ, we wish to find a set C of curves of complexity at most 𝓁, such that we can cover T with subcurves that each are within Fréchet distance Δ to at least one curve in C. We call C an (𝓁,Δ)-clustering and aim to find an (𝓁,Δ)-clustering of minimum cardinality. This problem variant was introduced by Akitaya et al. (2021) and shown to be NP-complete. The main focus has therefore been on bicriteria approximation algorithms, allowing for the clustering to be an (𝓁, Θ(Δ))-clustering of roughly optimal size. We present algorithms that construct (𝓁,4Δ)-clusterings of 𝒪(k log n) size, where k is the size of the optimal (𝓁, Δ)-clustering. We use 𝒪(n³) space and 𝒪(k n³ log⁴ n) time. Our algorithms significantly improve upon the clustering quality (improving the approximation factor in Δ) and size (whenever 𝓁 ∈ Ω(log n / log k)). We offer deterministic running times improving known expected bounds by a factor near-linear in 𝓁. Additionally, we match the space usage of prior work, and improve it substantially, by a factor super-linear in n𝓁, when compared to deterministic results.
Cite as

Ivor van der Hoog, Thijs van der Horst, and Tim Ophelders. Faster, Deterministic and Space Efficient Subtrajectory Clustering. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 133:1-133:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{vanderhoog_et_al:LIPIcs.ICALP.2025.133,
  author =	{van der Hoog, Ivor and van der Horst, Thijs and Ophelders, Tim},
  title =	{{Faster, Deterministic and Space Efficient Subtrajectory Clustering}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{133:1--133:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l 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.2025.133},
  URN =		{urn:nbn:de:0030-drops-235109},
  doi =		{10.4230/LIPIcs.ICALP.2025.133},
  annote =	{Keywords: Fr\'{e}chet distance, clustering, set cover}
}
  • Refine by Type
  • 32 Document/PDF
  • 21 Document/HTML

  • Refine by Publication Year
  • 9 2026
  • 12 2025
  • 2 2022
  • 2 2021
  • 1 2020
  • Show More...

  • Refine by Author
  • 10 Fox, Kyle
  • 3 Agarwal, Pankaj K.
  • 3 van der Hoog, Ivor
  • 2 Conradi, Jacobus
  • 2 Mozes, Shay
  • Show More...

  • Refine by Series/Journal
  • 31 LIPIcs
  • 1 OASIcs

  • Refine by Classification
  • 15 Theory of computation → Computational geometry
  • 3 Theory of computation → Design and analysis of algorithms
  • 2 Mathematics of computing → Algebraic topology
  • 2 Mathematics of computing → Topology
  • 2 Theory of computation → Approximation algorithms analysis
  • Show More...

  • Refine by Keyword
  • 8 Fréchet distance
  • 3 shape matching
  • 2 Algorithms engineering
  • 2 Gromov-Hausdorff distance
  • 2 Persistent Homology
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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