Constant-depth circuit size lower bounds

恒定深度电路尺寸下限

• 批准号: 2421736
• 金额: --
• 依托单位: University of Oxford
• 依托单位国家: 英国
• 项目类别: Studentship
• 财政年份: 2020
• 资助国家: 英国
• 起止时间: 2020 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=studentship-2421736
• 关键词: Constant; depth; circuit; size; lower

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.

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