BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Traces of Hypergraphs Alon, Noga


What is the largest number of distinct projections onto $k$ coordinates guaranteed in every family of $m$ binary vectors of length $n$ This fundamental combinatorial question has applications in theoretical computer science, geometry, machine learning, probability and more, and is wide open for most settings of the parameters. I will briefly mention some of the history, motivation and known results, focusing on a recent asymptotic solution of the question, in joint work with Moshkovitz and Solomon, for linear $k$ and sub-exponential $m$.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International