Almost k-Wise Independent Sets Establish Hitting Sets for Width-3 1-Branching Programs

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

Citováno: 13

--- Gopalan, P. - Meka, R. - Reimgold, O. - Trevisan, L. Better Pseudorandom Generators from Milder Pseudorandom Restrictions. arXiv:1210.0049v1 [cs.CC] 28 Sep 2012
--- Vadhan S. Pseudorandomness. Draft version for Foundations and Trends in Theoretical Computer Science 2012. http://people.seas.harvard.edu/~salil/pseudorandomness/
--- GOPALAN, P. - MEKA, R. - REINGOLD, O. - TREVISAN, L. - VADHAN, S. Better Pseudorandom Generators from Milder Pseudorandom Restrictions. 2012 IEEE 53RD ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS). ISSN 0272-5428, 2012, p. 120-129. [WOS]
--- STEINBERGER, J. The distinguishability of product distributions by read-once branching programs. 2013 IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY (CCC). ISSN 1093-0159, 2013, p. 248-254. [WOS]
--- Forbes, M.A. - Shpilka, A. Hitting sets for multilinear read-once algebraic branching programs, in any order. STOC '14 Proceedings of the 46th Annual ACM Symposium on Theory of Computing. ISBN: 978-1-4503-2710-7, 2014, p. 867-875.
--- Vadhan, S.P. Pseudorandomness. Foundations and Trends in Theoretical Computer Science. 2012, vol. 7, iss. 1-3.
--- Forbes, M - Shpilka, A. Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs. 54rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013. arXiv:1209.2408 [cs.CC]
--- FORBES, M.A. - SHPILKA, A. Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs. 2013 IEEE 54TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS). ISSN 0272-5428, 2013, p. 243-252. [WOS]
--- BAZZI, L. - NAHAS, N. Small-Bias is Not Enough to Hit Read-Once CNF. THEORY OF COMPUTING SYSTEMS. ISSN 1432-4350, FEB 2017, vol. 60, no. 2, p. 324-345. [WOS]
--- Murtagh, J. - Reingold, O. - Sidford, A. - Vadhan, S. Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space. 2017 arXiv:1708.04634 [cs.CC]
--- BRAVERMAN, M. - COHEN, G. - GARG, S. Hitting Sets with Near-Optimal Error for Read-Once Branching Programs. STOC'18: PROCEEDINGS OF THE 50TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING. 2018, p. 353-362. [WOS]
--- HOZA, W.M. - ZUCKERMAN, D. Simple Optimal Hitting Sets for Small-Success RL. 2018 IEEE 59TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS). ISSN 0272-5428, 2018, p. 59-64. [WOS]
--- MURTAGH, J. - REINGOLD, O. - SIDFORD, A. - VADHAN, S. Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space. 2017 IEEE 58TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS). ISSN 0272-5428, 2017, p. 801-812. [WOS]

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