A Polynomial Time Constructible Hitting Set for Restricted 1-Branching Programs of Width 3

0339973 - ÚI 2010 RIV DE eng C - Conference Paper (international conference)
Šíma, Jiří - Žák, Stanislav
A Polynomial Time Constructible Hitting Set for Restricted 1-Branching Programs of Width 3.
SOFSEM 2007: Theory and Practice of Computer Science. Berlin: Springer, 2007 - (van Leeuwen, J.; Italiano, G.; van der Hoek, W.; Meinel, C.; Sack, H.; Plášil, F.), s. 522-531. Lecture Notes in Computer Science, 4362. ISBN 978-3-540-69506-6.
[SOFSEM 2007. Conference on Current Trends in Theory and Practice of Computer Science /33./. Harrachov (CZ), 20.01.2007-26.01.2007]
R&D Projects: GA MŠMT 1M0545; GA AV ČR 1ET100300517
Institutional research plan: CEZ:AV0Z10300504
Keywords : derandomization * hiting set * branching programs of boundedf width
Subject RIV: IN - Informatics, Computer Science

An important problem in complexity theory is to find polynomial time constructible hitting sets for Boolean functions in different standard models. This would have consequences for the relationalship between deterministic and probabilistic computations in the respective models. Using the result by Alon, Goldreich, Hastad, and Peralta (1992) we provide a polynomial time constructible hitting set for restricted read-once branching programs of width 3. The restriction excludes only one from all patterns of level-to-level transitions in a normalized form of 3-width 1-branching programs. In fact, our technique works for a slightly more general class of such programs. Although this restriction seems to be relatively strong our proof reveals the core of difficulties and thus represents the first step for proving the result for less restricted models.
Permanent Link: http://hdl.handle.net/11104/0183327