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

0364426 - ÚI 2012 RIV DE eng C - Konferenční příspěvek (zahraniční konf.)
Ší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]
Grant CEP: GA ČR GAP202/10/1333; GA MŠMT(CZ) 1M0545
Výzkumný záměr: CEZ:AV0Z10300504
Klíčová slova: derandomization * hitting set * read-once branching programs * bounded width
Kód oboru RIV: IN - Informatika

Citováno: 5

--- Steinke, T. Pseudorandomness for Permutation Branching Programs Without the Group Theory. Electronic Colloquium on Computational Complexity, TR12-083. Trier, 2012
--- Reingold, O. - Steinke, T. - Vadhan, S. Pseudorandomness for Regular Branching Programs via Fourier Analysis. arXiv:1306.3004 [cs.CC] 2013
--- Reingold, O. - Steinke, T. - Vadhan, S. Pseudorandomness for Regular Branching Programs via Fourier Analysis. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Springer LNCS 8096, 2013, pp 655-670
--- Steinke, T. - Vadhan, S. - Wan, A. Pseudorandomness and Fourier Growth Bounds for Width 3 Branching Programs. arXiv:1405.7028 [cs.CC] 2014
--- STEINKE, T. - VADHAN, S. - WAN, A. Pseudorandomness and Fourier-Growth Bounds for Width-3 Branching Programs. THEORY OF COMPUTING. ISSN 1557-2862, 2017, vol. 13, SI. [WOS]

Trvalý link: http://hdl.handle.net/11104/0199914