Open Collections

Description

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$.