New advances on the log rank conjecture

Speaker: Shachar Lovett, Assistant Professor, CSE department, UC San Diego

Date: Tuesday, September 16, 2014

Time: 4:15 PM to 5:15 PM Note: all times are in the Eastern Time Zone

Refreshments: 4:00 PM

Public: Yes

Location: G449 (Patil/Kiva)

Event Type:

Room Description:

Host: Dana Moshkovitz

Contact: Deborah Lehto, 617.324.7303,

Relevant URL:

Speaker URL: None

Speaker Photo:

Reminders to:,

Reminder Subject: TALK: TOC Seminar, Shachar Lovett, Assistant Professor, CSE department, UC San Diego


The log rank conjecture is one of the fundamental open problems in communication complexity. It speculates that the simplest lower bound for deterministic protocols, the log-rank lower bound, is in fact tight up to polynomial factors. That is, for a boolean function f(x,y), if its associated matrix M_{x,y}=f(x,y) has rank r (over the reals), then there exists a deterministic protocol computing f which uses only poly-log(r) bits of communication. This problem also has several other equivalent formulations: the relation between chromatic number and rank of graphs, and the relation between rank and non-negative rank for boolean matrices.

A simple argument shows that there is always a deterministic protocol which uses r bits of communication, and until recently the best known bounds improved on this only by a constant factor. Recently, two new approaches allowed for improved bounds. The first (joint with Eli Ben-Sasson and Noga Ron-Zewi) related it to a central conjecture in additive number theory, and showed that if it holds then there are protocols which use O(r / log(r)) bits. The second approach is analytical and gives an (unconditional) improved upper bound of O(\sqrt{r} \log(r)) bits of communication.

In the talk I will give the necessary background on the problem, explain the two approaches, sketch the proofs, and discuss intriguing connections to other central problems in complexity theory, such as matrix rigidity and two-source extractors.

Research Areas:

Impact Areas:

See other events that are part of the Theory of Computation Colloquium - 2014.

Created by Deborah Goodwin Email at Tuesday, July 29, 2014 at 11:30 AM.