The topic
What should a basic graduate complexity course, whose audience is mostly
nontheorists (say 15 nontheorists, 20 theorists) have in it
has been the subject of a
a prior blog.
This question is relevant to many people since such courses
are common.
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 nontheorists 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 lessdepends 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.

2party 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 ChandraFurstLipton 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 2party (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

Posted By GASARCH to
Computational Complexity at 8/26/2008 01:03:00 PM