1 of 35

BOUNDED-DEGREE HDXS��(FOR THE WORKING COMPUTER SCIENTIST)

YOTAM DIKSTEIN (IAS)

STOC 2025

HIGH DIMENSIONAL EXPANDER WORKSHOP

2 of 35

RECAP HDXS

  •  

3 of 35

LINKS

  •  

 

 

 

 

 

 

 

 

 

 

 

 

 

4 of 35

HIGH DIMENSIONAL EXPANDERS

  •  

5 of 35

BOUNDED DEGREE COMPLEXES

  •  

 

6 of 35

WHY WE CARE?

  • Short high-error PCPs [Bafna, Minzer, Vyas, Yun]
  • Derandomizing property tests (agreement testing) [Dinur, Kaufman], [D, Dinur],[Bafna, Minzer]…
  • Error correcting codes [Dinur, Livni-Navon, Harsha, Kaufman, Ta-Shma], [Dinur, Liu, Zhang], [D, Hopkins]
  • Other expander primitives (Lossless expanders, Samplers, Double samplers) [Hsieh, Lin, Mohanty, O'Donnell, Zhang], [D, Hopkins], [Dinur, Livni-Navon, Harsha, Kaufman, Ta-Shma],

7 of 35

HARD TO CONSTRUCT

  • Constructing bounded-degree expander graphs – well understood.
    • Algebraic, Random, elementary (combinatorial).
  • Constructing bounded-degree HDXs – difficult.
    • Only algebraic methods known to work.
  • Open: is there a combinatorial/randomized construction of bounded degree HDX?
    • Prior work: [Chapman, Lineal, Peled], [Liu, Mohanty, Yang], [Konlon], [D], [Liu, Mohanty, Schramm, Yang], [Golowich], [Ben Yaacov, D, Maor], [D, Liu, Wigderson]…

8 of 35

AGENDA

  • Spherical building - simple construction (degree unbounded).
  • Quotients of Bruhat-Tits buildings
    • Links of vertices – spherical buildings!
  • Coset complexes

9 of 35

 

  •  
  •  

10 of 35

 

  •  

 

 

 

 

 

 

 

 

11 of 35

 

  •  

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

12 of 35

 

  •  

 

 

 

 

 

13 of 35

 

  •  

 

 

 

 

14 of 35

 

  •  

 

 

 

 

 

15 of 35

 

  •  

16 of 35

 

  •  

17 of 35

QUOTIENTS OF THE BUILDING

  •  

18 of 35

QUOTIENTS UPSHOT

  •  

19 of 35

AND NOW FOR SOMETHING COMPLETELY DIFFERENT…

20 of 35

COSET COMPLEXES

  • A second type of complexes – introduced by Kaufman-Oppenheim.
    • More variants analyzed by [O’donnell,Pratt],[de Peralta, Valentiner-Branth]
  • Based on more elementary group theory.
  • We will show the construction for 2-dimensional Kaufmann-Oppenheim complex.

21 of 35

HIGH LEVEL IDEA

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

22 of 35

HIGH LEVEL IDEA

  •  

23 of 35

THE SET PARTITIONED

  •  

24 of 35

PARTITION SUBGROUPS

  •  

25 of 35

THE PARTITIONS

  •  

26 of 35

THE COSET COMPLEX

  •  

27 of 35

SIZE AND NEIGHBORHOODS

  •  

 

28 of 35

 

  •  

 

 

 

 

29 of 35

COROLLARY: CONNECTIVITY

  •  

30 of 35

 

  •  

31 of 35

 

  •  

32 of 35

ELEMENTARY DESCRIPTION OF THE LINK [HARSHA, SAPTHARISHI]

  •  

33 of 35

TO CONCLUDE

  •  

34 of 35

WHAT ELSE IS THERE?

  • More Sophisticated properties.
    • Regular complexes [Freidgut, Iluz]
    • Coboundary expanders [Chapman, Lubotzky], [D, Dinur, Lubotzky], [Bafna, Lifshitz, Minzer], [O’Donnell, Singer]
    • Ramanujan Complexes [Lubotzky, Samuels, Vishne]
  • Beyond Simplicial complexes:
    • Cubical complexes [Dinur, Evra, Livne, Lubotzky, Mozes], [Pantaleev, Kalachev], [Hsieh, Lubotzky, Mohanty, Reiner, Zhang], [Golowich, Lin]
    • Vector space high dimensional expanders [Golowich], [D, Liu, Wigderson]

35 of 35

THANK YOU FOR LISTENING!