Program for the Workshop on Algorithms in
Communication Complexity, Property Testing and
Combinatorics
Also is
available as pdf file.
|
Time |
Title |
Speaker |
|
April
9, Saturday, Tutorials |
||
|
13:00-14:00 |
Registration
and coffee |
|
|
14:00-15:30 |
Locality
in Coding Theory (1) |
Madhu
Sudan |
|
15:30-16:00 |
Coffeebreak |
|
|
16:00-17:30 |
Locality
in Coding Theory (2) |
Madhu
Sudan |
|
April
10, Sunday, Tutorials |
||
|
10:00-11:30 |
Communication
complexity (1) |
Amir
Yehudayoff |
|
11:30-12:00 |
Coffeebreak |
|
|
12:00-13:30 |
Communication
complexity (2) |
Amir
Yehudayoff |
|
13:30-15:00 |
Lunch |
|
|
15:00-16:30 |
Introduction to Property Testing |
Sofya
Raskhodnikova |
|
16:30-17:00 |
Coffeebreak |
|
|
17:00-18:30 |
Testing Graph
Properties |
Artur Czumaj |
|
April
11, Monday, Day 1 |
||
|
10:00-11:00 |
Communication Amid Uncertainty |
Madhu Sudan |
|
11:00-11:30 |
Coffeebreak |
|
|
11:30-12:10 |
Balanced
Allocation on Graphs: A Random Walk Approach |
Ali
Pourmiri |
|
12:10-12:50 |
Towards
Constant Size Graphs That Preserve the Local Structure of Large Graphs |
Hendrik Fichtenberger |
|
12:50-14:20 |
Lunch |
|
|
14:20-15:20 |
Kolmogorov
width of discrete linear spaces: an approach to matrix rigidity |
Sergey
Yekhanin |
|
15:30-16:10 |
How
Limited Interaction Hinders Real Communication (and What It Means for Proof
and Circuit Complexity) |
Jakob Nordstršm |
|
16:10-16:40 |
Coffeebreak |
|
|
16:40-17:40 |
Geometric
stability via information theory |
Amir Yehudayoff |
|
17:50-18:30 |
On
Slepian-Wolf theorem with interaction |
Alexander Kozachinsky |
|
April
12, Tuesday, Day 2 |
||
|
10:00-11:00 |
Public-setup computational integrity from quasi-linear PCPs |
Eli Ben-Sasson |
|
11:00-11:30 |
Coffeebreak |
|
|
11:30-12:10 |
On the
Space Complexity of Computing Degeneracy in Streaming Model |
Meng-Tsung
Tsai |
|
12:10-12:50 |
k-Vertex Graph
Connectivity Problem in the Streaming Settings |
Meng
Li |
|
12:50-14:20 |
Lunch |
|
|
14:20-15:20 |
Approximate
Nonnegative Rank is Equivalent to the Smooth Rectangle Bound |
Amir
Shpilka |
|
15:30-16:10 |
Tribes
is hard in the message passing model |
Sagnik Mukhopadhyay |
|
16:10-16:40 |
Coffeebreak |
|
|
16:40-17:20 |
Streaming
Property Testing of Visibly Push-Down Languages |
Nathana‘l FranŤois |
|
17:20-18:00 |
Fair Hierarchical Resource Scheduling |
Andrei Kashin |
|
April
13, Wednesday, Day 3 |
||
|
10:00-11:00 |
Testing clustering in graphs |
Artur Czumaj |
|
11:00-11:30 |
Coffeebreak |
|
|
11:30-12:10 |
Unit-distance
graph recognition complexity |
Mikhail
Tikhomirov |
|
12:10-12:50 |
Independence
numbers of random subgraphs of some distance graphs |
Andrei Raigorodskii |
|
12:50-14:20 |
Lunch |
|
|
14:20-15:20 |
Fast
sample-based testers for visual properties |
Sofya
Raskhodnikova |
|
15:20-15:50 |
Coffeebreak |
|
|
15:50-16:30 |
The
Role of Adaptivity in Testing Visual Properties |
Meiram
Murzabulatov |
|
16:30-17:10 |
Relating Two
Property Testing Models for Bounded Degree Directed Graphs |
Pan
Peng |