7 Search Results for "Schöning, Uwe"

Document
DOI: 10.4230/LIPIcs.ITCS.2023.3
Kolmogorov Complexity Characterizes Statistical Zero Knowledge

Authors: Eric Allender, Shuichi Hirahara, and Harsha Tirumala

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
We show that a decidable promise problem has a non-interactive statistical zero-knowledge proof system if and only if it is randomly reducible via an honest polynomial-time reduction to a promise problem for Kolmogorov-random strings, with a superlogarithmic additive approximation term. This extends recent work by Saks and Santhanam (CCC 2022). We build on this to give new characterizations of Statistical Zero Knowledge SZK, as well as the related classes NISZK_L and SZK_L.
Cite as

Eric Allender, Shuichi Hirahara, and Harsha Tirumala. Kolmogorov Complexity Characterizes Statistical Zero Knowledge. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 3:1-3:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{allender_et_al:LIPIcs.ITCS.2023.3,
  author =	{Allender, Eric and Hirahara, Shuichi and Tirumala, Harsha},
  title =	{{Kolmogorov Complexity Characterizes Statistical Zero Knowledge}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{3:1--3:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.3},
  URN =		{urn:nbn:de:0030-drops-175063},
  doi =		{10.4230/LIPIcs.ITCS.2023.3},
  annote =	{Keywords: Kolmogorov Complexity, Interactive Proofs}
}
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-dev.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-dev.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-dev.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-dev.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-dev.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-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.30},
  URN =		{urn:nbn:de:0030-drops-149183},
  doi =		{10.4230/DagSemRep.30},
}
  • Refine by Author
  • 6 Schöning, Uwe
  • 2 Allender, Eric
  • 2 Ambos-Spies, Klaus
  • 2 Homer, Steven
  • 1 Goerdt, Andreas
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Circuit complexity
  • 1 Theory of computation → Complexity classes

  • Refine by Keyword
  • 1 Entropy
  • 1 Interactive Proofs
  • 1 Interpolant
  • 1 Kolmogorov Complexity
  • 1 QuickSort
  • Show More...

  • Refine by Type
  • 7 document

  • Refine by Publication Year
  • 1 1992
  • 1 1994
  • 1 1996
  • 1 2003
  • 1 2005
  • 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact