On Lower Bounds for Parity Branching Programs

Homeister, Matthias

dc.contributor.advisor	Waack, Stephan Prof. Dr.	de
dc.contributor.author	Homeister, Matthias	de
dc.date.accessioned	2003-12-18T15:27:44Z	de
dc.date.accessioned	2013-01-18T13:22:40Z	de
dc.date.available	2013-01-30T23:51:07Z	de
dc.date.issued	2003-12-18	de
dc.identifier.uri	http://hdl.handle.net/11858/00-1735-0000-0006-B3FB-D	de
dc.identifier.uri	http://dx.doi.org/10.53846/goediss-2524
dc.description.abstract	Diese Arbeit beschaeftigt sich mit der Komplexität von parity Branching Programmen. Es werden superpolynomiale untere Schranken für verschiedene Varianten bewiesen, nämlich für well-structured graph-driven parity branching programs, general graph-driven parity branching programs und Summen von graph-driven parity branching programs.	de
dc.format.mimetype	application/pdf	de
dc.language.iso	eng	de
dc.rights.uri	http://webdoc.sub.gwdg.de/diss/copyrdiss.htm	de
dc.title	On Lower Bounds for Parity Branching Programs	de
dc.type	doctoralThesis	de
dc.title.translated	On Lower Bounds for Parity Branching Programs	de
dc.contributor.referee	Waack, Stephan Prof. Dr.	de
dc.date.examination	2003-10-15	de
dc.description.abstracteng	This thesis concerns the complexity of parity branching programs with limitations on the way in which variables may be read.Interest in such branching programs has been raised by a popular method for verifying hardware circuits. Oblivious read-once branching programs (or OBDDs). Recently, Parity OBDDs have been studied intensively and have been found very useful in this application, too.Thus, one is interested in lower bounds for restricted parity branching programs. While exponential lower bounds for deterministic as well as nondeterministic read-once branching programs are known for a long time, superpolynomial lower bounds for parity read-once branching programs are still a challenge.In this thesis three different restricted variants of parity read-once branching programs are under consideration, well-structured graph-driven parity branching programs, general graph-driven parity branching programs and sums of graph-driven parity branching programs. We present superpolynomial lower bounds for these models and natural functions, for instance, for linear codes and permutation matrices. These lower bounds are the most general ones known in this area. In addition, algorithmic properties of the considered models are discussed.	de
dc.contributor.coReferee	Damm, Carsten PD Dr.	de
dc.subject.topic	Mathematics and Computer Science	de
dc.subject.ger	Verzweigungsdiagramme	de
dc.subject.ger	untere Schranken	de
dc.subject.ger	004 Informatik	de
dc.subject.eng	branching programs	de
dc.subject.eng	lower bounds	de
dc.subject.bk	54.10	de
dc.identifier.urn	urn:nbn:de:gbv:7-webdoc-448-3	de
dc.identifier.purl	webdoc-448	de
dc.affiliation.institute	Fakultät für Mathematik und Informatik	de
dc.subject.gokfull	AH	de
dc.identifier.ppn	379432161	de

Dateien

Name:homeister.pdf

Größe:484.1Kb

Format:PDF

Beschreibung:Dissertation

Öffnen

Name:: homeister.pdf
Größe:: 484.1Kb
Format:: PDF
Beschreibung:: Dissertation

Öffnen

Das Dokument erscheint in:

Fakultät für Mathematik und Informatik (inkl. GAUSS) [518]

Zur Kurzanzeige