License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2023.35
URN: urn:nbn:de:0030-drops-183053
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18305/
Santhanam, Rahul
An Algorithmic Approach to Uniform Lower Bounds
Abstract
We propose a new family of circuit-based sampling tasks, such that non-trivial algorithmic solutions to certain tasks from this family imply frontier uniform lower bounds such as "NP is not in uniform ACC⁰" and "NP does not have uniform polynomial-size depth-two threshold circuits". Indeed, the most general versions of our sampling tasks have implications for central open problems such as NP vs P and PSPACE vs P.
We argue the soundness of our approach by showing that the non-trivial algorithmic solutions we require do follow from standard cryptographic assumptions. In addition, we give evidence that a version of our approach for uniform circuits is necessary in order to separate NP from P or PSPACE from P. We give an algorithmic characterization for the PSPACE vs P question: PSPACE ≠ P iff either E has sub-exponential time non-uniform algorithms infinitely often or there are non-trivial space-efficient solutions to our sampling tasks for uniform Boolean circuits.
We show how to use our framework to capture uniform versions of known non-uniform lower bounds, as well as classical uniform lower bounds such as the space hierarchy theorem and Allender’s uniform lower bound for the Permanent. We also apply our framework to prove new lower bounds: NP does not have polynomial-size uniform AC⁰ circuits with a bottom layer of MOD 6 gates, nor does it have polynomial-size uniform AC⁰ circuits with a bottom layer of threshold gates.
Our proofs exploit recently defined probabilistic time-bounded variants of Kolmogorov complexity [Zhenjian Lu et al., 2022; Halley Goldberg et al., 2022; Halley Goldberg et al., 2022].
BibTeX - Entry
@InProceedings{santhanam:LIPIcs.CCC.2023.35,
author = {Santhanam, Rahul},
title = {{An Algorithmic Approach to Uniform Lower Bounds}},
booktitle = {38th Computational Complexity Conference (CCC 2023)},
pages = {35:1--35:26},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-282-2},
ISSN = {1868-8969},
year = {2023},
volume = {264},
editor = {Ta-Shma, Amnon},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18305},
URN = {urn:nbn:de:0030-drops-183053},
doi = {10.4230/LIPIcs.CCC.2023.35},
annote = {Keywords: Probabilistic Kolmogorov complexity, sampling algorithms, uniform lower bounds}
}
|
Keywords: |
|
Probabilistic Kolmogorov complexity, sampling algorithms, uniform lower bounds |
|
Collection: |
|
38th Computational Complexity Conference (CCC 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
10.07.2023 |
