Lower bounds, meta-algorithms, and pseudorandomness
下界、元算法和伪随机性
基本信息
- 批准号:RGPIN-2019-05543
- 负责人:
- 金额:$ 2.99万
- 依托单位:
- 依托单位国家:加拿大
- 项目类别:Discovery Grants Program - Individual
- 财政年份:2022
- 资助国家:加拿大
- 起止时间:2022-01-01 至 2023-12-31
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
Which computational problems are ``easy'' and which ones are ``hard''? Why is it so difficult to prove that our candidate hard computational problems are actually hard? Can we extract efficient algorithms from hard computational problems (from the proofs establishing their hardness)? Conversely, can we get new lower bounds by designing more efficient algorithms? What is the role of (pseudo-) randomness in all of this? Lower bounds (proving limitations of computers) predate the first computers! In 1930s, Alan Turing invented the notion of a universal computer, while proving that no such computer can solve a certain problem in logic! Despite many efficient algorithms that have been discovered over the years, there are still many natural problems (e.g., NP-complete problems) whose complexity is not known. For the non-uniform computation model of boolean circuits, there are also many candidate hard problems, but no lower bound proofs for general enough circuit classes. The "natural proofs barrier" of Razborov and Rudich argues that certain constructive proof arguments cannot prove strong circuit lower bounds, under plausible cryptographic assumptions. At the heart of their argument is a certain average-case version of the Minimum Circuit Size Problem (MCSP) that asks to decide for a given truth table of a boolean function f, if f has circuits of size at most a given parameter s. MCSP is an important example of a meta-computational problem: the problem whose inputs are instances of other computational problems. Other examples of meta-problems include SATISFIABILITY (SAT), computational learning, and derandomization of randomized algorithms. There are many examples where circuit lower bounds lead to new algorithms, and vice versa. In particular, there are known connections between circuit lower bounds and derandomization, between constructive (in the sense of Razborov and Rudich) proofs of circuit lower bounds and learning algorithms, and between circuit lower bounds and non-trivial SAT algorithms. An important role in all these connections is played by pseudorandomness: the study of "random-like" objects that are not truly random, but "appear random" to certain computationally bounded observers. The main objective of the proposed research is to gain better understanding of the power and limitations of efficient computation by proving new lower bounds and designing new algorithms, exploring the apparent intimate connections between the two. The concepts and techniques from the pseudorandomness theory will be the main tools in this study. In particular, we will study the complexity of MCSP, look for more constructive lower bound proofs for the circuit class ACC0 and try to show that randomized polynomial-time algorithms are strictly weaker than deterministic exponential-time ones (or at least try to understand why such a separation is difficult to prove).
哪些计算问题是“容易的”,哪些是“困难的”?为什么要证明我们的候选计算难题实际上是困难的是如此困难?我们能从困难的计算问题中提取有效的算法吗(从证明其困难性的证据中)?相反,我们是否可以通过设计更有效的算法来获得新的下界?(伪)随机性在这一切中扮演什么角色?下限(证明计算机的局限性)早于第一台计算机!20世纪30年代,艾伦·图灵发明了通用计算机的概念,同时证明了没有这样的计算机可以解决逻辑中的某个问题!尽管多年来已经发现了许多有效的算法,但仍然存在许多自然问题(例如,对于布尔电路的非均匀计算模型,也有许多候选困难问题,但没有足够一般的电路类的下界证明。 Razborov和Rudich的“自然证明障碍”认为,在合理的密码学假设下,某些构造性证明参数不能证明强电路下界。他们争论的核心是最小电路尺寸问题(MCSP)的某个平均情况版本,该问题要求对布尔函数f的给定真值表进行判定,如果f的电路尺寸至多为给定参数s。 MCSP是元计算问题的一个重要例子:其输入是其他计算问题的实例的问题。元问题的其他示例包括满意度(SAT)、计算学习和随机算法的去随机化。有许多例子,电路下限导致新的算法,反之亦然。特别是,电路下界和去随机化之间,电路下界的构造性(在Razborov和Rudich的意义上)证明和学习算法之间,以及电路下界和非平凡SAT算法之间存在已知的联系。在所有这些联系中,伪随机性扮演了一个重要的角色:研究“类随机”对象,这些对象不是真正随机的,但对某些计算有限的观察者来说“看起来随机”。所提出的研究的主要目标是通过证明新的下限和设计新的算法,探索两者之间明显的密切联系,以更好地了解有效计算的能力和局限性。伪随机理论的概念和技术将是本研究的主要工具。特别是,我们将研究MCSP的复杂性,寻找电路类ACC 0的更具建设性的下界证明,并试图证明随机多项式时间算法严格弱于确定性指数时间算法(或至少试图理解为什么这种分离难以证明)。
项目成果
期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
数据更新时间:{{ journalArticles.updateTime }}
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
Kabanets, Valentine其他文献
AC0[p] Lower Bounds against MCSP via the Coin Problem
AC0[p] 通过硬币问题针对 MCSP 的下界
- DOI:
- 发表时间:
2019 - 期刊:
- 影响因子:0
- 作者:
Golovnev, Alexander;Ilango, Rahul;Impagliazzo, Russell;Kabanets, Valentine;Kolokolova, Antonina;Tal, Avishay - 通讯作者:
Tal, Avishay
Kabanets, Valentine的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('Kabanets, Valentine', 18)}}的其他基金
Lower bounds, meta-algorithms, and pseudorandomness
下界、元算法和伪随机性
- 批准号:
RGPIN-2019-05543 - 财政年份:2021
- 资助金额:
$ 2.99万 - 项目类别:
Discovery Grants Program - Individual
Lower bounds, meta-algorithms, and pseudorandomness
下界、元算法和伪随机性
- 批准号:
RGPIN-2019-05543 - 财政年份:2020
- 资助金额:
$ 2.99万 - 项目类别:
Discovery Grants Program - Individual
Lower bounds, meta-algorithms, and pseudorandomness
下界、元算法和伪随机性
- 批准号:
RGPIN-2019-05543 - 财政年份:2019
- 资助金额:
$ 2.99万 - 项目类别:
Discovery Grants Program - Individual
Meta-Algorithms versus Circuit Lower Bounds
元算法与电路下界
- 批准号:
298363-2012 - 财政年份:2018
- 资助金额:
$ 2.99万 - 项目类别:
Discovery Grants Program - Individual
Meta-Algorithms versus Circuit Lower Bounds
元算法与电路下界
- 批准号:
298363-2012 - 财政年份:2015
- 资助金额:
$ 2.99万 - 项目类别:
Discovery Grants Program - Individual
Meta-Algorithms versus Circuit Lower Bounds
元算法与电路下界
- 批准号:
298363-2012 - 财政年份:2014
- 资助金额:
$ 2.99万 - 项目类别:
Discovery Grants Program - Individual
Meta-Algorithms versus Circuit Lower Bounds
元算法与电路下界
- 批准号:
298363-2012 - 财政年份:2013
- 资助金额:
$ 2.99万 - 项目类别:
Discovery Grants Program - Individual
Meta-Algorithms versus Circuit Lower Bounds
元算法与电路下界
- 批准号:
298363-2012 - 财政年份:2012
- 资助金额:
$ 2.99万 - 项目类别:
Discovery Grants Program - Individual
Pseudorandomness and complexity
伪随机性和复杂性
- 批准号:
298363-2007 - 财政年份:2011
- 资助金额:
$ 2.99万 - 项目类别:
Discovery Grants Program - Individual
Pseudorandomness and complexity
伪随机性和复杂性
- 批准号:
298363-2007 - 财政年份:2010
- 资助金额:
$ 2.99万 - 项目类别:
Discovery Grants Program - Individual
相似国自然基金
资本外逃及其逆转:基于中国的理论与实证研究
- 批准号:70603008
- 批准年份:2006
- 资助金额:17.0 万元
- 项目类别:青年科学基金项目
相似海外基金
CAREER: Lower Bounds for Shallow Circuits
职业生涯:浅层电路的下限
- 批准号:
2338730 - 财政年份:2024
- 资助金额:
$ 2.99万 - 项目类别:
Continuing Grant
Complexity Lower Bounds from Expansion
扩展带来的复杂性下限
- 批准号:
23K16837 - 财政年份:2023
- 资助金额:
$ 2.99万 - 项目类别:
Grant-in-Aid for Early-Career Scientists
Non-parametric estimation under covariate shift: From fundamental bounds to efficient algorithms
协变量平移下的非参数估计:从基本界限到高效算法
- 批准号:
2311072 - 财政年份:2023
- 资助金额:
$ 2.99万 - 项目类别:
Standard Grant
Towards new classes of conic optimization problems
迈向新类别的二次曲线优化问题
- 批准号:
23K16844 - 财政年份:2023
- 资助金额:
$ 2.99万 - 项目类别:
Grant-in-Aid for Early-Career Scientists
Branching Program Lower Bounds
分支程序下界
- 批准号:
RGPIN-2019-06288 - 财政年份:2022
- 资助金额:
$ 2.99万 - 项目类别:
Discovery Grants Program - Individual
Tighter error bounds for representation learning and lifelong learning
表征学习和终身学习的更严格的误差范围
- 批准号:
RGPIN-2018-03942 - 财政年份:2022
- 资助金额:
$ 2.99万 - 项目类别:
Discovery Grants Program - Individual
AF: Small: New Techniques for Optimal Bounds on MCMC Algorithms
AF:小:MCMC 算法最优边界的新技术
- 批准号:
2147094 - 财政年份:2022
- 资助金额:
$ 2.99万 - 项目类别:
Standard Grant
Extremal Combinatorics Exact Bounds
极值组合精确界
- 批准号:
574168-2022 - 财政年份:2022
- 资助金额:
$ 2.99万 - 项目类别:
University Undergraduate Student Research Awards
Lower bounds on ranks of nontrivial toric vector bundles
非平凡环面向量丛的秩下界
- 批准号:
558713-2021 - 财政年份:2022
- 资助金额:
$ 2.99万 - 项目类别:
Postgraduate Scholarships - Doctoral
Bringing upper and lower bounds closer in computational geometry
使计算几何中的上限和下限更加接近
- 批准号:
567959-2022 - 财政年份:2022
- 资助金额:
$ 2.99万 - 项目类别:
Postgraduate Scholarships - Doctoral