Vyas, Nikhil ;
Williams, Ryan
On Oracles and Algorithmic Methods for Proving Lower Bounds
Abstract
This paper studies the interaction of oracles with algorithmic approaches to proving circuit complexity lower bounds, establishing new results on two different kinds of questions.
1) We revisit some prominent open questions in circuit lower bounds, and provide a clean way of viewing them as circuit upper bound questions. Let MissingString be the (total) search problem of producing a string that does not appear in a given list L containing M bitstrings of length N, where M < 2ⁿ. We show in a generic way how algorithms and uniform circuits (from restricted classes) for MissingString imply complexity lower bounds (and in some cases, the converse holds as well).
We give a local algorithm for MissingString, which can compute any desired output bit making very few probes into the input, when the number of strings M is small enough. We apply this to prove a new nearlyoptimal (up to oracles) time hierarchy theorem with advice.
We show that the problem of constructing restricted uniform circuits for MissingString is essentially equivalent to constructing functions without small nonuniform circuits, in a relativizing way. For example, we prove that small uniform depth3 circuits for MissingString would imply exponential circuit lower bounds for Σ₂ EXP, and depth3 lower bounds for MissingString would imply nontrivial circuits (relative to an oracle) for Σ₂ EXP problems. Both conclusions are longstanding open problems in circuit complexity.
2) It has been known since Impagliazzo, Kabanets, and Wigderson [JCSS 2002] that generic derandomizations improving subexponentially over exhaustive search would imply lower bounds such as NEXP ̸ ⊂ 𝖯/poly. Williams [SICOMP 2013] showed that CircuitSAT algorithms running barely faster than exhaustive search would imply similar lower bounds. The known proofs of such results do not relativize (they use techniques from interactive proofs/PCPs). However, it has remained open whether there is an oracle under which the generic implications from circuitanalysis algorithms to circuit lower bounds fail.
Building on an oracle of Fortnow, we construct an oracle relative to which the circuit approximation probability problem (CAPP) is in 𝖯, yet EXP^{NP} has polynomialsize circuits.
We construct an oracle relative to which SAT can be solved in "halfexponential" time, yet exponential time (EXP) has polynomialsize circuits. Improving EXP to NEXP would give an oracle relative to which Σ₂ 𝖤 has "halfexponential" size circuits, which is open. (Recall it is known that Σ₂ 𝖤 is not in "subhalfexponential" size, and the proof relativizes.) Moreover, the running time of the SAT algorithm cannot be improved: relative to all oracles, if SAT is in "subhalfexponential" time then EXP does not have polynomialsize circuits.
BibTeX  Entry
@InProceedings{vyas_et_al:LIPIcs.ITCS.2023.99,
author = {Vyas, Nikhil and Williams, Ryan},
title = {{On Oracles and Algorithmic Methods for Proving Lower Bounds}},
booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
pages = {99:199:26},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772631},
ISSN = {18688969},
year = {2023},
volume = {251},
editor = {Tauman Kalai, Yael},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17602},
URN = {urn:nbn:de:0030drops176021},
doi = {10.4230/LIPIcs.ITCS.2023.99},
annote = {Keywords: oracles, relativization, circuit complexity, missing string, exponential hierarchy}
}
01.02.2023
Keywords: 

oracles, relativization, circuit complexity, missing string, exponential hierarchy 
Seminar: 

14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Issue date: 

2023 
Date of publication: 

01.02.2023 