Skip to main content
You are not a member of this wiki.
Join now
Dismiss
guest
Help

Sign In
COMS 4995: Introduction to Communication Complexity
Home
guest

Help

Sign In
COMS 4995: Introduction to Communication Complexity
Wiki Home
Recent Changes
Pages and Files
Members
Favorites
20
All Pages
20
Home
Announcements
Discussion
Lectures
Links
Add
Add "All Pages"
Done
Lectures
Edit
0
44
…
0
Tags
No tags
Notify
RSS
Backlinks
Source
Print
Export (PDF)
Date
Topic
Readings
Exercises
Notes
Sep 7
Introduction; Class overview;
Examples of communication protocols;
and the twoparty deterministic model
CC Book Chapter 1
Chapter 13 of
Computational Complexity
A Modern Approach, by Arora and Barak
Some complexity questions related to distributive
computing
, by Yao
Exercise 1
Note 1
by Xiaorui Sun
Sep 12
Fooling sets and Rectangle size
Rank lower bound
CC Book Chapter 1
Chapter 13 of
Computational Complexity
A Modern Approach, by Arora and Barak
Exercise 2
Note 2
by Igor Carboni Oliveira
Sep 14
Covers and nondeterminism
Determinism versus nondeterminism
CC Book Chapter 2
Exercise 3
Note 3
by Igor Carboni Oliveira
Sep 19
Communication complexity of relations
KarchmerWigderson games
Khrapchenko's bound
CC Book Section 5.1, 10.1 and 10.2
Note 4
by Timothy Sun
Sep 21
Lower bound for the FORK relation
CC Book Section 5.3
Exercise 4
Sep 26
Randomized communication complexity
Public coin vs Private coin
Distributional complexity
CC Book Section 3.1, 3.3 and 3.4
Note
on the minimax theorem
Lecture Notes on Linear Duality
By Trevisan
Exercise 5
Sep 28
The discrepancy method
Lower bound for IP
CC Book Section 3.5
Exercise 6
Oct 3
Lower bound for Disjointness with
a product distribution
A publiccoin protocol for Disjointness
with sets of size k
Complexity Classes in Communication Complexity
Theory
, by Babai, Frankl and Simon.
The Randomized Communication Complexity of Set
Disjointness
, by Hastad and Wigderson
Oct 5
Linear lower bound for Disjointness
CC Book Section 3.4 and 4.6
Oct 10
Linear lower bound for Disjointness
Direct sum for nondeterministic and
deterministic communication complexity
CC Book Section 4.6 and 4.1
Exercise 7
Oct 13
Multiparty communication complexity
Cylinder intersection
CC Book Section 6.1 and 6.2
Oct 17
Discrepancy lower bound and GIP
CC Book Section 6.4
Oct 19
Timespace tradeoffs for Turing machines
Variable partition models
Widthlength tradeoffs for branching programs
CC Book Chapter 7 and Chapter 12
Exercise 8
Oct 31
Widthlength tradeoffs (cont.)
VLSI lower bounds
Application in combinatorial auctions
CC Book Section 8.3
Algorithmic Game Theory
Section 11.1 and 11.6
Exercise 9
Nov 2
Lower bounds for streaming algorithms
The space complexity of approximating the
frequency moments
, by Alon, Matias and Szegedy
Lower bounds on streaming algorithms for
approximating the length of the longest
increasing subsequence
, by Gal and Gopalan
Javascript Required
You need to enable Javascript in your browser to edit pages.
help on how to format text
Turn off "Getting Started"
Home
...
Loading...
Date
Topic
Readings
Exercises
Notes
Examples of communication protocols;
and the twoparty deterministic model
Chapter 13 of Computational Complexity
A Modern Approach, by Arora and Barak
Some complexity questions related to distributive
computing, by Yao
by Xiaorui Sun
Rank lower bound
Chapter 13 of Computational Complexity
A Modern Approach, by Arora and Barak
by Igor Carboni Oliveira
Determinism versus nondeterminism
by Igor Carboni Oliveira
KarchmerWigderson games
Khrapchenko's bound
by Timothy Sun
Public coin vs Private coin
Distributional complexity
Note on the minimax theorem
Lecture Notes on Linear Duality By Trevisan
Lower bound for IP
a product distribution
A publiccoin protocol for Disjointness
with sets of size k
Theory, by Babai, Frankl and Simon.
The Randomized Communication Complexity of Set
Disjointness, by Hastad and Wigderson
Direct sum for nondeterministic and
deterministic communication complexity
Cylinder intersection
Variable partition models
Widthlength tradeoffs for branching programs
VLSI lower bounds
Application in combinatorial auctions
Algorithmic Game Theory Section 11.1 and 11.6
frequency moments, by Alon, Matias and Szegedy
Lower bounds on streaming algorithms for
approximating the length of the longest
increasing subsequence, by Gal and Gopalan