A Polynomial Time Constructible Hitting Set for Restricted 1-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_____%2F07%3A00339973" target="_blank" >RIV/67985807:_____/07:00339973 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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

Název v anglickém jazyce

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

Popis výsledku anglicky

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

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

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2007

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 2007: Theory and Practice of Computer Science

ISBN

978-3-540-69506-6

ISSN

—

e-ISSN

—

Počet stran výsledku

10

Strana od-do

—

Název nakladatele

Springer

Místo vydání

Berlin

Místo konání akce

Harrachov

Datum konání akce

20. 1. 2007

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

WRD - Celosvětová akce

Kód UT WoS článku

000244537600045