1 of 34

Hardness amplification and local list decoding via HDX

Yotam Dikstein (IAS)

​

joint with

Max Hopkins (IAS) , Russell Impagliazzo (UCSD), Toni Pitassi (Columbia)

2 of 34

Hardness in complexity

  •  

2

3 of 34

Worst and Average Case Hardness

  •  

3

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4 of 34

Hardness amplification

4

-hard

​

-hard

​

5 of 34

Amplification by repetition [Yao82, Levin85, IW97]

  •  

6 of 34

 

  • No substantial improvement in input length since [Impagliazzo, Wigderson 97’].
  • Implies fast Pseudorandom generators [Nisan, Wigderson 81’], [Chen, Tell 21’].

​

6

7 of 34

Small blow-up amplification [D, Hopkins, Impagliazzo, Pitassi]

  •  

7

-hard

For

-hard

For

8 of 34

 

  •  

8

 

 

 

 

 

 

 

 

 

 

 

9 of 34

Error Correcting Codes

 

 

 

 

 

 

 

 

 

10 of 34

Decoding

 

 

 

 

 

 

 

 

 

 

 

11 of 34

Local Decoding

  •  

11

List decoding:

Dec(w) gives a short list of close messages.

 

 

 

 

 

12 of 34

Locally List Decodable Codes

  •  

12

13 of 34

Approximately Locally List Decodable Codes

  •  

13

14 of 34

Why aLLDCs?

  •  

14

15 of 34

 

  •  

15

16 of 34

Theorem [D, Hopkins, Impagliazzo, Pitassi]

  •  

16

Code

Rate

Queries

Locally Decodable

[IW 97’], [IJKW 08’]

​

​

YES

[KRSW 18’]

​

​

NO

17 of 34

Direct Product code

  •  

17

 

 

 

 

 

 

 

 

 

 

 

18 of 34

Direct Product codes as functions

  •  

18

19 of 34

aLLDC Direct Product Codes

  •  

19

20 of 34

[Impagliazzo, Jaiswal, Kabanets, Wigderson 07’]

  •  

20

21 of 34

[IJKW] decoders:

  •  

21

 

 

 

 

 

 

 

 

 

 

Output: 0

22 of 34

Idea behind decoders

  •  

22

 

 

 

23 of 34

Key Lemma

  •  

23

 

 

 

 

 

24 of 34

Key Lemma Meaning

  •  

24

25 of 34

Our construction – Expander graphs

  •  

25

26 of 34

Large sets in Expanders

  •  

26

 

 

 

 

 

27 of 34

High dimensional expanders

  •  

27

28 of 34

Neighborhoods in an HDX

  •  

28

 

 

 

 

 

29 of 34

Our Construction

  •  

29

30 of 34

Our decoder.

  •  

30

 

 

31 of 34

Short paths

  •  

31

 

 

 

 

 

 

32 of 34

Key Lemma

  •  

32

33 of 34

 

  •  

33

 

 

 

 

 

 

 

✔

✔

🗶

✔

✔

 

34 of 34

Summary

  • We construct aLLDC with high rate and small query complexity.
  • We get hardness amplification with almost no input blow-up.

​

Questions?

34