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 Citations and Data
Attribution-NonCommercial-NoDerivatives 4.0 International