62 Search Results for "M�dche, Alexander"


Document
PACE Solver Description
PACE Solver Description: Exact (GUTHMI) and Heuristic (GUTHM)

Authors: Alexander Leonhardt, Holger Dell, Anselm Haak, Frank Kammer, Johannes Meintrup, Ulrich Meyer, and Manuel Penschuck

Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)


Abstract
Twin-width (tww) is a parameter measuring the similarity of an undirected graph to a co-graph [Édouard Bonnet et al., 2022]. It is useful to analyze the parameterized complexity of various graph problems. This paper presents two algorithms to compute the twin-width and to provide a contraction sequence as witness. The two algorithms are motivated by the PACE 2023 challenge, one for the exact track and one for the heuristic track. Each algorithm produces a contraction sequence witnessing (i) the minimal twin-width admissible by the graph in the exact track (ii) an upper bound on the twin-width as tight as possible in the heuristic track. Our heuristic algorithm relies on several greedy approaches with different performance characteristics to find and improve solutions. For large graphs we use locality sensitive hashing to approximately identify suitable contraction candidates. The exact solver follows a branch-and-bound design. It relies on the heuristic algorithm to provide initial upper bounds, and uses lower bounds via contraction sequences to show the optimality of a heuristic solution found in some branch.

Cite as

Alexander Leonhardt, Holger Dell, Anselm Haak, Frank Kammer, Johannes Meintrup, Ulrich Meyer, and Manuel Penschuck. PACE Solver Description: Exact (GUTHMI) and Heuristic (GUTHM). In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 37:1-37:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{leonhardt_et_al:LIPIcs.IPEC.2023.37,
  author =	{Leonhardt, Alexander and Dell, Holger and Haak, Anselm and Kammer, Frank and Meintrup, Johannes and Meyer, Ulrich and Penschuck, Manuel},
  title =	{{PACE Solver Description: Exact (GUTHMI) and Heuristic (GUTHM)}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{37:1--37:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.37},
  URN =		{urn:nbn:de:0030-drops-194563},
  doi =		{10.4230/LIPIcs.IPEC.2023.37},
  annote =	{Keywords: PACE 2023 Challenge, Heuristic, Exact, Twin-Width}
}
Document
PACE Solver Description
PACE Solver Description: Touiouidth

Authors: Gaétan Berthe, Yoann Coudert-Osmont, Alexander Dobler, Laure Morelle, Amadeus Reinald, and Mathis Rocton

Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)


Abstract
We describe Touiouidth, a twin-width solver for the exact-track of the 2023 PACE Challenge: Twin Width. Our solver is based on a simple branch and bound algorithm with search space reductions and is implemented in C++.

Cite as

Gaétan Berthe, Yoann Coudert-Osmont, Alexander Dobler, Laure Morelle, Amadeus Reinald, and Mathis Rocton. PACE Solver Description: Touiouidth. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 38:1-38:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{berthe_et_al:LIPIcs.IPEC.2023.38,
  author =	{Berthe, Ga\'{e}tan and Coudert-Osmont, Yoann and Dobler, Alexander and Morelle, Laure and Reinald, Amadeus and Rocton, Mathis},
  title =	{{PACE Solver Description: Touiouidth}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{38:1--38:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.38},
  URN =		{urn:nbn:de:0030-drops-194576},
  doi =		{10.4230/LIPIcs.IPEC.2023.38},
  annote =	{Keywords: Twinwidth, Pace Challenge}
}
Document
Non-Clairvoyant Makespan Minimization Scheduling with Predictions

Authors: Evripidis Bampis, Alexander Kononov, Giorgio Lucarelli, and Fanny Pascual

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)


Abstract
We revisit the classical non-clairvoyant problem of scheduling a set of n jobs on a set of m parallel identical machines where the processing time of a job is not known until the job finishes. Our objective is the minimization of the makespan, i.e., the date at which the last job terminates its execution. We adopt the framework of learning-augmented algorithms and we study the question of whether (possibly erroneous) predictions may help design algorithms with a competitive ratio which is good when the prediction is accurate (consistency), deteriorates gradually with respect to the prediction error (smoothness), and not too bad and bounded when the prediction is arbitrarily bad (robustness). We first consider the non-preemptive case and we devise lower bounds, as a function of the error of the prediction, for any deterministic learning-augmented algorithm. Then we analyze a variant of Longest Processing Time first (LPT) algorithm (with and without release dates) and we prove that it is consistent, smooth, and robust. Furthermore, we study the preemptive case and we provide lower bounds for any deterministic algorithm with predictions as a function of the prediction error. Finally, we introduce a variant of the classical Round Robin algorithm (RR), the Predicted Proportional Round Robin algorithm (PPRR), which we prove to be consistent, smooth and robust.

Cite as

Evripidis Bampis, Alexander Kononov, Giorgio Lucarelli, and Fanny Pascual. Non-Clairvoyant Makespan Minimization Scheduling with Predictions. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 9:1-9:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{bampis_et_al:LIPIcs.ISAAC.2023.9,
  author =	{Bampis, Evripidis and Kononov, Alexander and Lucarelli, Giorgio and Pascual, Fanny},
  title =	{{Non-Clairvoyant Makespan Minimization Scheduling with Predictions}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{9:1--9:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.9},
  URN =		{urn:nbn:de:0030-drops-193114},
  doi =		{10.4230/LIPIcs.ISAAC.2023.9},
  annote =	{Keywords: scheduling, online, learning-augmented algorithm}
}
Document
Exploiting Configurations of MaxSAT Solvers

Authors: Josep Alòs, Carlos Ansótegui, Josep M. Salvia, and Eduard Torres

Published in: LIPIcs, Volume 280, 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)


Abstract
In this paper, we describe how we can effectively exploit alternative parameter configurations to a MaxSAT solver. We describe how these configurations can be computed in the context of MaxSAT. In particular, we experimentally show how to easily combine configurations of a non-competitive solver to obtain a better solving approach.

Cite as

Josep Alòs, Carlos Ansótegui, Josep M. Salvia, and Eduard Torres. Exploiting Configurations of MaxSAT Solvers. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{alos_et_al:LIPIcs.CP.2023.7,
  author =	{Al\`{o}s, Josep and Ans\'{o}tegui, Carlos and Salvia, Josep M. and Torres, Eduard},
  title =	{{Exploiting Configurations of MaxSAT Solvers}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{7:1--7:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-300-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{280},
  editor =	{Yap, Roland H. C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.7},
  URN =		{urn:nbn:de:0030-drops-190443},
  doi =		{10.4230/LIPIcs.CP.2023.7},
  annote =	{Keywords: maximum satisfiability, maxsat evaluation, automatic configuration}
}
Document
The Calculus of Temporal Influence

Authors: Florian Bruse, Marit Kastaun, Martin Lange, and Sören Möller

Published in: LIPIcs, Volume 278, 30th International Symposium on Temporal Representation and Reasoning (TIME 2023)


Abstract
We present the Calculus of Temporal Influence, a simple logical calculus that allows reasoning about the behaviour of real-valued functions over time by making assertions that bound their values or the values of their derivatives. The motivation for the design of such a proof system comes from the need to provide the background computational machinery for tools that support learning in experimental subjects in secondary-education classrooms. The end goal is a tool that allows school pupils to formalise hypotheses about phenomena in natural sciences, such that their validity with respect to some formal experiment model can be checked automatically. The Calculus of Temporal Influence provides a language for formal statements and the mechanisms for reasoning about valid logical consequences. It extends (and deviates in parts from) previous work introducing the Calculus of (Non-Temporal) Influence by integrating the ability to model temporal effects in such experiments. We show that reasoning in the calculus is sound with respect to a natural formal semantics, that logical consequence is at least semi-decidable, and that one obtains polynomial-time decidability for a natural stratification of the problem.

Cite as

Florian Bruse, Marit Kastaun, Martin Lange, and Sören Möller. The Calculus of Temporal Influence. In 30th International Symposium on Temporal Representation and Reasoning (TIME 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 278, pp. 10:1-10:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{bruse_et_al:LIPIcs.TIME.2023.10,
  author =	{Bruse, Florian and Kastaun, Marit and Lange, Martin and M\"{o}ller, S\"{o}ren},
  title =	{{The Calculus of Temporal Influence}},
  booktitle =	{30th International Symposium on Temporal Representation and Reasoning (TIME 2023)},
  pages =	{10:1--10:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-298-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{278},
  editor =	{Artikis, Alexander and Bruse, Florian and Hunsberger, Luke},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2023.10},
  URN =		{urn:nbn:de:0030-drops-191009},
  doi =		{10.4230/LIPIcs.TIME.2023.10},
  annote =	{Keywords: temporal reasoning, formal models, continuous functions, polynomial decidability}
}
Document
Extended Abstract
Converting Simple Temporal Networks with Uncertainty into Dispatchable Form - Faster (Extended Abstract)

Authors: Luke Hunsberger and Roberto Posenato

Published in: LIPIcs, Volume 278, 30th International Symposium on Temporal Representation and Reasoning (TIME 2023)


Abstract
In many sectors of real-world industry, it is necessary to plan and schedule tasks allocated to agents participating in complex processes. Temporal planning aims to schedule tasks while respecting temporal constraints such as release times, maximum durations, and deadlines, which requires quantitative temporal reasoning. Over the years, several major application developers have highlighted the need for the explicit representation of actions with uncertain durations; efficient algorithms for determining whether plans involving such actions are controllable; and efficient algorithms for converting such plans into forms that enable them to be executed in real time with minimal computation, while preserving maximum flexibility. A Simple Temporal Network with Uncertainty (STNU) is a data structure for reasoning about time constraints on actions that may have uncertain durations. An STNU is a triple (𝒯, 𝒞, ℒ) where 𝒯 is a set of real-valued variables called timepoints, 𝒞 is a set of constraints of the form Y-X ≤ δ, where X, Y ∈ 𝒯 and δ ∈ 𝐑, and ℒ is a set of contingent links of the form (A,x,y,C), where A,C ∈ 𝒯 and 0 < x < y < ∞. A contingent link (A,x,y,C) represents an uncertain duration where A is the activation timepoint, C is the contingent timepoint, and y-x is the uncertainty in the duration C-A. Typically, an executor controls the execution of A, but only observes the execution of C in real time. Although uncontrollable, the duration is guaranteed to satisfy C-A ∈ [x,y]. We let n = |𝒯|, m = |𝒞| and k = |ℒ|. An STNU graph is a pair (𝒯, ℰ), where the timepoints in 𝒯 serve as nodes in the graph, and the edges in ℰ correspond to the constraints in 𝒞 and contingent links in ℒ. For each Y-X ≤ δ in 𝒞, ℰ contains an ordinary edge X-δ->Y. For each (A,x,y,C) ∈ ℒ, ℰ contains a lower-case (LC) edge, A-c:y->C, and an upper-case (UC) edge, C-C:-y->A, representing the respective possibilities that C-A might take its minimum or maximum value. The LO-edges are the LC or ordinary edges; the OU-edges are the ordinary or UC edges. For any STNU, it is important to determine whether it is dynamically controllable (DC) (i.e., whether it is possible, in real time, to schedule its non-contingent timepoints such that all constraints will necessarily be satisfied no matter what durations turn out for the contingent links). Polynomial-time algorithms are available to solve this DC-checking problem. Each uses rules to generate new edges aiming to bypass certain kinds of edges in the STNU graph. Morris' O(n⁴)-time DC-checking algorithm [Paul Morris, 2006] starts from LC edges, propagating forward along OU-edges, looking for opportunities to generate new OU-edges that bypass the LC edges. Morris' O(n³)-time algorithm [Morris, 2014] starts from negative OU-edges, propagating backward along LO-edges, aiming to bypass negative edges with non-negative edges. The O(mn+k²n + knlog n)-time RUL¯ algorithm [Massimo Cairo et al., 2018] starts from UC edges, propagating backward along LO-edges, aiming to bypass UC edges with ordinary edges. After propagating, each algorithm checks for certain kinds of negative cycles to decide DC-vs.-non-DC. However, being DC only asserts the existence of a dynamic scheduler. It is also crucial to be able to execute a DC STNU efficiently in real time. For maximum flexibility and minimal space and time requirements, a dynamic scheduler for an STNU is typically computed incrementally, in real time, so that it can react to observations of contingent executions as they occur. An efficient dynamic scheduler can be realized by first transforming an STNU into an equivalent dispatchable form [Muscettola et al., 1998; Ioannis Tsamardinos et al., 1998]. Then, to execute the dispatchable STNU, it suffices to maintain time-windows for each timepoint and, as each timepoint X is executed, only updating time-windows for neighbors of X in the graph. Dispatchable STNUs are very important in applications that demand quick responses to observations of contingent events. Of the existing DC-checking algorithms, only Morris' O(n³)-time algorithm necessarily generates a dispatchable STNU for DC inputs. This abstract describes a faster, O(mn + kn² + n² log n)-time algorithm for converting DC STNUs into dispatchable form. (The full journal article is available elsewhere [Luke Hunsberger and Roberto Posenato, 2023].) This improvement is significant for applications (e.g., modeling business processes) where networks are typically sparse. For example, if m = O(n log n) and k = O(log n), then our algorithm runs in O(n²log n) ≪ O(n³) time. Our new Fast Dispatch algorithm, FD_STNU, has three phases. The first phase is similar to the RUL¯ DC-checking algorithm, but generates an order-of-magnitude fewer edges overall, while also generating new UC edges that correspond to wait constraints. The second phase is a version of Morris' 2006 algorithm that propagates forward from LC edges, but only along LO-edges, aiming to generate ordinary bypass edges. The third phase focuses on the subgraph of ordinary edges, which comprise a Simple Temporal Network (STN). It uses an existing dispatchability algorithm for STNs [Ioannis Tsamardinos et al., 1998] to convert that ordinary subgraph into a dispatchable STN. After completing the three phases, the STNU is guaranteed to be dispatchable. We provide the source code of a Java implementation of the considered algorithms (Morris, RUL¯, and FD_STNU) [Posenato, 2022] and the benchmarks used to compare their performances.

Cite as

Luke Hunsberger and Roberto Posenato. Converting Simple Temporal Networks with Uncertainty into Dispatchable Form - Faster (Extended Abstract). In 30th International Symposium on Temporal Representation and Reasoning (TIME 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 278, pp. 20:1-20:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{hunsberger_et_al:LIPIcs.TIME.2023.20,
  author =	{Hunsberger, Luke and Posenato, Roberto},
  title =	{{Converting Simple Temporal Networks with Uncertainty into Dispatchable Form - Faster}},
  booktitle =	{30th International Symposium on Temporal Representation and Reasoning (TIME 2023)},
  pages =	{20:1--20:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-298-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{278},
  editor =	{Artikis, Alexander and Bruse, Florian and Hunsberger, Luke},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2023.20},
  URN =		{urn:nbn:de:0030-drops-191104},
  doi =		{10.4230/LIPIcs.TIME.2023.20},
  annote =	{Keywords: Temporal constraint networks, contingent durations, dispatchable network}
}
Document
RANDOM
Range Avoidance for Constant Depth Circuits: Hardness and Algorithms

Authors: Karthik Gajulapalli, Alexander Golovnev, Satyajeet Nagargoje, and Sidhant Saraogi

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


Abstract
Range Avoidance (Avoid) is a total search problem where, given a Boolean circuit 𝖢: {0,1}ⁿ → {0,1}^m, m > n, the task is to find a y ∈ {0,1}^m outside the range of 𝖢. For an integer k ≥ 2, NC⁰_k-Avoid is a special case of Avoid where each output bit of 𝖢 depends on at most k input bits. While there is a very natural randomized algorithm for Avoid, a deterministic algorithm for the problem would have many interesting consequences. Ren, Santhanam, and Wang (FOCS 2022) and Guruswami, Lyu, and Wang (RANDOM 2022) proved that explicit constructions of functions of high formula complexity, rigid matrices, and optimal linear codes, reduce to NC⁰₄-Avoid, thus establishing conditional hardness of the NC⁰₄-Avoid problem. On the other hand, NC⁰₂-Avoid admits polynomial-time algorithms, leaving the question about the complexity of NC⁰₃-Avoid open. We give the first reduction of an explicit construction question to NC⁰₃-Avoid. Specifically, we prove that a polynomial-time algorithm (with an NP oracle) for NC⁰₃-Avoid for the case of m = n+n^{2/3} would imply an explicit construction of a rigid matrix, and, thus, a super-linear lower bound on the size of log-depth circuits. We also give deterministic polynomial-time algorithms for all NC⁰_k-Avoid problems for m ≥ n^{k-1}/log(n). Prior work required an NP oracle, and required larger stretch, m ≥ n^{k-1}.

Cite as

Karthik Gajulapalli, Alexander Golovnev, Satyajeet Nagargoje, and Sidhant Saraogi. Range Avoidance for Constant Depth Circuits: Hardness and Algorithms. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 65:1-65:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{gajulapalli_et_al:LIPIcs.APPROX/RANDOM.2023.65,
  author =	{Gajulapalli, Karthik and Golovnev, Alexander and Nagargoje, Satyajeet and Saraogi, Sidhant},
  title =	{{Range Avoidance for Constant Depth Circuits: Hardness and Algorithms}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{65:1--65:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.65},
  URN =		{urn:nbn:de:0030-drops-188901},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.65},
  annote =	{Keywords: Boolean function analysis, Explicit Constructions, Low-depth Circuits, Range Avoidance, Matrix Rigidity, Circuit Lower Bounds}
}
Document
On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion Errors

Authors: Alexander R. Block, Jeremiah Blocki, Kuan Cheng, Elena Grigorescu, Xin Li, Yu Zheng, and Minshen Zhu

Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)


Abstract
Locally Decodable Codes (LDCs) are error-correcting codes C:Σⁿ → Σ^m, encoding messages in Σⁿ to codewords in Σ^m, with super-fast decoding algorithms. They are important mathematical objects in many areas of theoretical computer science, yet the best constructions so far have codeword length m that is super-polynomial in n, for codes with constant query complexity and constant alphabet size. In a very surprising result, Ben-Sasson, Goldreich, Harsha, Sudan, and Vadhan (SICOMP 2006) show how to construct a relaxed version of LDCs (RLDCs) with constant query complexity and almost linear codeword length over the binary alphabet, and used them to obtain significantly-improved constructions of Probabilistically Checkable Proofs. In this work, we study RLDCs in the standard Hamming-error setting, and introduce their variants in the insertion and deletion (Insdel) error setting. Standard LDCs for Insdel errors were first studied by Ostrovsky and Paskin-Cherniavsky (Information Theoretic Security, 2015), and are further motivated by recent advances in DNA random access bio-technologies. Our first result is an exponential lower bound on the length of Hamming RLDCs making 2 queries (even adaptively), over the binary alphabet. This answers a question explicitly raised by Gur and Lachish (SICOMP 2021) and is the first exponential lower bound for RLDCs. Combined with the results of Ben-Sasson et al., our result exhibits a "phase-transition"-type behavior on the codeword length for some constant-query complexity. We achieve these lower bounds via a transformation of RLDCs to standard Hamming LDCs, using a careful analysis of restrictions of message bits that fix codeword bits. We further define two variants of RLDCs in the Insdel-error setting, a weak and a strong version. On the one hand, we construct weak Insdel RLDCs with almost linear codeword length and constant query complexity, matching the parameters of the Hamming variants. On the other hand, we prove exponential lower bounds for strong Insdel RLDCs. These results demonstrate that, while these variants are equivalent in the Hamming setting, they are significantly different in the insdel setting. Our results also prove a strict separation between Hamming RLDCs and Insdel RLDCs.

Cite as

Alexander R. Block, Jeremiah Blocki, Kuan Cheng, Elena Grigorescu, Xin Li, Yu Zheng, and Minshen Zhu. On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion Errors. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 14:1-14:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{block_et_al:LIPIcs.CCC.2023.14,
  author =	{Block, Alexander R. and Blocki, Jeremiah and Cheng, Kuan and Grigorescu, Elena and Li, Xin and Zheng, Yu and Zhu, Minshen},
  title =	{{On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion Errors}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{14:1--14:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.14},
  URN =		{urn:nbn:de:0030-drops-182847},
  doi =		{10.4230/LIPIcs.CCC.2023.14},
  annote =	{Keywords: Relaxed Locally Decodable Codes, Hamming Errors, Insdel Errors, Lower Bounds}
}
Document
On Finding Short Reconfiguration Sequences Between Independent Sets

Authors: Akanksha Agrawal, Soumita Hait, and Amer E. Mouawad

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


Abstract
Assume we are given a graph G, two independent sets S and T in G of size k ≥ 1, and a positive integer 𝓁 ≥ 1. The goal is to decide whether there exists a sequence ⟨ I₀, I₁, ..., I_𝓁 ⟩ of independent sets such that for all j ∈ {0,…,𝓁-1} the set I_j is an independent set of size k, I₀ = S, I_𝓁 = T, and I_{j+1} is obtained from I_j by a predetermined reconfiguration rule. We consider two reconfiguration rules, namely token sliding and token jumping. Intuitively, we view each independent set as a collection of tokens placed on the vertices of the graph. Then, the Token Sliding Optimization (TSO) problem asks whether there exists a sequence of at most 𝓁 steps that transforms S into T, where at each step we are allowed to slide one token from a vertex to an unoccupied neighboring vertex (while maintaining independence). In the Token Jumping Optimization (TJO) problem, at each step, we are allowed to jump one token from a vertex to any other unoccupied vertex of the graph (as long as we maintain independence). Both TSO and TJO are known to be fixed-parameter tractable when parameterized by 𝓁 on nowhere dense classes of graphs. In this work, we investigate the boundary of tractability for sparse classes of graphs. We show that both problems are fixed-parameter tractable for parameter k + 𝓁 + d on d-degenerate graphs as well as for parameter |M| + 𝓁 + Δ on graphs having a modulator M whose deletion leaves a graph of maximum degree Δ. We complement these result by showing that for parameter 𝓁 alone both problems become W[1]-hard already on 2-degenerate graphs. Our positive result makes use of the notion of independence covering families introduced by Lokshtanov et al. [Daniel Lokshtanov et al., 2020]. Finally, we show as a side result that using such families we can obtain a simpler and unified algorithm for the standard Token Jumping Reachability problem (a.k.a. Token Jumping) parameterized by k on both degenerate and nowhere dense classes of graphs.

Cite as

Akanksha Agrawal, Soumita Hait, and Amer E. Mouawad. On Finding Short Reconfiguration Sequences Between Independent Sets. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 39:1-39:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.ISAAC.2022.39,
  author =	{Agrawal, Akanksha and Hait, Soumita and Mouawad, Amer E.},
  title =	{{On Finding Short Reconfiguration Sequences Between Independent Sets}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{39:1--39:14},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.39},
  URN =		{urn:nbn:de:0030-drops-173244},
  doi =		{10.4230/LIPIcs.ISAAC.2022.39},
  annote =	{Keywords: Token sliding, token jumping, fixed-parameter tractability, combinatorial reconfiguration, shortest reconfiguration sequence}
}
Document
Realizability Problem for Constraint LTL

Authors: Ashwin Bhaskar and M. Praveen

Published in: LIPIcs, Volume 247, 29th International Symposium on Temporal Representation and Reasoning (TIME 2022)


Abstract
Constraint linear-time temporal logic (CLTL) is an extension of LTL that is interpreted on sequences of valuations of variables over an infinite domain. The atomic formulas are interpreted as constraints on the valuations. The atomic formulas can constrain valuations over a range of positions along a sequence, with the range being bounded by a parameter depending on the formula. The satisfiability and model checking problems for CLTL have been studied by Demri and D’Souza. We consider the realizability problem for CLTL. The set of variables is partitioned into two parts, with each part controlled by a player. Players take turns to choose valuations for their variables, generating a sequence of valuations. The winning condition is specified by a CLTL formula - the first player wins if the sequence of valuations satisfies the specified formula. We study the decidability of checking whether the first player has a winning strategy in the realizability game for a given CLTL formula. We prove that it is decidable in the case where the domain satisfies the completion property, a property introduced by Balbiani and Condotta in the context of satisfiability. We prove that it is undecidable over (ℤ, < , =), the domain of integers with order and equality. We prove that over (ℤ, < , =), it is decidable if the atomic constraints in the formula can only constrain the current valuations of variables belonging to the second player, but there are no such restrictions for the variables belonging to the first player. We call this single-sided games.

Cite as

Ashwin Bhaskar and M. Praveen. Realizability Problem for Constraint LTL. In 29th International Symposium on Temporal Representation and Reasoning (TIME 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 247, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{bhaskar_et_al:LIPIcs.TIME.2022.8,
  author =	{Bhaskar, Ashwin and Praveen, M.},
  title =	{{Realizability Problem for Constraint LTL}},
  booktitle =	{29th International Symposium on Temporal Representation and Reasoning (TIME 2022)},
  pages =	{8:1--8:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-262-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{247},
  editor =	{Artikis, Alexander and Posenato, Roberto and Tonetta, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2022.8},
  URN =		{urn:nbn:de:0030-drops-172556},
  doi =		{10.4230/LIPIcs.TIME.2022.8},
  annote =	{Keywords: Realizability, constraint LTL, Strategy trees, Tree automata}
}
Document
Deep Learning and Knowledge Integration for Music Audio Analysis (Dagstuhl Seminar 22082)

Authors: Meinard Müller, Rachel Bittner, Juhan Nam, Michael Krause, and Yigitcan Özer

Published in: Dagstuhl Reports, Volume 12, Issue 2 (2022)


Abstract
Given the increasing amount of digital music, the development of computational tools that allow users to find, organize, analyze, and interact with music has become central to the research field known as Music Information Retrieval (MIR). As in general multimedia processing, many of the recent advances in MIR have been driven by techniques based on deep learning (DL). There is a growing trend to relax problem-specific modeling constraints from MIR systems and instead apply relatively generic DL-based approaches that rely on large quantities of data. In the Dagstuhl Seminar 22082, we critically examined this trend, discussing the strengths and weaknesses of these approaches using music as a challenging application domain. We mainly focused on music analysis tasks applied to audio representations (rather than symbolic music representations) to give the seminar cohesion. In this context, we systematically explored how musical knowledge can be integrated into or relaxed from computational pipelines. We then discussed how this choice could affect the explainability of models or the vulnerability to data biases and confounding factors. Furthermore, besides explainability and generalization, we also addressed efficiency, ethical and educational aspects considering traditional model-based and recent data-driven methods. In this report, we give an overview of the various contributions and results of the seminar. We start with an executive summary describing the main topics, goals, and group activities. Then, we give an overview of the participants' stimulus talks and subsequent discussions (listed alphabetically by the main contributor’s last name) and summarize further activities, including group discussions and music sessions.

Cite as

Meinard Müller, Rachel Bittner, Juhan Nam, Michael Krause, and Yigitcan Özer. Deep Learning and Knowledge Integration for Music Audio Analysis (Dagstuhl Seminar 22082). In Dagstuhl Reports, Volume 12, Issue 2, pp. 103-133, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@Article{muller_et_al:DagRep.12.2.103,
  author =	{M\"{u}ller, Meinard and Bittner, Rachel and Nam, Juhan and Krause, Michael and \"{O}zer, Yigitcan},
  title =	{{Deep Learning and Knowledge Integration for Music Audio Analysis (Dagstuhl Seminar 22082)}},
  pages =	{103--133},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2022},
  volume =	{12},
  number =	{2},
  editor =	{M\"{u}ller, Meinard and Bittner, Rachel and Nam, Juhan and Krause, Michael and \"{O}zer, Yigitcan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.12.2.103},
  URN =		{urn:nbn:de:0030-drops-169333},
  doi =		{10.4230/DagRep.12.2.103},
  annote =	{Keywords: Audio signal processing, deep learning, knowledge representation, music information retrieval, user interaction and interfaces}
}
Document
CNF Encodings of Parity

Authors: Gregory Emdin, Alexander S. Kulikov, Ivan Mihajlin, and Nikita Slezkin

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)


Abstract
The minimum number of clauses in a CNF representation of the parity function x₁ ⊕ x₂ ⊕ … ⊕ x_n is 2^{n-1}. One can obtain a more compact CNF encoding by using non-deterministic variables (also known as guess or auxiliary variables). In this paper, we prove the following lower bounds, that almost match known upper bounds, on the number m of clauses and the maximum width k of clauses: 1) if there are at most s auxiliary variables, then m ≥ Ω(2^{n/(s+1)}/n) and k ≥ n/(s+1); 2) the minimum number of clauses is at least 3n. We derive the first two bounds from the Satisfiability Coding Lemma due to Paturi, Pudlák, and Zane using a tight connection between CNF encodings and depth-3 circuits. In particular, we show that lower bounds on the size of a CNF encoding of a Boolean function imply depth-3 circuit lower bounds for this function.

Cite as

Gregory Emdin, Alexander S. Kulikov, Ivan Mihajlin, and Nikita Slezkin. CNF Encodings of Parity. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 47:1-47:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{emdin_et_al:LIPIcs.MFCS.2022.47,
  author =	{Emdin, Gregory and Kulikov, Alexander S. and Mihajlin, Ivan and Slezkin, Nikita},
  title =	{{CNF Encodings of Parity}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{47:1--47:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert 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.MFCS.2022.47},
  URN =		{urn:nbn:de:0030-drops-168455},
  doi =		{10.4230/LIPIcs.MFCS.2022.47},
  annote =	{Keywords: encoding, parity, lower bounds, circuits, CNF}
}
Document
Pseudorandom Generators, Resolution and Heavy Width

Authors: Dmitry Sokolov

Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)


Abstract
Following the paper of Alekhnovich, Ben-Sasson, Razborov, Wigderson [Michael Alekhnovich et al., 2004] we call a pseudorandom generator ℱ:{0, 1}ⁿ → {0, 1}^m hard for a propositional proof system P if P cannot efficiently prove the (properly encoded) statement b ∉ Im(ℱ) for any string b ∈ {0, 1}^m. In [Michael Alekhnovich et al., 2004] the authors suggested the "functional encoding" of the considered statement for Nisan-Wigderson generator that allows the introduction of "local" extension variables. These extension variables may potentially significantly increase the power of the proof system. In [Michael Alekhnovich et al., 2004] authors gave a lower bound of exp[Ω(n²/{m⋅2^{2^Δ}})] on the length of Resolution proofs where Δ is the degree of the dependency graph of the generator. This lower bound meets the barrier for the restriction technique. In this paper, we introduce a "heavy width" measure for Resolution that allows us to show a lower bound of exp[n²/{m 2^𝒪(εΔ)}] on the length of Resolution proofs of the considered statement for the Nisan-Wigderson generator. This gives an exponential lower bound up to Δ := log^{2 - δ} n (the bigger degree the more extension variables we can use). In [Michael Alekhnovich et al., 2004] authors left an open problem to get rid of scaling factor 2^{2^Δ}, it is a solution to this open problem.

Cite as

Dmitry Sokolov. Pseudorandom Generators, Resolution and Heavy Width. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 15:1-15:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{sokolov:LIPIcs.CCC.2022.15,
  author =	{Sokolov, Dmitry},
  title =	{{Pseudorandom Generators, Resolution and Heavy Width}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{15:1--15:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-241-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{234},
  editor =	{Lovett, Shachar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.15},
  URN =		{urn:nbn:de:0030-drops-165770},
  doi =		{10.4230/LIPIcs.CCC.2022.15},
  annote =	{Keywords: proof complexity, pseudorandom generators, resolution, lower bounds}
}
Document
Dynamic Connectivity in Disk Graphs

Authors: Haim Kaplan, Alexander Kauer, Katharina Klost, Kristin Knorr, Wolfgang Mulzer, Liam Roditty, and Paul Seiferth

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)


Abstract
Let S ⊆ ℝ² be a set of n planar sites, such that each s ∈ S has an associated radius r_s > 0. Let 𝒟(S) be the disk intersection graph for S. It has vertex set S and an edge between two distinct sites s, t ∈ S if and only if the disks with centers s, t and radii r_s, r_t intersect. Our goal is to design data structures that maintain the connectivity structure of 𝒟(S) as sites are inserted and/or deleted. First, we consider unit disk graphs, i.e., r_s = 1, for all s ∈ S. We describe a data structure that has O(log² n) amortized update and O(log n/log log n) amortized query time. Second, we look at disk graphs with bounded radius ratio Ψ, i.e., for all s ∈ S, we have 1 ≤ r_s ≤ Ψ, for a Ψ ≥ 1 known in advance. In the fully dynamic case, we achieve amortized update time O(Ψ λ₆(log n) log⁷ n) and query time O(log n/log log n), where λ_s(n) is the maximum length of a Davenport-Schinzel sequence of order s on n symbols. In the incremental case, where only insertions are allowed, we get logarithmic dependency on Ψ, with O(α(n)) query time and O(logΨ λ₆(log n) log⁷ n) update time. For the decremental setting, where only deletions are allowed, we first develop an efficient disk revealing structure: given two sets R and B of disks, we can delete disks from R, and upon each deletion, we receive a list of all disks in B that no longer intersect the union of R. Using this, we get decremental data structures with amortized query time O(log n/log log n) that support m deletions in O((nlog⁵ n + m log⁷ n) λ₆(log n) + nlog Ψ log⁴n) overall time for bounded radius ratio Ψ and O((nlog⁶ n + m log⁸n) λ₆(log n)) for arbitrary radii.

Cite as

Haim Kaplan, Alexander Kauer, Katharina Klost, Kristin Knorr, Wolfgang Mulzer, Liam Roditty, and Paul Seiferth. Dynamic Connectivity in Disk Graphs. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 49:1-49:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{kaplan_et_al:LIPIcs.SoCG.2022.49,
  author =	{Kaplan, Haim and Kauer, Alexander and Klost, Katharina and Knorr, Kristin and Mulzer, Wolfgang and Roditty, Liam and Seiferth, Paul},
  title =	{{Dynamic Connectivity in Disk Graphs}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{49:1--49:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.49},
  URN =		{urn:nbn:de:0030-drops-160572},
  doi =		{10.4230/LIPIcs.SoCG.2022.49},
  annote =	{Keywords: Disk Graphs, Connectivity, Lower Envelopes}
}
Document
A Lower Bound on the Space Overhead of Fault-Tolerant Quantum Computation

Authors: Omar Fawzi, Alexander Müller-Hermes, and Ala Shayeghi

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)


Abstract
The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation stating that arbitrarily long quantum computations can be performed with a polylogarithmic overhead provided the noise level is below a constant level. A recent work by Fawzi, Grospellier and Leverrier (FOCS 2018) building on a result by Gottesman (QIC 2013) has shown that the space overhead can be asymptotically reduced to a constant independent of the circuit provided we only consider circuits with a length bounded by a polynomial in the width. In this work, using a minimal model for quantum fault tolerance, we establish a general lower bound on the space overhead required to achieve fault tolerance. For any non-unitary qubit channel 𝒩 and any quantum fault tolerance schemes against i.i.d. noise modeled by 𝒩, we prove a lower bound of max{Q(𝒩)^{-1}n,α_𝒩 log T} on the number of physical qubits, for circuits of length T and width n. Here, Q(𝒩) denotes the quantum capacity of 𝒩 and α_𝒩 > 0 is a constant only depending on the channel 𝒩. In our model, we allow for qubits to be replaced by fresh ones during the execution of the circuit and in the case of unital noise, we allow classical computation to be free and perfect. This improves upon results that assumed classical computations to be also affected by noise, and that sometimes did not allow for fresh qubits to be added. Along the way, we prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude damping noise resolving a conjecture by Ben-Or, Gottesman and Hassidim (2013).

Cite as

Omar Fawzi, Alexander Müller-Hermes, and Ala Shayeghi. A Lower Bound on the Space Overhead of Fault-Tolerant Quantum Computation. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 68:1-68:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{fawzi_et_al:LIPIcs.ITCS.2022.68,
  author =	{Fawzi, Omar and M\"{u}ller-Hermes, Alexander and Shayeghi, Ala},
  title =	{{A Lower Bound on the Space Overhead of Fault-Tolerant Quantum Computation}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{68:1--68:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.68},
  URN =		{urn:nbn:de:0030-drops-156649},
  doi =		{10.4230/LIPIcs.ITCS.2022.68},
  annote =	{Keywords: Fault-tolerant quantum computation, quantum error correction}
}
  • Refine by Author
  • 4 Müller-Hannemann, Matthias
  • 3 Chatterjee, Krishnendu
  • 3 Henzinger, Monika
  • 3 Okhotin, Alexander
  • 3 Rückert, Ralf
  • Show More...

  • Refine by Classification
  • 3 Applied computing → Transportation
  • 3 Theory of computation → Computational geometry
  • 3 Theory of computation → Graph algorithms analysis
  • 3 Theory of computation → Modal and temporal logics
  • 3 Theory of computation → Parameterized complexity and exact algorithms
  • Show More...

  • Refine by Keyword
  • 3 Modeling
  • 2 Circuit Lower Bounds
  • 2 Machine Learning
  • 2 Model-Driven Development
  • 2 Testing
  • Show More...

  • Refine by Type
  • 62 document

  • Refine by Publication Year
  • 8 2021
  • 8 2023
  • 7 2018
  • 7 2022
  • 6 2020
  • 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