268 Search Results for "Hoffmann, Michael"

Artifact
Dataset
DOI: 10.4230/dblp.rdf.ntriples.2026-05-01
dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of May 2026

Authors: dblp Team

Abstract
Cite as

dblp Team. dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of May 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Copy BibTex To Clipboard

@misc{dblp.rdf.ntriples.2026-05-01,
    title     = {{dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of May 2026}},
    author    = {dblp Team},
    doi       = {10.4230/dblp.rdf.ntriples.2026-05-01},
    url       = {https://doi.org/10.4230/dblp.rdf.ntriples.2026-05-01},
    month     = {May},
    year      = {2026},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik} 
}
Artifact
Dataset
DOI: 10.4230/dblp.xml.2026-05-01
dblp computer science bibliography – Monthly Snapshot XML Release of May 2026

Authors: dblp Team

Abstract
Cite as

dblp Team. dblp computer science bibliography – Monthly Snapshot XML Release of May 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Copy BibTex To Clipboard

@misc{dblp.xml.2026-05-01,
    title     = {{dblp computer science bibliography – Monthly Snapshot XML Release of May 2026}},
    author    = {dblp Team},
    doi       = {10.4230/dblp.xml.2026-05-01},
    url       = {https://doi.org/10.4230/dblp.xml.2026-05-01},
    month     = {May},
    year      = {2026},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik} 
}
Artifact
Dataset
DOI: 10.4230/dblp.rdf.ntriples.2026-04-01
dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of April 2026

Authors: dblp Team

Abstract
Cite as

dblp Team. dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of April 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Copy BibTex To Clipboard

@misc{dblp.rdf.ntriples.2026-04-01,
    title     = {{dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of April 2026}},
    author    = {dblp Team},
    doi       = {10.4230/dblp.rdf.ntriples.2026-04-01},
    url       = {https://doi.org/10.4230/dblp.rdf.ntriples.2026-04-01},
    month     = {April},
    year      = {2026},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik} 
}
Artifact
Dataset
DOI: 10.4230/dblp.xml.2026-04-01
dblp computer science bibliography – Monthly Snapshot XML Release of April 2026

Authors: dblp Team

Abstract
Cite as

dblp Team. dblp computer science bibliography – Monthly Snapshot XML Release of April 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Copy BibTex To Clipboard

@misc{dblp.xml.2026-04-01,
    title     = {{dblp computer science bibliography – Monthly Snapshot XML Release of April 2026}},
    author    = {dblp Team},
    doi       = {10.4230/dblp.xml.2026-04-01},
    url       = {https://doi.org/10.4230/dblp.xml.2026-04-01},
    month     = {April},
    year      = {2026},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik} 
}
Artifact
Dataset
DOI: 10.4230/dblp.rdf.ntriples.2026-03-01
dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of March 2026

Authors: dblp Team

Abstract
Cite as

dblp Team. dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of March 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Copy BibTex To Clipboard

@misc{dblp.rdf.ntriples.2026-03-01,
    title     = {{dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of March 2026}},
    author    = {dblp Team},
    doi       = {10.4230/dblp.rdf.ntriples.2026-03-01},
    url       = {https://doi.org/10.4230/dblp.rdf.ntriples.2026-03-01},
    month     = {March},
    year      = {2026},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik} 
}
Artifact
Dataset
DOI: 10.4230/dblp.xml.2026-03-01
dblp computer science bibliography – Monthly Snapshot XML Release of March 2026

Authors: dblp Team

Abstract
Cite as

dblp Team. dblp computer science bibliography – Monthly Snapshot XML Release of March 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Copy BibTex To Clipboard

@misc{dblp.xml.2026-03-01,
    title     = {{dblp computer science bibliography – Monthly Snapshot XML Release of March 2026}},
    author    = {dblp Team},
    doi       = {10.4230/dblp.xml.2026-03-01},
    url       = {https://doi.org/10.4230/dblp.xml.2026-03-01},
    month     = {March},
    year      = {2026},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik} 
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.32
Optimal Verification of a Minimum-Weight Basis in an Uncertainty Matroid

Authors: Haya Diwan, Lisa Hellerstein, Nicole Megow, and Jens Schlöter

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

Abstract
Research in explorable uncertainty addresses combinatorial optimization problems where there is partial information about the values of numeric input parameters, and exact values of these parameters can be determined by performing costly queries. The goal is to design an adaptive query strategy that minimizes the query cost incurred in computing an optimal solution. Solving such problems generally requires that we be able to solve the associated verification problem: given the answers to all queries in advance, find a minimum-cost set of queries that certifies an optimal solution to the combinatorial optimization problem. We present a polynomial-time algorithm for verifying a minimum-weight basis of a matroid, where each weight lies in a given uncertainty area. These areas may be finite sets, real intervals, or unions of open and closed intervals, strictly generalizing previous work by Erlebach and Hoffman which only handled the special case of open intervals. Our algorithm introduces new techniques to address the resulting challenges. Verification problems are of particular importance in the area of explorable uncertainty, as the structural insights and techniques used to solve the verification problem often heavily influence work on the corresponding online problem and its stochastic variant. In our case, we use structural results from the verification problem to give a best-possible algorithm for a promise variant of the corresponding adaptive online problem. Finally, we show that our algorithms can be applied to two learning-augmented variants of the minimum-weight basis problem under explorable uncertainty.
Cite as

Haya Diwan, Lisa Hellerstein, Nicole Megow, and Jens Schlöter. Optimal Verification of a Minimum-Weight Basis in an Uncertainty Matroid. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 32:1-32:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{diwan_et_al:LIPIcs.STACS.2026.32,
  author =	{Diwan, Haya and Hellerstein, Lisa and Megow, Nicole and Schl\"{o}ter, Jens},
  title =	{{Optimal Verification of a Minimum-Weight Basis in an Uncertainty Matroid}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{32:1--32:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.32},
  URN =		{urn:nbn:de:0030-drops-255216},
  doi =		{10.4230/LIPIcs.STACS.2026.32},
  annote =	{Keywords: Matroid verification, minimum-weight basis, query strategy, uncertainty matroid, explorable uncertainty}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.64
One-Clock Synthesis Problems

Authors: Sławomir Lasota, Mathieu Lehaut, Julie Parreaux, and Radosław Piórkowski

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

Abstract
We study a generalisation of Büchi-Landweber games to the timed setting. The winning condition is specified by a non-deterministic timed automaton, and one of the players can elapse time. We perform a systematic study of synthesis problems in all variants of timed games, depending on which player’s winning condition is specified, and which player’s strategy (or controller, a finite-memory strategy) is sought. As our main result we prove ubiquitous undecidability in all the variants, both for strategy and controller synthesis, already for winning conditions specified by one-clock automata. This strengthens and generalises previously known undecidability results. We also fully characterise those cases where finite memory is sufficient to win, namely existence of a strategy implies existence of a controller. All our results are stated in the timed setting, while analogous results hold in the data setting where one-clock automata are replaced by one-register ones.
Cite as

Sławomir Lasota, Mathieu Lehaut, Julie Parreaux, and Radosław Piórkowski. One-Clock Synthesis Problems. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 64:1-64:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{lasota_et_al:LIPIcs.STACS.2026.64,
  author =	{Lasota, S{\l}awomir and Lehaut, Mathieu and Parreaux, Julie and Pi\'{o}rkowski, Rados{\l}aw},
  title =	{{One-Clock Synthesis Problems}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{64:1--64:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.64},
  URN =		{urn:nbn:de:0030-drops-255533},
  doi =		{10.4230/LIPIcs.STACS.2026.64},
  annote =	{Keywords: timed automata, register automata, B\"{u}chi-Landweber games, Church synthesis problem, reactive synthesis problem}
}
Artifact
Dataset
DOI: 10.4230/dblp.rdf.ntriples.2026-02-01
dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of February 2026

Authors: dblp Team

Abstract
Cite as

dblp Team. dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of February 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Copy BibTex To Clipboard

@misc{dblp.rdf.ntriples.2026-02-01,
    title     = {{dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of February 2026}},
    author    = {dblp Team},
    doi       = {10.4230/dblp.rdf.ntriples.2026-02-01},
    url       = {https://doi.org/10.4230/dblp.rdf.ntriples.2026-02-01},
    month     = {February},
    year      = {2026},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik} 
}
Artifact
Dataset
DOI: 10.4230/dblp.xml.2026-02-01
dblp computer science bibliography – Monthly Snapshot XML Release of February 2026

Authors: dblp Team

Abstract
Cite as

dblp Team. dblp computer science bibliography – Monthly Snapshot XML Release of February 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Copy BibTex To Clipboard

@misc{dblp.xml.2026-02-01,
    title     = {{dblp computer science bibliography – Monthly Snapshot XML Release of February 2026}},
    author    = {dblp Team},
    doi       = {10.4230/dblp.xml.2026-02-01},
    url       = {https://doi.org/10.4230/dblp.xml.2026-02-01},
    month     = {February},
    year      = {2026},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik} 
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.61
Random Unitaries in Constant (Quantum) Time

Authors: Ben Foxman, Natalie Parham, Francisca Vasconcelos, and Henry Yuen

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

Abstract
Random unitaries are a central object of study in quantum information, with applications to quantum computation, quantum many-body physics, and quantum cryptography. Recent work has constructed unitary designs and pseudorandom unitaries (PRUs) using Θ(log log n)-depth unitary circuits with two-qubit gates. In this work, we show that unitary designs and PRUs can be efficiently constructed in several well-studied models of constant-time quantum computation (i.e., the time complexity on the quantum computer is independent of the system size). These models are constant-depth circuits augmented with certain nonlocal operations, such as (a) many-qubit TOFFOLI gates, (b) many-qubit FANOUT gates, or (c) mid-circuit measurements with classical feedforward control. Recent advances in quantum computing hardware suggest experimental feasibility of these models in the near future. Our results demonstrate that unitary designs and PRUs can be constructed in much weaker circuit models than previously thought. Furthermore, our construction of PRUs in constant-depth with many-qubit TOFFOLI gates shows that, under cryptographic assumptions, there is no polynomial-time learning algorithm for the circuit class QAC⁰. Finally, our results suggest a new approach towards proving that PARITY is not computable in QAC⁰, a long-standing question in quantum complexity theory.
Cite as

Ben Foxman, Natalie Parham, Francisca Vasconcelos, and Henry Yuen. Random Unitaries in Constant (Quantum) Time. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 61:1-61:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{foxman_et_al:LIPIcs.ITCS.2026.61,
  author =	{Foxman, Ben and Parham, Natalie and Vasconcelos, Francisca and Yuen, Henry},
  title =	{{Random Unitaries in Constant (Quantum) Time}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{61:1--61:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.61},
  URN =		{urn:nbn:de:0030-drops-253481},
  doi =		{10.4230/LIPIcs.ITCS.2026.61},
  annote =	{Keywords: Quantum Information, Pseudorandomness, Circuit Complexity}
}
Artifact
Dataset
DOI: 10.4230/dblp.rdf.ntriples.2026-01-01
dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of January 2026

Authors: dblp Team

Abstract
Cite as

dblp Team. dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of January 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Copy BibTex To Clipboard

@misc{dblp.rdf.ntriples.2026-01-01,
    title     = {{dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of January 2026}},
    author    = {dblp Team},
    doi       = {10.4230/dblp.rdf.ntriples.2026-01-01},
    url       = {https://doi.org/10.4230/dblp.rdf.ntriples.2026-01-01},
    month     = {January},
    year      = {2026},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik} 
}
Artifact
Dataset
DOI: 10.4230/dblp.xml.2026-01-01
dblp computer science bibliography – Monthly Snapshot XML Release of January 2026

Authors: dblp Team

Abstract
Cite as

dblp Team. dblp computer science bibliography – Monthly Snapshot XML Release of January 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Copy BibTex To Clipboard

@misc{dblp.xml.2026-01-01,
    title     = {{dblp computer science bibliography – Monthly Snapshot XML Release of January 2026}},
    author    = {dblp Team},
    doi       = {10.4230/dblp.xml.2026-01-01},
    url       = {https://doi.org/10.4230/dblp.xml.2026-01-01},
    month     = {January},
    year      = {2026},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik} 
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.30
A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles II: Vertex and Edge Deletion Numbers

Authors: Jesse Beisegel, Katharina Klost, Kristin Knorr, Fabienne Ratajczak, and Robert Scheffler

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
We consider the problem of finding a Hamiltonian path or cycle with precedence constraints in the form of a partial order on the vertex set. We study the complexity for graph width parameters for which the ordinary problems Hamiltonian Path and Hamiltonian Cycle are in FPT. In particular, we focus on parameters that describe how many vertices and edges have to be deleted to become a member of a certain graph class. We show that the problems are W[1]-hard for such restricted cases as vertex distance to path and vertex distance to clique. We complement these results by showing that the problems can be solved in XP time for vertex distance to outerplanar and vertex distance to block. Furthermore, we present some FPT algorithms, e.g., for edge distance to block. Additionally, we prove para-NP-hardness when considered with the edge clique cover number.
Cite as

Jesse Beisegel, Katharina Klost, Kristin Knorr, Fabienne Ratajczak, and Robert Scheffler. A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles II: Vertex and Edge Deletion Numbers. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 30:1-30:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{beisegel_et_al:LIPIcs.IPEC.2025.30,
  author =	{Beisegel, Jesse and Klost, Katharina and Knorr, Kristin and Ratajczak, Fabienne and Scheffler, Robert},
  title =	{{A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles II: Vertex and Edge Deletion Numbers}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{30:1--30:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.30},
  URN =		{urn:nbn:de:0030-drops-251623},
  doi =		{10.4230/LIPIcs.IPEC.2025.30},
  annote =	{Keywords: Hamiltonian path, Hamiltonian cycle, partial order, graph width parameter, parameterized complexity}
}
Artifact
Dataset
DOI: 10.4230/dblp.rdf.ntriples.2025-12-01
dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of December 2025

Authors: dblp Team

Abstract
Cite as

dblp Team. dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of December 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Copy BibTex To Clipboard

@misc{dblp.rdf.ntriples.2025-12-01,
    title     = {{dblp computer science bibliography – Monthly Snapshot RDF/N-Triple Release of December 2025}},
    author    = {dblp Team},
    doi       = {10.4230/dblp.rdf.ntriples.2025-12-01},
    url       = {https://doi.org/10.4230/dblp.rdf.ntriples.2025-12-01},
    month     = {December},
    year      = {2025},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik} 
}
  • Refine by Type
  • 200 Artifact
  • 68 Document/PDF
  • 49 Document/HTML

  • Refine by Publication Year
  • 13 2026
  • 70 2025
  • 26 2024
  • 29 2023
  • 27 2022
  • Show More...

  • Refine by Author
  • 200 dblp Team
  • 16 Hoffmann, Michael
  • 4 Kaufmann, Michael
  • 3 Erlebach, Thomas
  • 3 Tóth, Csaba D.
  • Show More...

  • Refine by Series/Journal
  • 62 LIPIcs
  • 4 OASIcs
  • 1 TGDK
  • 1 DagSemProc

  • Refine by Classification
  • 14 Theory of computation → Computational geometry
  • 9 Human-centered computing → Graph drawings
  • 7 Mathematics of computing → Combinatorics
  • 7 Mathematics of computing → Graph theory
  • 7 Theory of computation → Design and analysis of algorithms
  • Show More...

  • Refine by Keyword
  • 200 bibliography
  • 200 computer science
  • 200 dblp
  • 200 knowledge graph
  • 200 open data
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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