2026-07-23T05:29:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14113 2024-03-06T10:53:30Z ddc:004 open_access

Lifting for Constant-Depth Circuits and Applications to MCSP Carmosino, Marco Hoover, Kenneth Impagliazzo, Russell Kabanets, Valentine Kolokolova, Antonina circuit complexity constant-depth circuits lifting theorems Minimum Circuit Size Problem reductions Switching Lemma Lifting arguments show that the complexity of a function in one model is essentially that of a related function (often the composition of the original function with a small function called a gadget) in a more powerful model. Lifting has been used to prove strong lower bounds in communication complexity, proof complexity, circuit complexity and many other areas. We present a lifting construction for constant depth unbounded fan-in circuits. Given a function f, we construct a function g, so that the depth d+1 circuit complexity of g, with a certain restriction on bottom fan-in, is controlled by the depth d circuit complexity of f, with the same restriction. The function g is defined as f composed with a parity function. With some quantitative losses, average-case and general depth-d circuit complexity can be reduced to circuit complexity with this bottom fan-in restriction. As a consequence, an algorithm to approximate the depth d (for any d > 3) circuit complexity of given (truth tables of) Boolean functions yields an algorithm for approximating the depth 3 circuit complexity of functions, i.e., there are quasi-polynomial time mapping reductions between various gap-versions of AC⁰-MCSP. Our lifting results rely on a blockwise switching lemma that may be of independent interest. We also show some barriers on improving the efficiency of our reductions: such improvements would yield either surprisingly efficient algorithms for MCSP or stronger than known AC⁰ circuit lower bounds. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Marco Carmosino and Kenneth Hoover and Russell Impagliazzo and Valentine Kabanets and Antonina Kolokolova 2021 Is Part Of LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2021.44 urn:nbn:de:0030-drops-141135 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.44 eng https://creativecommons.org/licenses/by/4.0/legalcode