A note on monotone complexity and the rank of matrices.

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F03%3A05030188" target="_blank" >RIV/67985840:_____/03:05030188 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

A note on monotone complexity and the rank of matrices.

Popis výsledku v původním jazyce

We shall give simpler proofs of some lower bounds on monotone computations. Wedescribe a simple condition on combinatorial structures, such that the rank ofthe matrix associated with these structures gives lower bounds on monotone span program size and monotone formula size. We also prove an upper bound on the rank of the corresponding matrices, and show that such structures can be......

Název v anglickém jazyce

A note on monotone complexity and the rank of matrices.

Popis výsledku anglicky

We shall give simpler proofs of some lower bounds on monotone computations. Wedescribe a simple condition on combinatorial structures, such that the rank ofthe matrix associated with these structures gives lower bounds on monotone span program size and monotone formula size. We also prove an upper bound on the rank of the corresponding matrices, and show that such structures can be......

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

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í

2003

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 periodika

Information Processing Letters

ISSN

0020-0190

e-ISSN

—

Svazek periodika

87

Číslo periodika v rámci svazku

6

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

6

Strana od-do

321-326

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—