• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Approximation, randomization, and combinatorial optimization : Algorithms and techniques >Pseudorandomness for Linear Length Branching Programs and Stack Machines
【24h】

Pseudorandomness for Linear Length Branching Programs and Stack Machines

机译：线性长度分支程序和堆栈机的伪随机性

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We show the existence of an explicit pseudorandom generator G of linear stretch such that for every constant k, the output of G is pseudorandom against: 1. Oblivious branching programs over alphabet {0,1} of length kn and size 2~(O{n/log n)) on inputs of size n. 2. Non-oblivious branching programs over alphabet Σ of length kn, provided the size of Σ is a power of 2 and sufficiently large in terms of k. 3. The model of logarithmic space randomized Turing Machines (over alphabet {0,1}) extended with an unbounded stack that make k passes over their randomness. The construction of the pseudorandom generator G is the same as in our previous work (FOCS 2011). The results here rely on a stronger analysis of the construction. For the last result we give a length-efficient simulation of stack machines by non-deterministic branching programs, (over a large alphabet) whose accepting computations have a unique witness.
机译：我们证明了存在线性拉伸的显式伪随机发生器G的存在，使得对于每个常数k，G的输出都针对以下伪随机发生器：1.在长度为kn且大小为2〜（O { n / log n））在大小为n的输入上。 2.在长度为kn的字母Σ上的非遗忘分支程序，条件是Σ的大小为2的幂且在k方面足够大。 3.对数空间随机图灵机模型（在字母{0,1}上）扩展为无限制堆栈，使k越过其随机性。伪随机数发生器G的结构与我们先前的工作（FOCS 2011）相同。这里的结果依赖于对构造的更强分析。对于最后一个结果，我们通过不确定的分支程序（以较大的字母表示）对堆栈机进行了长度有效的仿真，该程序的接受计算具有唯一的见证。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号