Today I ask a question that may be of less relevance. Univ of MD's requirements are such that I will be teaching a course on Communication Complexity that non-theorists will be taking. The Complexity Theory course is not a prereq. I will be using the book Communication Complexity by Kushilevits and Nisan which will add 10 to their book sales this year (maybe less-depends on the used book marked). What should be in such a course? Here is what I am planning, though I am flexible and your answers may influence me.
- Overall themes: (1) Given a problem, what is its Comm. Comp.? (2) Applications to other models of computation.
2-party Comm Comp
- Deterministic: Rectangles, foolings sets. SAMPLE : EQ requires n+1 bits. Not hard to prove, but interesting that, unlike complexity theory, we can actually get real results here. Will look at other functions as well like IP (Inner Product), Not sure if I will do Rank lower bound. Powerful, but somewhat mysterious.
- Nondeterministic: covers, relation to deterministic. SAMPLE: NE in N(log n), so in this setting P\ne NP. Also, in this setting NP\cap coNP = P. (P is polylog bits)
- Randomized: private coin and public coin. SAMPLE: Randomized provably more powerful than deterministic, as EQ shows.
- Relation to Circuits: Lower bounds on monotone circuits for MATCHING and other problems.
- Upper and lower bounds on streaming algorithms
- Upper and lower bounds on the Cell Probe Model
Multiparty Comp Complexity
- Multiparty Comp Complexity and Branching Programs and Ramsey Theory Go over Chandra-Furst-Lipton paper on this topic, but fill in all details and background (I'll have my own notes on this.) This is alot of material: Multiparty stuff, Ramsey Theory, Branching Programs. Will also do lower bounds on BP's that use 2-party (these results may imply the results with multiparty, but need to look at it more carefully). Will also do some other material on Branching Programs (might do Dave Barringtons result that NC^1 is in BP_5, but that may take us too far afield).
- Other applications of Multiparty comp. Complexity