Search Results

Documents authored by Reischuk, Rüdiger

Document
DOI: 10.4230/LIPIcs.IPEC.2021.7
Dynamic Kernels for Hitting Sets and Set Packing

Authors: Max Bannach, Zacharias Heinrich, Rüdiger Reischuk, and Till Tantau

Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)

Abstract
Computing small kernels for the hitting set problem is a well-studied computational problem where we are given a hypergraph with n vertices and m hyperedges, each of size d for some small constant d, and a parameter k. The task is to compute a new hypergraph, called a kernel, whose size is polynomial with respect to the parameter k and which has a size-k hitting set if, and only if, the original hypergraph has one. State-of-the-art algorithms compute kernels of size k^d (which is a polynomial kernel size as d is a constant), and they do so in time m⋅ 2^d poly(d) for a small polynomial poly(d) (which is a linear runtime as d is again a constant). We generalize this task to the dynamic setting where hyperedges may continuously be added or deleted and one constantly has to keep track of a size-k^d hitting set kernel in memory (including moments when no size-k hitting set exists). This paper presents a deterministic solution with worst-case time 3^d poly(d) for updating the kernel upon hyperedge inserts and time 5^d poly(d) for updates upon deletions. These bounds nearly match the time 2^d poly(d) needed by the best static algorithm per hyperedge. Let us stress that for constant d our algorithm maintains a dynamic hitting set kernel with constant, deterministic, worst-case update time that is independent of n, m, and the parameter k. As a consequence, we also get a deterministic dynamic algorithm for keeping track of size-k hitting sets in d-hypergraphs with update times O(1) and query times O(c^k) where c = d - 1 + O(1/d) equals the best base known for the static setting.
Cite as

Max Bannach, Zacharias Heinrich, Rüdiger Reischuk, and Till Tantau. Dynamic Kernels for Hitting Sets and Set Packing. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bannach_et_al:LIPIcs.IPEC.2021.7,
  author =	{Bannach, Max and Heinrich, Zacharias and Reischuk, R\"{u}diger and Tantau, Till},
  title =	{{Dynamic Kernels for Hitting Sets and Set Packing}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{7:1--7:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-216-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{214},
  editor =	{Golovach, Petr A. and Zehavi, Meirav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.7},
  URN =		{urn:nbn:de:0030-drops-153900},
  doi =		{10.4230/LIPIcs.IPEC.2021.7},
  annote =	{Keywords: Kernelization, Dynamic Algorithms, Hitting Set, Set Packings}
}
Document
DOI: 10.4230/DagRep.4.3.62
Computational Complexity of Discrete Problems (Dagstuhl Seminar 14121)

Authors: Anna Gal, Michal Koucky, Oded Regev, and Rüdiger Reischuk

Published in: Dagstuhl Reports, Volume 4, Issue 3 (2014)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 14121 "Computational Complexity of Discrete Problems". The first section gives an overview of the topics covered and the organization of the meeting. Section 2 lists the talks given in chronological order. The last section contains the abstracts of the talks.
Cite as

Anna Gal, Michal Koucky, Oded Regev, and Rüdiger Reischuk. Computational Complexity of Discrete Problems (Dagstuhl Seminar 14121). In Dagstuhl Reports, Volume 4, Issue 3, pp. 62-84, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Article{gal_et_al:DagRep.4.3.62,
  author =	{Gal, Anna and Koucky, Michal and Regev, Oded and Reischuk, R\"{u}diger},
  title =	{{Computational Complexity of Discrete Problems (Dagstuhl Seminar 14121)}},
  pages =	{62--84},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2014},
  volume =	{4},
  number =	{3},
  editor =	{Gal, Anna and Koucky, Michal and Regev, Oded and Reischuk, R\"{u}diger},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.4.3.62},
  URN =		{urn:nbn:de:0030-drops-45921},
  doi =		{10.4230/DagRep.4.3.62},
  annote =	{Keywords: discrete problems, computational complexity, Turing machines, Boolean circuits, arithmetic circuits, quantum computing, communication complexity, pseudorandomness, derandomization, approximation, data streams}
}
Document
DOI: 10.4230/DagSemProc.08381.1
08381 Abstracts Collection – Computational Complexity of Discrete Problems

Authors: Peter Bro Miltersen, Rüdiger Reischuk, Georg Schnitger, and Dieter van Melkebeek

Published in: Dagstuhl Seminar Proceedings, Volume 8381, Computational Complexity of Discrete Problems (2008)

Abstract
From the 14th of September to the 19th of September, the Dagstuhl Seminar 08381 ``Computational Complexity of Discrete Problems'' was held in Schloss Dagstuhl - Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work as well as open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this report. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Peter Bro Miltersen, Rüdiger Reischuk, Georg Schnitger, and Dieter van Melkebeek. 08381 Abstracts Collection – Computational Complexity of Discrete Problems. In Computational Complexity of Discrete Problems. Dagstuhl Seminar Proceedings, Volume 8381, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{miltersen_et_al:DagSemProc.08381.1,
  author =	{Miltersen, Peter Bro and Reischuk, R\"{u}diger and Schnitger, Georg and van Melkebeek, Dieter},
  title =	{{08381 Abstracts Collection – Computational Complexity of Discrete Problems}},
  booktitle =	{Computational Complexity of Discrete Problems},
  pages =	{1--18},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8381},
  editor =	{Peter Bro Miltersen and R\"{u}diger Reischuk and Georg Schnitger and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08381.1},
  URN =		{none},
  doi =		{10.4230/DagSemProc.08381.1},
  annote =	{Keywords: Computational complexity, discrete problems, Turing machines, circuits, proof complexity, pseudorandomness, derandomization, cryptography, computational learning, communication complexity, query complexity, hardness of approximation}
}
Document
DOI: 10.4230/DagSemProc.08381.2
08381 Executive Summary – Computational Complexity of Discrete Problems

Authors: Peter Bro Miltersen, Rüdiger Reischuk, Georg Schnitger, and Dieter van Melkebeek

Published in: Dagstuhl Seminar Proceedings, Volume 8381, Computational Complexity of Discrete Problems (2008)

Abstract
Estimating the computational complexity of discrete problems constitutes one of the central and classical topics in the theory of computation. Mathematicians and computer scientists have long tried to classify natural families of Boolean relations according to fundamental complexity measures like time and space, both in the uniform and in the nonuniform setting. Several models of computation have been developed in order to capture the various capabilities of digital computing devices, including parallelism, randomness, and quantum interference.
Cite as

Peter Bro Miltersen, Rüdiger Reischuk, Georg Schnitger, and Dieter van Melkebeek. 08381 Executive Summary – Computational Complexity of Discrete Problems. In Computational Complexity of Discrete Problems. Dagstuhl Seminar Proceedings, Volume 8381, pp. 1-7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{miltersen_et_al:DagSemProc.08381.2,
  author =	{Miltersen, Peter Bro and Reischuk, R\"{u}diger and Schnitger, Georg and van Melkebeek, Dieter},
  title =	{{08381 Executive Summary – Computational Complexity of Discrete Problems}},
  booktitle =	{Computational Complexity of Discrete Problems},
  pages =	{1--7},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8381},
  editor =	{Peter Bro Miltersen and R\"{u}diger Reischuk and Georg Schnitger and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08381.2},
  URN =		{urn:nbn:de:0030-drops-17789},
  doi =		{10.4230/DagSemProc.08381.2},
  annote =	{Keywords: Computational complexity, discrete problems, Turing machines, circuits, proof complexity, pseudorandomness, derandomization, cryptography, computational learning, communication complexity, query complexity, hardness of approximation}
}
Document
DOI: 10.4230/DagSemProc.06111.2
06111 Executive Summary – Complexity of Boolean Functions

Authors: Matthias Krause, Dieter van Melkebeek, Pavel Pudlák, and Rüdiger Reischuk

Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)

Abstract
We briefly describe the state of the art concerning the complexity of discrete functions. Computational models and analytical techniques are summarized. After describing the formal organization of the Dagstuhl seminar "Complexity of Boolean Functions" held in March 2006, we introduce the different topics that have been discussed there and mention some of the major achievements. The summary closes with an outlook on the development of discrete computational complexity in the future.
Cite as

Matthias Krause, Dieter van Melkebeek, Pavel Pudlák, and Rüdiger Reischuk. 06111 Executive Summary – Complexity of Boolean Functions. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{krause_et_al:DagSemProc.06111.2,
  author =	{Krause, Matthias and van Melkebeek, Dieter and Pudl\'{a}k, Pavel and Reischuk, R\"{u}diger},
  title =	{{06111 Executive Summary – Complexity of Boolean Functions}},
  booktitle =	{Complexity of Boolean Functions},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6111},
  editor =	{Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.2},
  URN =		{urn:nbn:de:0030-drops-8409},
  doi =		{10.4230/DagSemProc.06111.2},
  annote =	{Keywords: Boolean and quantum circuits, discrete problems, computational complexity, lower bounds, communication complexity, proof and query complexity, randomization, pseudo-randomness, derandomization, approximation, cryptography, computational learning}
}
Document
DOI: 10.4230/DagSemProc.06111.1
06111 Abstracts Collection – Complexity of Boolean Functions

Authors: Matthias Krause, Pavel Pudlák, Rüdiger Reischuk, and Dieter van Melkebeek

Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)

Abstract
From 12.03.06 to 17.03.06, the Dagstuhl Seminar 06111 ``Complexity of Boolean Functions'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Matthias Krause, Pavel Pudlák, Rüdiger Reischuk, and Dieter van Melkebeek. 06111 Abstracts Collection – Complexity of Boolean Functions. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{krause_et_al:DagSemProc.06111.1,
  author =	{Krause, Matthias and Pudl\'{a}k, Pavel and Reischuk, R\"{u}diger and van Melkebeek, Dieter},
  title =	{{06111 Abstracts Collection – Complexity of Boolean Functions}},
  booktitle =	{Complexity of Boolean Functions},
  pages =	{1--24},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6111},
  editor =	{Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.1},
  URN =		{urn:nbn:de:0030-drops-7593},
  doi =		{10.4230/DagSemProc.06111.1},
  annote =	{Keywords: Complexity of Boolean functions, Boolean circuits, binary decision diagrams, lower bound proof techniques, combinatorics of Boolean functions, communi algorithmic learning, cryptography, derandomization}
}
Document
DOI: 10.4230/DagSemRep.338
Complexity of Boolean Functions (Dagstuhl Seminar 02121)

Authors: Johan Hastad, Matthias Krause, David A. M. Barrington, and Rüdiger Reischuk

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Johan Hastad, Matthias Krause, David A. M. Barrington, and Rüdiger Reischuk. Complexity of Boolean Functions (Dagstuhl Seminar 02121). Dagstuhl Seminar Report 338, pp. 1-25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2002)

Copy BibTex To Clipboard

@TechReport{hastad_et_al:DagSemRep.338,
  author =	{Hastad, Johan and Krause, Matthias and Barrington, David A. M. and Reischuk, R\"{u}diger},
  title =	{{Complexity of Boolean Functions (Dagstuhl Seminar 02121)}},
  pages =	{1--25},
  ISSN =	{1619-0203},
  year =	{2002},
  type = 	{Dagstuhl Seminar Report},
  number =	{338},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.338},
  URN =		{urn:nbn:de:0030-drops-152207},
  doi =		{10.4230/DagSemRep.338},
}
Document
DOI: 10.4230/DagSemRep.257
Complexity of Boolean Functions (Dagstuhl Seminar 99441)

Authors: D. M. Barrington, Rüdiger Reischuk, and Ingo Wegener

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

D. M. Barrington, Rüdiger Reischuk, and Ingo Wegener. Complexity of Boolean Functions (Dagstuhl Seminar 99441). Dagstuhl Seminar Report 257, pp. 1-30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2000)

Copy BibTex To Clipboard

@TechReport{barrington_et_al:DagSemRep.257,
  author =	{Barrington, D. M. and Reischuk, R\"{u}diger and Wegener, Ingo},
  title =	{{Complexity of Boolean Functions (Dagstuhl Seminar 99441)}},
  pages =	{1--30},
  ISSN =	{1619-0203},
  year =	{2000},
  type = 	{Dagstuhl Seminar Report},
  number =	{257},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.257},
  URN =		{urn:nbn:de:0030-drops-151420},
  doi =		{10.4230/DagSemRep.257},
}
Document
DOI: 10.4230/DagSemRep.172
Complexity of Boolean Functions (Dagstuhl Seminar 9711)

Authors: David Mix Barrington, Noam Nisan, Rüdiger Reischuk, and Ingo Wegener

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

David Mix Barrington, Noam Nisan, Rüdiger Reischuk, and Ingo Wegener. Complexity of Boolean Functions (Dagstuhl Seminar 9711). Dagstuhl Seminar Report 172, pp. 1-26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1997)

Copy BibTex To Clipboard

@TechReport{barrington_et_al:DagSemRep.172,
  author =	{Barrington, David Mix and Nisan, Noam and Reischuk, R\"{u}diger and Wegener, Ingo},
  title =	{{Complexity of Boolean Functions (Dagstuhl Seminar 9711)}},
  pages =	{1--26},
  ISSN =	{1619-0203},
  year =	{1997},
  type = 	{Dagstuhl Seminar Report},
  number =	{172},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.172},
  URN =		{urn:nbn:de:0030-drops-150594},
  doi =		{10.4230/DagSemRep.172},
}
Document
DOI: 10.4230/DagSemRep.138
Time Services (Dagstuhl Seminar 9611)

Authors: Danny Dolev, Rüdiger Reischuk, Fred B. Schneider, and H. Raymond Strong

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Danny Dolev, Rüdiger Reischuk, Fred B. Schneider, and H. Raymond Strong. Time Services (Dagstuhl Seminar 9611). Dagstuhl Seminar Report 138, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1996)

Copy BibTex To Clipboard

@TechReport{dolev_et_al:DagSemRep.138,
  author =	{Dolev, Danny and Reischuk, R\"{u}diger and Schneider, Fred B. and Strong, H. Raymond},
  title =	{{Time Services (Dagstuhl Seminar 9611)}},
  pages =	{1--19},
  ISSN =	{1619-0203},
  year =	{1996},
  type = 	{Dagstuhl Seminar Report},
  number =	{138},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.138},
  URN =		{urn:nbn:de:0030-drops-150256},
  doi =		{10.4230/DagSemRep.138},
}
Document
DOI: 10.4230/DagSemRep.45
Complexity and Realization of Boolean Functions (Dagstuhl Seminar 9235)

Authors: Rüdiger Reischuk and Dietmar Uhlig

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Rüdiger Reischuk and Dietmar Uhlig. Complexity and Realization of Boolean Functions (Dagstuhl Seminar 9235). Dagstuhl Seminar Report 45, pp. 1-28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1992)

Copy BibTex To Clipboard

@TechReport{reischuk_et_al:DagSemRep.45,
  author =	{Reischuk, R\"{u}diger and Uhlig, Dietmar},
  title =	{{Complexity and Realization of Boolean Functions (Dagstuhl Seminar 9235)}},
  pages =	{1--28},
  ISSN =	{1619-0203},
  year =	{1992},
  type = 	{Dagstuhl Seminar Report},
  number =	{45},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.45},
  URN =		{urn:nbn:de:0030-drops-149332},
  doi =		{10.4230/DagSemRep.45},
}
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