Počet záznamů: 1
A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3
- 1.0364426 - ÚI 2012 RIV DE eng C - Konferenční příspěvek (zahraniční konf.)
Šíma, Jiří - Žák, Stanislav
A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3.
SOFSEM 2012. Theory and Practice of Computer Science. Berlin: Springer, 2012 - (Bieliková, M.; Friedrich, G.; Gottlob, G.; Katzenbeisser, S.; Turán, G.), s. 406-418. Lecture Notes in Computer Science, 7147. ISBN 978-3-642-27659-0. ISSN 0302-9743.
[SOFSEM 2012. Conference on Current Trends in Theory and Practice of Computer Science /38./. Špindlerův Mlýn (CZ), 21.01.2012-27.01.2012]
Grant CEP: GA ČR GAP202/10/1333; GA MŠMT(CZ) 1M0545
Výzkumný záměr: CEZ:AV0Z10300504
Klíčová slova: derandomization * hitting set * read-once branching programs * bounded width
Kód oboru RIV: IN - Informatika
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.
Trvalý link: http://hdl.handle.net/11104/0199914
Název souboru Staženo Velikost Komentář Verze Přístup a0364426.pdf 0 320.8 KB Vydavatelský postprint vyžádat 0364426.pdf 1 576.4 KB Autorský preprint povolen
Počet záznamů: 1