Navigation ▼

Show simple item record

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.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

Files in this item

This item appears in the following Collection(s)

Show simple item record