Search Results

Documents authored by Schöning, Uwe

Document
DOI: 10.4230/DagSemProc.06451.3
A note on the size of Craig Interpolants

Authors: Uwe Schöning and Jacobo Torán

Published in: Dagstuhl Seminar Proceedings, Volume 6451, Circuits, Logic, and Games (2007)

Abstract
Mundici considered the question of whether the interpolant of two propositional formulas of the form $F ightarrow G$ can always have a short circuit description, and showed that if this is the case then every problem in NP $cap$ co-NP would have polynomial size circuits. In this note we observe further consequences of the interpolant having short circuit descriptions, namely that UP $subseteq$ P$/$poly, and that every single valued NP function has a total extension in FP$/$poly. We also relate this question with other Complexity Theory assumptions.
Cite as

Uwe Schöning and Jacobo Torán. A note on the size of Craig Interpolants. In Circuits, Logic, and Games. Dagstuhl Seminar Proceedings, Volume 6451, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{schoning_et_al:DagSemProc.06451.3,
  author =	{Sch\"{o}ning, Uwe and Tor\'{a}n, Jacobo},
  title =	{{A note on the size of Craig Interpolants}},
  booktitle =	{Circuits, Logic, and Games},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6451},
  editor =	{Thomas Schwentick and Denis Th\'{e}rien and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06451.3},
  URN =		{urn:nbn:de:0030-drops-9735},
  doi =		{10.4230/DagSemProc.06451.3},
  annote =	{Keywords: Interpolant, non-uniform complexity}
}
Document
DOI: 10.4230/DagSemProc.04421.5
Randomized QuickSort and the Entropy of the Random Source

Authors: Beatrice List, Markus Maucher, Uwe Schöning, and Rainer Schuler

Published in: Dagstuhl Seminar Proceedings, Volume 4421, Algebraic Methods in Computational Complexity (2005)

Abstract
The worst-case complexity of an implementation of Quicksort depends on the random number generator that is used to select the pivot elements. In this paper we estimate the expected number of comparisons of Quicksort as a function in the entropy of the random source. We give upper and lower bounds and show that the expected number of comparisons increases from $n\log n$ to $n^2$, if the entropy of the random source is bounded. As examples we show explicit bounds for distributions with bounded min-entropy and the geometrical distribution.
Cite as

Beatrice List, Markus Maucher, Uwe Schöning, and Rainer Schuler. Randomized QuickSort and the Entropy of the Random Source. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 4421, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{list_et_al:DagSemProc.04421.5,
  author =	{List, Beatrice and Maucher, Markus and Sch\"{o}ning, Uwe and Schuler, Rainer},
  title =	{{Randomized QuickSort and the Entropy of the Random Source}},
  booktitle =	{Algebraic Methods in Computational Complexity},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4421},
  editor =	{Harry Buhrman and Lance Fortnow and Thomas Thierauf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04421.5},
  URN =		{urn:nbn:de:0030-drops-1043},
  doi =		{10.4230/DagSemProc.04421.5},
  annote =	{Keywords: Randomized Algorithms , QuickSort , Entropy}
}
Document
DOI: 10.4230/DagSemRep.374
The Propositional Satisfiability Problem -- Algorithms and Lower Bounds (Dagstuhl Seminar 03141)

Authors: Andreas Goerdt, Pavel Pudlák, Uwe Schöning, and Osamu Watanabe

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

Abstract
Cite as

Andreas Goerdt, Pavel Pudlák, Uwe Schöning, and Osamu Watanabe. The Propositional Satisfiability Problem -- Algorithms and Lower Bounds (Dagstuhl Seminar 03141). Dagstuhl Seminar Report 374, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2003)

Copy BibTex To Clipboard

@TechReport{goerdt_et_al:DagSemRep.374,
  author =	{Goerdt, Andreas and Pudl\'{a}k, Pavel and Sch\"{o}ning, Uwe and Watanabe, Osamu},
  title =	{{The Propositional Satisfiability Problem -- Algorithms and Lower Bounds (Dagstuhl Seminar 03141)}},
  pages =	{1--5},
  ISSN =	{1619-0203},
  year =	{2003},
  type = 	{Dagstuhl Seminar Report},
  number =	{374},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.374},
  URN =		{urn:nbn:de:0030-drops-152545},
  doi =		{10.4230/DagSemRep.374},
}
Document
DOI: 10.4230/DagSemRep.158
Structure and Complexity (Dagstuhl Seminar 9640)

Authors: Eric Allender, Uwe Schöning, and Klaus W. Wagner

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

Abstract
Cite as

Eric Allender, Uwe Schöning, and Klaus W. Wagner. Structure and Complexity (Dagstuhl Seminar 9640). Dagstuhl Seminar Report 158, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1996)

Copy BibTex To Clipboard

@TechReport{allender_et_al:DagSemRep.158,
  author =	{Allender, Eric and Sch\"{o}ning, Uwe and Wagner, Klaus W.},
  title =	{{Structure and Complexity (Dagstuhl Seminar 9640)}},
  pages =	{1--22},
  ISSN =	{1619-0203},
  year =	{1996},
  type = 	{Dagstuhl Seminar Report},
  number =	{158},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.158},
  URN =		{urn:nbn:de:0030-drops-150450},
  doi =		{10.4230/DagSemRep.158},
}
Document
DOI: 10.4230/DagSemRep.82
Structure and Complexity (Dagstuhl Seminar 9407)

Authors: Klaus Ambos-Spies, Steven Homer, and Uwe Schöning

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

Abstract
Cite as

Klaus Ambos-Spies, Steven Homer, and Uwe Schöning. Structure and Complexity (Dagstuhl Seminar 9407). Dagstuhl Seminar Report 82, pp. 1-30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1994)

Copy BibTex To Clipboard

@TechReport{ambosspies_et_al:DagSemRep.82,
  author =	{Ambos-Spies, Klaus and Homer, Steven and Sch\"{o}ning, Uwe},
  title =	{{Structure and Complexity (Dagstuhl Seminar 9407)}},
  pages =	{1--30},
  ISSN =	{1619-0203},
  year =	{1994},
  type = 	{Dagstuhl Seminar Report},
  number =	{82},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.82},
  URN =		{urn:nbn:de:0030-drops-149701},
  doi =		{10.4230/DagSemRep.82},
}
Document
DOI: 10.4230/DagSemRep.30
Structure and Complexity Theory (Dagstuhl Seminar 9206)

Authors: Klaus Ambos-Spies, Steven Homer, and Uwe Schöning

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

Abstract
Cite as

Klaus Ambos-Spies, Steven Homer, and Uwe Schöning. Structure and Complexity Theory (Dagstuhl Seminar 9206). Dagstuhl Seminar Report 30, pp. 1-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1992)

Copy BibTex To Clipboard

@TechReport{ambosspies_et_al:DagSemRep.30,
  author =	{Ambos-Spies, Klaus and Homer, Steven and Sch\"{o}ning, Uwe},
  title =	{{Structure and Complexity Theory (Dagstuhl Seminar 9206)}},
  pages =	{1--24},
  ISSN =	{1619-0203},
  year =	{1992},
  type = 	{Dagstuhl Seminar Report},
  number =	{30},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.30},
  URN =		{urn:nbn:de:0030-drops-149183},
  doi =		{10.4230/DagSemRep.30},
}
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