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
How is a 15:20 nontheorist-to-theorist ratio "mostly non-theorists"? Is there some kind of weighting factor that I missed?
ReplyDeleteI think it is important to motivate communication complexity to non-theorists via some applications. Natural lower bound questions such as for data structures, VLSO and streaming algorithms are ideal. There are several neat results to pick from.
ReplyDelete15:20 ratio: Pardon, I
ReplyDeletemean 15 OUT OF 20 of the
students are non-theorists.
15 NON theorists,
5 theorists.
And YES, I agree that
applications to data structures and VLSI are good. Also VLSI was the origin of the subject.
Just curious, what are you going to do in the asymmetric communication / cell-probe regime?
ReplyDeleteHope to do lower bound on
ReplyDeletecell probe model for PRED
problem, the loglog n
lower bound. Will work out
of Peter Bro Miltersen's
survey and paper by
Miltersen, Nisan, Safra,
Wigderson. Not sure I'll
get that far.
The rank lower bound takes almost no time to prove and implies the fooling set lower bounds (which makes a nice guided exercise). Why would you skip it?
ReplyDeleteThe biggest question if you are going to deal with the applications to MATCHING and streaming is that you will have to confront Set Disjointness for randomized algorithms. How you deal with that seems to be the biggest question. Do you just state the lower bound without proof? If you go through a proof, which one do you give? All the proofs have some significant subtlety that would be tough for this audience.
Hmm, Miltersen's survey is rather dated now, and the bounds that you get by that old round elimination lemma are not very nice.
ReplyDeleteWith the obvious personal bias, I think that if you want to teach a single topic at the intersection of cell probe and communication complexity, it should be my (Data) Structures paper. There are no complicated technical details, and the results are for very interesting problems (in the cell-probe world).
If you want round elimination, you can presumably teach the better version of Sen and Venkatesh [JCSS'08]. Or better yet, I have a self-contained and very clean proof (via deterministic round elimination). That will show up shortly in my PhD thesis.
Lucky you, getting to teach such a lovely topic!
ReplyDeleteFor the audience you describe, I would emphasize applications and leave out topics for which you can't get to applications within the course (e.g., nondeterministic communication). I would also definitely do the rank lower bound, which is just too cool to omit. Side note: non-theorists tend to relate better to the concept of "rank" than anything combinatorial like "fooling set".
It would be nice to get to the information theoretic methods that have arisen since Kushilevitz-Nisan (yes, my personal bias is showing)... it will take a little background-building, but it does give you the most intuitive proof of the randomized DISJOINTNESS lower bound, plus various round elimination lemmas.
-- Amit C
I would encourage you to explicitly devote a portion of the class to a more "information theoretic" view of the world. Shannon theory and entropy are the foundation of what most of the "rest of the world" thinks about when they hear about communication complexity, and there are certainly connections (explicit and implicit) between that view of the subject and ours that would be worth covering -- particularly if there are non-theorists in the audience, who are arguably more likely to see that side of the subject in the future.
ReplyDeleteCommunication complexity is a tool, a bit like calculus; so it's important to illustrate its applications in a variety of contexts:
ReplyDelete() VLSI
() Karchmer-Wigderson theorem (at least the easy direction, which makes cc a tool to show circuit depth lower bounds, one of the most important questions in complexity)
() data structure lower bounds
() data stream algorithm lower bounds
As for the fundamentals of cc:
() "the fundamental theorem of cc", the set of all input pairs that have the same transcript form a combinatorial rectangle (both proofs)
() fooling set
() rank method (this is just so pretty and low mess)
() I wouldn't mention "nondeterministic cc" but will include zero-covers and one-covers, and the theorem that Dcc(f) <= N0(f) N1(f) [if memory serves me right]
() Randomized CC is interesting only to the extent that it yields surprising upper bounds; randomized cc lower bounds are motivated by data stream algorithm problems (more on this later in the list).
() One-way and simultaneous models (these correspond loosely to streaming and sketching algorithms)
() The equivalence of public and private coin protocols (Newman's theorem) except in the simultaneous model (EQUALITY being the counterexample - simple proof due to Babai and Kimmel)
() Yao's minimax principle (if they haven't seen it elsewhere, this is a good opportunity to show at least the easy direction of this), and the equivalence of randomized and distributional cc -- randomized one-way cc lower bound for the indexing problem
() The notion of a reduction in cc lower bounds, and a lower bound, via reduction from indexing, for the problem of distinguishing Hamming distance < n/2 from Hamming distance > n/2 + sqrt(n) [this yields a nice 1/epsilon^2 lower bound for epsilon-approximation of the number of distinct elements in a data stream]
() Patrascu's lower bound on asymmetric set disjointness (detereministic version only - the randomized version is messy and doesn't add any intuitive value, esp. to non-theorists)
() Schulman's theorem on coding for communication (a stretch topic)
() Mention frontiers of the field: the work of Pranab Sen, Jaikumar Radhakrishnan, Rahul Jain, et al. on "message compression" as a form of producing "informationally-optimal protocols" (a form of Shannon's source-coding theorem for communication complexity, in my imprecise and intuitive way of thinking)
Some of the classics that I would leave out, but only because they are not that important to a general audience:
-- the result of Kalyanasundaram-Schnitger on the randomized cc of set disjointness
-- the discrepancy lower bound for inner product
-- Number-on-the-Forehead, Number-on-the-Rear, etc., including recent breakthroughs and connections to pseudorandom generators
It's fun to suggest what someone else should teach, so here's my 2-cents...
ReplyDeleteIn a theory course for non-theoreticians I prefer to concentrate on concepts, applications, and basic techniques, and avoid proofs with technical difficulty. In CC this can be done nicely I think:
(1) inside the CC model: several LB tecniques (I see no reason to leave out the easy rank LB), nondeterminism, randomness, and as you suggest the analogs of P!=NP, P!=RP, P=NP^coNP.
(2) applications:
a) Time-space for Turing-Machines
b) VLSI [using best-partition CC model]
c) streaming/sketching [using 1-way/simultaneous CC]
d) data structures [using asymmetric CC, and the "richness technique" rather than the hard round-eliminaion one, following the "modern" approach of Mihai.
e)My personal bias: economic applicaion for combinatorial auctions and relation to prices [a very easy writeup is in http://www.cs.huji.ac.il/~noam/NisanSegalExpo.ps]
I would give up both Karchmer-Wigderson and multiparty models due to the tecnical hardness of getting interesting results there. I think that the randomized LB for DISJ can be completely skipped this way, and if its wanted/needed then the sqrt(n) LB of BFS which is easy can be given.
I believe that this would give a very rich course without a single proof that has more than a single technical step in it.
THANKS for all of your advice,
ReplyDeleteand THANKS to MiP-- I
will look up some of the
references you point to,
including your own work.
bill g.
Bill,
ReplyDeleteGreat comments--I especially like Nisan's course outline--so very little to add, other than this is a great course to teach!
One small comment: VLSI was NOT the origin of cc. It was an application of the theory.
The first paper was one by Abelson (FOCS 1978)--probably inspired somewhat by Minsky's comments on "Global vs. local in computation" and perhaps by Gentleman's work on distributed algorithms for Numerical Linear Algebra problems. Yao's paper was next: applications to VLSI followed.