Lower bounds, meta-algorithms, and pseudorandomness

哪些计算问题“容易”，哪些“难”？为什么要证明我们的考生计算难题真的很难呢？我们能从困难的计算问题(从确定其难易程度的证明)中提取有效的算法吗？相反，我们能通过设计更有效的算法来获得新的下界吗？在所有这一切中，(伪)随机性扮演了什么角色？ 下限(证明计算机的局限性)早于第一代计算机！20世纪30年代，艾伦·图灵发明了通用计算机的概念，同时证明了没有这样的计算机可以解决逻辑上的特定问题！尽管多年来已经发现了许多有效的算法，但仍然有许多自然问题(如NP-完全问题)的复杂性未知。对于布尔电路的非均匀计算模型，也存在许多候选困难问题，但对于足够多的一般电路类，还没有下界证明。 Razborov和Rudich的“自然证明障碍”认为，在看似合理的密码假设下，某些建设性的证明论点不能证明强大的电路下界。他们争论的核心是最小电路大小问题的某个平均情况版本，该问题要求确定一个布尔函数f的给定真值表，如果f有至多一个给定参数的电路S。 MCSP是元计算问题的一个重要例子：该问题的输入是其他计算问题的实例。元问题的其他例子包括可满足性(SAT)、计算学习和随机化算法的去随机化。电路下限导致新算法的例子很多，反之亦然。特别地，在电路下界和去随机化之间、在电路下界的构造性(在Razborov和Rudich意义下)证明和学习算法之间、在电路下界和非平凡SAT算法之间存在着已知的联系。在所有这些联系中，伪随机性扮演着一个重要的角色：研究并不是真正随机的、但在某些计算有界的观察者看来“看起来是随机的”“类似随机”的对象。 这项研究的主要目的是通过证明新的下界和设计新的算法来更好地理解高效计算的能力和局限性，探索两者之间明显的密切联系。伪随机性理论中的概念和方法将是本研究的主要工具。特别是，我们将研究MCSP的复杂性，为电路类ACC0寻找更具建设性的下界证明，并试图证明随机多项式时间算法严格弱于确定性指数时间算法(或者至少试图理解为什么这种分离很难证明)。

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