6 Search Results for "Fischer, Michael"


Document
Superlinear Lower Bounds Based on ETH

Authors: András Z. Salamon and Michael Wehar

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)


Abstract
We introduce techniques for proving superlinear conditional lower bounds for polynomial time problems. In particular, we show that CircuitSAT for circuits with m gates and log(m) inputs (denoted by log-CircuitSAT) is not decidable in essentially-linear time unless the exponential time hypothesis (ETH) is false and k-Clique is decidable in essentially-linear time in terms of the graph’s size for all fixed k. Such conditional lower bounds have previously only been demonstrated relative to the strong exponential time hypothesis (SETH). Our results therefore offer significant progress towards proving unconditional superlinear time complexity lower bounds for natural problems in polynomial time.

Cite as

András Z. Salamon and Michael Wehar. Superlinear Lower Bounds Based on ETH. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 55:1-55:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{salamon_et_al:LIPIcs.STACS.2022.55,
  author =	{Salamon, Andr\'{a}s Z. and Wehar, Michael},
  title =	{{Superlinear Lower Bounds Based on ETH}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{55:1--55:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.55},
  URN =		{urn:nbn:de:0030-drops-158652},
  doi =		{10.4230/LIPIcs.STACS.2022.55},
  annote =	{Keywords: Circuit Satisfiability, Conditional Lower Bounds, Exponential Time Hypothesis, Limited Nondeterminism}
}
Document
The First Bijective Proof of the Alternating Sign Matrix Theorem Theorem

Authors: Ilse Fischer and Matjaž Konvalinka

Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)


Abstract
Alternating sign matrices are known to be equinumerous with descending plane partitions, totally symmetric self-complementary plane partitions and alternating sign triangles, but a bijective proof for any of these equivalences has been elusive for almost 40 years. In this extended abstract, we provide a sketch of the first bijective proof of the enumeration formula for alternating sign matrices, and of the fact that alternating sign matrices are equinumerous with descending plane partitions. The bijections are based on the operator formula for the number of monotone triangles due to the first author. The starting point for these constructions were known "computational" proofs, but the combinatorial point of view led to several drastic modifications and simplifications. We also provide computer code where all of our constructions have been implemented.

Cite as

Ilse Fischer and Matjaž Konvalinka. The First Bijective Proof of the Alternating Sign Matrix Theorem Theorem. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 12:1-12:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{fischer_et_al:LIPIcs.AofA.2020.12,
  author =	{Fischer, Ilse and Konvalinka, Matja\v{z}},
  title =	{{The First Bijective Proof of the Alternating Sign Matrix Theorem Theorem}},
  booktitle =	{31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)},
  pages =	{12:1--12:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-147-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{159},
  editor =	{Drmota, Michael and Heuberger, Clemens},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.12},
  URN =		{urn:nbn:de:0030-drops-120424},
  doi =		{10.4230/LIPIcs.AofA.2020.12},
  annote =	{Keywords: enumeration, bijective proof, alternating sign matrix, plane partition}
}
Document
Bidirectional Text Compression in External Memory

Authors: Patrick Dinklage, Jonas Ellert, Johannes Fischer, Dominik Köppl, and Manuel Penschuck

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)


Abstract
Bidirectional compression algorithms work by substituting repeated substrings by references that, unlike in the famous LZ77-scheme, can point to either direction. We present such an algorithm that is particularly suited for an external memory implementation. We evaluate it experimentally on large data sets of size up to 128 GiB (using only 16 GiB of RAM) and show that it is significantly faster than all known LZ77 compressors, while producing a roughly similar number of factors. We also introduce an external memory decompressor for texts compressed with any uni- or bidirectional compression scheme.

Cite as

Patrick Dinklage, Jonas Ellert, Johannes Fischer, Dominik Köppl, and Manuel Penschuck. Bidirectional Text Compression in External Memory. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 41:1-41:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{dinklage_et_al:LIPIcs.ESA.2019.41,
  author =	{Dinklage, Patrick and Ellert, Jonas and Fischer, Johannes and K\"{o}ppl, Dominik and Penschuck, Manuel},
  title =	{{Bidirectional Text Compression in External Memory}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{41:1--41:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola 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.2019.41},
  URN =		{urn:nbn:de:0030-drops-111624},
  doi =		{10.4230/LIPIcs.ESA.2019.41},
  annote =	{Keywords: text compression, bidirectional parsing, text decompression, external algorithms}
}
Document
Online Privacy: Towards Informational Self-Determination on the Internet (Dagstuhl Perspectives Workshop 11061)

Authors: Simone Fischer-Hübner, Chris Hoofnagle, Ioannis Krontiris, Kai Rannenberg, and Michael Waidner

Published in: Dagstuhl Manifestos, Volume 1, Issue 1 (2011)


Abstract
While the collection and monetization of user data has become a main source for funding ``free'' services like search engines, online social networks, news sites and blogs, neither privacy-enhancing technologies nor its regulations have kept up with user needs and privacy preferences. The aim of this Manifesto is to raise awareness for the actual state of the art of online privacy, especially in the international research community and in ongoing efforts to improve the respective legal frameworks, and to provide concrete recommendations to industry, regulators, and research agencies for improving online privacy. In particular we examine how the basic principle of informational self-determination, as promoted by European legal doctrines, could be applied to infrastructures like the internet, Web 2.0 and mobile telecommunication networks.

Cite as

Simone Fischer-Hübner, Chris Hoofnagle, Ioannis Krontiris, Kai Rannenberg, and Michael Waidner. Online Privacy: Towards Informational Self-Determination on the Internet (Dagstuhl Perspectives Workshop 11061). In Dagstuhl Manifestos, Volume 1, Issue 1, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@Article{fischerhubner_et_al:DagMan.1.1.1,
  author =	{Fischer-H\"{u}bner, Simone and Hoofnagle, Chris and Krontiris, Ioannis and Rannenberg, Kai and Waidner, Michael},
  title =	{{Online Privacy: Towards Informational Self-Determination on the Internet (Dagstuhl Perspectives Workshop 11061)}},
  pages =	{1--20},
  journal =	{Dagstuhl Manifestos},
  ISSN =	{2193-2433},
  year =	{2011},
  volume =	{1},
  number =	{1},
  editor =	{Fischer-H\"{u}bner, Simone and Hoofnagle, Chris and Krontiris, Ioannis and Rannenberg, Kai and Waidner, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagMan.1.1.1},
  URN =		{urn:nbn:de:0030-drops-32055},
  doi =		{10.4230/DagMan.1.1.1},
  annote =	{Keywords: Online Social Networks, Informational Self-Determination, Privacy Enhancing Technologies, Data Protection Directive}
}
Document
Online Privacy: Towards Informational Self-Determination on the Internet (Dagstuhl Perspectives Workshop 11061)

Authors: Simone Fischer-Hübner, Chris Hoofnagle, Kai Rannenberg, Michael Waidner, Ioannis Krontiris, and Michael Marhöfer

Published in: Dagstuhl Reports, Volume 1, Issue 2 (2011)


Abstract
The Dagstuhl Perspectives Workshop "Online Privacy: Towards Informational Self-Determination on the Internet" (11061) has been held in February 6-11, 2011 at Schloss Dagstuhl. 30 participants from academia, public sector, and industry have identified the current status-of-the-art of and challenges for online privacy as well as derived recommendations for improving online privacy. Whereas the Dagstuhl Manifesto of this workshop concludes the results of the working groups and panel discussions, this article presents the talks of this workshop by their abstracts.

Cite as

Simone Fischer-Hübner, Chris Hoofnagle, Kai Rannenberg, Michael Waidner, Ioannis Krontiris, and Michael Marhöfer. Online Privacy: Towards Informational Self-Determination on the Internet (Dagstuhl Perspectives Workshop 11061). In Dagstuhl Reports, Volume 1, Issue 2, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@Article{fischerhubner_et_al:DagRep.1.2.1,
  author =	{Fischer-H\"{u}bner, Simone and Hoofnagle, Chris and Rannenberg, Kai and Waidner, Michael and Krontiris, Ioannis and Marh\"{o}fer, Michael},
  title =	{{Online Privacy: Towards Informational Self-Determination on the Internet (Dagstuhl Perspectives Workshop 11061)}},
  pages =	{1--15},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2011},
  volume =	{1},
  number =	{2},
  editor =	{Fischer-H\"{u}bner, Simone and Hoofnagle, Chris and Rannenberg, Kai and Waidner, Michael and Krontiris, Ioannis and Marh\"{o}fer, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.1.2.1},
  URN =		{urn:nbn:de:0030-drops-31515},
  doi =		{10.4230/DagRep.1.2.1},
  annote =	{Keywords: Online privacy, Data protection, Data security, Data loss prevention, Informational self-determination, Web 2.0, (mobile) Internet}
}
Document
Programming Multi Agent Systems based on Logic (Dagstuhl Seminar 02481)

Authors: Jürgen Dix and Michael Fischer

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


Abstract

Cite as

Jürgen Dix and Michael Fischer. Programming Multi Agent Systems based on Logic (Dagstuhl Seminar 02481). Dagstuhl Seminar Report 361, pp. 1-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2002)


Copy BibTex To Clipboard

@TechReport{dix_et_al:DagSemRep.361,
  author =	{Dix, J\"{u}rgen and Fischer, Michael},
  title =	{{Programming Multi Agent Systems based on Logic (Dagstuhl Seminar 02481)}},
  pages =	{1--18},
  ISSN =	{1619-0203},
  year =	{2002},
  type = 	{Dagstuhl Seminar Report},
  number =	{361},
  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.361},
  URN =		{urn:nbn:de:0030-drops-152415},
  doi =		{10.4230/DagSemRep.361},
}
  • Refine by Author
  • 2 Fischer-Hübner, Simone
  • 2 Hoofnagle, Chris
  • 2 Krontiris, Ioannis
  • 2 Rannenberg, Kai
  • 2 Waidner, Michael
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Combinatorial algorithms
  • 1 Mathematics of computing → Combinatoric problems
  • 1 Mathematics of computing → Enumeration
  • 1 Theory of computation → Complexity classes
  • 1 Theory of computation → Data compression
  • Show More...

  • Refine by Keyword
  • 1 (mobile) Internet
  • 1 Circuit Satisfiability
  • 1 Conditional Lower Bounds
  • 1 Data Protection Directive
  • 1 Data loss prevention
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 2 2011
  • 1 2002
  • 1 2019
  • 1 2020
  • 1 2022

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