On Uncertainty versus Size in Branching Programs.

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F01%3A06010201" target="_blank" >RIV/67985807:_____/01:06010201 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

On Uncertainty versus Size in Branching Programs.

Popis výsledku v původním jazyce

Using an information-theoretic approach we prove a lower bound for so-called 'balanced' branching programs which for some classes of Boolean functions are more powerful than the most of previously considered restricted branching programs. The argument ofthe proof is based on an inequality for the average amount of uncertainty during the computation.

Název v anglickém jazyce

On Uncertainty versus Size in Branching Programs.

Popis výsledku anglicky

Using an information-theoretic approach we prove a lower bound for so-called 'balanced' branching programs which for some classes of Boolean functions are more powerful than the most of previously considered restricted branching programs. The argument ofthe proof is based on an inequality for the average amount of uncertainty during the computation.

Druh

A - Audiovizuální tvorba

CEP obor

BA - Obecná matematika

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í

2001

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ů

ISBN

—

Místo vydání

—

Název nakladatele resp. objednatele

—

Verze

—

Identifikační číslo nosiče

—