53 Search Results for "W�chter, Thomas"

Document
DOI: 10.4230/LIPIcs.CSL.2024.32
Characterising and Verifying the Core in Concurrent Multi-Player Mean-Payoff Games

Authors: Julian Gutierrez, Anthony W. Lin, Muhammad Najib, Thomas Steeples, and Michael Wooldridge

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

Abstract
Concurrent multi-player mean-payoff games are important models for systems of agents with individual, non-dichotomous preferences. Whilst these games have been extensively studied in terms of their equilibria in non-cooperative settings, this paper explores an alternative solution concept: the core from cooperative game theory. This concept is particularly relevant for cooperative AI systems, as it enables the modelling of cooperation among agents, even when their goals are not fully aligned. Our contribution is twofold. First, we provide a characterisation of the core using discrete geometry techniques and establish a necessary and sufficient condition for its non-emptiness. We then use the characterisation to prove the existence of polynomial witnesses in the core. Second, we use the existence of such witnesses to solve key decision problems in rational verification and provide tight complexity bounds for the problem of checking whether some/every equilibrium in a game satisfies a given LTL or GR(1) specification. Our approach is general and can be adapted to handle other specifications expressed in various fragments of LTL without incurring additional computational costs.
Cite as

Julian Gutierrez, Anthony W. Lin, Muhammad Najib, Thomas Steeples, and Michael Wooldridge. Characterising and Verifying the Core in Concurrent Multi-Player Mean-Payoff Games. In 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 288, pp. 32:1-32:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gutierrez_et_al:LIPIcs.CSL.2024.32,
  author =	{Gutierrez, Julian and Lin, Anthony W. and Najib, Muhammad and Steeples, Thomas and Wooldridge, Michael},
  title =	{{Characterising and Verifying the Core in Concurrent Multi-Player Mean-Payoff Games}},
  booktitle =	{32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)},
  pages =	{32:1--32:25},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2024.32},
  URN =		{urn:nbn:de:0030-drops-196752},
  doi =		{10.4230/LIPIcs.CSL.2024.32},
  annote =	{Keywords: Concurrent games, multi-agent systems, temporal logic, game theory}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2024.67
Small Sunflowers and the Structure of Slice Rank Decompositions

Authors: Thomas Karam

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
Let d ≥ 3 be an integer. We show that whenever an order-d tensor admits d+1 decompositions according to Tao’s slice rank, if the linear subspaces spanned by their one-variable functions constitute a sunflower for each choice of special coordinate, then the tensor admits a decomposition where these linear subspaces are contained in the centers of these respective sunflowers. As an application, we deduce that for every nonnegative integer k and every finite field 𝔽 there exists an integer C(d,k,|𝔽|) such that every order-d tensor with slice rank k over 𝔽 admits at most C(d,k,|𝔽|) decompositions with length k, up to a class of transformations that can be easily described.
Cite as

Thomas Karam. Small Sunflowers and the Structure of Slice Rank Decompositions. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 67:1-67:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{karam:LIPIcs.ITCS.2024.67,
  author =	{Karam, Thomas},
  title =	{{Small Sunflowers and the Structure of Slice Rank Decompositions}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{67:1--67:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.67},
  URN =		{urn:nbn:de:0030-drops-195953},
  doi =		{10.4230/LIPIcs.ITCS.2024.67},
  annote =	{Keywords: Slice rank, tensors, sunflowers, decompositions}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.21
An Efficient Algorithm for Power Dominating Set

Authors: Thomas Bläsius and Max Göttlicher

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
The problem Power Dominating Set (PDS) is motivated by the placement of phasor measurement units to monitor electrical networks. It asks for a minimum set of vertices in a graph that observes all remaining vertices by exhaustively applying two observation rules. Our contribution is twofold. First, we determine the parameterized complexity of PDS by proving it is W[P]-complete when parameterized with respect to the solution size. We note that it was only known to be W[2]-hard before. Our second and main contribution is a new algorithm for PDS that efficiently solves practical instances. Our algorithm consists of two complementary parts. The first is a set of reduction rules for PDS that can also be used in conjunction with previously existing algorithms. The second is an algorithm for solving the remaining kernel based on the implicit hitting set approach. Our evaluation on a set of power grid instances from the literature shows that our solver outperforms previous state-of-the-art solvers for PDS by more than one order of magnitude on average. Furthermore, our algorithm can solve previously unsolved instances of continental scale within a few minutes.
Cite as

Thomas Bläsius and Max Göttlicher. An Efficient Algorithm for Power Dominating Set. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{blasius_et_al:LIPIcs.ESA.2023.21,
  author =	{Bl\"{a}sius, Thomas and G\"{o}ttlicher, Max},
  title =	{{An Efficient Algorithm for Power Dominating Set}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{21:1--21:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.21},
  URN =		{urn:nbn:de:0030-drops-186743},
  doi =		{10.4230/LIPIcs.ESA.2023.21},
  annote =	{Keywords: Power Dominating Set, Implicit Hitting Set, Parameterized Complexity, Reduction Rules}
}
Document
DOI: 10.4230/OASIcs.WCET.2023.1
Warp-Level CFG Construction for GPU Kernel WCET Analysis

Authors: Louison Jeanmougin, Pascal Sotin, Christine Rochange, and Thomas Carle

Published in: OASIcs, Volume 114, 21th International Workshop on Worst-Case Execution Time Analysis (WCET 2023)

Abstract
We present an abstract interpretation technique to automatically build a Control Flow Graph (CFG) representation of the execution of a GPU kernel. GPUs implement an inherently parallel execution model, in which threads are grouped within so-called warps that execute in lockstep. This execution model enables the representation of the execution of the threads of a warp as a single CFG. However, thread divergence may appear within a warp and its effect must be captured explicitly within the CFG. Our method builds the CFG of a warp by applying abstract interpretation on the assembly (Nvidia SASS) code of a kernel, and by maintaining an abstract representation of which threads within the warp agree on which values. This allows the method to detect precisely the points in the program where thread divergence may occur, and avoid spurious reactivation edges in the CFG. We apply our technique on benchmark kernels as a proof-of-concept, and generate IPET systems using the resulting CFGs.
Cite as

Louison Jeanmougin, Pascal Sotin, Christine Rochange, and Thomas Carle. Warp-Level CFG Construction for GPU Kernel WCET Analysis. In 21th International Workshop on Worst-Case Execution Time Analysis (WCET 2023). Open Access Series in Informatics (OASIcs), Volume 114, pp. 1:1-1:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{jeanmougin_et_al:OASIcs.WCET.2023.1,
  author =	{Jeanmougin, Louison and Sotin, Pascal and Rochange, Christine and Carle, Thomas},
  title =	{{Warp-Level CFG Construction for GPU Kernel WCET Analysis}},
  booktitle =	{21th International Workshop on Worst-Case Execution Time Analysis (WCET 2023)},
  pages =	{1:1--1:13},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-293-8},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{114},
  editor =	{W\"{a}gemann, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2023.1},
  URN =		{urn:nbn:de:0030-drops-184303},
  doi =		{10.4230/OASIcs.WCET.2023.1},
  annote =	{Keywords: Graphical Processing Unit (GPU), Control Flow Graphs (CFG), Worst-Case Execution Time (WCET), Program analysis}
}
Document
DOI: 10.4230/OASIcs.WCET.2023.2
Validation of Processor Timing Models Using Cycle-Accurate Timing Simulators

Authors: Alban Gruin, Thomas Carle, Christine Rochange, and Pascal Sainrat

Published in: OASIcs, Volume 114, 21th International Workshop on Worst-Case Execution Time Analysis (WCET 2023)

Abstract
We propose a workflow to help find errors in the processor models that are used to prove their timing predictability. Recently, several papers have modeled processor cores using formal models that represent how instructions progress through the pipeline in each execution cycle. However, such models grow with the complexity of the cores and they are built by hand, using a description of the core, usually the HDL-level code. Such a task is error-prone, and verifying that the model actually captures the core’s timing behavior is required, otherwise the proofs become useless. Our workflow simulates the execution of benchmark applications using the HDL specification of a core in order to extract timing information as well as other relevant information (e.g. cache miss events, branch mispredictions). This information is used to replay the execution in a simulator of the core timing model, and to determine whether or not the model accurately represents the execution timing of the instructions. To avoid writing the simulator by hand for each new core, or new variation of a core, we developed a compiler that translates the timing model of a core into a C++ program. We evaluated our approach on the open source MINOTAuR core and we show how it enabled us to detect and correct errors in its model.
Cite as

Alban Gruin, Thomas Carle, Christine Rochange, and Pascal Sainrat. Validation of Processor Timing Models Using Cycle-Accurate Timing Simulators. In 21th International Workshop on Worst-Case Execution Time Analysis (WCET 2023). Open Access Series in Informatics (OASIcs), Volume 114, pp. 2:1-2:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{gruin_et_al:OASIcs.WCET.2023.2,
  author =	{Gruin, Alban and Carle, Thomas and Rochange, Christine and Sainrat, Pascal},
  title =	{{Validation of Processor Timing Models Using Cycle-Accurate Timing Simulators}},
  booktitle =	{21th International Workshop on Worst-Case Execution Time Analysis (WCET 2023)},
  pages =	{2:1--2:12},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-293-8},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{114},
  editor =	{W\"{a}gemann, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2023.2},
  URN =		{urn:nbn:de:0030-drops-184319},
  doi =		{10.4230/OASIcs.WCET.2023.2},
  annote =	{Keywords: Processor model, timing predictability, simulator generation}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2023.120
Compositionality of Planar Perfect Matchings: A Universal and Complete Fragment of ZW-Calculus

Authors: Titouan Carette, Etienne Moutot, Thomas Perez, and Renaud Vilmart

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

Abstract
We exhibit a strong connection between the matchgate formalism introduced by Valiant and the ZW-calculus of Coecke and Kissinger. This connection provides a natural compositional framework for matchgate theory as well as a direct combinatorial interpretation of the diagrams of ZW-calculus through the perfect matchings of their underlying graphs. We identify a precise fragment of ZW-calculus, the planar W-calculus, that we prove to be complete and universal for matchgates, that are linear maps satisfying the matchgate identities. Computing scalars of the planar W-calculus corresponds to counting perfect matchings of planar graphs, and so can be carried in polynomial time using the FKT algorithm, making the planar W-calculus an efficiently simulable fragment of the ZW-calculus, in a similar way that the Clifford fragment is for ZX-calculus. This work opens new directions for the investigation of the combinatorial properties of ZW-calculus as well as the study of perfect matching counting through compositional diagrammatical technics.
Cite as

Titouan Carette, Etienne Moutot, Thomas Perez, and Renaud Vilmart. Compositionality of Planar Perfect Matchings: A Universal and Complete Fragment of ZW-Calculus. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 120:1-120:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{carette_et_al:LIPIcs.ICALP.2023.120,
  author =	{Carette, Titouan and Moutot, Etienne and Perez, Thomas and Vilmart, Renaud},
  title =	{{Compositionality of Planar Perfect Matchings: A Universal and Complete Fragment of ZW-Calculus}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{120:1--120:17},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.120},
  URN =		{urn:nbn:de:0030-drops-181726},
  doi =		{10.4230/LIPIcs.ICALP.2023.120},
  annote =	{Keywords: Perfect Matchings Counting, Quantum Computing, Matchgates, ZW-Calculus, String Diagrams, Completeness}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.32
When Ternary Triangulated Disc Packings Are Densest: Examples, Counter-Examples and Techniques

Authors: Thomas Fernique and Daria Pchelina

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
We consider ternary disc packings of the plane, i.e. the packings using discs of three different radii. Packings in which each "hole" is bounded by three pairwise tangent discs are called triangulated. Connelly conjectured that when such packings exist, one of them maximizes the proportion of the covered surface: this holds for unary and binary disc packings. For ternary packings, there are 164 pairs (r, s), 1 > r > s, allowing triangulated packings by discs of radii 1, r and s. In this paper, we enhance existing methods of dealing with maximal-density packings in order to study ternary triangulated packings. We prove that the conjecture holds for 31 triplets of disc radii and disprove it for 40 other triplets. Finally, we classify the remaining cases where our methods are not applicable. Our approach is based on the ideas present in the Hales' proof of the Kepler conjecture. Notably, our proof features local density redistribution based on computer search and interval arithmetic.
Cite as

Thomas Fernique and Daria Pchelina. When Ternary Triangulated Disc Packings Are Densest: Examples, Counter-Examples and Techniques. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 32:1-32:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{fernique_et_al:LIPIcs.SoCG.2023.32,
  author =	{Fernique, Thomas and Pchelina, Daria},
  title =	{{When Ternary Triangulated Disc Packings Are Densest: Examples, Counter-Examples and Techniques}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{32:1--32:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.32},
  URN =		{urn:nbn:de:0030-drops-178827},
  doi =		{10.4230/LIPIcs.SoCG.2023.32},
  annote =	{Keywords: Disc packing, density, interval arithmetic}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.45
The Localized Union-Of-Balls Bifiltration

Authors: Michael Kerber and Matthias Söls

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
We propose an extension of the classical union-of-balls filtration of persistent homology: fixing a point q, we focus our attention to a ball centered at q whose radius is controlled by a second scale parameter. We discuss an absolute variant, where the union is just restricted to the q-ball, and a relative variant where the homology of the q-ball relative to its boundary is considered. Interestingly, these natural constructions lead to bifiltered simplicial complexes which are not k-critical for any finite k. Nevertheless, we demonstrate that these bifiltrations can be computed exactly and efficiently, and we provide a prototypical implementation using the CGAL library. We also argue that some of the recent algorithmic advances for 2-parameter persistence (which usually assume k-criticality for some finite k) carry over to the ∞-critical case.
Cite as

Michael Kerber and Matthias Söls. The Localized Union-Of-Balls Bifiltration. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 45:1-45:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kerber_et_al:LIPIcs.SoCG.2023.45,
  author =	{Kerber, Michael and S\"{o}ls, Matthias},
  title =	{{The Localized Union-Of-Balls Bifiltration}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{45:1--45:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.45},
  URN =		{urn:nbn:de:0030-drops-178953},
  doi =		{10.4230/LIPIcs.SoCG.2023.45},
  annote =	{Keywords: Topological Data Analysis, Multi-Parameter Persistence, Persistent Local Homology}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2022.23
Geometry Meets Vectors: Approximation Algorithms for Multidimensional Packing

Authors: Arindam Khan, Eklavya Sharma, and K. V. N. Sreenivas

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract
We study the generalized multidimensional bin packing problem (GVBP) that generalizes both geometric packing and vector packing. Here, we are given n rectangular items where the i-th item has width w(i), height h(i), and d nonnegative weights v₁(i), v₂(i), …, v_d(i). Our goal is to get an axis-parallel non-overlapping packing of the items into square bins so that for all j ∈ [d], the sum of the j-th weight of items in each bin is at most 1. This is a natural problem arising in logistics, resource allocation, and scheduling. Despite being well-studied in practice, approximation algorithms for this problem have rarely been explored. We first obtain two simple algorithms for GVBP having asymptotic approximation ratios 6(d+1) and 3(1 + ln(d+1) + ε). We then extend the Round-and-Approx (R&A) framework [Bansal et al., 2009; Bansal and Khan, 2014] to wider classes of algorithms, and show how it can be adapted to GVBP. Using more sophisticated techniques, we obtain better approximation algorithms for GVBP, and we get further improvement by combining them with the R&A framework. This gives us an asymptotic approximation ratio of 2(1 + ln((d+4)/2)) + ε for GVBP, which improves to 2.919+ε for the special case of d = 1. We obtain further improvement when the items are allowed to be rotated. We also present algorithms for a generalization of GVBP where the items are high dimensional cuboids.
Cite as

Arindam Khan, Eklavya Sharma, and K. V. N. Sreenivas. Geometry Meets Vectors: Approximation Algorithms for Multidimensional Packing. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 23:1-23:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{khan_et_al:LIPIcs.FSTTCS.2022.23,
  author =	{Khan, Arindam and Sharma, Eklavya and Sreenivas, K. V. N.},
  title =	{{Geometry Meets Vectors: Approximation Algorithms for Multidimensional Packing}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{23:1--23:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.23},
  URN =		{urn:nbn:de:0030-drops-174151},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.23},
  annote =	{Keywords: Bin packing, rectangle packing, multidimensional packing, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.TQC.2022.3
The Parametrized Complexity of Quantum Verification

Authors: Srinivasan Arunachalam, Sergey Bravyi, Chinmay Nirkhe, and Bryan O'Gorman

Published in: LIPIcs, Volume 232, 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)

Abstract
We initiate the study of parameterized complexity of QMA problems in terms of the number of non-Clifford gates in the problem description. We show that for the problem of parameterized quantum circuit satisfiability, there exists a classical algorithm solving the problem with a runtime scaling exponentially in the number of non-Clifford gates but only polynomially with the system size. This result follows from our main result, that for any Clifford + t T-gate quantum circuit satisfiability problem, the search space of optimal witnesses can be reduced to a stabilizer subspace isomorphic to at most t qubits (independent of the system size). Furthermore, we derive new lower bounds on the T-count of circuit satisfiability instances and the T-count of the W-state assuming the classical exponential time hypothesis (ETH). Lastly, we explore the parameterized complexity of the quantum non-identity check problem.
Cite as

Srinivasan Arunachalam, Sergey Bravyi, Chinmay Nirkhe, and Bryan O'Gorman. The Parametrized Complexity of Quantum Verification. In 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 232, pp. 3:1-3:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{arunachalam_et_al:LIPIcs.TQC.2022.3,
  author =	{Arunachalam, Srinivasan and Bravyi, Sergey and Nirkhe, Chinmay and O'Gorman, Bryan},
  title =	{{The Parametrized Complexity of Quantum Verification}},
  booktitle =	{17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)},
  pages =	{3:1--3:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-237-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{232},
  editor =	{Le Gall, Fran\c{c}ois and Morimae, Tomoyuki},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2022.3},
  URN =		{urn:nbn:de:0030-drops-165104},
  doi =		{10.4230/LIPIcs.TQC.2022.3},
  annote =	{Keywords: parametrized complexity, quantum verification, QMA}
}
Document
DOI: 10.4230/LIPIcs.SAND.2022.15
Parameterized Temporal Exploration Problems

Authors: Thomas Erlebach and Jakob T. Spooner

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)

Abstract
In this paper we study the fixed-parameter tractability of the problem of deciding whether a given temporal graph 𝒢 admits a temporal walk that visits all vertices (temporal exploration) or, in some problem variants, a certain subset of the vertices. Formally, a temporal graph is a sequence 𝒢 = ⟨ G₁,..., G_L⟩ of graphs with V(G_t) = V(G) and E(G_t) ⊆ E(G) for all t ∈ [L] and some underlying graph G, and a temporal walk is a time-respecting sequence of edge-traversals. For the strict variant, in which edges must be traversed in strictly increasing timesteps, we give FPT algorithms for the problem of finding a temporal walk that visits a given set X of vertices, parameterized by |X|, and for the problem of finding a temporal walk that visits at least k distinct vertices in V, parameterized by k. For the non-strict variant, in which an arbitrary number of edges can be traversed in each timestep, we parameterize by the lifetime L of the input graph and provide an FPT algorithm for the temporal exploration problem. We also give additional FPT or W[2]-hardness results for further problem variants.
Cite as

Thomas Erlebach and Jakob T. Spooner. Parameterized Temporal Exploration Problems. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{erlebach_et_al:LIPIcs.SAND.2022.15,
  author =	{Erlebach, Thomas and Spooner, Jakob T.},
  title =	{{Parameterized Temporal Exploration Problems}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{15:1--15:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.15},
  URN =		{urn:nbn:de:0030-drops-159570},
  doi =		{10.4230/LIPIcs.SAND.2022.15},
  annote =	{Keywords: Temporal graphs, fixed-parameter tractability, parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.CP.2021.33
Learning TSP Requires Rethinking Generalization

Authors: Chaitanya K. Joshi, Quentin Cappart, Louis-Martin Rousseau, and Thomas Laurent

Published in: LIPIcs, Volume 210, 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)

Abstract
End-to-end training of neural network solvers for combinatorial optimization problems such as the Travelling Salesman Problem is intractable and inefficient beyond a few hundreds of nodes. While state-of-the-art Machine Learning approaches perform closely to classical solvers when trained on trivially small sizes, they are unable to generalize the learnt policy to larger instances of practical scales. Towards leveraging transfer learning to solve large-scale TSPs, this paper identifies inductive biases, model architectures and learning algorithms that promote generalization to instances larger than those seen in training. Our controlled experiments provide the first principled investigation into such zero-shot generalization, revealing that extrapolating beyond training data requires rethinking the neural combinatorial optimization pipeline, from network layers and learning paradigms to evaluation protocols.
Cite as

Chaitanya K. Joshi, Quentin Cappart, Louis-Martin Rousseau, and Thomas Laurent. Learning TSP Requires Rethinking Generalization. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 33:1-33:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{joshi_et_al:LIPIcs.CP.2021.33,
  author =	{Joshi, Chaitanya K. and Cappart, Quentin and Rousseau, Louis-Martin and Laurent, Thomas},
  title =	{{Learning TSP Requires Rethinking Generalization}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{33:1--33:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-211-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{210},
  editor =	{Michel, Laurent D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2021.33},
  URN =		{urn:nbn:de:0030-drops-153248},
  doi =		{10.4230/LIPIcs.CP.2021.33},
  annote =	{Keywords: Combinatorial Optimization, Travelling Salesman Problem, Graph Neural Networks, Deep Learning}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.59
The Complexity of Connectivity Problems in Forbidden-Transition Graphs And Edge-Colored Graphs

Authors: Thomas Bellitto, Shaohua Li, Karolina Okrasa, Marcin Pilipczuk, and Manuel Sorge

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
The notion of forbidden-transition graphs allows for a robust generalization of walks in graphs. In a forbidden-transition graph, every pair of edges incident to a common vertex is permitted or forbidden; a walk is compatible if all pairs of consecutive edges on the walk are permitted. Forbidden-transition graphs and related models have found applications in a variety of fields, such as routing in optical telecommunication networks, road networks, and bio-informatics. We initiate the study of fundamental connectivity problems from the point of view of parameterized complexity, including an in-depth study of tractability with regards to various graph-width parameters. Among several results, we prove that finding a simple compatible path between given endpoints in a forbidden-transition graph is W[1]-hard when parameterized by the vertex-deletion distance to a linear forest (so it is also hard when parameterized by pathwidth or treewidth). On the other hand, we show an algebraic trick that yields tractability when parameterized by treewidth of finding a properly colored Hamiltonian cycle in an edge-colored graph; properly colored walks in edge-colored graphs is one of the most studied special cases of compatible walks in forbidden-transition graphs.
Cite as

Thomas Bellitto, Shaohua Li, Karolina Okrasa, Marcin Pilipczuk, and Manuel Sorge. The Complexity of Connectivity Problems in Forbidden-Transition Graphs And Edge-Colored Graphs. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 59:1-59:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bellitto_et_al:LIPIcs.ISAAC.2020.59,
  author =	{Bellitto, Thomas and Li, Shaohua and Okrasa, Karolina and Pilipczuk, Marcin and Sorge, Manuel},
  title =	{{The Complexity of Connectivity Problems in Forbidden-Transition Graphs And Edge-Colored Graphs}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{59:1--59:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.59},
  URN =		{urn:nbn:de:0030-drops-134036},
  doi =		{10.4230/LIPIcs.ISAAC.2020.59},
  annote =	{Keywords: Graph algorithms, fixed-parameter tractability, parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.47
Fault Tolerant Subgraphs with Applications in Kernelization

Authors: William Lochet, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, Roohani Sharma, and Meirav Zehavi

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract
In the past decade, the design of fault tolerant data structures for networks has become a central topic of research. Particular attention has been given to the construction of a subgraph H of a given digraph D with as fewest arcs/vertices as possible such that, after the failure of any set F of at most k ≥ 1 arcs, testing whether D-F has a certain property P is equivalent to testing whether H-F has that property. Here, reachability (or, more generally, distance preservation) is the most basic requirement to maintain to ensure that the network functions properly. Given a vertex s ∈ V(D), Baswana et al. [STOC'16] presented a construction of H with O(2^kn) arcs in time O(2^{k}nm) where n=|V(D)| and m= |E(D)| such that for any vertex v ∈ V(D): if there exists a path from s to v in D-F, then there also exists a path from s to v in H-F. Additionally, they gave a tight matching lower bound. While the question of the improvement of the dependency on k arises for special classes of digraphs, an arguably more basic research direction concerns the dependency on n (for reachability between a pair of vertices s,t ∈ V(D)) - which are the largest classes of digraphs where the dependency on n can be made sublinear, logarithmic or even constant? Already for the simple classes of directed paths and tournaments, Ω(n) arcs are mandatory. Nevertheless, we prove that "almost acyclicity" suffices to eliminate the dependency on n entirely for a broad class of dense digraphs called bounded independence digraphs. Also, the dependence in k is only a polynomial factor for this class of digraphs. In fact, our sparsification procedure extends to preserve parity-based reachability. Additionally, it finds notable applications in Kernelization: we prove that the classic Directed Feedback Arc Set (DFAS) problem as well as Directed Edge Odd Cycle Transversal (DEOCT) (which, in sharp contrast to DFAS, is W[1]-hard on general digraphs) admit polynomial kernels on bounded independence digraphs. In fact, for any p ∈ N, we can design a polynomial kernel for the problem of hitting all cycles of length ℓ where (ℓ mod p = 1). As a complementary result, we prove that DEOCT is NP-hard on tournaments by establishing a combinatorial identity between the minimum size of a feedback arc set and the minimum size of an edge odd cycle transversal. In passing, we also improve upon the running time of the sub-exponential FPT algorithm for DFAS in digraphs of bounded independence number given by Misra et at. [FSTTCS 2018], and give the first sub-exponential FPT algorithm for DEOCT in digraphs of bounded independence number.
Cite as

William Lochet, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh, Roohani Sharma, and Meirav Zehavi. Fault Tolerant Subgraphs with Applications in Kernelization. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 47:1-47:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{lochet_et_al:LIPIcs.ITCS.2020.47,
  author =	{Lochet, William and Lokshtanov, Daniel and Misra, Pranabendu and Saurabh, Saket and Sharma, Roohani and Zehavi, Meirav},
  title =	{{Fault Tolerant Subgraphs with Applications in Kernelization}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{47:1--47:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.47},
  URN =		{urn:nbn:de:0030-drops-117326},
  doi =		{10.4230/LIPIcs.ITCS.2020.47},
  annote =	{Keywords: sparsification, kernelization, fault tolerant subgraphs, directed feedback arc set, directed edge odd cycle transversal, bounded independence number digraphs}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.85
Combinatorial Lower Bounds for 3-Query LDCs

Authors: Arnab Bhattacharyya, L. Sunil Chandran, and Suprovat Ghoshal

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract
A code is called a q-query locally decodable code (LDC) if there is a randomized decoding algorithm that, given an index i and a received word w close to an encoding of a message x, outputs x_i by querying only at most q coordinates of w. Understanding the tradeoffs between the dimension, length and query complexity of LDCs is a fascinating and unresolved research challenge. In particular, for 3-query binary LDC’s of dimension k and length n, the best known bounds are: 2^{k^o(1)} ≥ n ≥ Ω ̃(k²). In this work, we take a second look at binary 3-query LDCs. We investigate a class of 3-uniform hypergraphs that are equivalent to strong binary 3-query LDCs. We prove an upper bound on the number of edges in these hypergraphs, reproducing the known lower bound of Ω ̃(k²) for the length of strong 3-query LDCs. In contrast to previous work, our techniques are purely combinatorial and do not rely on a direct reduction to 2-query LDCs, opening up a potentially different approach to analyzing 3-query LDCs.
Cite as

Arnab Bhattacharyya, L. Sunil Chandran, and Suprovat Ghoshal. Combinatorial Lower Bounds for 3-Query LDCs. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 85:1-85:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bhattacharyya_et_al:LIPIcs.ITCS.2020.85,
  author =	{Bhattacharyya, Arnab and Chandran, L. Sunil and Ghoshal, Suprovat},
  title =	{{Combinatorial Lower Bounds for 3-Query LDCs}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{85:1--85:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.85},
  URN =		{urn:nbn:de:0030-drops-117704},
  doi =		{10.4230/LIPIcs.ITCS.2020.85},
  annote =	{Keywords: Coding theory, Graph theory, Hypergraphs}
}
  • Refine by Author
  • 3 Wadge, William W.
  • 2 Alexopoulou, Dimitra
  • 2 Bläsius, Thomas
  • 2 Bravyi, Sergey
  • 2 Carle, Thomas
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Computational geometry
  • 2 Theory of computation → Parameterized complexity and exact algorithms
  • 2 Theory of computation → Quantum computation theory
  • 1 Computer systems organization → Real-time systems
  • 1 Computing methodologies → Neural networks
  • Show More...

  • Refine by Keyword
  • 3 Quantum computing
  • 3 parameterized complexity
  • 2 Automata theory
  • 2 Cartesian programming
  • 2 Complexity
  • Show More...

  • Refine by Type
  • 53 document

  • Refine by Publication Year
  • 11 2008
  • 6 2023
  • 5 2011
  • 4 2012
  • 4 2015
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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