Symmetric Exponential Time Requires Near-Maximum Circuit Size: Simplified, Truly Uniform

2023/10/26 by Zeyong Li, Li, Zeyong · 7 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2310.17762

openalex publication_date 2023/10/26 · openalex created_date 2023/11/01 · openalex updated_date 2026/07/28

Abstract

In a recent breakthrough, Chen, Hirahara and Ren prove that S₂E/₁ \not⊂ SIZE[2ⁿ/n] by giving a single-valued FS₂P algorithm for the Range Avoidance Problem (Avoid) that works for infinitely many input size n. Building on their work, we present a simple single-valued FS₂P algorithm for Avoid that works for all input size n. As a result, we obtain the circuit lower bound S₂E \not⊂ i.o.-SIZE[2ⁿ/n] and many other corollaries: 1. Almost-everywhere near-maximum circuit lower bound for Σ₂E ∩ Π₂E and ZPE^NP. 2. Pseudodeterministic FZPP^NP constructions for: Ramsey graphs, rigid matrices, pseudorandom generators, two-source extractors, linear codes, hard truth tables, and K^poly-random strings.

Cited by

• Hardness of Range Avoidance and Proof Complexity Generators from Demi-Bits
• New Algebrization Barriers to Circuit Lower Bounds via Communication Complexity of Missing-String
• Oblivious Complexity Classes Revisited: Lower Bounds and Hierarchies
• The Structure of In-Place Space-Bounded Computation
• Counting Martingales for Measure and Dimension in Complexity Classes
• Cell-Probe Lower Bounds via Semi-Random CSP Refutation: Simplified and the Odd-Locality Case
• Downward self-reducibility in the total function polynomial hierarchy

Related

• Symmetric Exponential Time Requires Near-Maximum Circuit Size
• Polynomial formulations as a barrier for reduction-based hardness proofs
• Relationship between circuit complexity and symmetry
• Simulating Branching Programs with Edit Distance and Friends or: A Polylog Shaved is a Lower Bound Made
• Circuits and Backdoors: Five Shades of the SETH