A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3

Kód výsledku v 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>

Výsledek na webu

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

Jazyk výsledku

angličtina

Název v původním jazyce

A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2012

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

SOFSEM 2012. Theory and Practice of Computer Science

ISBN

978-3-642-27659-0

ISSN

—

e-ISSN

—

Počet stran výsledku

13

Strana od-do

406-418

Název nakladatele

Springer

Místo vydání

Berlin

Místo konání akce

Špindlerův Mlýn

Datum konání akce

21. 1. 2012

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—