A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F12%3A00364426" target="_blank" >RIV/67985807:_____/12:00364426 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1007/978-3-642-27660-6_33" target="_blank" >http://dx.doi.org/10.1007/978-3-642-27660-6_33</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-642-27660-6_33" target="_blank" >10.1007/978-3-642-27660-6_33</a>
Alternative languages
Result language
angličtina
Original language name
A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3
Original language description
We characterize the hitting sets for read-once (1-branching) branching programs of width 3 by a so-called richness condition which is independent of a rather technical definition of branching programs. The richness property proves to be (in certain sense) necessary and sufficient condition for such hitting sets. In particular, we show that any rich set extended with all strings within Hamming distance of 3 is a hitting set for width-3 1-branching programs. Applying this result to an example of an efficiently constructible rich set from our previous work we achieve an explicit polynomial time construction of an epsilon-hitting set for 1-branching programs of width 3 with acceptance probability epsilon gt 11/12.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2012
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
SOFSEM 2012. Theory and Practice of Computer Science
ISBN
978-3-642-27659-0
ISSN
—
e-ISSN
—
Number of pages
13
Pages from-to
406-418
Publisher name
Springer
Place of publication
Berlin
Event location
Špindlerův Mlýn
Event date
Jan 21, 2012
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—