CS Events

Seminar

New Results on Projections

 

Download as iCal file

Wednesday, September 04, 2019, 11:00am

 

Abstract:

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

Based on joint work with Noga Alon and Noam Solomon

Speaker: Guy Moshkovitz

Location : CoRE A 301

Committee

Rutgers/DIMACS Theory of Computing

Event Type: Seminar

Abstract: 

Organization

Rutgers University