Počet záznamů: 1

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

SYSNO ASEP	0364426
Druh ASEP	C - Konferenční příspěvek (mezinárodní konf.)
Zařazení RIV	D - Článek ve sborníku
Název	A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3
Tvůrce(i)	Šíma, Jiří (UIVT-O)_{RID, SAI, ORCID} Žák, Stanislav (UIVT-O)_{SAI, RID}
Zdroj.dok.	SOFSEM 2012. Theory and Practice of Computer Science. - Berlin : Springer, 2012 / Bieliková M. ; Friedrich G. ; Gottlob G. ; Katzenbeisser S. ; Turán G. - ISSN 0302-9743 - ISBN 978-3-642-27659-0
Rozsah stran	s. 406-418
Poč.str.	13 s.
Akce	SOFSEM 2012. Conference on Current Trends in Theory and Practice of Computer Science /38./
Datum konání	21.01.2012-27.01.2012
Místo konání	Špindlerův Mlýn
Země	CZ - Česká republika
Typ akce	WRD
Jazyk dok.	eng - angličtina
Země vyd.	DE - Německo
Klíč. slova	derandomization ; hitting set ; read-once branching programs ; bounded width
Vědní obor RIV	IN - Informatika
CEP	GAP202/10/1333 GA ČR - Grantová agentura ČR
	1M0545 GA MŠMT - Ministerstvo školství, mládeže a tělovýchovy
CEZ	AV0Z10300504 - UIVT-O (2005-2011)
UT WOS	000307258500033
EID SCOPUS	84856044272
DOI	10.1007/978-3-642-27660-6_33
Anotace	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.
Pracoviště	Ústav informatiky
Kontakt	Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800
Rok sběru	2012

Počet záznamů: 1