About: A note on monotone complexity and the rank of matrices.

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: A note on monotone complexity and the rank of matrices. Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
Description	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...... 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...... (en)
Title	A note on monotone complexity and the rank of matrices. A note on monotone complexity and the rank of matrices. (en)
skos:prefLabel	A note on monotone complexity and the rank of matrices. A note on monotone complexity and the rank of matrices. (en)
skos:notation	RIV/67985840:_____/03:05030188!RIV/2004/MSM/A05004/N
http://linked.open.../vavai/riv/strany	321;326
http://linked.open...avai/riv/aktivita	P Z
http://linked.open...avai/riv/aktivity	P(GA201/01/1195), P(IAA1019901), P(LN00A056), Z(AV0Z1019905)
http://linked.open...iv/cisloPeriodika	6
http://linked.open...vai/riv/dodaniDat	2004
http://linked.open...aciTvurceVysledku	Pudlák, Pavel
http://linked.open.../riv/druhVysledku	J - Článek v odborném periodiku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Matematický ústav AV ČR, v. v. i.
http://linked.open...dnocenehoVysledku	597023
http://linked.open...ai/riv/idVysledku	RIV/67985840:_____/03:05030188
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	computational complexity; lower bounds; span programs (en)
http://linked.open.../riv/klicoveSlovo	lower bounds computational complexity span programs
http://linked.open...odStatuVydavatele	NL - Nizozemsko
http://linked.open...ontrolniKodProRIV	[2A7A744240B5]
http://linked.open...i/riv/nazevZdroje	Information Processing Letters
http://linked.open...in/vavai/riv/obor	BA
http://linked.open...ichTvurcuVysledku	1 (xsd:int)
http://linked.open...cetTvurcuVysledku	2 (xsd:int)
http://linked.open...ocetUcastnikuAkce	0 (xsd:int)
http://linked.open...nichUcastnikuAkce	0 (xsd:int)
http://linked.open...vavai/riv/projekt	Institute of Theoretical Computer Science (Center of Young Science) Combinatorial algorithms and combinatorial problems in complexity theory Mathematical logic and computational complexity
http://linked.open...UplatneniVysledku	2003
http://linked.open...v/svazekPeriodika	87
http://linked.open...iv/tvurceVysledku	Pudlák, Pavel Gál, A.
http://linked.open...n/vavai/riv/zamer	Complex development of all branches of mathematics with regard to the needs of physics and technology
issn	0020-0190
number of pages	6 (xsd:int)

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 48 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software