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:0014:00 
Registration
and coffee 

14:0015:30 
Locality
in Coding Theory (1) 
Madhu
Sudan 
15:3016:00 
Coffeebreak 

16:0017:30 
Locality
in Coding Theory (2) 
Madhu
Sudan 
April
10, Sunday, Tutorials 

10:0011:30 
Communication
complexity (1) 
Amir
Yehudayoff 
11:3012:00 
Coffeebreak 

12:0013:30 
Communication
complexity (2) 
Amir
Yehudayoff 
13:3015:00 
Lunch 

15:0016:30 
Introduction to Property Testing 
Sofya
Raskhodnikova 
16:3017:00 
Coffeebreak 

17:0018:30 
Testing Graph
Properties 
Artur Czumaj 
April
11, Monday, Day 1 

10:0011:00 
Communication Amid Uncertainty 
Madhu Sudan 
11:0011:30 
Coffeebreak 

11:3012:10 
Balanced
Allocation on Graphs: A Random Walk Approach 
Ali
Pourmiri 
12:1012:50 
Towards
Constant Size Graphs That Preserve the Local Structure of Large Graphs 
Hendrik Fichtenberger 
12:5014:20 
Lunch 

14:2015:20 
Kolmogorov
width of discrete linear spaces: an approach to matrix rigidity 
Sergey
Yekhanin 
15:3016:10 
How
Limited Interaction Hinders Real Communication (and What It Means for Proof
and Circuit Complexity) 
Jakob Nordstršm 
16:1016:40 
Coffeebreak 

16:4017:40 
Geometric
stability via information theory 
Amir Yehudayoff 
17:5018:30 
On
SlepianWolf theorem with interaction 
Alexander Kozachinsky 
April
12, Tuesday, Day 2 

10:0011:00 
Publicsetup computational integrity from quasilinear PCPs 
Eli BenSasson 
11:0011:30 
Coffeebreak 

11:3012:10 
On the
Space Complexity of Computing Degeneracy in Streaming Model 
MengTsung
Tsai 
12:1012:50 
kVertex Graph
Connectivity Problem in the Streaming Settings 
Meng
Li 
12:5014:20 
Lunch 

14:2015:20 
Approximate
Nonnegative Rank is Equivalent to the Smooth Rectangle Bound 
Amir
Shpilka 
15:3016:10 
Tribes
is hard in the message passing model 
Sagnik Mukhopadhyay 
16:1016:40 
Coffeebreak 

16:4017:20 
Streaming
Property Testing of Visibly PushDown Languages 
Nathana‘l FranŤois 
17:2018:00 
Fair Hierarchical Resource Scheduling 
Andrei Kashin 
April
13, Wednesday, Day 3 

10:0011:00 
Testing clustering in graphs 
Artur Czumaj 
11:0011:30 
Coffeebreak 

11:3012:10 
Unitdistance
graph recognition complexity 
Mikhail
Tikhomirov 
12:1012:50 
Independence
numbers of random subgraphs of some distance graphs 
Andrei Raigorodskii 
12:5014:20 
Lunch 

14:2015:20 
Fast
samplebased testers for visual properties 
Sofya
Raskhodnikova 
15:2015:50 
Coffeebreak 

15:5016:30 
The
Role of Adaptivity in Testing Visual Properties 
Meiram
Murzabulatov 
16:3017:10 
Relating Two
Property Testing Models for Bounded Degree Directed Graphs 
Pan
Peng 