Computer Science/Discrete Mathematics Seminar II | |

Topic: | New Results on Projections |

Speaker: | Guy Moshkovitz |

Affiliation: | Member, School of Mathematics |

Date: | Tuesday, January 22 |

Time/Room: | 10:30am - 12:30pm/Simonyi Hall 101 |

Video Link: | https://video.ias.edu/csdm/2019/0122-GuyMoshkovitz |

What is the largest number of projections onto k coordinates guaranteed in every family of m binary vectors of length n? This fundamental question is intimately connected to important topics and results in combinatorics and computer science (Turan number, Sauer-Shelah Lemma, Kahn-Kalai-Linial Theorem, and more), and is wide open for most settings of the parameters. We essentially settle the question for linear k and sub-exponential m.

Based on joint work with Noga Alon and Noam Solomon.