- Series
- ACO Colloquium
- Time
- Friday, November 13, 2015 - 3:05pm for 1 hour (actually 50 minutes)
- Location
- Skiles 005
- Speaker
- Noga Alon – Tel Aviv University and IAS, Princeton
- Organizer
- Robin Thomas
Please Note: Refreshments will be served in the atrium after the talk.
The sign-rank of a real matrix A with no 0 entries is the
minimum rank of a matrix B so that A_{ij}B_{ij} >0 for all i,j. The
study of this notion combines combinatorial, algebraic, geometric
and probabilistic techniques with tools from real algebraic geometry,
and is related to questions in Communication Complexity, Computational
Learning and Asymptotic Enumeration. I will discuss the topic and describe
its background, several recent results from joint work with Moran and
Yehudayoff, and some intriguing open problems.