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还想证明，在普遍相信的复杂性假设下，一些随机算法不可能在没有显著速度损失的情况下进行非随机化。

项目成果

Extractors for Images of Varieties

• DOI: 10.1145/3564246.3585109
• 发表时间: 2022-11
• 期刊: Proceedings of the 55th Annual ACM Symposium on Theory of Computing
• 作者: Zeyu Guo;Ben lee Volk;Akhil Jalan;David Zuckerman

XOR lemmas for resilient functions against polynomials

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

• DOI: 10.1145/3357713.3384242
• 发表时间: 2020
• 期刊: 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

• DOI: 10.4007/annals.2019.189.3.1
• 发表时间: 2019-05-01
• 期刊: ANNALS OF MATHEMATICS
• 影响因子: 4.9
• 作者: Chattopadhyay, Eshan;Zuckerman, David
• 通讯作者: Zuckerman, David

Simple Optimal Hitting Sets for Small-Success RL

小成功 RL 的简单最佳击球组合

• DOI: 10.1137/19m1268707
• 发表时间: 2020
• 期刊: SIAM Journal on Computing
• 影响因子: 1.6
• 作者: Hoza, William M.;Zuckerman, David
• 通讯作者: Zuckerman, David

Randomness Efficient Noise Stability and Generalized Small Bias Sets

随机性、高效噪声稳定性和广义小偏差集

• DOI: 10.4230/lipics.fsttcs.2020.31
• 发表时间: 2020
• 期刊: Leibniz international proceedings in informatics
• 作者: Moshkovitz, D;Zuckerman, D.
• 通讯作者: Zuckerman, D.