首页    期刊浏览 2024年11月24日 星期日
登录注册

文章基本信息

  • 标题:Simple Optimal Hitting Sets for Small-Success RL
  • 本地全文:下载
  • 作者:William Hoza ; David Zuckerman
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2018
  • 卷号:2018
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    We give a simple explicit hitting set generator for read-once branching programs of width w and length r with known variable order. Our generator has seed length O log ( w r ) log r max 1 log log w − log log r + log (1 ) . This seed length improves on recent work by Braverman, Cohen, and Garg (STOC '18). In addition, our generator and its analysis are dramatically simpler than the work by Braverman et al. Our generator's seed length improves on all the classic generators for space-bounded computation (Nisan Combinatorica '92; Impagliazzo, Nisan, and Wigderson STOC '94; Nisan and Zuckerman JCSS '96) when is small. When r polylog w , our generator has optimal seed length O ( log w + log (1 )) . As a corollary, we show that every RL algorithm that uses r random bits can be simulated by an NL algorithm that uses only O ( r log c n ) nondeterministic bits, where c is an arbitrarily large constant. Finally, we show that any RL algorithm with small success probability can be simulated deterministically in space O ( log 3 2 n + log n log log (1 )) . This improves on work by Saks and Zhou (JCSS '99), who gave an algorithm that runs in space O ( log 3 2 n + log n log (1 )) .

国家哲学社会科学文献中心版权所有