Constant-depth circuit size lower bounds

项目概述：恒深逻辑电路是复杂度下界最成功的设置之一。早期的结果证实奇偶校验函数（给定一个n位字符串，是否有偶数1?）不具有多项式大小的定深电路。在一系列的论文中，我们知道需要指数大小的等深度电路来计算奇偶校验，提供了许多新技术和使用强大的开关引理或可满足性编码引理的几乎最优下界。该项目的目的之一是改进已知的基于灵敏度的技术，并为奇偶校验（或其他高灵敏度函数）提供一个本质上最优的下界。寻找一种基于可满足性编码引理的电路交换新技术。一个类似的，但更难的问题是，计算函数MAJORITY的恒深电路的最小尺寸（给定一个n位字符串，15比0多吗？）对于MAJORITY，最著名的等深度大小界限之间存在较大的差距。来自奇偶性分析的基于灵敏度的方法不够强大，无法为MAJORITY提供更严格的界限。该项目的另一个目的是更好地了解这些技术的局限性，并找到替代方法来解决有关MAJORITY复杂性的问题。一种候选方法是基于组合学中的极值超图理论技术。该项目旨在研究相应的问题，广义超图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.