Lower bounds, meta-algorithms, and pseudorandomness

下界、元算法和伪随机性

• 批准号: RGPIN-2019-05543
• 负责人: Kabanets, Valentine
• 金额: $ 2.99万
• 依托单位: Simon Fraser University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=750564
• 关键词: Lower; bounds; meta; algorithms; pseudorandomness

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).

哪些计算问题是``简单''，哪些计算问题是``hard''？为什么很难证明我们的候选人硬计算问题实际上很困难？我们可以从严格的计算问题中提取有效的算法（从确定硬度的证据中）吗？相反，我们可以通过设计更有效的算法来获得新的下限吗？ （伪）随机性在所有这些中的作用是什么？下限（计算机的证明局限性）早于第一台计算机！在1930年代，艾伦·图灵（Alan Turing）发明了通用计算机的概念，同时说明没有这样的计算机可以解决逻辑上的某些问题！尽管多年来发现了许多有效的算法，但仍然存在许多自然问题（例如NP完全问题），它们的复杂性尚不清楚。对于布尔电路的非均匀计算模型，也有许多候选硬性问题，但没有足够的电路类别的下限证明。 Razborov和Rudich论点的“自然证明障碍”认为某些建设性的证据论点不能在合理的加密假设下证明强大的电路下限。他们的论点的核心是最小电路尺寸问题（MCSP）的一定平均案例版本，该版本要求确定布尔函数f的给定真实表，如果F最多具有给定参数s的大小的电路。 MCSP是元计算问题的重要示例：输入是其他计算问题实例的问题。元问题的其他示例包括满意度（SAT），计算学习和随机算法的衍生化。有许多示例，电路下限导致新算法，反之亦然。特别是，电路下限与降低的范围之间存在已知的联系，在构造性（在拉兹博罗夫和鲁迪奇的意义上），电路下限和学习算法的证明，以及电路下限和非平凡的SAT算法之间。在所有这些连接中的重要作用是通过伪随机性发挥的：对不是真正随机的“随机”对象的研究，而是对某些计算有限观察者的“随机”。拟议研究的主要目的是通过证明新的下限和设计新算法来更好地了解有效计算的能力和局限性，探讨两者之间明显的亲密联系。伪随身理论的概念和技术将是本研究的主要工具。特别是，我们将研究MCSP的复杂性，寻找对电路类ACC0的更具建设性的下限证明，并试图证明随机多项式时间算法严格严格弱于确定性指数时间的算法（或至少试图理解为什么这种分离很难透露出来）。