This HTML5 document contains 46 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
n13http://linked.opendata.cz/ontology/domain/vavai/riv/typAkce/
dctermshttp://purl.org/dc/terms/
n12http://purl.org/net/nknouf/ns/bibtex#
n10http://linked.opendata.cz/resource/domain/vavai/projekt/
n7http://linked.opendata.cz/resource/domain/vavai/riv/tvurce/
n19http://linked.opendata.cz/resource/domain/vavai/subjekt/
n18http://linked.opendata.cz/ontology/domain/vavai/
n21http://linked.opendata.cz/resource/domain/vavai/zamer/
n8https://schema.org/
shttp://schema.org/
skoshttp://www.w3.org/2004/02/skos/core#
n3http://linked.opendata.cz/ontology/domain/vavai/riv/
n5http://bibframe.org/vocab/
n2http://linked.opendata.cz/resource/domain/vavai/vysledek/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n11http://linked.opendata.cz/ontology/domain/vavai/riv/klicoveSlovo/
n14http://linked.opendata.cz/ontology/domain/vavai/riv/duvernostUdaju/
xsdhhttp://www.w3.org/2001/XMLSchema#
n17http://linked.opendata.cz/ontology/domain/vavai/riv/jazykVysledku/
n22http://linked.opendata.cz/resource/domain/vavai/vysledek/RIV%2F67985807%3A_____%2F12%3A00364426%21RIV12-AV0-67985807/
n9http://linked.opendata.cz/ontology/domain/vavai/riv/aktivita/
n23http://linked.opendata.cz/ontology/domain/vavai/riv/obor/
n20http://linked.opendata.cz/ontology/domain/vavai/riv/druhVysledku/
n16http://reference.data.gov.uk/id/gregorian-year/

Statements

Subject Item
n2:RIV%2F67985807%3A_____%2F12%3A00364426%21RIV12-AV0-67985807
rdf:type
skos:Concept n18:Vysledek
dcterms: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.
dcterms: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
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
skos:notation
RIV/67985807:_____/12:00364426!RIV12-AV0-67985807
n18:predkladatel
n19:ico%3A67985807
n3:aktivita
n9:Z n9:P
n3:aktivity
P(1M0545), P(GAP202/10/1333), Z(AV0Z10300504)
n3:dodaniDat
n16:2012
n3:domaciTvurceVysledku
n7:3031314 n7:3179133
n3:druhVysledku
n20:D
n3:duvernostUdaju
n14:S
n3:entitaPredkladatele
n22:predkladatel
n3:idSjednocenehoVysledku
120667
n3:idVysledku
RIV/67985807:_____/12:00364426
n3:jazykVysledku
n17:eng
n3:klicovaSlova
derandomization; hitting set; read-once branching programs; bounded width
n3:klicoveSlovo
n11:hitting%20set n11:bounded%20width n11:derandomization n11:read-once%20branching%20programs
n3:kontrolniKodProRIV
[F53CD90B18CA]
n3:mistoKonaniAkce
Špindlerův Mlýn
n3:mistoVydani
Berlin
n3:nazevZdroje
SOFSEM 2012. Theory and Practice of Computer Science
n3:obor
n23:IN
n3:pocetDomacichTvurcuVysledku
2
n3:pocetTvurcuVysledku
2
n3:projekt
n10:GAP202%2F10%2F1333 n10:1M0545
n3:rokUplatneniVysledku
n16:2012
n3:tvurceVysledku
Žák, Stanislav Šíma, Jiří
n3:typAkce
n13:WRD
n3:zahajeniAkce
2012-01-21+01:00
n3:zamer
n21:AV0Z10300504
s:numberOfPages
13
n5:doi
10.1007/978-3-642-27660-6_33
n12:hasPublisher
Springer-Verlag
n8:isbn
978-3-642-27659-0