AF:Medium:Fine-Grained Derandomization

AF：中：细粒度去随机化

• 批准号: 1705028
• 负责人: David Zuckerman
• 金额: $ 119.99万
• 依托单位: University of Texas at Austin
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-09-01 至 2022-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1705028&HistoricalAwards=false
• 关键词: AF; Medium; Fine; Grained; Derandomization

For many problems, randomized algorithms offer significant speedups over known algorithms that don't use randomness. However, randomization introduces uncertainty in the outcome of the algorithm, as there will be a small probability of error. The purpose of this project is to explore when uncertainty can be eliminated without giving up on speed. The project integrates education and outreach, including mentoring of students, public lectures and popular science writing. The PIs identify several families of problems where randomized algorithms outperform the best known deterministic ones, including: problems on dense graphs like finding an approximate clique in a dense graph; algebraic problems like polynomial identity testing and factorization; and problems that can be solved using Markov chains, like approximately counting the number of perfect matchings in a bipartite graph. The PIs wish to develop new techniques for derandomization that do not increase the run-time substantially. The PIs also want to prove that, under widely believed complexity assumptions, some randomized algorithms are impossible to derandomize without a significant loss in speed.

对于许多问题，随机算法比不使用随机性的已知算法提供了显着的加速。然而，随机化会给算法的结果带来不确定性，因为错误的概率很小。该项目的目的是探索何时可以在不放弃速度的情况下消除不确定性。该项目整合了教育和推广，包括学生指导、公开讲座和科普写作。 PI 确定了随机算法优于最著名的确定性算法的几类问题，包括： 稠密图上的问题，例如在稠密图中查找近似派系；代数问题，例如多项式恒等测试和因式分解；以及可以使用马尔可夫链解决的问题，例如近似计算二分图中完美匹配的数量。 PI 希望开发出不会大幅增加运行时间的去随机化新技术。 PI 还想证明，在人们普遍认为的复杂性假设下，一些随机算法不可能在不显着降低速度的情况下实现去随机化。

项目成果

Pseudorandomness from Shrinkage

收缩带来的伪随机性

• 发表时间: 2019-04
• 期刊: Journal of the ACM
• 影响因子: 2.5
• 作者: Impagliazzo, R;Meka, R;Zuckerman, D
• 通讯作者: Zuckerman, D

Improved Extractors for Recognizable and Algebraic Sources

改进的可识别代数源提取器

• 发表时间: 2019-01
• 期刊: 23rd International Conference on Randomization and Computation (RANDOM
• 作者: Li, F;Zuckerman, D
• 通讯作者: Zuckerman, D

Size Bounds on Low Depth Circuits for Promise Majority

低深度电路的尺寸限制，以实现多数承诺

• DOI: 10.4230/lipics.fsttcs.2020.19
• 发表时间: 2020-01
• 期刊: Leibniz international proceedings in informatics
• 作者: Cook; J
• 通讯作者: J

XOR lemmas for resilient functions against polynomials

针对多项式的弹性函数的异或引理

• DOI: 10.1145/3357713.3384242
• 发表时间: 2020-06
• 期刊: 52nd Annual ACM Symposium on Theory of Computing (STOC
• 作者: Chattopadhyay, Eshan;Hatami, Pooya;Hosseini, Kaave;Lovett, Shachar;Zuckerman, David
• 通讯作者: Zuckerman, David

Explicit two-source extractors and resilient functions

显式双源提取器和弹性函数

• 发表时间: 2019-05
• 期刊: Annals of mathematics
• 影响因子: 4.9
• 作者: Chattopadhyay, E;Zuckerman, D
• 通讯作者: Zuckerman, D