Constant-depth circuit size lower bounds

项目摘要：恒定深度逻辑电路是最成功的复杂性下限设置之一。早期的结果确定了奇偶函数(给定一个n位字符串，是否有偶数为1？)没有多项式大小的恒定深度电路。在一系列的论文中，我们知道需要指数大小的恒定深度电路来计算奇偶性，提供了许多新的技术和使用强大的开关引理或可满足性编码引理的几乎最优的下界。该项目的目标之一是改进已知的、基于灵敏度的技术，并为奇偶性(或其他高度敏感的函数)提供本质上最优的下界。寻找一种新的基于可满足性编码引理的电路交换技术。一个类似但困难得多的问题是，计算函数多数的恒定深度电路的最小尺寸(给定n位串，1是否比0多？)。大多数最知名的恒定深度大小界限之间存在较大差距。来自平价分析的基于敏感性的方法不够强大，不足以为多数人提供更严格的界限。这个项目的另一个目的是更好地理解这种技术的局限性，并找到替代方法来解决关于多数的复杂性的问题。一种候选方法是基于组合学的极值超图理论中的技术。该项目旨在研究相应的问题，广义超图Turán问题。针对恒定深度电路的新的下界通常包含关于CNF(本质上是深度2电路)的结构的新信息。关于CNF的新的结构结果历来转化为更好的CNF可满足性(SAT)求解器。一个成功的项目可能被用来改进或寻找新的SAT解算器。该项目属于EPSRC理论计算机科学研究领域，在ICT项下。

Summary of the project: Constant-depth logical circuits have been one of the most successful settings for complexity lower bounds. Early results established that the PARITY function (given an n bit string, are there an even number of 1?) does not have polynomial-size constant-depth circuits. Over a series of papers, we know that exponential-size constant-depth circuits are required to calculate PARITY, providing numerous new techniques and an almost-optimal lower bound using the powerful switching lemma or the satisfiability coding lemma. One of the aims of this project is to improve the already-known, sensitivity based, techniques and provide an essentially optimal lower bound for PARITY (or other highly sensitive functions). To find a new circuit switching technique based on the satisfiability coding lemma.A similar, but much harder question, asks the minimum size of constant-depth circuits calculating the function MAJORITY (given an n bit string, are there more 1s than 0s?). There is a larger gap between the best-known constant-depth size bounds for MAJORITY. The sensitivity-based approaches coming from the analysis of PARITY are not powerful enough to provide tighter bounds for MAJORITY. Another aim of this project is to better understand the limitations of such techniques and to find alternative methods to attack the question regarding the complexity of MAJORITY. One candidate method is based on techniques in extremal hypergraph theory from combinatorics. The project aims to investigate the corresponding question, the generalized hypergraph Turán problem.New lower bounds against constant-depth circuits often involve novel information about the structure of CNFs (which is essentially a depth 2 circuit). New structural results about CNFs historically translate to better CNF satisfiability (SAT) solvers. A successful project might be applied to improve or find new SAT solvers.This project falls within the EPSRC Theoretical Computer Science research area, under ICT.