New Circuit Lower Bounds and Complexity Theory Insights

New Circuit Lower Bounds via Solving Range Avoidance Shuichi Hirahara National Institute of Informatics Lijie Chen UC Berkeley Hanlin Ren University of Oxford Zeyong Li National University of Singapore https://eccc.weizmann.ac.il/report/2023/144/ https://eccc.weizmann.ac.il/report/2023/156/

Todays Plan Motivation, Background, New Results: New Maximum Circuit Lower Bounds New Algorithms for Range Avoidance Proof Overview: Korten s algorithm An Infinitely-often algorithm for range avoidance via Iterative win-win [CHR 23] An almost-everywhere algorithm for range avoidance [Li 23]

Motivation: Exponential Circuit Lower Bounds Counting Argument [Shannon 49] Most of the ?-bit functions ?: 0,1? {0,1} has circuit complexity at least 2?/?. A Fundamental Challenge of Complexity Theory Can we find an explicit? that requires 2 (?)-size circuits? In other words, what is the smallest complexity class that contains a function requiring 2 (?)-size circuits?

Motivation: Exponential Circuit Lower Bounds Counting Argument [Shannon 49] Most of the ?-bit functions ?: 0,1? {0,1} has circuit complexity at least 2?/?. Exponential Circuit Lower Bounds are Important [Nisan-Wigderson 94] [Impagliazzo-Wigderson 97] If there is ? E that requires 2 (?)-size circuits, then prP = prBPP Super-polynomial lower bounds only gives prBPP in prSUBEXP

Exponential Circuit Lower Bounds: Whats Known In 1982, Kannan proved that there is ? 3E that requires 2?/?-size circuits. In 1999, Miltersen, Vinodchandran, and Watanabe observed that ? E 2P suffices. These are all we knew before 2023 Four-decade-old open question Does 2E require 2 (?)-size circuits?

Complexity Theory 201 The Polynomial Hierarchy The Exponential Hierarchy ?: a deterministic 2?(?)-time algorithm ?: a deterministic poly(?)-time algorithm ? = ?; ? , ? , ? ??(?) iff there is ? s.t. ? = ?; ? , ? , ? ????(?) iff there is ? s.t. ? is in ? is in P ? ? ? ? = ? E ? ? ? ? = ? NP ? ? ? ? ?,? = ? NE ? ? ? ? ?,? = ? 2P ? ? ? ? ? ?,?,? = ? 2E ? ? ? ? ? ?,?,? = ? 3P ? ? ? ? ? ? ?,?,?,? = ? 3E ? ? ? ? ? ? ?,?,?,? = ?

(Finally) New Results [Chen-Hirahara-Ren 23] There is ? 2E requiring 2?/?-size circuits. [Li 23] There is ? 2E requiring 2?/?-size circuits, on all input lengths. In fact, the same lower bound holds for S2Ewith one bit of advice [CHR 23] and S2E[Li 23] ENP S2E ZPENP

Win-win method in proving circuit lower bounds Kannan proved 2P does not have ??-size circuits for every ?. Win II If NP has polynomial-size circuits. PH collapses to 2P. PH does not have ??-size circuits for every ?. 2P does not have ??-size circuits for every ?. Win I If NP does not have polynomial-size circuits. DONE Key idea: case analysis depending on whether NP has polynomial-size circuits or not. Drawbacks of the win-win method If scaling to 2E, it only proves half-exponential circuit lower bound. It can only show 2P (or 2E) is hard on infinitely many input lengths.

Win-win method in proving circuit lower bounds 2?(?) ?:? ? ? Drawbacks of the win-win method If scaling to 2?, it only proves half-exponential circuit lower bound. It can only show 2P (or 2E) is hard on infinitely many input lengths. For the last four decades, all lower bounds against unrestricted circuits follow the win-win method. (To the best of my knowledge.) In 2023 we have two new techniques! (both drawbacks are addressed) [Chen-Hirahara-Ren 23]: Iterative win-win method (or Winlog ? method) (Initiated by the pseudo-deterministic poly-time construction of primes [Chen-Lu-Oliveira-Ren-Santhanam]) [Li 23]: Just-win method (?)

Todays Plan Motivation, Background, New Results: New Maximum Circuit Lower Bounds New Algorithms for Range Avoidance Proof Overview: Korten s algorithm An Infinitely-often algorithm for range avoidance via Iterative win-win [CHR 23] An almost-everywhere algorithm for range avoidance [Li 23]

Range Avoidance Input: Given a circuit ?: 0,1? 0,1?+1. Goal: Find a non-output of ?. (i.e., a string ? 0,1?+1 s.t. ? ? ? ? 0,1?). A non-output 0,1?+1 ? 0,1? ? Range(?)

Single-valued F2P Algorithm A single-valued F 2P algorithm ? is given by a deterministic poly(?)-time algorithm ? ?,?,?,? ; we assume ? = ?; ? , ? , ? poly(?). We say ?(?)outputs?, if ? is the unique string such that ? ?? ?,?,?,? = 1. Intuitions: ? is a proof for ? ? = ? . Each ? corresponds to a condition that ? must satisfy. ? is a verifierthat checks exponentially many conditions (for each ?) on the proof ?; accept only if all of them pass.

Results [Chen-Hirahara-Ren 23] There is a single-valued ????-algorithm for range avoidance that works on infinitely many input lengths. [Li 23] There is a single-valued ????-algorithm for range avoidance that works on all input lengths. In fact, the algorithm can be improved to single-valued FS2P; see the papers for details!

Circuit Lower Bounds from Range Avoidance ? = 2?. ???: 0,1? 1 0,1? ??? maps the description of a 2?/?-size circuit ? (that can be encoded by 2? 1 = ? 1 bits) into its truth-table: ? 0?, ,?(1?). A non-output of ??? is the truth-table of a function ?: 0,1? {0,1}without2?/?-size circuits Exercise Single-valued F 2Palgorithm for Range Avoidance with TT? There is L 2E that requires 2?/?-size circuits.

Corollary: Zero-error Pseudo-deterministic Algorithm for Range Avoidance [Chen-Hirahara-Ren 23], [Li 23] There is a randomized polynomial-time algorithm ? that uses an NP oracle, such that for all circuits ?: 0,1? 0,1?+1, there exists a string ?? 0,1?+1 that is not in the range of ?, such that 1. with probability at least 1 2 ?, ?(?) outputs ??; 2. if ?(?) does not output ??, it outputs FAIL [CHR 23] got an infinitely-often algorithm, improved to almost-everywhere [Li 23]. Corollary of the single-valued FS2P algorithm and S2P ZPPNP; (omitted in this talk; see the paper!)

Corollary: Explicit Construction [Chen-Hirahara-Ren 23], [Li 23] There is a randomized polynomial-time algorithm ? that uses an NP oracle, such that for all circuits ?: 0,1? 0,1?+1, there exists a string ?? 0,1?+1 that is not in the range of ?, such that 1. with probability at least 1 2 ?, ?(?) outputs ??; 2. if ?(?) does not output ??, it outputs FAIL Imply (zero-error pseudodeterministic with an NP oracle) constructions of Ramsey graphs, rigid matrices, two-source extractors, linear codes, and ?????-random strings with nearly optimal parameters.

Todays Plan Motivation, Background, New Results: New Maximum Circuit Lower Bounds New Algorithms for Range Avoidance Proof Overview: Korten s algorithm An Infinitely-often algorithm for range avoidance via Iterative win-win [CHR 23] An almost-everywhere algorithm for range avoidance [Li 23]

Some Intuition Given a circuit ?: 0,1? 0,12? For convenience, from now on we assume ? maps ? bits into 2? bits (instead of ? + 1 bits) Let Invert?: 0,12? 0,1? { } be the PNP function that finds the lexicographically first preimage of its input, or output if no preimage. Suppose I have a string ? 0,12? and oracle access to Invert? I can either losslessly compress ? into ? bits (? Invert?(z)) OR I solvedrange avoidance for ?! I can indeed recursively compress anarbitrarily long string into ? bits!

Kortens algorithm: Korten(?,?) The algorithm takes a circuit ?: 0,1? 0,12? together with a string ? 0,1? as input. It uses an NP oracle and runs in poly(T) time The guarantee: Korten(?,?) either finds a non-output of ?, or finds an ?-bit, succinctrepresentation of ?.

Input: Circuit ?: 0,1? 0,12? and a string ? 0,1?; ? = ? 2?. Invert?: find the lex. first preimage or report in ???. Consider a depth-?full binary tree, we partition ? into 2? blocks, and write ? on the last layer. Here ? = 3. ? bits ?(1) ?(2) ?(3) ?(4) ?(5) ?(6) ?(7) ?(8) ? = ?(1) ?(2) ?(7) ?(8)

Input: Circuit ?: 0,1? 0,12? a string ? 0,1?; ? = ? 2?. Invert?: find the lex. first preimage or report in ???. Korten(?,?) from bottom (leaves) to top (root), and from left to right, try to fill in each intermediate node using Invert?; stop if get . 7 5 6 1 2 3 4 ?(1) ?(2) ?(3) ?(4) ?(5) ?(6) ?(7) ?(8) ? = ?(1) ?(2) ?(7) ?(8)

Input: Circuit ?: 0,1? 0,12? a string ? 0,1?; ? = ? 2?. Invert?: find the lex. first preimage or report in ???. Korten(?,?) from bottom (leaves) to top (root), and from left to right, try to fill in each intermediate node using Invert?; stop if get . ?7 Invert? (?5 ?6) ?5 ?6 Invert? (?1 ?2) Invert? (?3 ?4) ?1 ?2 ?3 ?4 Invert? (?1 ?(2)) Invert? (?3 ?(4)) Invert? (?5 ?(6)) Invert? (?7 ?(8)) ?(1) ?(2) ?(3) ?(4) ?(5) ?(6) ?(7) ?(8) ? = ?(1) ?(2) ?(7) ?(8)

Key Lemma If the algorithm does not find a non-output of ? (i.e., it finds the root ?2? 1), then?has a ( ? ?)-size circuit. Hint: this is just GGM! ?7 ?5 ?6 = ?(?7) ?5 ?6 ?3 ?4 = ?(?6) ?1 ?2 ?3 ?4 ?(5) ?(6)= ?(?3) ?(5) ?(6)

Korten(?,?): Hardness vs Randomness If? has no( ? ?)-size circuits, then Korten(?,?) finds a non-output of ?. Using a hard truth-table to solve a derandomization task. [Nisan-Wigderson 94] [Impagliazzo-Wigderson 97] If? has nopoly(|?|)-size circuits, then NW(?,?) approximatesPr ?[? ? = 1] within 0.01.

Key idea in [CHR23] The Computational History of Korten(?,?) Korten(?,?) from bottom (leaves) to top (root), and from left to right, try to fill in each intermediate node using Invert?; stop if get . History ?,? the values of all nodes in the end + index of last node History ?,? = ?(1) ?(2) ?(7) ?(8) ?1 ?2 ?3 ?4 + 5 Korten(?,?) = ?1 ?2 ?? Invert? (?1 ?2) ?1 ?2 ?3 ?4 Invert? (?1 ?(2)) Invert? (?3 ?(4)) Invert? (?5 ?(6)) Invert? (?7 ?(8)) ?(1) ?(2) ?(3) ?(4) ?(5) ?(6) ?(7) ?(8) ? = ?(1) ?(2) ?(7) ?(8)

[CHR23]: Local Verification of History ?,? History(?,?) is unique given ? and ?. History(?,?) is the only string passing all ?(? ??) local checks below: They are local since each check only reads ?(?) bits from the history

[CHR23]: Local Verification of History ?,? History(?,?) is unique given ? and ?. History(?,?) is the only string passing all ?(? ??) local checks below: For all ? ?? if and only if ? < ? ? (English version) Check that the algorithm ends at ??

[CHR23]: Local Verification of History ?,? History(?,?) is unique given ? and ?. History(?,?) is the only string passing all ?(? ??) local checks below: For all ? ?? if and only if ? < ? ? For all? < ? ?(??) = (? ??)AND ? ? (? ??) for all? < ?? ?? ? ?? (English version) Check that ??= Invert?(? ??)

[CHR23]: Local Verification of History ?,? History(?,?) is unique given ? and ?. History(?,?) is the only string passing all ?(? ??) local checks below: For all ? ?? if and only if ? < ? ? For all? < ? ?(??) = (? ??)AND ? ? (? ??) for all? < ?? ?? ? ?? ?? For ? = ? ? ? (? ??) for all? 0,1? ? ?? (English version) Check that ?? = Invert?? ?? =

[CHR23]: The Starting Point Input: Circuit ?: 0,1? 0,12?; ? = 2? 22?. ? is set to the concatenation of all 2?-bit strings in lexicographical order. Fact: Korten(?,?) solves range avoidance for ? in 2?(?) time. ?7 Invert? (?5 ?6) ?5 ?6 Invert? (?1 ?2) Invert? (?3 ?4) Must fail on this level ?1 ?2 ?3 ?4 Invert? (?1 ?(2)) Invert? (?3 ?(4)) Invert? (?5 ?(6)) Invert? (?7 ?(8)) ?(1) ?(2) ?(3) ?(4) ?(5) ?(6) ?(7) ?(8) ? = ?(1) ?(2) ?(7) ?(8)

Single-valued F2P Algorithm: Reminder A single-valued F 2P algorithm ? is given by a deterministic poly(?)-time algorithm ? ?,?,?,? ; we assume ? = ?; ? , ? , ? poly(?). We say ?(?)outputs?, if ? is the unique string such that ? ?? ?,?,?,? = 1. Intuitions: ? is a proof for ? ? = ? . Each ? corresponds to a condition that ? must satisfy. ? is a verifierthat checks exponentially many conditions (for each ?) on the proof ?; accept only if all of them pass.

[CHR23]: The Starting Point Consider Circuit ??: 0,1? 0,12?; ?? = 2? 22?. ?? is set to the concatenation of all 2?-bit strings in lexicographical order. Suppose has ?100-size circuit Let = History(?,??); = 2?(?). Korten(??,??) in single-valuedF 2P Proof for Korten(??,??) = ? ? = ? ; ? is an ?100-size circuit, ? : last-node index in ??(? ) ??(? ) is supposed to be History(??,??) The verifier ?(??,?,?,?) (Using ?) check that ??(? ) satisfies all local checks on History(?,?). check that ? is the values on the children of node ?? .

[CHR23]: Supposehas?100-size circuit Proof for Korten(??,??) = ? ? = ? ; ? is an ?100-size circuit, ? : last-node index in ??(? ) ??(? ) is supposed to be History(??,??) The verifier ?(??,?,?,?) (Using ?) check that ??(? ) satisfies all local checks on History(?,?). check that ? is the values on the children of node ?? . ? runs in poly(?) time, since each local check only needs to read ?(?) bits from ??(? ) If ??(? ) passes all local checks, then ?? ? = History(?,?), so the values on the children of node ?? is Korten(??,??)!

[CHR23]: When has NO?100-size circuit = History(?,??) If? has no ( ? ?)-size circuits, then Korten(?,?) finds a non-output of ?. Let ? = ?50. ??: 0,1? 0,12? be a circuit of size ?(?). Korten( ,??) is a 2?(?)-time algorithm that solves Range Avoidance for ??. 2?= 2?1/50. Sub-exponential time now! [CHR 23]: perform a sophisticated case-analysis (the iterative win-win ) that gradually improve the running time until it becomes polynomial (not the focus of this talk)

Key Idea from [Li23] Why do a Win-Win if you can JUST WIN?

The Key Idea from [Li23] [Li 23] By modifying Korten ?,??, History ?,??always has a small circuit. Therefore, the starting point always work!

Korten(?,?) (in BFS order) from bottom (leaves) to top (root), and from left to right, try to fill in each intermediate node using Invert?; stop if get . ?7 Invert? (?5 ?6) ?5 ?6 Invert? (?1 ?2) Invert? (?3 ?4) ?1 ?2 ?3 ?4 Invert? (?1 ?(2)) Invert? (?3 ?(4)) Invert? (?5 ?(6)) Invert? (?7 ?(8)) ?(1) ?(2) ?(3) ?(4) ?(5) ?(6) ?(7) ?(8) ? = ?(1) ?(2) ?(7) ?(8)

Korten(?,?) (in DFS order) from left to right, try to fill in each intermediate node usingInvert?; also try to fill in a node immediately after its two children are filled; stop if get . ?15 Invert? (?7 ?14) ?7 ?14 Invert? (?3 ?6) Invert? (?10 ?13) ?3 ?6 ?10 ?13 Invert? (?8 ?9) Invert? (?4 ?5) Invert? (?1 ?2) Invert? (?11 ?12) ?1 ?2 ?4 ?5 ?8 ?9 ?11 ?12

Korten(?,?) in DFS order from left to right, try to fill in each intermediate node usingInvert?; also try to fill in a node immediately after its two children are filled; stop if get . History ?,? valuesof all nodes in the end + index of last node ?7 ?3 ?6 ?10 ?1 ?2 ?4 ?5 ?8 ?9 11 ?11 12 ?12

Input: Circuit ??: 0,1? 0,12?; ?? = 2? 22?. ? is set to the concatenation of all 2?-bit strings in lexicographical order. Lemma History(?,?) always has a small circuit. 7 ?7 ?3 ?6 10 ?10 3 6 ?1 ?2 ?4 ?5 ?8 ?9 11 ?11 12 ?12 1 2 4 5 8 9 Proof by picture: storing all the red blocks gives a poly(?,|?|)-size circuit for History(?,?)

Local Verification of History ?,? in DFS order History(?,?) is unique given ? and ?. History(?,?) is the only string passing all ?(? ??) local checks below: They are local since each check only read ?(?) bits from the history For all ? ?? if and only if ? < ? ? For all? < ? ?(??) = (? ??)AND ? ? (? ??) for all? < ?? ?? ? ?? ?? For ? = ? ? ? (? ??) for all? 0,1? ? ??

Open Questions Can we prove maximum circuit lower bounds for MAEXP, AMEXP, or PPEXP? Can we prove almost-everywhere lower bounds for MA, AM, or PP? Any chance of proving non-trivial circuit lower bounds for ENP using range avoidance?

Thanks!