关于Impagliazzo-Nisan-Wigderson伪随机生成器对换分支程序的限制
William M Hoza1, Edward Pyne2, Salil Vadhan3
1University of Chicago, Chicago, USA.
概括
这项研究在光谱分析中确定了伪随机生成器 (PRG) 种子长度的下限,并显示了它.
科学领域:
- 理论计算机科学 理论计算机科学
- 密码学 密码学 密码学 密码学
- 计算复杂性 计算复杂性
背景情况:
- 伊帕格利亚佐-尼桑-维格德森 (INW) 伪随机生成器 (PRG) 是空间有限计算的基础.
- 之前的分析改善了INW发电机的种子长度依赖性,用于 permutation 和正规分支程序.
- 在考虑所有参数时,现有的分析不足以达到最佳的PRG种子长度.
研究的目的:
- 为了确定INW发电机的光谱分析所需的种子长度的下限.
- 为了将这个下限与欺骗分支程序的现有上限进行比较.
- 为了研究种子长度的要求,用光谱规范来欺骗 permutation 分支程序.
主要方法:
- 证明INW发电机的任何"光谱分析"的下限.
- 将"光谱分析"定义为依赖生成器图的光谱扩展的方法.
- 分析种子长度的要求,以欺骗在光谱规范下的变分支程序.
主要成果:
- 任何INW生成器的光谱分析都需要种子长度
来欺骗有序排列分支程序. - 这个下边界与常规分支程序 (除了差距) 和恒宽顺位分支程序的已知上边界相匹配.
- 用光谱规范进行INW的光谱分析,用于使用光谱规范的变分支程序,需要种子长度为多项式宽度.
结论:
- 对INW发电机的光谱分析在种子长度效率方面存在固有的限制.
- 建立的下限为PRG设计和分析的未来改进提供了一个基准.
- 这些发现为分析方法和伪随机生成中的种子长度要求之间的权衡提供了见解.
相关概念视频
Radical Chain-Growth Polymerization: Chain Branching
1.9K
The skeletal structure of polymers synthesized via radical polymerization is always branched. For example, the polymerization of ethylene by radical polymerization results in a low-density grade of polyethylene with a heavily branched skeletal structure. Here, the radical site abstracts hydrogen from the growing chain, and the radical site shifts from the end (a primary carbon center) to anywhere within the growing chain (a secondary carbon center). Consequently, the part of the chain from the...
1.9K
Woodward–Hoffmann Selection Rules and Microscopic Reversibility
3.0K
Electrocyclic reactions, cycloadditions, and sigmatropic rearrangements are concerted pericyclic reactions that proceed via a cyclic transition state. These reactions are stereospecific and regioselective. The stereochemistry of the products depends on the symmetry characteristics of the interacting orbitals and the reaction conditions. Accordingly, pericyclic reactions are classified as either symmetry-allowed or symmetry-forbidden. Woodward and Hoffmann presented the selection criteria for...
3.0K
Polymer Classification: Architecture
2.6K
Polymers are classified as linear or branched on the basis of their chain architecture. The polymer chains in linear polymers have a long chain-like structure with minimal to no branching at all. Even if a polymer features large substituent groups on the monomer, which appear as branches to the skeleton, it is not considered a branched polymer. A branched polymer contains secondary polymer chains that arise from the main polymer chain. The branching occurs when the polymer growth shifts from...
2.6K
Olefin Metathesis Polymerization: Ring-Opening Metathesis Polymerization (ROMP)
2.5K
Ring-opening metathesis polymerization or ROMP involves strained cycloalkenes as starting materials. The mechanism of ROMP proceeds by reacting cycloalkene with Grubbs catalyst to give metallacyclobutane intermediate which undergoes a ring-opening reaction to form new carbene. The new carbene reacts with another molecule of cycloalkene. Repetition of these steps leads to the formation of an unsaturated open-chain polymer product. All these steps are reversible, however, relieving the ring...
2.5K
Restarting Stalled Replication Forks
5.7K
DNA replication is initiated at sites containing predefined DNA sequences known as origins of replication. DNA is unwound at these sites by the minichromosome maintenance (MCM) helicase and other factors such as Cdc45 and the associated GINS complex.The unwound single strands are protected by replication protein A (RPA) until DNA polymerase starts synthesizing DNA at the 5’ end of the strand in the same direction as the replication fork. To prevent the replication fork from falling apart,...
5.7K
Radical Chain-Growth Polymerization: Overview
2.4K
Chain-growth or addition polymerization is successive addition reactions of monomers with a polymer chain. In radical chain-growth polymerization, the reaction proceeds via a free-radical intermediate. The free radical is formed from radical initiators, which spontaneously generate free radicals by homolytic fission. Organic peroxides (such as dibenzoyl peroxide, as shown in Figure 1) or azo compounds are popular radical initiators. A low concentration ratio of radical initiator to monomer is...
2.4K


