1 of 41

New Circuit Lower Bounds via Solving Range Avoidance

Lijie Chen

UC Berkeley

Hanlin Ren

University of Oxford

Shuichi Hirahara

National Institute of Informatics

Zeyong Li

National University of Singapore

https://eccc.weizmann.ac.il/report/2023/144/

https://eccc.weizmann.ac.il/report/2023/156/

2 of 41

Today’s 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]�

3 of 41

Motivation: Exponential Circuit Lower Bounds

 

 

 

4 of 41

Motivation: Exponential Circuit Lower Bounds

 

Exponential Circuit Lower Bounds are Important

 

5 of 41

Exponential Circuit Lower Bounds: What’s Known

 

These are all we knew before 2023

 

6 of 41

Complexity Theory 201

​

​

​

​

​

​

​

​

​

​

 

The Polynomial Hierarchy

​

​

​

​

​

​

​

​

​

​

 

The Exponential Hierarchy

7 of 41

(Finally) New Results

 

 

 

8 of 41

Today’s 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]�

9 of 41

Range Avoidance

  •  

 

 

 

 

 

A non-output

10 of 41

 

  •  

11 of 41

Results

 

 

 

12 of 41

Circuit Lower Bounds from Range Avoidance

  •  

 

13 of 41

Corollary: Zero-error Pseudo-deterministic Algorithm for Range Avoidance

 

[CHR’23] got an infinitely-often algorithm, improved to almost-everywhere [Li’23].

 

14 of 41

Corollary: Explicit Construction

 

 

15 of 41

Today’s 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]�

16 of 41

Some Intuition

  •  

17 of 41

 

  •  

18 of 41

  •  

 

 

 

 

 

 

 

 

 

 

19 of 41

  •  

1

2

3

4

5

6

7

 

 

 

 

 

 

 

 

 

 

20 of 41

  •  

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

21 of 41

  •  

 

 

 

 

 

 

 

 

 

 

 

 

22 of 41

  •  

Using a hard truth-table to solve a derandomization task.

 

 

23 of 41

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

24 of 41

 

 

 

25 of 41

 

 

 

 

 

26 of 41

 

 

 

 

 

 

 

 

 

27 of 41

 

 

 

 

 

 

 

 

 

 

 

 

 

28 of 41

[CHR’23]: The Starting Point

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Must fail on this level

29 of 41

 

  •  

30 of 41

[CHR’23]: Iterative Win-Win, Case I

 

 

 

 

 

 

31 of 41

[CHR’23]: Iterative Win-Win, Case I

 

 

 

 

32 of 41

[CHR’23]: Iterative Win-Win, Case II

 

 

 

 

 

 

 

Or…do we really have to?

33 of 41

Key Idea from [Li’23]

Why do a Win-Win if �you can JUST WIN?

34 of 41

The Key Idea from [Li’23]

 

35 of 41

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

36 of 41

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

37 of 41

11

12

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

38 of 41

1

2

4

5

8

9

11

12

3

6

10

 

7

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

39 of 41

 

 

 

 

 

 

 

 

 

 

 

 

 

40 of 41

Open Questions

 

41 of 41

Thanks!