## Organizer(s) | Jeffry Kahn, Jacob D Baron, Patrick Devlin | ## Archive |

## Upcoming Talks

## Monday, February 20th |

## Pat Devlin, |

## "Proof of an entropy conjecture of Leighton and Moitra" |

Time: 2:00 PM |

Location: Hill 705 |

Abstract: Suppose F is a random (not necessarily uniform) permutation of {1, 2, ... , n} such that |Prob(F(i) < F(j)) -1/2| > epsilon for all i,j. We show that under this assumption, the entropy of F is at most (1-delta)log(n!), for some fixed delta depending only on epsilon [proving a conjecture of Leighton and Moitra]. In other words, if (for every distinct i,j) our random permutation either noticeably prefers F(i) < F(j) or prefers F(i) > F(j), then the distribution inherently carries significantly less uncertainty (or information) than the uniform distribution.
Our proof relies on a version of the regularity lemma, a combinatorial bookkeeping gadget, and a few basic probabilistic ideas. The talk should be accessible for any background, and I'll gently recall any relevant notions (e.g., entropy) as we go. Those dissatisfied with the talk will not be refunded the cost of admission, and those tremendously dissatisfied won't like my defense either.
This is from a recent paper joint with Huseyin Acan and Jeff Kahn. |

## Past Talks

## Monday, February 13th |

## Oanh Nguyen, |

## "Roots of random polynomials" |

Time: 2:00 PM |

Location: Hill 705 |

Abstract: Random polynomials, despite their simple appearance, remain a mysterious object with a large number of open questions that have attracted intensive research for many decades. In this talk, we will discuss some properties of random polynomials including universality and asymptotic normality. I will also talk about some interesting open questions.
The talk is based on joint works with Yen Do, Hoi Nguyen, and Van Vu. |

## Monday, February 6th |

## Abdul Basit, |

## "On the number of ordinary lines determined by sets in complex space" |

Time: 2:00 PM |

Location: Hill 705 |

Abstract: Consider a set of n points in R^d. The classical theorem of Sylvester-Gallai says that, if the points are not all collinear then there must be a line through exactly two of the points. We call such a line an "ordinary line". In a recent result, Green and Tao were able to give optimal linear lower bounds (roughly n/2) on the number of ordinary lines determined n non-collinear points in R^d. In this talk we will consider the analog over the complex numbers. While the Sylvester-Gallai theorem as stated above is known to be false over the field of complex numbers, it was shown by Kelly that for a set of n points in C^d, if the points don’t all lie on a 2-dimensional plane then the points must determine an ordinary line. Using techniques developed for bounding the rank of design matrices, we will show that such a point set must determine at least 3n/2 ordinary lines, except in the trivial case of n−1 of the points being contained in a 2-dimensional plane.
Joint work with Z. Dvir, S. Saraf and C. Wolf |

## Monday, January 30th |

## Rafael Oliveira, |

## "Operator Scaling: Theory & Applications, and the simplest algorithm for the linear matroid intersection problem ever designed!" |

Time: 2:00 PM |

Location: Hill 705 |

Abstract: In this talk we shall explore quantum operators, the operator scaling problem and its myriad incarnations in commutative and non-commutative algebra, computational complexity, optimization and quantum information theory. We will describe an efficient algorithm solving the operator scaling problem and all these related problems, and how its analysis combines ideas from all these areas. The problem these algorithms solve is non-convex, and we hope they will have many other applications.
As a combinatorial bonus, we will see the shortest algorithm for the linear matroid intersection problem ever designed! Joint work with Ankit Garg, Leonid Gurvits and Avi Wigderson. |

## Monday, January 23rd |

## Zeev Dvir, |

## "Rank bounds for design matrices with block entries and geometric applications" |

Time: 2:00 PM |

Location: Hill 705 |

Abstract: Design matrices are sparse matrices in which the supports of different columns intersect in a few positions. Such matrices come up naturally when studying problems involving point sets with many collinear triples. In this work we consider design matrices with block (or matrix) entries. Our main result is a lower bound on the rank of such matrices, extending the bounds proven in [BDWY12, DSW14] for the scalar case. As a result we obtain several applications in combinatorial geometry. The main application involves extending the notion of combinatorial rigidity from pairwise distance constraints to three wise collinearities.
The main technical tool in the proof of the rank bound is an extension of the technique of matrix scaling to the setting of block matrices. We generalize the definition of doubly stochastic matrices to matrices with block entries and derive sufficient conditions for a doubly stochastic scaling to exist.
Joint work with Ankit Garg, Rafael Oliveira and Jozsef Solymosi |