7 Search Results for "Wegener, Ingo"

Document
DOI: 10.4230/LIPIcs.CCC.2021.17
Branching Programs with Bounded Repetitions and Flow Formulas

Authors: Anastasia Sofronova and Dmitry Sokolov

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

Abstract
Restricted branching programs capture various complexity measures like space in Turing machines or length of proofs in proof systems. In this paper, we focus on the application in the proof complexity that was discovered by Lovasz et al. [László Lovász et al., 1995] who showed the equivalence between regular Resolution and read-once branching programs for "unsatisfied clause search problem" (Search_φ). This connection is widely used, in particular, in the recent breakthrough result about the Clique problem in regular Resolution by Atserias et al. [Albert Atserias et al., 2018]. We study the branching programs with bounded repetitions, so-called (1,+k)-BPs (Sieling [Detlef Sieling, 1996]) in application to the Search_φ problem. On the one hand, it is a natural generalization of read-once branching programs. On the other hand, this model gives a powerful proof system that can efficiently certify the unsatisfiability of a wide class of formulas that is hard for Resolution (Knop [Alexander Knop, 2017]). We deal with Search_φ that is "relatively easy" compared to all known hard examples for the (1,+k)-BPs. We introduce the first technique for proving exponential lower bounds for the (1,+k)-BPs on Search_φ. To do it we combine a well-known technique for proving lower bounds on the size of branching programs [Detlef Sieling, 1996; Detlef Sieling and Ingo Wegener, 1994; Stasys Jukna and Alexander A. Razborov, 1998] with the modification of the "closure" technique [Michael Alekhnovich et al., 2004; Michael Alekhnovich and Alexander A. Razborov, 2003]. In contrast with most Resolution lower bounds, our technique uses not only "local" properties of the formula, but also a "global" structure. Our hard examples are based on the Flow formulas introduced in [Michael Alekhnovich and Alexander A. Razborov, 2003].
Cite as

Anastasia Sofronova and Dmitry Sokolov. Branching Programs with Bounded Repetitions and Flow Formulas. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 17:1-17:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{sofronova_et_al:LIPIcs.CCC.2021.17,
  author =	{Sofronova, Anastasia and Sokolov, Dmitry},
  title =	{{Branching Programs with Bounded Repetitions and Flow Formulas}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{17:1--17:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.17},
  URN =		{urn:nbn:de:0030-drops-142915},
  doi =		{10.4230/LIPIcs.CCC.2021.17},
  annote =	{Keywords: proof complexity, branching programs, bounded repetitions, lower bounds}
}
Document
DOI: 10.4230/LIPIcs.STACS.2008.1348
Tight Bounds for Blind Search on the Integers

Authors: Martin Dietzfelbinger, Jonathan E. Rowe, Ingo Wegener, and Philipp Woelfel

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

Abstract
We analyze a simple random process in which a token is moved in the interval $A={0,dots,n$: Fix a probability distribution $mu$ over ${1,dots,n$. Initially, the token is placed in a random position in $A$. In round $t$, a random value $d$ is chosen according to $mu$. If the token is in position $ageq d$, then it is moved to position $a-d$. Otherwise it stays put. Let $T$ be the number of rounds until the token reaches position 0. We show tight bounds for the expectation of $T$ for the optimal distribution $mu$. More precisely, we show that $min_mu{E_mu(T)=Thetaleft((log n)^2 ight)$. For the proof, a novel potential function argument is introduced. The research is motivated by the problem of approximating the minimum of a continuous function over $[0,1]$ with a ``blind'' optimization strategy.
Cite as

Martin Dietzfelbinger, Jonathan E. Rowe, Ingo Wegener, and Philipp Woelfel. Tight Bounds for Blind Search on the Integers. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 241-252, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{dietzfelbinger_et_al:LIPIcs.STACS.2008.1348,
  author =	{Dietzfelbinger, Martin and Rowe, Jonathan E. and Wegener, Ingo and Woelfel, Philipp},
  title =	{{Tight Bounds for Blind Search on the Integers}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{241--252},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1348},
  URN =		{urn:nbn:de:0030-drops-13486},
  doi =		{10.4230/LIPIcs.STACS.2008.1348},
  annote =	{Keywords: }
}
Document
DOI: 10.4230/DagSemRep.330
Theory of Evolutionary Algorithms (Dagstuhl Seminar 02031)

Authors: Hans-Georg Beyer, Kenneth A. De Jong, Colin Reeves, and Ingo Wegener

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

Abstract
Cite as

Hans-Georg Beyer, Kenneth A. De Jong, Colin Reeves, and Ingo Wegener. Theory of Evolutionary Algorithms (Dagstuhl Seminar 02031). Dagstuhl Seminar Report 330, pp. 1-26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2002)

Copy BibTex To Clipboard

@TechReport{beyer_et_al:DagSemRep.330,
  author =	{Beyer, Hans-Georg and De Jong, Kenneth A. and Reeves, Colin and Wegener, Ingo},
  title =	{{Theory of Evolutionary Algorithms (Dagstuhl Seminar 02031)}},
  pages =	{1--26},
  ISSN =	{1619-0203},
  year =	{2002},
  type = 	{Dagstuhl Seminar Report},
  number =	{330},
  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.330},
  URN =		{urn:nbn:de:0030-drops-152137},
  doi =		{10.4230/DagSemRep.330},
}
Document
DOI: 10.4230/DagSemRep.265
Theory of Evolutionary Algorithms (Dagstuhl Seminar 00071)

Authors: Hans-Georg Beyer, Kenneth De Jong, David B. Fogel, and Ingo Wegener

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

Abstract
Cite as

Hans-Georg Beyer, Kenneth De Jong, David B. Fogel, and Ingo Wegener. Theory of Evolutionary Algorithms (Dagstuhl Seminar 00071). Dagstuhl Seminar Report 265, pp. 1-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2000)

Copy BibTex To Clipboard

@TechReport{beyer_et_al:DagSemRep.265,
  author =	{Beyer, Hans-Georg and De Jong, Kenneth and Fogel, David B. and Wegener, Ingo},
  title =	{{Theory of Evolutionary Algorithms (Dagstuhl Seminar 00071)}},
  pages =	{1--24},
  ISSN =	{1619-0203},
  year =	{2000},
  type = 	{Dagstuhl Seminar Report},
  number =	{265},
  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.265},
  URN =		{urn:nbn:de:0030-drops-151506},
  doi =		{10.4230/DagSemRep.265},
}
Document
DOI: 10.4230/DagSemRep.257
Complexity of Boolean Functions (Dagstuhl Seminar 99441)

Authors: D. M. Barrington, Rüdiger Reischuk, and Ingo Wegener

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

Abstract
Cite as

D. M. Barrington, Rüdiger Reischuk, and Ingo Wegener. Complexity of Boolean Functions (Dagstuhl Seminar 99441). Dagstuhl Seminar Report 257, pp. 1-30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2000)

Copy BibTex To Clipboard

@TechReport{barrington_et_al:DagSemRep.257,
  author =	{Barrington, D. M. and Reischuk, R\"{u}diger and Wegener, Ingo},
  title =	{{Complexity of Boolean Functions (Dagstuhl Seminar 99441)}},
  pages =	{1--30},
  ISSN =	{1619-0203},
  year =	{2000},
  type = 	{Dagstuhl Seminar Report},
  number =	{257},
  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.257},
  URN =		{urn:nbn:de:0030-drops-151420},
  doi =		{10.4230/DagSemRep.257},
}
Document
DOI: 10.4230/DagSemRep.172
Complexity of Boolean Functions (Dagstuhl Seminar 9711)

Authors: David Mix Barrington, Noam Nisan, Rüdiger Reischuk, and Ingo Wegener

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

Abstract
Cite as

David Mix Barrington, Noam Nisan, Rüdiger Reischuk, and Ingo Wegener. Complexity of Boolean Functions (Dagstuhl Seminar 9711). Dagstuhl Seminar Report 172, pp. 1-26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1997)

Copy BibTex To Clipboard

@TechReport{barrington_et_al:DagSemRep.172,
  author =	{Barrington, David Mix and Nisan, Noam and Reischuk, R\"{u}diger and Wegener, Ingo},
  title =	{{Complexity of Boolean Functions (Dagstuhl Seminar 9711)}},
  pages =	{1--26},
  ISSN =	{1619-0203},
  year =	{1997},
  type = 	{Dagstuhl Seminar Report},
  number =	{172},
  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.172},
  URN =		{urn:nbn:de:0030-drops-150594},
  doi =		{10.4230/DagSemRep.172},
}
Document
DOI: 10.4230/DagSemRep.103
Neural Computing (Dagstuhl Seminar 9445)

Authors: Wolfgang Maass, Christoph von der Malsburg, Eduardo Sontag, and Ingo Wegener

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

Abstract
Cite as

Wolfgang Maass, Christoph von der Malsburg, Eduardo Sontag, and Ingo Wegener. Neural Computing (Dagstuhl Seminar 9445). Dagstuhl Seminar Report 103, pp. 1-27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1995)

Copy BibTex To Clipboard

@TechReport{maass_et_al:DagSemRep.103,
  author =	{Maass, Wolfgang and von der Malsburg, Christoph and Sontag, Eduardo and Wegener, Ingo},
  title =	{{Neural Computing (Dagstuhl Seminar 9445)}},
  pages =	{1--27},
  ISSN =	{1619-0203},
  year =	{1995},
  type = 	{Dagstuhl Seminar Report},
  number =	{103},
  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.103},
  URN =		{urn:nbn:de:0030-drops-149912},
  doi =		{10.4230/DagSemRep.103},
}
  • Refine by Author
  • 6 Wegener, Ingo
  • 2 Beyer, Hans-Georg
  • 2 Reischuk, Rüdiger
  • 1 Barrington, D. M.
  • 1 Barrington, David Mix
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Proof complexity

  • Refine by Keyword
  • 1 bounded repetitions
  • 1 branching programs
  • 1 lower bounds
  • 1 proof complexity

  • Refine by Type
  • 7 document

  • Refine by Publication Year
  • 2 2000
  • 1 1995
  • 1 1997
  • 1 2002
  • 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact