81 citations · 136 across the 38 of their papers we have counts for
Showing 2014Show all
2 papers · 1 filter
cs.CC2014
A direct proof for Lovett's bound on the communication complexity of low rank matrices
Thomas Rothvoss
The log-rank conjecture in communication complexity suggests that the deterministic communication complexity of any Boolean rank-r function is bounded by polylog(r). Recently, majo…
cs.DM2014
Constructive discrepancy minimization for convex sets
Thomas Rothvoss
A classical theorem of Spencer shows that any set system with n sets and n elements admits a coloring of discrepancy O(n^1/2). Recent exciting work of Bansal, Lovett and Meka shows…