21 Search Results for "Kranakis, Evangelos"

Document
DOI: 10.4230/LIPIcs.STACS.2026.18
Optimal Deterministic Rendezvous in Labeled Lines

Authors: Yann Bourreau, Ananth Narayanan, and Alexandre Nolin

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

Abstract
In a rendezvous task, a set of mobile agents initially dispersed in a network have to gather at an arbitrary common site. We consider the rendezvous problem on the infinite labeled line, with 2 initially asleep agents, without communication, and a synchronous notion of time. Each node on the line is labeled with a unique positive integer. The initial distance between the two agents is denoted by D. Time is divided into rounds and measured from the moment an agent first wakes up. We denote by τ the delay between the two agents' wake up times. If awake in a given round T, an agent at a node v has three options: stay at the node v, take port 0, or take port 1. If it decides to stay, the agent will still be at node v in round T+1. Otherwise, it will be at one of the two neighbors of v on the infinite line, depending on the port it chose. The agents achieve rendezvous in T rounds if they are at the same node in round T. We aim for a deterministic algorithm for this problem. The problem was recently considered by Miller and Pelc [Distributed Computing, 2025]. With 𝓁_{max} the largest label of the two starting nodes, they showed that no algorithm can guarantee rendezvous in o(D log^* 𝓁_{max}) rounds. The lower bound follows from a connection with the LOCAL model of distributed computing, and holds even if the agents are guaranteed simultaneous wake-up (τ = 0) and are told their initial distance D. Miller and Pelc also gave an algorithm of optimal matching complexity O(D log^* 𝓁_{max}) when the agents know D, but only obtained the higher bound of O(D² (log^* 𝓁_{max})³) when D is unknown to the agents. In this paper, we improve this second complexity to a tight O(D log^* 𝓁_{max}), closing the gap between the best known lower and upper bounds. In fact, our algorithm achieves rendezvous in O(D log^* 𝓁_{min}) rounds, where 𝓁_{min} is the smallest label within distance O(D) of the two starting positions. We obtain this result by having the agents compute sparse subsets of the nodes to gather at (formally, ruling sets over the line), as well as some general observations about the setting of rendezvous on labeled graphs.
Cite as

Yann Bourreau, Ananth Narayanan, and Alexandre Nolin. Optimal Deterministic Rendezvous in Labeled Lines. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 18:1-18:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bourreau_et_al:LIPIcs.STACS.2026.18,
  author =	{Bourreau, Yann and Narayanan, Ananth and Nolin, Alexandre},
  title =	{{Optimal Deterministic Rendezvous in Labeled Lines}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{18:1--18:20},
  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.18},
  URN =		{urn:nbn:de:0030-drops-255071},
  doi =		{10.4230/LIPIcs.STACS.2026.18},
  annote =	{Keywords: mobile agents, rendezvous, ruling set, deterministic algorithms, labeled line}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.47
Dudeney’s Dissection Is Optimal

Authors: Erik D. Demaine, Tonan Kamata, and Ryuhei Uehara

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

Abstract
In 1907, Henry Ernest Dudeney posed a puzzle: "cut any equilateral triangle ... into as few pieces as possible that will fit together and form a perfect square" (without overlap, via translation and rotation). Four weeks later, Dudeney demonstrated a beautiful four-piece solution, which today remains perhaps the most famous example of dissection. In this paper (over a century later), we finally solve Dudeney’s puzzle, by proving that the equilateral triangle and square have no common dissection with three or fewer polygonal pieces. We reduce the problem to the analysis of discrete graph structures representing the correspondence between the edges and the vertices of the pieces forming each polygon.
Cite as

Erik D. Demaine, Tonan Kamata, and Ryuhei Uehara. Dudeney’s Dissection Is Optimal. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 47:1-47:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{demaine_et_al:LIPIcs.ITCS.2026.47,
  author =	{Demaine, Erik D. and Kamata, Tonan and Uehara, Ryuhei},
  title =	{{Dudeney’s Dissection Is Optimal}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{47:1--47:22},
  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.47},
  URN =		{urn:nbn:de:0030-drops-253345},
  doi =		{10.4230/LIPIcs.ITCS.2026.47},
  annote =	{Keywords: Geometric Dissection, Dudeney Dissection, Dissection with Fewest Pieces}
}
Document
Invited Paper
DOI: 10.4230/OASIcs.RW.2024/2025.8
ASP Essentials: Modelling and Efficient Solving (Invited Paper)

Authors: Giuseppe Mazzotta and Francesco Ricca

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

Abstract
Answer Set Programming (ASP) is a logic-based Knowledge Representation and Reasoning (KRR) paradigm that facilitates rapid prototyping of solutions for complex problems. It is particularly effective for tackling Deep Reasoning tasks involving exponentially large search spaces, such as combinatorial search and optimization. While getting started with ASP is relatively easy, mastering its advanced constructs and scaling solutions to real-world problem sizes can be challenging. This paper provides an introduction to ASP, guiding the reader from the fundamentals of the language to the application of programming methodologies and the computation of answer sets. Beyond the core framework, the paper also examines selected extensions of ASP that enable the modeling of complex problems, as well as compilation techniques designed to enhance solving efficiency. Furthermore, it mentions some recent tools that combine ASP with LLMs.
Cite as

Giuseppe Mazzotta and Francesco Ricca. ASP Essentials: Modelling and Efficient Solving (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. 8:1-8:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{mazzotta_et_al:OASIcs.RW.2024/2025.8,
  author =	{Mazzotta, Giuseppe and Ricca, Francesco},
  title =	{{ASP Essentials: Modelling and Efficient Solving}},
  booktitle =	{Joint Proceedings of the 20th and 21st Reasoning Web Summer Schools (RW 2024 \& RW 2025)},
  pages =	{8:1--8:21},
  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.8},
  URN =		{urn:nbn:de:0030-drops-250539},
  doi =		{10.4230/OASIcs.RW.2024/2025.8},
  annote =	{Keywords: Answer Set Programming, ASP with Quantifiers, Grounding Bottleneck, Compilation-based ASP solving, Neurosymbolic AI, LLMs}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.34
Deterministic Local Problems in Radio Networks: On the Impact of Local Domination and a Bit of Advice

Authors: Pawel Garncarek, Tomasz Jurdzinski, Dariusz R. Kowalski, Shay Kutten, and Miguel A. Mosteiro

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

Abstract
Radio Networks (RN) is one of the fundamental models for network communication where nodes can broadcast messages locally but their simultaneous transmissions can interfere with each other at their shared neighbors. This work focuses on performing the very fundamental primitive of Local Broadcast, in spite of the interferences. We investigate to what extent local knowledge, called advice, relating to the 2-local domination number γ₂ may speed up Local Broadcast. Specifically for each node and some dominating set, knowledge about some neighboring dominating node and the local number among the neighbors of that dominating node. We show that such advice is sufficient to build an efficient oblivious transmission schedule. Along those lines, we present three algorithms trading the level of adaptiveness (from oblivious to adaptive) for bits of advice per node (from O(log (Δγ₂)) to 1). All our algorithms complete Local Broadcast in Õ(Δγ₂²) rounds, where Δ is the maximum degree of the network. On the side of lower bounds, we show that, for each quasi-adaptive deterministic Local Broadcast algorithm, there is some RN that requires Ω(min{(min{Δ,γ₂}/log n)²,n}) communication rounds, where n is the number of network nodes. In quasi-adaptive protocols nodes may stop executing once its computational task is completed. To the best of our knowledge, this is the first (nearly) quadratic Local Broadcast (same message for all neighbors) lower bound in the RN model. Our lower bound is stronger than previous works in multiple ways: i) it is nearly quadratically better than the best known general lower bound for this class of algorithms, ii) it applies to a wider class of algorithms than previous work for fully oblivious, iii) it achieves similar time lower bound than previous work proved for a much more demanding Local Broadcast where each node sends a possibly different message to each neighbor, and iv) it takes into account the local domination parameter γ₂.
Cite as

Pawel Garncarek, Tomasz Jurdzinski, Dariusz R. Kowalski, Shay Kutten, and Miguel A. Mosteiro. Deterministic Local Problems in Radio Networks: On the Impact of Local Domination and a Bit of Advice. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 34:1-34:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{garncarek_et_al:LIPIcs.ISAAC.2025.34,
  author =	{Garncarek, Pawel and Jurdzinski, Tomasz and Kowalski, Dariusz R. and Kutten, Shay and Mosteiro, Miguel A.},
  title =	{{Deterministic Local Problems in Radio Networks: On the Impact of Local Domination and a Bit of Advice}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{34:1--34: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.34},
  URN =		{urn:nbn:de:0030-drops-249426},
  doi =		{10.4230/LIPIcs.ISAAC.2025.34},
  annote =	{Keywords: Radio Networks, Local Broadcast, Distributed Deterministic Algorithms, Lower Bounds, Graph algorithms, Advice, Labeling Schemes, Local Domination}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.25
Structural Parameterizations of Simultaneous Planarity

Authors: Thomas Depian, Simon D. Fink, Alexander Firbas, Robert Ganian, Matthias Pfretzschner, and Ignaz Rutter

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

Abstract
Given a set of graphs on the same vertex set, the problem Simultaneous Embedding With Fixed Edges (SEFE) asks, whether there exist planar drawings of all input graphs, such that every pair of drawings coincides on their shared subgraph. It is known that SEFE is NP-complete [Elisabeth Gassner et al., 2006], even in the so-called sunflower case, where all pairs of input graphs have the same shared graph G_∩ [Marcus Schaefer, 2012]. Fink, Pfretzschner, and Rutter [Simon D. Fink et al., 2023] recently initiated the study of the parameterized complexity of SEFE in the sunflower case, mainly focusing on structural parameters of G_∩. In this work, we shift the focus towards parameters of the union graph G_∪ that contains the edges of all input graphs. On the positive side, we establish fixed-parameter tractability for the problem with respect to the feedback edge set number of G_∪. We complement this result by showing that it, surprisingly, remains NP-complete even if G_∪ has constant vertex cover number. These results settle two open questions posed by Fink et al. [Simon D. Fink et al., 2023].
Cite as

Thomas Depian, Simon D. Fink, Alexander Firbas, Robert Ganian, Matthias Pfretzschner, and Ignaz Rutter. Structural Parameterizations of Simultaneous Planarity. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{depian_et_al:LIPIcs.ISAAC.2025.25,
  author =	{Depian, Thomas and Fink, Simon D. and Firbas, Alexander and Ganian, Robert and Pfretzschner, Matthias and Rutter, Ignaz},
  title =	{{Structural Parameterizations of Simultaneous Planarity}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{25:1--25:17},
  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.25},
  URN =		{urn:nbn:de:0030-drops-249332},
  doi =		{10.4230/LIPIcs.ISAAC.2025.25},
  annote =	{Keywords: SEFE, Simultaneous Planarity, Fixed-Parameter Tractability, NP-hardness}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.27
Simple, Strict, Proper, and Directed: Comparing Reachability in Directed and Undirected Temporal Graphs

Authors: Michelle Döring

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

Abstract
Temporal graphs model networks whose connections are available only at specific points in time. Several definitional subtleties - whether paths must follow strictly increasing time labels (strict vs. non-strict), whether adjacent edges cannot appear simultaneously (proper), and whether edges are forbidden to appear multiple times (simple) - give rise to different temporal graph settings. These distinctions directly impact the definition of temporal reachability, a core concept in temporal graph theory. Casteigts, Corsini, and Sarkar [TCS24] introduced a framework of equivalence notions to compare the expressive power of these settings focusing solely on undirected temporal graphs. In this work, we extend their framework to include the fundamental dimension of directed vs. undirected. Our contribution is three-fold. We (1) complete the undirected hierarchy by resolving the two open questions from [TCS24], (2) fully characterize the hierarchy of the directed settings, and (3) compare the directed and undirected settings, showing that directed temporal graphs are strictly more expressive than undirected temporal graphs in terms of reachability. Our structural results highlight both the limitations and strengths of various temporal graph settings - for example, directed + strict + simple graphs can realize every possible reachability graph, while directed + proper graphs necessarily induce at least one transitive reachability on each directed cycle. We also provide transformation procedures between temporal settings offering practical tools for transferring algorithms and hardness results across models.
Cite as

Michelle Döring. Simple, Strict, Proper, and Directed: Comparing Reachability in Directed and Undirected Temporal Graphs. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 27:1-27:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{doring:LIPIcs.ISAAC.2025.27,
  author =	{D\"{o}ring, Michelle},
  title =	{{Simple, Strict, Proper, and Directed: Comparing Reachability in Directed and Undirected Temporal Graphs}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{27:1--27: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.27},
  URN =		{urn:nbn:de:0030-drops-249353},
  doi =		{10.4230/LIPIcs.ISAAC.2025.27},
  annote =	{Keywords: temporal graphs, directed graphs, temporal reachability, dynamic networks}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.33
Approach of Agents with Restricted Fuel Tanks

Authors: Adam Ganczorz, Tomasz Jurdzinski, Andrzej Pelc, and Grzegorz Stachowiak

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
Two mobile agents, modelled as points in the plane moving at speed 1, have to get at a distance at most 1 from each other. This task is known as approach or rendezvous in the plane. An adversary initially places both agents at distinct points, called their bases, at distance at most D, and wakes them up at possibly different times. Each of the agents has a fuel tank that allows them to traverse a trajectory of length D, and can be replenished at the base of the agent. The algorithm of each agent consists of a series of actions which are either moves at a chosen distance in a chosen direction or staying idle for a chosen period of time. For a given instance of the approach task, the execution time of an approach algorithm is the length of the period between the start of the later agent and the moment of approach. Our goal is to design approach algorithms with optimal time complexity. We consider two independent coherence assumptions. One of them is time coherence, i.e., agents start simultaneously, and the other is orientation coherence: agents have compatible compasses, showing the same North direction. Our main result is establishing optimal time complexity of the approach problem with restricted fuel tanks. It turns out that this optimal complexity heavily depends on the above coherence assumptions. If both of them are satisfied then approach can be performed in time O(D²) and we show that this complexity is optimal. If any of the two coherence assumptions is missing then approach can be performed in time O(D²√D) and we prove that this order of magnitude cannot be improved. Our main technical contribution are lower bounds showing that, for each of the considered scenarios, our fairly natural approach algorithms are, in fact, optimal.
Cite as

Adam Ganczorz, Tomasz Jurdzinski, Andrzej Pelc, and Grzegorz Stachowiak. Approach of Agents with Restricted Fuel Tanks. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 33:1-33:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ganczorz_et_al:LIPIcs.DISC.2025.33,
  author =	{Ganczorz, Adam and Jurdzinski, Tomasz and Pelc, Andrzej and Stachowiak, Grzegorz},
  title =	{{Approach of Agents with Restricted Fuel Tanks}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{33:1--33:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.33},
  URN =		{urn:nbn:de:0030-drops-248506},
  doi =		{10.4230/LIPIcs.DISC.2025.33},
  annote =	{Keywords: mobile agent, approach, rendezvous, plane, restricted energy}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.48
Sharp Thresholds for the Overlap Gap Property: Ising p-Spin Glass and Random k-SAT

Authors: Eren C. Kızıldağ

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

Abstract
The Ising p-spin glass and random k-SAT are two canonical examples of disordered systems that play a central role in understanding the link between geometric features of optimization landscapes and computational tractability. Both models exhibit hard regimes where all known polynomial-time algorithms fail and possess the multi Overlap Gap Property (m-OGP), an intricate geometrical property that rigorously rules out a broad class of algorithms exhibiting input stability. We establish that, in both models, the symmetric m-OGP undergoes a sharp phase transition, and we pinpoint its exact threshold. For the Ising p-spin glass, our results hold for all sufficiently large p; for the random k-SAT, they apply to all k growing mildly with the number of Boolean variables. Notably, our findings yield qualitative insights into the power of OGP-based arguments. A particular consequence for the Ising p-spin glass is that the strength of the m-OGP in establishing algorithmic hardness grows without bound as m increases. These are the first sharp threshold results for the m-OGP. Our analysis hinges on a judicious application of the second moment method, enhanced by concentration. While a direct second moment calculation fails, we overcome this via a refined approach that leverages an argument of Frieze [Frieze, 1990] and exploiting concentration properties of carefully constructed random variables.
Cite as

Eren C. Kızıldağ. Sharp Thresholds for the Overlap Gap Property: Ising p-Spin Glass and Random k-SAT. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 48:1-48:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kizildag:LIPIcs.APPROX/RANDOM.2025.48,
  author =	{K{\i}z{\i}lda\u{g}, Eren C.},
  title =	{{Sharp Thresholds for the Overlap Gap Property: Ising p-Spin Glass and Random k-SAT}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{48:1--48:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.48},
  URN =		{urn:nbn:de:0030-drops-244147},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.48},
  annote =	{Keywords: spin glasses, p-spin model, random constraint satisfaction problems, overlap gap property, phase transitions, computational complexity}
}
Document
Research
DOI: 10.4230/OASIcs.Grossi.12
Encoding Data Structures for Range Queries on Arrays

Authors: Seungbum Jo and Srinivasa Rao Satti

Published in: OASIcs, Volume 132, From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday (2025)

Abstract
Efficiently processing range queries on arrays is a fundamental problem in computer science, with applications spanning diverse domains such as database management, computational biology, and geographic information systems. A range query retrieves information about a specific segment of an array, such as the sum, minimum, maximum, or median of elements within a given range. The challenge lies in designing data structures that allow such queries to be answered quickly, often in constant or logarithmic time, while keeping space overhead (and preprocessing time) small. Encoding data structures for range queries has emerged as a pivotal area of research due to the increasing demand for high-performance systems handling massive datasets. These structures consider the data together with the queries and aim to store only as much information about the data as is needed to answer the queries. The data structure does not need to access the original data to answer the queries. Encoding-based solutions often leverage techniques from succinct data structures, bit manipulation, and combinatorial optimization to achieve both space and time efficiency. By encoding the array in a manner that preserves critical information, these methods strike a balance between query time and space usage. In this survey article, we explore the landscape of encoding data structures for range queries on arrays, providing a comprehensive overview of some important results on space-efficient encodings for various types of range query.
Cite as

Seungbum Jo and Srinivasa Rao Satti. Encoding Data Structures for Range Queries on Arrays. In From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday. Open Access Series in Informatics (OASIcs), Volume 132, pp. 12:1-12:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jo_et_al:OASIcs.Grossi.12,
  author =	{Jo, Seungbum and Satti, Srinivasa Rao},
  title =	{{Encoding Data Structures for Range Queries on Arrays}},
  booktitle =	{From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday},
  pages =	{12:1--12:12},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-391-1},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{132},
  editor =	{Conte, Alessio and Marino, Andrea and Rosone, Giovanna and Vitter, Jeffrey Scott},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Grossi.12},
  URN =		{urn:nbn:de:0030-drops-238116},
  doi =		{10.4230/OASIcs.Grossi.12},
  annote =	{Keywords: range queries, RMQ, Cartesian tree, top-k queries, range median, range mode}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.22
New Bounds for the Ideal Proof System in Positive Characteristic

Authors: Amik Raj Behera, Nutan Limaye, Varun Ramanathan, and Srikanth Srinivasan

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

Abstract
In this work, we prove upper and lower bounds over fields of positive characteristics for several fragments of the Ideal Proof System (IPS), an algebraic proof system introduced by Grochow and Pitassi (J. ACM 2018). Our results extend the works of Forbes, Shpilka, Tzameret, and Wigderson (Theory of Computing 2021) and also of Govindasamy, Hakoniemi, and Tzameret (FOCS 2022). These works primarily focused on proof systems over fields of characteristic 0, and we are able to extend these results to positive characteristic. The question of proving general IPS lower bounds over positive characteristic is motivated by the important question of proving AC⁰[p]-Frege lower bounds. This connection was observed by Grochow and Pitassi (J. ACM 2018). Additional motivation comes from recent developments in algebraic complexity theory due to Forbes (CCC 2024) who showed how to extend previous lower bounds over characteristic 0 to positive characteristic. In our work, we adapt the functional lower bound method of Forbes et al. (Theory of Computing 2021) to prove exponential-size lower bounds for various subsystems of IPS. In order to establish these size lower bounds, we first prove a tight degree lower bound for a variant of Subset Sum over positive characteristic. This forms the core of all our lower bounds. Additionally, we derive upper bounds for the instances presented above. We show that they have efficient constant-depth IPS refutations. This demonstrates that constant-depth IPS refutations are stronger than the proof systems considered above even in positive characteristic. We also show that constant-depth IPS can efficiently refute a general class of instances, namely all symmetric instances, thereby further uncovering the strength of these algebraic proofs in positive characteristic.
Cite as

Amik Raj Behera, Nutan Limaye, Varun Ramanathan, and Srikanth Srinivasan. New Bounds for the Ideal Proof System in Positive Characteristic. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 22:1-22:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{behera_et_al:LIPIcs.ICALP.2025.22,
  author =	{Behera, Amik Raj and Limaye, Nutan and Ramanathan, Varun and Srinivasan, Srikanth},
  title =	{{New Bounds for the Ideal Proof System in Positive Characteristic}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{22:1--22:20},
  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.22},
  URN =		{urn:nbn:de:0030-drops-233992},
  doi =		{10.4230/LIPIcs.ICALP.2025.22},
  annote =	{Keywords: Ideal Proof Systems, Algebraic Complexity, Positive Characteristic}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2024.11
Gathering Teams of Deterministic Finite Automata on a Line

Authors: Younan Gao and Andrzej Pelc

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract
Several mobile agents, modelled as deterministic finite automata, navigate in an infinite line in synchronous rounds. All agents start in the same round. In each round, an agent can move to one of the two neighboring nodes, or stay idle. Agents have distinct labels which are integers from the set {1,…,L}. They start in teams, each of which consists of x agents, for some fixed integer x. Agents in a team have the same starting node. The adversary decides the compositions of teams, and their starting nodes. Whenever an agent enters a node, it sees the entry port number and the states of all collocated agents; this information forms the input of the agent on the basis of which it transits to the next state and decides the current action. The aim is for all agents to gather at the same node and stop. Gathering is feasible, if this task can be accomplished for any decisions of the adversary, and its time is the worst-case number of rounds from the start till gathering. We consider the feasibility and time complexity of gathering teams of agents, and give a complete solution of this problem. It turns out that both feasibility and complexity of gathering depend on the crucial parameter x which is the size of teams. For the oriented line, gathering is impossible if x = 1, and it can be accomplished in time O(D), for x > 1, where D is the distance between the starting nodes of the most distant teams. This complexity is of course optimal. For the unoriented line, the situation is different. For x = 1, gathering is also impossible, but for x = 2, the optimal time of gathering is Θ(Dlog L), and for x ≥ 3 the optimal time of gathering is Θ(D). Solving the gathering problem for agents that are finite automata navigating in an infinite environment requires new methodological tools. Traditional gathering techniques in graphs are count driven: agents make decisions based on counting steps. Since distances between agents may be unbounded, agents have to count unbounded numbers of steps. When agents are finite automata, counting unbounded numbers of steps is impossible, hence we must use different methods. In all our gathering algorithms, changes of the agents' behavior are triggered not by counting steps but by events which are meetings between agents during which they interact. Hence our new technique is event driven. Designing the behavior of the agents based on meeting events, so as to guarantee gathering regardless of the adversary’s decisions is our main methodological contribution.
Cite as

Younan Gao and Andrzej Pelc. Gathering Teams of Deterministic Finite Automata on a Line. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gao_et_al:LIPIcs.OPODIS.2024.11,
  author =	{Gao, Younan and Pelc, Andrzej},
  title =	{{Gathering Teams of Deterministic Finite Automata on a Line}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{11:1--11:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.11},
  URN =		{urn:nbn:de:0030-drops-225478},
  doi =		{10.4230/LIPIcs.OPODIS.2024.11},
  annote =	{Keywords: Gathering, deterministic finite automaton, mobile agent, team of agents, line, time}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2024.9
Crash-Tolerant Exploration of Trees by Energy-Sharing Mobile Agents

Authors: Quentin Bramas, Toshimitsu Masuzawa, and Sébastien Tixeuil

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract
We consider the problem of graph exploration by energy sharing mobile agents that are subject to crash faults. More precisely, we consider a team of two agents where at most one of them may fail unpredictably, and the considered topology is that of connected acyclic graphs (i.e. trees). We consider both the asynchronous and the synchronous settings, and we provide necessary and sufficient conditions about the energy.
Cite as

Quentin Bramas, Toshimitsu Masuzawa, and Sébastien Tixeuil. Crash-Tolerant Exploration of Trees by Energy-Sharing Mobile Agents. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bramas_et_al:LIPIcs.OPODIS.2024.9,
  author =	{Bramas, Quentin and Masuzawa, Toshimitsu and Tixeuil, S\'{e}bastien},
  title =	{{Crash-Tolerant Exploration of Trees by Energy-Sharing Mobile Agents}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{9:1--9:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.9},
  URN =		{urn:nbn:de:0030-drops-225452},
  doi =		{10.4230/LIPIcs.OPODIS.2024.9},
  annote =	{Keywords: Mobile Agents, Distributed Algorithms, Energy sharing}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2022.12
Line Search for an Oblivious Moving Target

Authors: Jared Coleman, Evangelos Kranakis, Danny Krizanc, and Oscar Morales-Ponce

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)

Abstract
Consider search on an infinite line involving an autonomous robot starting at the origin of the line and an oblivious moving target at initial distance d ≥ 1 from it. The robot can change direction and move anywhere on the line with constant maximum speed 1 while the target is also moving on the line with constant speed v > 0 but is unable to change its speed or direction. The goal is for the robot to catch up to the target in as little time as possible. The classic case where v = 0 and the target’s initial distance d is unknown to the robot is the well-studied "cow-path problem". Alpert and Gal [Steve Alpern and Shmuel Gal, 2003] gave an optimal algorithm for the case where a target with unknown initial distance d is moving away from the robot with a known speed v < 1. In this paper we design and analyze search algorithms for the remaining possible knowledge situations, namely, when d and v are known, when v is known but d is unknown, when d is known but v is unknown, and when both v and d are unknown. Furthermore, for each of these knowledge models we consider separately the case where the target is moving away from the origin and the case where it is moving toward the origin. We design algorithms and analyze competitive ratios for all eight cases above. The resulting competitive ratios are shown to be optimal when the target is moving towards the origin as well as when v is known and the target is moving away from the origin.
Cite as

Jared Coleman, Evangelos Kranakis, Danny Krizanc, and Oscar Morales-Ponce. Line Search for an Oblivious Moving Target. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 12:1-12:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{coleman_et_al:LIPIcs.OPODIS.2022.12,
  author =	{Coleman, Jared and Kranakis, Evangelos and Krizanc, Danny and Morales-Ponce, Oscar},
  title =	{{Line Search for an Oblivious Moving Target}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{12:1--12:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.12},
  URN =		{urn:nbn:de:0030-drops-176325},
  doi =		{10.4230/LIPIcs.OPODIS.2022.12},
  annote =	{Keywords: Infinite Line, Knowledge, Oblivious, Robot, Search, Search-Time, Speed, Target}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.19
Evacuation from a Disk for Robots with Asymmetric Communication

Authors: Konstantinos Georgiou, Nikos Giachoudis, and Evangelos Kranakis

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
We consider evacuation of two robots from an Exit placed at an unknown location on the perimeter of a unit (radius) disk. The robots can move with max speed 1 and start at the center of the disk at the same time. We consider a new communication model, known as the SR model, in which the robots have communication faults as follows: one of the robots is a Sender and can only send wirelessly at any distance, while the other is a Receiver in that it can only receive wirelessly from any distance. The communication status of each robot is known to the other robot. In addition, both robots can exchange messages when they are co-located, which is known as Face-to-Face (F2F) model. There have been several studies in the literature concerning the evacuation time when both robots may employ either F2F or Wireless (WiFi) communication. The SR communication model diverges from these two in that the two robots themselves have differing communication capabilities. We study the evacuation time, namely the time it takes until the last robot reaches the Exit, and show that the evacuation time in the SR model is strictly between the F2F and the WiFi models. The main part of our technical contribution is also an evacuation algorithm in which two cooperating robots accomplish the task in worst-case time at most π+2. Interesting features of the proposed algorithm are the asymmetry inherent in the resulting trajectories, as well as that the robots do not move at full speed for the entire duration of their trajectories.
Cite as

Konstantinos Georgiou, Nikos Giachoudis, and Evangelos Kranakis. Evacuation from a Disk for Robots with Asymmetric Communication. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{georgiou_et_al:LIPIcs.ISAAC.2022.19,
  author =	{Georgiou, Konstantinos and Giachoudis, Nikos and Kranakis, Evangelos},
  title =	{{Evacuation from a Disk for Robots with Asymmetric Communication}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{19:1--19:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.19},
  URN =		{urn:nbn:de:0030-drops-173047},
  doi =		{10.4230/LIPIcs.ISAAC.2022.19},
  annote =	{Keywords: Communication, Cycle, Evacuation, Receiver, Sender, Mobile Agents}
}
Document
DOI: 10.4230/LITES.8.2.2
Swarms of Mobile Robots: Towards Versatility with Safety

Authors: Pierre Courtieu, Lionel Rieg, Sébastien Tixeuil, and Xavier Urbain

Published in: LITES, Volume 8, Issue 2 (2022): Special Issue on Distributed Hybrid Systems. Leibniz Transactions on Embedded Systems, Volume 8, Issue 2

Abstract
We present Pactole, a formal framework to design and prove the correctness of protocols (or the impossibility of their existence) that target mobile robotic swarms. Unlike previous approaches, our methodology unifies in a single formalism the execution model, the problem specification, the protocol, and its proof of correctness. The Pactole framework makes use of the Coq proof assistant, and is specially targeted at protocol designers and problem specifiers, so that a common unambiguous language is used from the very early stages of protocol development. We stress the underlying framework design principles to enable high expressivity and modularity, and provide concrete examples about how the Pactole framework can be used to tackle actual problems, some previously addressed by the Distributed Computing community, but also new problems, while being certified correct.
Cite as

Pierre Courtieu, Lionel Rieg, Sébastien Tixeuil, and Xavier Urbain. Swarms of Mobile Robots: Towards Versatility with Safety. In LITES, Volume 8, Issue 2 (2022): Special Issue on Distributed Hybrid Systems. Leibniz Transactions on Embedded Systems, Volume 8, Issue 2, pp. 02:1-02:36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{courtieu_et_al:LITES.8.2.2,
  author =	{Courtieu, Pierre and Rieg, Lionel and Tixeuil, S\'{e}bastien and Urbain, Xavier},
  title =	{{Swarms of Mobile Robots: Towards Versatility with Safety}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{02:1--02:36},
  ISSN =	{2199-2002},
  year =	{2022},
  volume =	{8},
  number =	{2},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES.8.2.2},
  URN =		{urn:nbn:de:0030-drops-192942},
  doi =		{10.4230/LITES.8.2.2},
  annote =	{Keywords: distributed algorithm, mobile autonomous robots, formal proof}
}
  • Refine by Type
  • 21 Document/PDF
  • 12 Document/HTML

  • Refine by Publication Year
  • 2 2026
  • 10 2025
  • 1 2023
  • 2 2022
  • 1 2021
  • Show More...

  • Refine by Author
  • 8 Kranakis, Evangelos
  • 5 Czyzowicz, Jurek
  • 5 Killick, Ryan
  • 5 Krizanc, Danny
  • 4 Georgiou, Konstantinos
  • Show More...

  • Refine by Series/Journal
  • 18 LIPIcs
  • 2 OASIcs
  • 1 LITES

  • Refine by Classification
  • 7 Theory of computation → Distributed algorithms
  • 3 Computing methodologies → Mobile agents
  • 2 Theory of computation → Design and analysis of algorithms
  • 2 Theory of computation → Online algorithms
  • 2 Theory of computation → Randomness, geometry and discrete structures
  • Show More...

  • Refine by Keyword
  • 4 Evacuation
  • 4 Search
  • 3 rendezvous
  • 2 Communication
  • 2 Cycle
  • 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