4 Search Results for "Koenig, Hartmut"

Document
DOI: 10.4230/LIPIcs.ITCS.2026.17
Unconditional Quantum Advantage for Sampling with Shallow Circuits

Authors: Adam Bene Watts and Natalie Parham

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

Abstract
Recent work by Bravyi, Gosset, and Koenig showed that there exists a search problem that a constant-depth quantum circuit can solve, but that any constant-depth classical circuit with bounded fan-in cannot. They also pose the question: Can we achieve a similar proof of separation for an input-independent sampling task? In this paper, we show that the answer to this question is yes when the number of random input bits given to the classical circuit is bounded. We introduce a distribution D_{n} over {0,1}ⁿ and construct a constant-depth uniform quantum circuit family {C_n}_n such that C_n samples from a distribution close to D_{n} in total variation distance. For any δ < 1 we also prove, unconditionally, that any classical circuit with bounded fan-in gates that takes as input kn + n^δ i.i.d. Bernouli random variables with entropy 1/k and produces output close to D_{n} in total variation distance has depth Ω(log log n). This gives an unconditional proof that constant-depth quantum circuits can sample from distributions that can't be reproduced by constant-depth bounded fan-in classical circuits, even up to additive error. We also show a similar separation between constant-depth quantum circuits with advice and classical circuits with bounded fan-in and fan-out, but access to an unbounded number of i.i.d random inputs. The distribution D_n and classical circuit lower bounds are inspired by work of Viola, in which he shows a different (but related) distribution cannot be sampled from approximately by constant-depth bounded fan-in classical circuits.
Cite as

Adam Bene Watts and Natalie Parham. Unconditional Quantum Advantage for Sampling with Shallow Circuits. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 17:1-17:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{benewatts_et_al:LIPIcs.ITCS.2026.17,
  author =	{Bene Watts, Adam and Parham, Natalie},
  title =	{{Unconditional Quantum Advantage for Sampling with Shallow Circuits}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{17:1--17:12},
  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.17},
  URN =		{urn:nbn:de:0030-drops-253048},
  doi =		{10.4230/LIPIcs.ITCS.2026.17},
  annote =	{Keywords: Circuit Complexity, Sampling Separation, Shallow Quantum Circuits, Unconditional Separations, Complexity of Distributions}
}
Document
DOI: 10.4230/DagSemProc.08102.1
1. 08102 Executive Summary – Perspectives Workshop: Network Attack Detection and Defense

Authors: Georg Carle, Falko Dressler, Richard A. Kemmerer, Hartmut Koenig, and Christopher Kruegel

Published in: Dagstuhl Seminar Proceedings, Volume 8102, Perspectives Workshop: Network Attack Detection and Defense (2008)

Abstract
From March 2nd to 6th, 2008, the Dagstuhl Perspective Workshop 08102 Net-work Attack Detection and Defense was held at the International Conference and Research Center (IBFI), Schloss Dagstuhl. The objective of the workshop was to work out a manifesto that identifies past shortcomings and future direc-tions for the field. During the workshop, several participants presented their perspective on the development of the area. Furthermore, ongoing work and on open problems were discussed. Six working groups were formed to discuss the state of the art and the challenges of future research directions. The Executive Summary describes the workshop topics and goals in general, and gives an overview of its course. Abstracts of the presentations given during the work-shop, the outcomes of the working groups, and the manifesto are put together in the online proceedings.
Cite as

Georg Carle, Falko Dressler, Richard A. Kemmerer, Hartmut Koenig, and Christopher Kruegel. 1. 08102 Executive Summary – Perspectives Workshop: Network Attack Detection and Defense. In Perspectives Workshop: Network Attack Detection and Defense. Dagstuhl Seminar Proceedings, Volume 8102, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{carle_et_al:DagSemProc.08102.1,
  author =	{Carle, Georg and Dressler, Falko and Kemmerer, Richard A. and Koenig, Hartmut and Kruegel, Christopher},
  title =	{{1. 08102 Executive Summary – Perspectives Workshop: Network Attack Detection and Defense}},
  booktitle =	{Perspectives Workshop: Network Attack Detection and Defense},
  pages =	{1--6},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8102},
  editor =	{Georg Carle and Falko Dressler and Richard A. Kemmerer and Hartmut K\"{o}nig and Christopher Kruegel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08102.1},
  URN =		{urn:nbn:de:0030-drops-14926},
  doi =		{10.4230/DagSemProc.08102.1},
  annote =	{Keywords: Intrusion detection and prevention, attack response and countermeasures, reactive security, automated security, survivability and self-protection, ma network monitoring, flow analysis, denial of service detection and response, event correlation}
}
Document
DOI: 10.4230/DagSemProc.08102.3
3. 08102 Outcome Working Group – Situational Awareness

Authors: Richard A. Kemmerer, Roland Bueschkes, Ali Fessi, Hartmut Koenig, Peter Herrmann, Stephen Wolthusen, Marko Jahnke, Hervé Debar, Ralph Holz, Tanja Zseby, and Dirk Haage

Published in: Dagstuhl Seminar Proceedings, Volume 8102, Perspectives Workshop: Network Attack Detection and Defense (2008)

Abstract
Situation awareness (SA) has been defined as "the perception of elements in the environment within a volume of time and space, the comprehension of their meaning, and the projection of their status in the near future" (Endsley, 1988, 1995b, 2000).
Cite as

Richard A. Kemmerer, Roland Bueschkes, Ali Fessi, Hartmut Koenig, Peter Herrmann, Stephen Wolthusen, Marko Jahnke, Hervé Debar, Ralph Holz, Tanja Zseby, and Dirk Haage. 3. 08102 Outcome Working Group – Situational Awareness. In Perspectives Workshop: Network Attack Detection and Defense. Dagstuhl Seminar Proceedings, Volume 8102, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{kemmerer_et_al:DagSemProc.08102.3,
  author =	{Kemmerer, Richard A. and Bueschkes, Roland and Fessi, Ali and Koenig, Hartmut and Herrmann, Peter and Wolthusen, Stephen and Jahnke, Marko and Debar, Herv\'{e} and Holz, Ralph and Zseby, Tanja and Haage, Dirk},
  title =	{{3. 08102 Outcome Working Group – Situational Awareness}},
  booktitle =	{Perspectives Workshop: Network Attack Detection and Defense},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8102},
  editor =	{Georg Carle and Falko Dressler and Richard A. Kemmerer and Hartmut K\"{o}nig and Christopher Kruegel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08102.3},
  URN =		{urn:nbn:de:0030-drops-14942},
  doi =		{10.4230/DagSemProc.08102.3},
  annote =	{Keywords: Intrusion detection and prevention, attack response and countermeasures, reactive security, automated security, survivability and self-protection, ma network monitoring, flow analysis, denial of service detection and response, event correlation}
}
Document
DOI: 10.4230/DagSemProc.08102.8
8. 08102 Manifesto – Perspectives Workshop: Network Attack Detection and Defense

Authors: Georg Carle, Falko Dressler, Richard A. Kemmerer, Hartmut Koenig, Christopher Kruegel, and Pavel Laskov

Published in: Dagstuhl Seminar Proceedings, Volume 8102, Perspectives Workshop: Network Attack Detection and Defense (2008)

Abstract
This manifesto is the result of the Perspective Workshop Network Attack Detection and Defense held in Schloss Dagstuhl (Germany) from March 2nd – 6th, 2008. The participants of the workshop represent researchers from Austria, France, Norway, the Switzerland, the United States, and Germany who work actively in the field of intrusion detection and network monitoring. The workshop attendee’s opinion was that intrusion detection and flow analysis, which have been developed as complementary approaches for the detection of network attacks, should more strongly combine event detection and correlation techniques to better meet future challenges in future reactive security. The workshop participants considered various perspectives to envision future network attack detection and defense. The following topics are seen as important in the future: the development of early warning systems, the introduction of situation awareness, the improvement of measurement technology, taxonomy of attacks, the application of intrusion and fraud detection for web services, and anomaly detection. In order to realize those visions the state of the art, the challenges, and research priorities were identified for each topic by working groups. The outcome of the discussion is summarized in working group papers which are published in the workshop proceedings. The papers were compiled by the editors to this manifesto.
Cite as

Georg Carle, Falko Dressler, Richard A. Kemmerer, Hartmut Koenig, Christopher Kruegel, and Pavel Laskov. 8. 08102 Manifesto – Perspectives Workshop: Network Attack Detection and Defense. In Perspectives Workshop: Network Attack Detection and Defense. Dagstuhl Seminar Proceedings, Volume 8102, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{carle_et_al:DagSemProc.08102.8,
  author =	{Carle, Georg and Dressler, Falko and Kemmerer, Richard A. and Koenig, Hartmut and Kruegel, Christopher and Laskov, Pavel},
  title =	{{8. 08102 Manifesto – Perspectives Workshop: Network Attack Detection and Defense}},
  booktitle =	{Perspectives Workshop: Network Attack Detection and Defense},
  pages =	{1--16},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8102},
  editor =	{Georg Carle and Falko Dressler and Richard A. Kemmerer and Hartmut K\"{o}nig and Christopher Kruegel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08102.8},
  URN =		{urn:nbn:de:0030-drops-14917},
  doi =		{10.4230/DagSemProc.08102.8},
  annote =	{Keywords: Manifesto of the Dagstuhl Perspective Workshop, March 2nd - 6th, 2008}
}
  • Refine by Type
  • 4 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 3 2008

  • Refine by Author
  • 3 Kemmerer, Richard A.
  • 3 Koenig, Hartmut
  • 2 Carle, Georg
  • 2 Dressler, Falko
  • 2 Kruegel, Christopher
  • Show More...

  • Refine by Series/Journal
  • 1 LIPIcs
  • 3 DagSemProc

  • Refine by Classification
  • 1 Theory of computation → Circuit complexity
  • 1 Theory of computation → Quantum complexity theory

  • Refine by Keyword
  • 2 Intrusion detection and prevention
  • 2 attack response and countermeasures
  • 2 automated security
  • 2 denial of service detection and response
  • 2 event correlation
  • 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