Log-rank conjecture for XOR functions Goal:D(f⊕)≤log2fl Even this special case seems very hard. ·One approach*:D(fo⊕)≤2D⊕(f). -D):Parity decision tree complexity.(DT with queries like“x1⊕x3⊕x4=?") -simulating 1 -query by 2 bits of communication. *Zhang and Shi.Theoretical Computer Science,2009.Log-rank conjecture for XOR functions • Goal: 𝐷 𝑓 ∘⊕ ≤ log2 𝑂(1) 𝑓 መ 0 . • Even this special case seems very hard. • One approach*: 𝐷 𝑓 ∘⊕ ≤ 2𝐷⊕ 𝑓 . – 𝐷⊕ 𝑓 : Parity decision tree complexity. (DT with queries like “𝑥1 ⊕ 𝑥3 ⊕ 𝑥4 =?”) – simulating 1 ⊕-query by 2 bits of communication. *. Zhang and Shi. Theoretical Computer Science, 2009