About: A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3

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

About: A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3 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 characterize the hitting sets for read-once (1-branching) branching programs of width 3 by a so-called richness condition which is independent of a rather technical definition of branching programs. The richness property proves to be (in certain sense) necessary and sufficient condition for such hitting sets. In particular, we show that any rich set extended with all strings within Hamming distance of 3 is a hitting set for width-3 1-branching programs. Applying this result to an example of an efficiently constructible rich set from our previous work we achieve an explicit polynomial time construction of an epsilon-hitting set for 1-branching programs of width 3 with acceptance probability epsilon gt 11/12. We characterize the hitting sets for read-once (1-branching) branching programs of width 3 by a so-called richness condition which is independent of a rather technical definition of branching programs. The richness property proves to be (in certain sense) necessary and sufficient condition for such hitting sets. In particular, we show that any rich set extended with all strings within Hamming distance of 3 is a hitting set for width-3 1-branching programs. Applying this result to an example of an efficiently constructible rich set from our previous work we achieve an explicit polynomial time construction of an epsilon-hitting set for 1-branching programs of width 3 with acceptance probability epsilon gt 11/12. (en)
Title	A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3 A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3 (en)
skos:prefLabel	A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3 A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3 (en)
skos:notation	RIV/67985807:_____/12:00364426!RIV12-AV0-67985807
http://linked.open...avai/riv/aktivita	P Z
http://linked.open...avai/riv/aktivity	P(1M0545), P(GAP202/10/1333), Z(AV0Z10300504)
http://linked.open...vai/riv/dodaniDat	2012
http://linked.open...aciTvurceVysledku	Šíma, Jiří Žák, Stanislav
http://linked.open.../riv/druhVysledku	D - Článek ve sborníku
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	Ústav informatiky AV ČR, v. v. i.
http://linked.open...dnocenehoVysledku	120667
http://linked.open...ai/riv/idVysledku	RIV/67985807:_____/12:00364426
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	derandomization; hitting set; read-once branching programs; bounded width (en)
http://linked.open.../riv/klicoveSlovo	bounded width derandomization hitting set read-once branching programs
http://linked.open...ontrolniKodProRIV	[F53CD90B18CA]
http://linked.open...v/mistoKonaniAkce	Špindlerův Mlýn
http://linked.open...i/riv/mistoVydani	Berlin
http://linked.open...i/riv/nazevZdroje	SOFSEM 2012. Theory and Practice of Computer Science
http://linked.open...in/vavai/riv/obor	IN
http://linked.open...ichTvurcuVysledku	2 (xsd:int)
http://linked.open...cetTvurcuVysledku	2 (xsd:int)
http://linked.open...vavai/riv/projekt	Institute for Theoretical Computer Science NoSCoM: Non-Standard Computational Models and Their Applications in Complexity, Linguistics, and Learning
http://linked.open...UplatneniVysledku	2012
http://linked.open...iv/tvurceVysledku	Šíma, Jiří Žák, Stanislav
http://linked.open...vavai/riv/typAkce	WRD - Světová
http://linked.open.../riv/zahajeniAkce	2012-01-21 (xsd:date)
http://linked.open...n/vavai/riv/zamer	Informatika pro informační společnost: modely, algoritmy, aplikace
number of pages	13 (xsd:int)
http://bibframe.org/vocab/doi	10.1007/978-3-642-27660-6_33
http://purl.org/ne...btex#hasPublisher	Springer-Verlag
https://schema.org/isbn	978-3-642-27659-0

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, 58 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software