Log-rank conjecture Not only interesting on its own,but also important because of numerous applications to prove lower bounds. 0 Question:How to lower bound communication complexity itself? y Communication matrix X→ F(x,y) ME [F(x,y)]x.y: 10Log-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 𝑀𝐹 ≝ 𝐹 𝑥, 𝑦 𝑥,𝑦: 10 𝑥 → 𝑦 ↓ 𝐹(𝑥, 𝑦)