Log-rank conjecture Not only interesting on its own,but also important because of numerous applications. to prove lower bounds. Ouestion:How to lower bound communication complexity itself? y Communication matrix X→ F(x,y) ME [F(x,y)x: 5Log-rank conjecture • Not only interesting on its own, but also important because of numerous applications. – to prove lower bounds. • Question: How to lower bound communication complexity itself? • Communication matrix 𝑀𝐹 ≝ 𝐹 𝑥, 𝑦 𝑥,𝑦: 5 𝑥 → 𝑦 ↓ 𝐹(𝑥, 𝑦)