Signrank and its applications in combinatorics and complexity

Series: 
ACO Colloquium
Friday, November 13, 2015 - 15:05
1 hour (actually 50 minutes)
Location: 
Skiles 005
,  
Tel Aviv University and IAS, Princeton
Organizer: 

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.