ACO The ACO Seminar (2020–2021)

October 15, 3:30pm, https://cmu.zoom.us/j/98951280265
Kaave Hosseini, Carnegie Mellon University
Signrank vs Discrepancy

Abstract:

Sign-rank and discrepancy are two central notions in communication complexity. The seminal work of Babai, Frankl, and Simon from 1986 initiated an active line of research that investigates the gap between these two notions. In this article, we establish the strongest possible separation by constructing a boolean matrix whose sign-rank is only $3$, and yet its discrepancy is $2^{-\Omega(n)}$. We note that every matrix of sign-rank $2$ has discrepancy $n^{-O(1)}$.

Please email Boris Bukh (bbukh ~at~ math) for a password.


Back to the ACO home page Back to the ACO Seminar schedule