Search results
- 1.0405528 - UIVT-O 330906 RIV NL eng J - Journal Article
Savický, Petr - Sieling, D.
A Hierarchy Result for Read-Once Branching Programs with Restricted Parity Nondeterminism.
[Výsledek o hierarchii pro read-once rozhodovací diagramy s omezeným nedeterminismem paritního typu.]
Theoretical Computer Science. Roč. 340, č. 3 (2005), s. 594-605. ISSN 0304-3975. E-ISSN 1879-2294
R&D Projects: GA MŠMT LN00A056
Institutional research plan: CEZ:AV0Z10300504
Keywords : read-once branching programs * restricted parity nondeterminism * lower bounds on complexity * hierarchy
Subject RIV: BA - General Mathematics
Impact factor: 0.743, year: 2005
Permanent Link: http://hdl.handle.net/11104/0125686 - 2.0404725 - UIVT-O 20020127 DE eng A - Abstract
Žák, Stanislav
Information Flow in Read-Once Branching Programs.
Complexity of Boolean Functions. Dagstuhl, 2002 - (Barrington, D.; Hastad, J.; Krause, M.; Reischuk, R.). s. 11
[Seminar. 17.03.2002-22.03.2002, Dagstuhl]
Institutional research plan: AV0Z1030915
Keywords : read-once branching programs * lower bound * information flow
Subject RIV: BA - General Mathematics
Permanent Link: http://hdl.handle.net/11104/0124963 - 3.0403962 - UIVT-O 20000105 CZ eng V - Research Report
Žák, Stanislav
A Subexponential Lower Bound on Read-once Branching Programs by a New Argument.
Prague: ICS AS CR, 2000. 10 s. Technical Report, V-813.
R&D Projects: GA ČR GA201/98/0717
Institutional research plan: AV0Z1030915
Keywords : read-once branching programs * lower bound
Permanent Link: http://hdl.handle.net/11104/0124246File Download Size Commentary Version Access v813-00.pdf 19 135.3 KB Other open-access - 4.0367350 - ÚI 2022 RIV NL eng J - Journal Article
Šíma, Jiří - Žák, Stanislav
A Polynomial-Time Construction of a Hitting Set for Read-once Branching Programs of Width 3.
Fundamenta Informaticae. Roč. 184, č. 4 (2021), s. 307-354. ISSN 0169-2968. E-ISSN 1875-8681
R&D Projects: GA ČR GBP202/12/G061; GA ČR GAP202/10/1333
Institutional support: RVO:67985807
Keywords : derandomization * hitting set * read-once branching programs * bounded width * almost k-wise independent set
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Impact factor: 1.166, year: 2021
Method of publishing: Limited access
http://dx.doi.org/10.3233/FI-2021-2101
Permanent Link: http://hdl.handle.net/11104/0202062 - 5.0364426 - ÚI 2012 RIV DE eng C - Conference Paper (international conference)
Šíma, Jiří - Žák, Stanislav
A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3.
SOFSEM 2012. Theory and Practice of Computer Science. Berlin: Springer, 2012 - (Bieliková, M.; Friedrich, G.; Gottlob, G.; Katzenbeisser, S.; Turán, G.), s. 406-418. Lecture Notes in Computer Science, 7147. ISBN 978-3-642-27659-0. ISSN 0302-9743.
[SOFSEM 2012. Conference on Current Trends in Theory and Practice of Computer Science /38./. Špindlerův Mlýn (CZ), 21.01.2012-27.01.2012]
R&D Projects: GA ČR GAP202/10/1333; GA MŠMT(CZ) 1M0545
Institutional research plan: CEZ:AV0Z10300504
Keywords : derandomization * hitting set * read-once branching programs * bounded width
Subject RIV: IN - Informatics, Computer Science
Permanent Link: http://hdl.handle.net/11104/0199914File Download Size Commentary Version Access a0364426.pdf 0 320.8 KB Publisher’s postprint require 0364426.pdf 1 576.4 KB Author´s preprint open-access - 6.0360403 - ÚI 2012 RIV DE eng C - Conference Paper (international conference)
Šíma, Jiří - Žák, Stanislav
Almost k-Wise Independent Sets Establish Hitting Sets for Width-3 1-Branching Programs.
Computer Science - Theory and Applications. Berlin: Springer, 2011 - (Kulikov, A.; Vereshchagin, N.), s. 120-133. Lecture Notes in Computer Science, 6651. ISBN 978-3-642-20711-2. ISSN 0302-9743.
[CSR 2011. International Computer Science Symposium in Russia /6./. St. Petersburg (RU), 14.06.2011-18.06.2011]
R&D Projects: GA ČR GAP202/10/1333; GA MŠMT(CZ) 1M0545
Institutional research plan: CEZ:AV0Z10300504
Keywords : almost k-wise independent set * hitting set * read-once branching programs * derandomization * bounded width
Subject RIV: IN - Informatics, Computer Science
Permanent Link: http://hdl.handle.net/11104/0197967File Download Size Commentary Version Access a0360403.pdf 15 331.7 KB Publisher’s postprint require 0360403.pdf 0 622.5 KB Author´s preprint open-access - 7.0331291 - ÚI 2010 CZ eng V - Research Report
Šíma, Jiří - Žák, Stanislav
A Characterization of Hitting Sets for 1-Branching Programs of Width 3 (Revised Version).
Prague: ICS AS CR, 2009. 18 s. Technical Report, V-1054.
R&D Projects: GA MŠMT(CZ) 1M0545; GA AV ČR 1ET100300517
Institutional research plan: CEZ:AV0Z10300504
Keywords : derandomization, hitting set * hitting set * read-once branching programs * bounded width
Subject RIV: IN - Informatics, Computer Science
Permanent Link: http://hdl.handle.net/11104/0176844File Download Size Commentary Version Access v1054-09.pdf 16 253 KB Other open-access