Main result There are three lower bound techniques known forQ1(⑤. Nayak'99:Partition Tree Aaronson'05:Trace Distance The two-way complexity Q(f) [Thm]All of these lower bounds can be arbitrarily weak. Actually,random functions have Q(f)=(n),but the first two lower bounds only give O(1).Main result • There are three lower bound techniques known for Q1 (f). – Nayak’99: Partition Tree – Aaronson’05: Trace Distance – The two-way complexity Q(f) • [Thm] All of these lower bounds can be arbitrarily weak. • Actually, random functions have Q(f) = Ω(n), but the first two lower bounds only give O(1)