278 Search Results for "Dawar, Anuj"

Volume

LIPIcs, Volume 254

40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

STACS 2023, March 7-9, 2023, Hamburg, Germany

Editors: Petra Berenbrink, Patricia Bouyer, Anuj Dawar, and Mamadou Moustapha Kanté

Volume

LIPIcs, Volume 250

42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

FSTTCS 2022, December 18-20, 2022, IIT Madras, Chennai, India

Editors: Anuj Dawar and Venkatesan Guruswami

Volume

LIPIcs, Volume 168

47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference)

Editors: Artur Czumaj, Anuj Dawar, and Emanuela Merelli

Document
DOI: 10.4230/LIPIcs.CSL.2025.6
Equi-Rank Homomorphism Preservation Theorem on Finite Structures

Authors: Benjamin Rossman

Published in: LIPIcs, Volume 326, 33rd EACSL Annual Conference on Computer Science Logic (CSL 2025)

Abstract
The Homomorphism Preservation Theorem (HPT) of classical model theory states that a first-order sentence is preserved under homomorphisms if, and only if, it is equivalent to an existential-positive sentence. This theorem remains valid when restricted to finite structures, as demonstrated by the author in [Rossman, 2008; Rossman, 2017] via distinct model-theoretic and circuit-complexity based proofs. In this paper, we present a third (and significantly simpler) proof of the finitary HPT based on a generalized Cai-Fürer-Immerman construction. This method establishes a tight correspondence between syntactic parameters of a homomorphism-preserved sentence (quantifier rank, variable width, alternation height) and structural parameters of its minimal models (tree-width, tree-depth, decomposition height). Consequently, we prove a conjectured "equi-rank" version of the finitary HPT. In contrast, previous versions of the finitary HPT possess additional properties, but incur blow-ups in the quantifier rank of the equivalent existential-positive sentence.
Cite as

Benjamin Rossman. Equi-Rank Homomorphism Preservation Theorem on Finite Structures. In 33rd EACSL Annual Conference on Computer Science Logic (CSL 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 326, pp. 6:1-6:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{rossman:LIPIcs.CSL.2025.6,
  author =	{Rossman, Benjamin},
  title =	{{Equi-Rank Homomorphism Preservation Theorem on Finite Structures}},
  booktitle =	{33rd EACSL Annual Conference on Computer Science Logic (CSL 2025)},
  pages =	{6:1--6:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-362-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{326},
  editor =	{Endrullis, J\"{o}rg and Schmitz, Sylvain},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2025.6},
  URN =		{urn:nbn:de:0030-drops-227634},
  doi =		{10.4230/LIPIcs.CSL.2025.6},
  annote =	{Keywords: finite model theory, preservation theorems, quantifier rank}
}
Document
DOI: 10.4230/LIPIcs.CSL.2025.16
Undefinability of Approximation of 2-To-2 Games

Authors: Anuj Dawar and Bálint Molnár

Published in: LIPIcs, Volume 326, 33rd EACSL Annual Conference on Computer Science Logic (CSL 2025)

Abstract
Recent work by Atserias and Dawar [Albert Atserias and Anuj Dawar, 2019] and Tucker-Foltz [Jamie Tucker-Foltz, 2024] has established undefinability results in fixed-point logic with counting (FPC) corresponding to many classical complexity results from the hardness of approximation. In this line of work, NP-hardness results are turned into unconditional FPC undefinability results. We extend this work by showing the FPC undefinability of any constant factor approximation of weighted 2-to-2 games, based on the NP-hardness results of Khot, Minzer and Safra. Our result shows that the completely satisfiable 2-to-2 games are not FPC-separable from those that are not ε-satisfiable, for arbitrarily small ε. The perfect completeness of our inseparability is an improvement on the complexity result, as the NP-hardness of such a separation is still only conjectured. This perfect completeness enables us to show the FPC undefinability of other problems whose NP-hardness is conjectured. In particular, we are able to show that no FPC formula can separate the 3-colourable graphs from those that are not t-colourable, for any constant t.
Cite as

Anuj Dawar and Bálint Molnár. Undefinability of Approximation of 2-To-2 Games. In 33rd EACSL Annual Conference on Computer Science Logic (CSL 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 326, pp. 16:1-16:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dawar_et_al:LIPIcs.CSL.2025.16,
  author =	{Dawar, Anuj and Moln\'{a}r, B\'{a}lint},
  title =	{{Undefinability of Approximation of 2-To-2 Games}},
  booktitle =	{33rd EACSL Annual Conference on Computer Science Logic (CSL 2025)},
  pages =	{16:1--16:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-362-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{326},
  editor =	{Endrullis, J\"{o}rg and Schmitz, Sylvain},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2025.16},
  URN =		{urn:nbn:de:0030-drops-227735},
  doi =		{10.4230/LIPIcs.CSL.2025.16},
  annote =	{Keywords: Hardness of Approximation, Unique Games, Descriptive Complexity, Fixed-Point Logic with Counting}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2024.47
Preservation Theorems on Sparse Classes Revisited

Authors: Anuj Dawar and Ioannis Eleftheriadis

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

Abstract
We revisit the work studying homomorphism preservation for first-order logic in sparse classes of structures initiated in [Atserias et al., JACM 2006] and [Dawar, JCSS 2010]. These established that first-order logic has the homomorphism preservation property in any sparse class that is monotone and addable. It turns out that the assumption of addability is not strong enough for the proofs given. We demonstrate this by constructing classes of graphs of bounded treewidth which are monotone and addable but fail to have homomorphism preservation. We also show that homomorphism preservation fails on the class of planar graphs. On the other hand, the proofs of homomorphism preservation can be recovered by replacing addability by a stronger condition of amalgamation over bottlenecks. This is analogous to a similar condition formulated for extension preservation in [Atserias et al., SiCOMP 2008].
Cite as

Anuj Dawar and Ioannis Eleftheriadis. Preservation Theorems on Sparse Classes Revisited. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 47:1-47:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dawar_et_al:LIPIcs.MFCS.2024.47,
  author =	{Dawar, Anuj and Eleftheriadis, Ioannis},
  title =	{{Preservation Theorems on Sparse Classes Revisited}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{47:1--47:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.47},
  URN =		{urn:nbn:de:0030-drops-206036},
  doi =		{10.4230/LIPIcs.MFCS.2024.47},
  annote =	{Keywords: Homomorphism preservation, sparsity, finite model theory, planar graphs}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.ICALP.2024.1
Limits of Symmetric Computation (Invited Talk)

Authors: Anuj Dawar

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

Abstract
I survey recent work on symmetric computation. A number of strands of work, from logic, circuit complexity, combinatorial optimization and other areas have converged on similar notions of symmetry in computation. This write-up of an invited talk gives a whirlwind tour through the results and pointers to the relevant literature.
Cite as

Anuj Dawar. Limits of Symmetric Computation (Invited Talk). In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 1:1-1:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dawar:LIPIcs.ICALP.2024.1,
  author =	{Dawar, Anuj},
  title =	{{Limits of Symmetric Computation}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{1:1--1:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.1},
  URN =		{urn:nbn:de:0030-drops-201444},
  doi =		{10.4230/LIPIcs.ICALP.2024.1},
  annote =	{Keywords: Logic, Complexity Theory, Symmetric Computation}
}
Document
DOI: 10.4230/LIPIcs.CSL.2024.23
Quantifiers Closed Under Partial Polymorphisms

Authors: Anuj Dawar and Lauri Hella

Published in: LIPIcs, Volume 288, 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)

Abstract
We study Lindström quantifiers that satisfy certain closure properties which are motivated by the study of polymorphisms in the context of constraint satisfaction problems (CSP). When the algebra of polymorphisms of a finite structure 𝔅 satisfies certain equations, this gives rise to a natural closure condition on the class of structures that map homomorphically to 𝔅. The collection of quantifiers that satisfy closure conditions arising from a fixed set of equations are rather more general than those arising as CSP. For any such conditions 𝒫, we define a pebble game that delimits the distinguishing power of the infinitary logic with all quantifiers that are 𝒫-closed. We use the pebble game to show that the problem of deciding whether a system of linear equations is solvable in ℤ / 2ℤ is not expressible in the infinitary logic with all quantifiers closed under a near-unanimity condition.
Cite as

Anuj Dawar and Lauri Hella. Quantifiers Closed Under Partial Polymorphisms. In 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 288, pp. 23:1-23:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dawar_et_al:LIPIcs.CSL.2024.23,
  author =	{Dawar, Anuj and Hella, Lauri},
  title =	{{Quantifiers Closed Under Partial Polymorphisms}},
  booktitle =	{32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)},
  pages =	{23:1--23:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-310-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{288},
  editor =	{Murano, Aniello and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2024.23},
  URN =		{urn:nbn:de:0030-drops-196662},
  doi =		{10.4230/LIPIcs.CSL.2024.23},
  annote =	{Keywords: generalized quantifiers, constraint satisfaction problems, pebble games, finite variable logics, descriptive complexity theory}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2023.119
Monadic NIP in Monotone Classes of Relational Structures

Authors: Samuel Braunfeld, Anuj Dawar, Ioannis Eleftheriadis, and Aris Papadopoulos

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

Abstract
We prove that for any monotone class of finite relational structures, the first-order theory of the class is NIP in the sense of stability theory if, and only if, the collection of Gaifman graphs of structures in this class is nowhere dense. This generalises results previously known for graphs to relational structures and answers an open question posed by Adler and Adler (2014). The result is established by the application of Ramsey-theoretic techniques and shows that the property of being NIP is highly robust for monotone classes. We also show that the model-checking problem for first-order logic is intractable on any monotone class of structures that is not (monadically) NIP. This is a contribution towards the conjecture that the hereditary classes of structures admitting fixed-parameter tractable model-checking are precisely those that are monadically NIP.
Cite as

Samuel Braunfeld, Anuj Dawar, Ioannis Eleftheriadis, and Aris Papadopoulos. Monadic NIP in Monotone Classes of Relational Structures. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 119:1-119:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{braunfeld_et_al:LIPIcs.ICALP.2023.119,
  author =	{Braunfeld, Samuel and Dawar, Anuj and Eleftheriadis, Ioannis and Papadopoulos, Aris},
  title =	{{Monadic NIP in Monotone Classes of Relational Structures}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{119:1--119:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.119},
  URN =		{urn:nbn:de:0030-drops-181712},
  doi =		{10.4230/LIPIcs.ICALP.2023.119},
  annote =	{Keywords: Model theory, finite model theory, structural graph theory, model-checking}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.STACS.2023
LIPIcs, Volume 254, STACS 2023, Complete Volume

Authors: Petra Berenbrink, Patricia Bouyer, Anuj Dawar, and Mamadou Moustapha Kanté

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

Abstract
LIPIcs, Volume 254, STACS 2023, Complete Volume
Cite as

40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 1-1026, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Proceedings{berenbrink_et_al:LIPIcs.STACS.2023,
  title =	{{LIPIcs, Volume 254, STACS 2023, Complete Volume}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{1--1026},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023},
  URN =		{urn:nbn:de:0030-drops-176515},
  doi =		{10.4230/LIPIcs.STACS.2023},
  annote =	{Keywords: LIPIcs, Volume 254, STACS 2023, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.STACS.2023.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Petra Berenbrink, Patricia Bouyer, Anuj Dawar, and Mamadou Moustapha Kanté

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

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

40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 0:i-0:xxii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{berenbrink_et_al:LIPIcs.STACS.2023.0,
  author =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{0:i--0:xxii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.0},
  URN =		{urn:nbn:de:0030-drops-176525},
  doi =		{10.4230/LIPIcs.STACS.2023.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.STACS.2023.1
A Brief History of History-Determinism (Invited Talk)

Authors: Karoliina Lehtinen

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

Abstract
Most nondeterministic automata models are more expressive, or at least more succinct, than their deterministic counterparts; however, this comes at a cost, as deterministic automata tend to have better algorithmic properties. History-deterministic automata are an intermediate model that allows a restricted form of nondeterminism: all nondeterministic choices must be resolvable on-the-fly, with only the knowledge of the word prefix read so far - as opposed to general nondeterminism, which allows for guessing the future of the word. History-deterministic automata combine some of the algorithmic benefits of determinism with some of the increased power of nondeterminism, thus enjoying (some of) the best of both worlds. History-determinism, as it is understood today, has its roots in several independently invented notions: Kupferman, Safra and Vardi’s automata recognising tree languages derived from word languages [Kupferman et al., 2006] (a notion that has been later referred to as automata that are good-for-trees [Udi Boker et al., 2013]), Henzinger and Piterman’s good-for-games automata [Thomas Henzinger and Nir Piterman, 2006], and Colcombet’s history-deterministic automata, introduced in his work on regular cost-automata [Colcombet, 2009]. In the ω-regular setting, where they were initially most studied, the notions of good-for-trees, good-for-games and history-determinism are equivalent, despite differences in their definitions. The key algorithmic appeal of these automata is that like deterministic automata, they have good compositional properties. This makes them particularly useful for applications such as reactive synthesis, where composition of games and automata is at the heart of effective solutions. Since then, history-determinism has received its fair share of attention, not least because of its relevance to synthesis. Indeed it turns out to be a natural and useful form of nondeterminism more broadly, and can be generalised to all sorts of different automata models: alternating automata [Udi Boker and Karoliina Lehtinen, 2019], pushdown automata [Enzo Erlich et al., 2022; Enzo Erlich et al., 2022], timed automata [Thomas A. Henzinger et al., 2022; Sougata Bose et al., 2022], Parikh automata [Enzo Erlich et al., 2022], and quantiative automata [Udi Boker and Karoliina Lehtinen, 2021], to name a few. In each of these models, history-determinism offers some trade-offs between the power of nondeterminism and the algorithmic properties of determinism. In particular, depending on the model, they can be either more expressive or more succinct than their deterministic counterparts, while retaining better algorithmic properties - in particular with respect to deciding universality, language inclusion and games - than fully nondeterministic automata. The drive to extend history-determinism to more powerful automata models has also lead to a better understanding of the properties of these automata, of how they compare to related notions (such as good-for-games automata and determinisability by pruning), and of the various games and tools used to study them. This talk aims to give a broad introduction to the notion of history determinism as well as an overview of some of the recent developements on the topic. It will also highlight some of the many problems that remain open. It is loosely based on a recent survey, written jointly with Udi Boker, which gives an informal presentation of what are, in our view, the key aspects of history-determinism [Udi Boker and Karoliina Lehtinen, 2023].
Cite as

Karoliina Lehtinen. A Brief History of History-Determinism (Invited Talk). In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 1:1-1:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{lehtinen:LIPIcs.STACS.2023.1,
  author =	{Lehtinen, Karoliina},
  title =	{{A Brief History of History-Determinism}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{1:1--1:2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.1},
  URN =		{urn:nbn:de:0030-drops-176535},
  doi =		{10.4230/LIPIcs.STACS.2023.1},
  annote =	{Keywords: History-determinism, nondeterminism, automata, good-for-games}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.STACS.2023.2
Amortised Analysis of Dynamic Data Structures (Invited Talk)

Authors: Eva Rotenberg

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

Abstract
In dynamic data structures, one is interested in efficiently facilitating queries to a data set, while being able to efficiently perform updates as the data set undergoes changes. Often, relaxing the efficiency measure to the amortised setting allows for simpler algorithms. A well-known example of a data structure with amortised guarantees is the splay tree by Sleator and Tarjan [Daniel D. Sleator and Robert E. Tarjan, 1985]. Similarly, in data structures for dynamic graphs, one is interested in efficiently maintaining some information about the graph, or facilitating queries, as the graph undergoes changes in the form of insertion and deletion of edges. Examples of such information include connectivity, planarity, and approximate sparsity of the graph: is the graph presently connected? Is it planar? Has its arboricity grossly exceeded some specified number α̃? The related queries could be: is a connected to b? Are the edges uv and uw consecutive in the ordering around u in its current planar embedding? Or, report the O(α) out-edges of vertex x. In this talk, we will see Brodal and Fagerberg’s amortised algorithm for orienting sparse graphs (i.e. of arboricity ≤ α), so that each vertex has O(α) out-edges [Gerth Stølting Brodal and Rolf Fagerberg, 1999]. The algorithm itself is extremely simple, and uses an elegant amortised argument in its analysis. Then, we will visit the problem of dynamic planarity testing: is the graph presently planar? Here, we will see an elegant amortised reduction to the seemingly easier problem, where planarity-violating edges may be detected and rejected [Eppstein et al., 1996]. We will see a sketch of how the current state-of-the-art algorithm for efficient planarity testing [Jacob Holm and Eva Rotenberg, 2020] uses ideas similar to those in [Gerth Stølting Brodal and Rolf Fagerberg, 1999] to analyse the behaviour of a greedy algorithm via a possibly inefficient algorithm with provably low recourse [Jacob Holm and Eva Rotenberg, 2020]. If time permits, we will touch upon a recent simple amortised data structure for maintaining information in dynamic forests [Jacob Holm et al., 2023], which builds on ideas from splay trees. The talk concludes with some open questions in the area.
Cite as

Eva Rotenberg. Amortised Analysis of Dynamic Data Structures (Invited Talk). In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 2:1-2:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{rotenberg:LIPIcs.STACS.2023.2,
  author =	{Rotenberg, Eva},
  title =	{{Amortised Analysis of Dynamic Data Structures}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{2:1--2:2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.2},
  URN =		{urn:nbn:de:0030-drops-176547},
  doi =		{10.4230/LIPIcs.STACS.2023.2},
  annote =	{Keywords: Amortised analysis, splaying, dynamic graphs, planarity testing}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.STACS.2023.3
Logical Algorithmics: From Theory to Practice (Invited Talk)

Authors: Moshe Y. Vardi

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

Abstract
The standard approach to algorithm development is to focus on a specific problem and develop for it a specific algorithm. Codd’s introduction of the relational model in 1970 included two fundamental ideas: (1) Relations provide a universal data representation formalism, and (2) Relational databases can be queried using first-order logic. Realizing these ideas required the development of a meta-algorithm, which takes a declarative query and executes it with respect to a database. In this talk, I will describe this approach, which I call Logical Algorithmics, in detail, and explore its profound ramification.
Cite as

Moshe Y. Vardi. Logical Algorithmics: From Theory to Practice (Invited Talk). In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{vardi:LIPIcs.STACS.2023.3,
  author =	{Vardi, Moshe Y.},
  title =	{{Logical Algorithmics: From Theory to Practice}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{3:1--3:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.3},
  URN =		{urn:nbn:de:0030-drops-176555},
  doi =		{10.4230/LIPIcs.STACS.2023.3},
  annote =	{Keywords: Logic, Algorithms}
}
Document
DOI: 10.4230/LIPIcs.STACS.2023.4
The Complexity of Checking Quasi-Identities over Finite Algebras with a Mal'cev Term

Authors: Erhard Aichinger and Simon Grünbacher

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

Abstract
We consider finite algebraic structures and ask whether every solution of a given system of equations satisfies some other equation. This can be formulated as checking the validity of certain first order formulae called quasi-identities. Checking the validity of quasi-identities is closely linked to solving systems of equations. For systems of equations over finite algebras with finitely many fundamental operations, a complete P/NPC dichotomy is known, while the situation appears to be more complicated for single equations. The complexity of checking the validity of a quasi-identity lies between the complexity of term equivalence (checking whether two terms induce the same function) and the complexity of solving systems of polynomial equations. We prove that for each finite algebra with a Mal'cev term and finitely many fundamental operations, checking the validity of quasi-identities is coNP-complete if the algebra is not abelian, and in P when the algebra is abelian.
Cite as

Erhard Aichinger and Simon Grünbacher. The Complexity of Checking Quasi-Identities over Finite Algebras with a Mal'cev Term. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 4:1-4:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{aichinger_et_al:LIPIcs.STACS.2023.4,
  author =	{Aichinger, Erhard and Gr\"{u}nbacher, Simon},
  title =	{{The Complexity of Checking Quasi-Identities over Finite Algebras with a Mal'cev Term}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{4:1--4:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.4},
  URN =		{urn:nbn:de:0030-drops-176560},
  doi =		{10.4230/LIPIcs.STACS.2023.4},
  annote =	{Keywords: quasi-identities, conditional identities, systems of equations}
}
  • Refine by Author
  • 34 Dawar, Anuj
  • 4 Bouyer, Patricia
  • 4 Panigrahi, Debmalya
  • 4 Pilipczuk, Michał
  • 4 Zetzsche, Georg
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 8 finite model theory
  • 5 Approximation algorithms
  • 5 Complexity
  • 5 hardness of approximation
  • 4 Algorithms
  • Show More...

  • Refine by Type
  • 275 document
  • 3 volume

  • Refine by Publication Year
  • 145 2020
  • 59 2023
  • 50 2022
  • 3 2015
  • 3 2018
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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