Number of the records: 1

Almost k-Wise Independent Sets Establish Hitting Sets for Width-3 1-Branching Programs

SYSNO ASEP	0360403
Document Type	C - Proceedings Paper (int. conf.)
R&D Document Type	Conference Paper
Title	Almost k-Wise Independent Sets Establish Hitting Sets for Width-3 1-Branching Programs
Author(s)	Šíma, Jiří (UIVT-O)_{RID, SAI, ORCID} Žák, Stanislav (UIVT-O)_{SAI, RID}
Source Title	Computer Science - Theory and Applications. - Berlin : Springer, 2011 / Kulikov A. ; Vereshchagin N. - ISSN 0302-9743 - ISBN 978-3-642-20711-2
Pages	s. 120-133
Number of pages	14 s.
Action	CSR 2011. International Computer Science Symposium in Russia /6./
Event date	14.06.2011-18.06.2011
VEvent location	St. Petersburg
Country	RU - Russian Federation
Event type	WRD
Language	eng - English
Country	DE - Germany
Keywords	almost k-wise independent set ; hitting set ; read-once branching programs ; derandomization ; bounded width
Subject RIV	IN - Informatics, Computer Science
R&D Projects	GAP202/10/1333 GA ČR - Czech Science Foundation (CSF)
	1M0545 GA MŠMT - Ministry of Education, Youth and Sports (MEYS)
CEZ	AV0Z10300504 - UIVT-O (2005-2011)
EID SCOPUS	79959304214
DOI	10.1007/978-3-642-20712-9_10
Annotation	Recently, an interest in constructing pseudorandom or hitting set generators for restricted branching programs has increased, which is motivated by the fundamental problem of derandomizing space bounded computations. Such constructions have been known only in the case of width 2 and in very restricted cases of bounded width. In our previous work, we have introduced a so-called richness condition which is, in a certain sense, sufficient for a set to be a hitting set for read-once branching programs of width 3. In this paper, we prove that, for a suitable constant C, any almost (C log n)-wise independent set satisfies this richness condition. Hence, we achieve an explicit polynomial time construction of a hitting set for read-once branching programs of width~3 with the acceptance probability greater than 12/13 by using the result due to Alon et al. (1992).
Workplace	Institute of Computer Science
Contact	Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800
Year of Publishing	2012

Number of the records: 1