10 Search Results for "Klein, Michael"


Document
(No) Quantum Space-Time Tradeoff for USTCON

Authors: Simon Apers, Stacey Jeffery, Galina Pass, and Michael Walter

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)


Abstract
Undirected st-connectivity is important both for its applications in network problems, and for its theoretical connections with logspace complexity. Classically, a long line of work led to a time-space tradeoff of T = Õ(n²/S) for any S such that S = Ω(log(n)) and S = O(n²/m). Surprisingly, we show that quantumly there is no nontrivial time-space tradeoff: there is a quantum algorithm that achieves both optimal time Õ(n) and space O(log(n)) simultaneously. This improves on previous results, which required either O(log(n)) space and Õ(n^{1.5}) time, or Õ(n) space and time. To complement this, we show that there is a nontrivial time-space tradeoff when given a lower bound on the spectral gap of a corresponding random walk.

Cite as

Simon Apers, Stacey Jeffery, Galina Pass, and Michael Walter. (No) Quantum Space-Time Tradeoff for USTCON. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{apers_et_al:LIPIcs.ESA.2023.10,
  author =	{Apers, Simon and Jeffery, Stacey and Pass, Galina and Walter, Michael},
  title =	{{(No) Quantum Space-Time Tradeoff for USTCON}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{10:1--10:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.10},
  URN =		{urn:nbn:de:0030-drops-186636},
  doi =		{10.4230/LIPIcs.ESA.2023.10},
  annote =	{Keywords: Undirected st-connectivity, quantum walks, time-space tradeoff}
}
Document
Quantum Algorithm for Path-Edge Sampling

Authors: Stacey Jeffery, Shelby Kimmel, and Alvaro Piedrafita

Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)


Abstract
We present a quantum algorithm for sampling an edge on a path between two nodes s and t in an undirected graph given as an adjacency matrix, and show that this can be done in query complexity that is asymptotically the same, up to log factors, as the query complexity of detecting a path between s and t. We use this path sampling algorithm as a subroutine for st-path finding and st-cut-set finding algorithms in some specific cases. Our main technical contribution is an algorithm for generating a quantum state that is proportional to the positive witness vector of a span program.

Cite as

Stacey Jeffery, Shelby Kimmel, and Alvaro Piedrafita. Quantum Algorithm for Path-Edge Sampling. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 5:1-5:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{jeffery_et_al:LIPIcs.TQC.2023.5,
  author =	{Jeffery, Stacey and Kimmel, Shelby and Piedrafita, Alvaro},
  title =	{{Quantum Algorithm for Path-Edge Sampling}},
  booktitle =	{18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)},
  pages =	{5:1--5:28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-283-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{266},
  editor =	{Fawzi, Omar and Walter, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2023.5},
  URN =		{urn:nbn:de:0030-drops-183151},
  doi =		{10.4230/LIPIcs.TQC.2023.5},
  annote =	{Keywords: Algorithm design and analysis, Query complexity, Graph algorithms, Span program algorithm, Path finding, Path detection}
}
Document
Parallelizing a SAT-Based Product Configurator

Authors: Nils Merlin Ullmann, Tomáš Balyo, and Michael Klein

Published in: LIPIcs, Volume 210, 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)


Abstract
This paper presents how state-of-the-art parallel algorithms designed to solve the Satisfiability (SAT) problem can be applied in the domain of product configuration. During an interactive configuration process, a user selects features step-by-step to find a suitable configuration that fulfills his desires and the set of product constraints. A configuration system can be used to guide the user through the process by validating the selections and providing feedback. Each validation of a user selection is formulated as a SAT problem. Furthermore, an optimization problem is identified to find solutions with the minimum amount of changes compared to the previous configuration. Another additional constraint is deterministic computation, which is not trivial to achieve in well performing parallel SAT solvers. In the paper we propose five new deterministic parallel algorithms and experimentally compare them. Experiments show that reasonable speedups are achieved by using multiple threads over the sequential counterpart.

Cite as

Nils Merlin Ullmann, Tomáš Balyo, and Michael Klein. Parallelizing a SAT-Based Product Configurator. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 55:1-55:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{ullmann_et_al:LIPIcs.CP.2021.55,
  author =	{Ullmann, Nils Merlin and Balyo, Tom\'{a}\v{s} and Klein, Michael},
  title =	{{Parallelizing a SAT-Based Product Configurator}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{55:1--55:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-211-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{210},
  editor =	{Michel, Laurent D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2021.55},
  URN =		{urn:nbn:de:0030-drops-153464},
  doi =		{10.4230/LIPIcs.CP.2021.55},
  annote =	{Keywords: Configuration, Satisfiability, Parallel}
}
Document
System Calls Instrumentation for Intrusion Detection in Embedded Mixed-Criticality Systems

Authors: Marine Kadar, Sergey Tverdyshev, and Gerhard Fohler

Published in: OASIcs, Volume 73, 4th International Workshop on Security and Dependability of Critical Embedded Real-Time Systems (CERTS 2019)


Abstract
System call relative information such as occurrences, type, parameters, and return values are well established metrics to reveal intrusions in a system software. Many Host Intrusion Detection Systems (HIDS) from research and industry analyze these data for continuous system monitoring at runtime. Despite a significant false alarm rate, this type of defense offers high detection precision for both known and zero-day attacks. Recent research focuses on HIDS deployment for desktop computers. Yet, the integration of such run-time monitoring solution in mixed-criticality embedded systems has not been discussed. Because of the cohabitation of potentially vulnerable non-critical software with critical software, securing mixed-criticality systems is a non trivial but essential issue. Thus, we propose a methodology to evaluate the impact of deploying system call instrumentation in such context. We analyze the impact in a concrete use-case with PikeOS real-time hypervisor.

Cite as

Marine Kadar, Sergey Tverdyshev, and Gerhard Fohler. System Calls Instrumentation for Intrusion Detection in Embedded Mixed-Criticality Systems. In 4th International Workshop on Security and Dependability of Critical Embedded Real-Time Systems (CERTS 2019). Open Access Series in Informatics (OASIcs), Volume 73, pp. 2:1-2:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{kadar_et_al:OASIcs.CERTS.2019.2,
  author =	{Kadar, Marine and Tverdyshev, Sergey and Fohler, Gerhard},
  title =	{{System Calls Instrumentation for Intrusion Detection in Embedded Mixed-Criticality Systems}},
  booktitle =	{4th International Workshop on Security and Dependability of Critical Embedded Real-Time Systems (CERTS 2019)},
  pages =	{2:1--2:13},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-119-1},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{73},
  editor =	{Asplund, Mikael and Paulitsch, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.CERTS.2019.2},
  URN =		{urn:nbn:de:0030-drops-108933},
  doi =		{10.4230/OASIcs.CERTS.2019.2},
  annote =	{Keywords: Instrumentation, Mixed-criticality, Real-Time, System Calls, Host Intrusion Detection Systems}
}
Document
Partially Walking a Polygon

Authors: Franz Aurenhammer, Michael Steinkogler, and Rolf Klein

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)


Abstract
Deciding two-guard walkability of an n-sided polygon is a well-understood problem. We study the following more general question: How far can two guards reach from a given source vertex while staying mutually visible, in the (more realistic) case that the polygon is not entirely walkable? There can be Theta(n) such maximal walks, and we show how to find all of them in O(n log n) time.

Cite as

Franz Aurenhammer, Michael Steinkogler, and Rolf Klein. Partially Walking a Polygon. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 60:1-60:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{aurenhammer_et_al:LIPIcs.ISAAC.2018.60,
  author =	{Aurenhammer, Franz and Steinkogler, Michael and Klein, Rolf},
  title =	{{Partially Walking a Polygon}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{60:1--60:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.60},
  URN =		{urn:nbn:de:0030-drops-100089},
  doi =		{10.4230/LIPIcs.ISAAC.2018.60},
  annote =	{Keywords: Polygon, guard walk, visibility}
}
Document
Closing the Gap for Makespan Scheduling via Sparsification Techniques

Authors: Klaus Jansen, Kim-Manuel Klein, and José Verschae

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)


Abstract
Makespan scheduling on identical machines is one of the most basic and fundamental packing problem studied in the discrete optimization literature. It asks for an assignment of n jobs to a set of m identical machines that minimizes the makespan. The problem is strongly NPhard, and thus we do not expect a (1 + epsilon)-approximation algorithm with a running time that depends polynomially on 1/epsilon. Furthermore, Chen et al. [Chen/JansenZhang, SODA'13] recently showed that a running time of 2^{1/epsilon}^{1-delta} + poly(n) for any delta > 0 would imply that the Exponential Time Hypothesis (ETH) fails. A long sequence of algorithms have been developed that try to obtain low dependencies on 1/epsilon, the better of which achieves a running time of 2^{~O(1/epsilon^{2})} + O(n*log(n)) [Jansen, SIAM J. Disc. Math. 2010]. In this paper we obtain an algorithm with a running time of 2^{~O(1/epsilon)} + O(n*log(n)), which is tight under ETH up to logarithmic factors on the exponent. Our main technical contribution is a new structural result on the configuration-IP. More precisely, we show the existence of a highly symmetric and sparse optimal solution, in which all but a constant number of machines are assigned a configuration with small support. This structure can then be exploited by integer programming techniques and enumeration. We believe that our structural result is of independent interest and should find applications to other settings. In particular, we show how the structure can be applied to the minimum makespan problem on related machines and to a larger class of objective functions on parallel machines. For all these cases we obtain an efficient PTAS with running time 2^{~O(1/epsilon)} + poly(n).

Cite as

Klaus Jansen, Kim-Manuel Klein, and José Verschae. Closing the Gap for Makespan Scheduling via Sparsification Techniques. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 72:1-72:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.ICALP.2016.72,
  author =	{Jansen, Klaus and Klein, Kim-Manuel and Verschae, Jos\'{e}},
  title =	{{Closing the Gap for Makespan Scheduling via Sparsification Techniques}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{72:1--72:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.72},
  URN =		{urn:nbn:de:0030-drops-62122},
  doi =		{10.4230/LIPIcs.ICALP.2016.72},
  annote =	{Keywords: scheduling, approximation, PTAS, makespan, ETH}
}
Document
08191 Working Group Summary – Visually Comparing a Set of Graphs

Authors: Mario Albrecht, Alejandro Estrella-Balderrama, Markus Geyer, Carsten Gutwenger, Karsten Klein, Oliver Kohlbacher, and Michael Schulz

Published in: Dagstuhl Seminar Proceedings, Volume 8191, Graph Drawing with Applications to Bioinformatics and Social Sciences (2008)


Abstract
We consider methods to visually compare graphs, more to focus on the differences of the graphs than on the similarities. Our two-level approach constructs a meaningful overview of the given graphs combined with a detailed view focusing on a local area of change. The actual layout of these graphs has to be evaluated depending on the specific type of biological network to be visualized in each case. We look into different variants and propose properties to be optimized in our visualizations.

Cite as

Mario Albrecht, Alejandro Estrella-Balderrama, Markus Geyer, Carsten Gutwenger, Karsten Klein, Oliver Kohlbacher, and Michael Schulz. 08191 Working Group Summary – Visually Comparing a Set of Graphs. In Graph Drawing with Applications to Bioinformatics and Social Sciences. Dagstuhl Seminar Proceedings, Volume 8191, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{albrecht_et_al:DagSemProc.08191.6,
  author =	{Albrecht, Mario and Estrella-Balderrama, Alejandro and Geyer, Markus and Gutwenger, Carsten and Klein, Karsten and Kohlbacher, Oliver and Schulz, Michael},
  title =	{{08191 Working Group Summary – Visually Comparing a Set of Graphs}},
  booktitle =	{Graph Drawing with Applications to Bioinformatics and Social Sciences},
  pages =	{1--6},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8191},
  editor =	{Stephen P. Borgatti and Stephen Kobourov and Oliver Kohlbacher and Petra Mutzel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08191.6},
  URN =		{urn:nbn:de:0030-drops-15536},
  doi =		{10.4230/DagSemProc.08191.6},
  annote =	{Keywords: Graph drawing, visual graph comparison}
}
Document
04441 Working Group – Description and Matching of Services in Mobile Environments

Authors: Johannes Grünbauer, Michael Klein, Georgia Koloniari, George Samaras, and Can Türker

Published in: Dagstuhl Seminar Proceedings, Volume 4441, Mobile Information Management (2005)


Abstract
Service oriented computing is a new paradigm that is especially interesting in mobile environments. As a characteristics, functionality is hidden behind an interface and described as a black box with the help of a service description lan- guage. This enables participants of the network to enlarge the limited capabilities of their devices by using services provided by others. As service requestors and providers are not fixedly tied together but are dynamically matched and bound, this architecture is especially advantageous in mobile environments and their constantly changing situation

Cite as

Johannes Grünbauer, Michael Klein, Georgia Koloniari, George Samaras, and Can Türker. 04441 Working Group – Description and Matching of Services in Mobile Environments. In Mobile Information Management. Dagstuhl Seminar Proceedings, Volume 4441, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{grunbauer_et_al:DagSemProc.04441.5,
  author =	{Gr\"{u}nbauer, Johannes and Klein, Michael and Koloniari, Georgia and Samaras, George and T\"{u}rker, Can},
  title =	{{04441 Working Group – Description and Matching of Services in Mobile Environments}},
  booktitle =	{Mobile Information Management},
  pages =	{1--6},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4441},
  editor =	{Margaret H. Dunham and Birgitta K\"{o}nig-Ries and Evaggelia Pitoura and Peter Reiher and Can T\"{u}rker},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.04441.5},
  URN =		{urn:nbn:de:0030-drops-1672},
  doi =		{10.4230/DagSemProc.04441.5},
  annote =	{Keywords: Service Description , Mobile Environment}
}
Document
Multimedia Retrieval (Dagstuhl Seminar 03112)

Authors: Michael Clause, Rolf Klein, and Ian H. Witten

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


Abstract

Cite as

Michael Clause, Rolf Klein, and Ian H. Witten. Multimedia Retrieval (Dagstuhl Seminar 03112). Dagstuhl Seminar Report 371, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2003)


Copy BibTex To Clipboard

@TechReport{clause_et_al:DagSemRep.371,
  author =	{Clause, Michael and Klein, Rolf and Witten, Ian H.},
  title =	{{Multimedia Retrieval (Dagstuhl Seminar 03112)}},
  pages =	{1--4},
  ISSN =	{1619-0203},
  year =	{2003},
  type = 	{Dagstuhl Seminar Report},
  number =	{371},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.371},
  URN =		{urn:nbn:de:0030-drops-152517},
  doi =		{10.4230/DagSemRep.371},
}
Document
Computational Geometry (Dagstuhl Seminar 99102)

Authors: Michael Goodrich, Rolf Klein, and Raimund Seidel

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


Abstract

Cite as

Michael Goodrich, Rolf Klein, and Raimund Seidel. Computational Geometry (Dagstuhl Seminar 99102). Dagstuhl Seminar Report 233, pp. 1-27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2000)


Copy BibTex To Clipboard

@TechReport{goodrich_et_al:DagSemRep.233,
  author =	{Goodrich, Michael and Klein, Rolf and Seidel, Raimund},
  title =	{{Computational Geometry (Dagstuhl Seminar 99102)}},
  pages =	{1--27},
  ISSN =	{1619-0203},
  year =	{2000},
  type = 	{Dagstuhl Seminar Report},
  number =	{233},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.233},
  URN =		{urn:nbn:de:0030-drops-151191},
  doi =		{10.4230/DagSemRep.233},
}
  • Refine by Author
  • 3 Klein, Rolf
  • 2 Jeffery, Stacey
  • 2 Klein, Michael
  • 1 Albrecht, Mario
  • 1 Apers, Simon
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Design and analysis of algorithms
  • 1 Applied computing → E-commerce infrastructure
  • 1 Security and privacy → Embedded systems security
  • 1 Security and privacy → Intrusion detection systems
  • 1 Theory of computation → Algorithm design techniques
  • Show More...

  • Refine by Keyword
  • 1 Algorithm design and analysis
  • 1 Configuration
  • 1 ETH
  • 1 Graph algorithms
  • 1 Graph drawing
  • Show More...

  • Refine by Type
  • 10 document

  • Refine by Publication Year
  • 2 2023
  • 1 2000
  • 1 2003
  • 1 2005
  • 1 2008
  • 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