External Program 3: Synergies of combinatorics and theoretical computer science

August 19 – September 13

Recently, there have been several breakthroughs on long-standing open problems in combinatorics and theoretical computer science, resulting from such synergistic connections between these two areas. This month-long program is focusing on the connections and unifying themes between combinatorics and theoretical computer science. It includes a one-week workshop with leading experts from both areas, a one-week summer school for graduate students and post-docs as well as the possibility of long-term research stays for the entire one-month program.

Website : https://bernoulli.epfl.ch/comb2024/

Recordings :

Monday 19

Rico Zenklusen: Random-Assignment Matroid Secretary Without Knowing the Matroid
Matthew Kwan: Resolution of the Quadratic Littlewood-Offord problem
Vera Traub: The Bidirected Cut Relaxation for Steiner Tree has Integrality Gap Smaller than 2

Sorrachai Yingchareonthawornchai: How to Search and Sort using Forbidden 0-1 Matrix Theory – Slides
Alexey Gordeev: Combinatorial Nullstellensatz and the Erdős box problem – Slides
Sophie Huiberts: Short Stories about Linear Programming – Slides

Tuesday 20

Nati Linial: The Rank-Ramsey Problem and the Log-Rank Conjecture – Slides
Rob Morris: Geometric conjectures and Ramsey numbers

Pravesh Kothari: Spectral Refutation via Kikuchi Matrices and Applications
Mehtaab Sawhney: Improved Bounds for Szemerédi’s Theorem
Venkatesan Guruswami: Combinatorial challenges in coding theory: A sampler

Wednesday 21

Benny Sudakov: SDP, MaxCut, discrepancy and log-rank-conjecture
Hannaneh Akrami: Epistemic EFX Allocations Exist for Monotone Valuations
Zixuan Xu: Essential covers of the hypercube requires many hyperplanes

Sammy Luo: A New Polynomial Method in Additive Combinatorics – Slides
Maya Sankar: On the Generalized Ramsey–Turan Density of Cliques

Thursday 22