2 Search Results for "Länger, Thomas"

Document
DOI: 10.4230/LIPIcs.STACS.2012.326
Lower Bounds on the Complexity of MSO_1 Model-Checking

Authors: Robert Ganian, Petr Hlineny, Alexander Langer, Jan Obdržálek, Peter Rossmanith, and Somnath Sikdar

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Abstract
One of the most important algorithmic meta-theorems is a famous result by Courcelle, which states that any graph problem definable in monadic second-order logic with edge-set quantifications (MSO2) is decidable in linear time on any class of graphs of bounded tree-width. In the parlance of parameterized complexity, this means that MSO2 model-checking is fixed-parameter tractable with respect to the tree-width as parameter. Recently, Kreutzer and Tazari proved a corresponding complexity lower-bound---that MSO2 model-checking is not even in XP wrt the formula size as parameter for graph classes that are subgraph-closed and whose tree-width is poly-logarithmically unbounded. Of course, this is not an unconditional result but holds modulo a certain complexity-theoretic assumption, namely, the Exponential Time Hypothesis (ETH). In this paper we present a closely related result. We show that even MSO1 model-checking with a fixed set of vertex labels, but without edge-set quantifications, is not in XP wrt the formula size as parameter for graph classes which are subgraph-closed and whose tree-width is poly-logarithmically unbounded unless the non-uniform ETH fails. In comparison to Kreutzer and Tazari, (1) we use a stronger prerequisite, namely non-uniform instead of uniform ETH, to avoid the effectiveness assumption and the construction of certain obstructions used in their proofs; and (2) we assume a different set of problems to be efficiently decidable, namely MSO1-definable properties on vertex labeled graphs instead of MSO2-definable properties on unlabeled graphs. Our result has an interesting consequence in the realm of digraph width measures: Strengthening a recent result, we show that no subdigraph-monotone measure can be algorithmically useful, unless it is within a poly-logarithmic factor of (undirected) tree-width.
Cite as

Robert Ganian, Petr Hlineny, Alexander Langer, Jan Obdržálek, Peter Rossmanith, and Somnath Sikdar. Lower Bounds on the Complexity of MSO_1 Model-Checking. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 326-337, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{ganian_et_al:LIPIcs.STACS.2012.326,
  author =	{Ganian, Robert and Hlineny, Petr and Langer, Alexander and Obdr\v{z}\'{a}lek, Jan and Rossmanith, Peter and Sikdar, Somnath},
  title =	{{Lower Bounds on the Complexity of MSO\underline1 Model-Checking}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{326--337},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.326},
  URN =		{urn:nbn:de:0030-drops-34185},
  doi =		{10.4230/LIPIcs.STACS.2012.326},
  annote =	{Keywords: Monadic Second-Order Logic, Treewidth, Lower Bounds, Exponential Time Hypothesis, Parameterized Complexity}
}
Document
DOI: 10.4230/DagSemProc.09311.3
Quantum key distribution and cryptography: a survey

Authors: Romain Alléaume, Norbert Lütkenhaus, Renato Renner, Philippe Grangier, Thierry Debuisschert, Gregoire Ribordy, Nicolas Gisin, Philippe Painchault, Thomas Pornin, Louis Slavail, Michel Riguidel, Andrew Shilds, Thomas Länger, Momtchil Peev, Mehrdad Dianati, Anthony Leverrier, Andreas Poppe, Jan Bouda, Cyril Branciard, Mark Godfrey, John Rarity, Harald Weinfurter, Anton Zeilinger, and Christian Monyk

Published in: Dagstuhl Seminar Proceedings, Volume 9311, Classical and Quantum Information Assurance Foundations and Practice (2010)

Abstract
I will try to partially answer, based on a review on recent work, the following question: Can QKD and more generally quantum information be useful to cover some practical security requirements in current (and future) IT infrastructures ? I will in particular cover the following topics - practical performances of QKD - QKD network deployment - SECOQC project - Capabilities of QKD as a cryptographic primitive - comparative advantage with other solution, in order to cover practical security requirements - Quantum information and Side-channels - QKD security assurance - Thoughts about "real" Post-Quantum Cryptography
Cite as

Romain Alléaume, Norbert Lütkenhaus, Renato Renner, Philippe Grangier, Thierry Debuisschert, Gregoire Ribordy, Nicolas Gisin, Philippe Painchault, Thomas Pornin, Louis Slavail, Michel Riguidel, Andrew Shilds, Thomas Länger, Momtchil Peev, Mehrdad Dianati, Anthony Leverrier, Andreas Poppe, Jan Bouda, Cyril Branciard, Mark Godfrey, John Rarity, Harald Weinfurter, Anton Zeilinger, and Christian Monyk. Quantum key distribution and cryptography: a survey. In Classical and Quantum Information Assurance Foundations and Practice. Dagstuhl Seminar Proceedings, Volume 9311, pp. 1-29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{alleaume_et_al:DagSemProc.09311.3,
  author =	{All\'{e}aume, Romain and L\"{u}tkenhaus, Norbert and Renner, Renato and Grangier, Philippe and Debuisschert, Thierry and Ribordy, Gregoire and Gisin, Nicolas and Painchault, Philippe and Pornin, Thomas and Slavail, Louis and Riguidel, Michel and Shilds, Andrew and L\"{a}nger, Thomas and Peev, Momtchil and Dianati, Mehrdad and Leverrier, Anthony and Poppe, Andreas and Bouda, Jan and Branciard, Cyril and Godfrey, Mark and Rarity, John and Weinfurter, Harald and Zeilinger, Anton and Monyk, Christian},
  title =	{{Quantum key distribution and cryptography: a survey}},
  booktitle =	{Classical and Quantum Information Assurance Foundations and Practice},
  pages =	{1--29},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9311},
  editor =	{Samual L. Braunstein and Hoi-Kwong Lo and Kenny Paterson and Peter Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09311.3},
  URN =		{urn:nbn:de:0030-drops-23618},
  doi =		{10.4230/DagSemProc.09311.3},
  annote =	{Keywords: QKD, QKD networks, Security assurance, Post-Quantum Cryptography}
}
  • Refine by Author
  • 1 Alléaume, Romain
  • 1 Bouda, Jan
  • 1 Branciard, Cyril
  • 1 Debuisschert, Thierry
  • 1 Dianati, Mehrdad
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 1 Exponential Time Hypothesis
  • 1 Lower Bounds
  • 1 Monadic Second-Order Logic
  • 1 Parameterized Complexity
  • 1 Post-Quantum Cryptography
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2010
  • 1 2012

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