Monday September 8, 2014

TIME

ACTIVITIES

VENUE

08:15-09:00

Registration

Lobby of Room 1-312, FIT Building

09:00-09:10

Opening Remarks

Room 1-312, FIT Building

09:10-10:10

Keynote Talk 1
Chair:
Peter Miltersen

New Facets of the Random-Facet Algorithm
Uri Zwick (Tel Aviv University)

10:10-10:40

Coffee Break

Lobby of Room 1-312, FIT Building

10:40-11:15

Chair:
Jian Li

Fully Dynamic Maximal Matching in O(log n) Update Time
Manoj Gupta (Indian Institute of Technology Delhi)

Room 1-312, FIT Building

11:15-11:50

Faster LP Algorithm and Faster Maxflow Algorithm
    Yin Tat Lee (MIT)

12:00-14:00

Lunch (Lunch is on your own)

14:00-14:35

Chair:
Periklis Papakonstantinou

Online Learning & Manipulation-proof Reputation Systems
Paul Christiano (UC Berkeley)

Room 1-312, FIT Building

14:35-15:10

The Secretary Returns
Shai Vardi (Tel Aviv University)

15:10-15:40

Coffee Break

Lobby of Room 1-312, FIT Building

15:40-16:15

Chair:
Gregory Valiant

Distributed Algorithms for the Lovász Local Lemma and Graph Coloring
    Hsin-Hao Su (University of Michigan)

Room 1-312, FIT Building

16:15-16:50

Algorithms and Generalizations for the Lovasz Local Lemma
    David Harris (University of Maryland)

Tuesday September 9, 2014

TIME

ACTIVITIES

VENUE

09:00-10:00

Keynote Talk 2
Chair:
Peter Miltersen

Towards Instance Optimal Property Testing
    Gregory Valiant (Stanford University)

Room 1-312, FIT Building

10:00-10:30

Group Photo + Coffee Break

Photo at the lobby of FIT Building

10:30-11:05

Chair:
Pingzhong Tang

Complexity of Approximating CSP with Balance / Hard Constraints
    Euiwoong Lee (Carnegie Mellon University)

Room 1-312, FIT Building

11:05-11:40

The Complexity of Optimal Multidimensional Pricing
    Dimitris Paparas (Columbia University)

12:00-14:00

Lunch

14:00-14:35

Chair:
Periklis Papakonstantinou

Sum of Squares Lower Bounds for Planted Clique
    Aaron Potechin (MIT)

Room 1-312, FIT Building

14:35-15:10

Open Problems in Communication Complexity
    Mika Göös (University of Toronto)

15:10-15:40

Coffee Break

Lobby of Room 1-312, FIT Building

15:40-16:15

Chair:
Gregory Valiant

Optimal Detection of Intersections between Convex Polyhedra
    Luis Barba (Carleton University & Université Libre de Bruxelles)

Room 1-312, FIT Building

16:15-16:50

On the Complexity of Randomly Weighted Multiplicative Voronoi Diagrams
    Ben Raichel (University of Illinois, Urbana-Champaign)

18:00-20:00

Reception (Buffet Dinner)

Immperial Ballroom, Holiday Inn

Wednesday September 10, 2014

TIME

ACTIVITIES

VENUE

9:00-10:00

Keynote Talk 3
Chair:
Jian Li

Communication Complexity Theory: Thirty-Five Years of Set Disjointness
    Alexander Sherstov (University of California, Los Angeles)

Room 1-312, FIT Building

10:00-10:30

Coffee Break

Lobby of Room 1-312, FIT Building

10:30-11:05

Chair:
Alexander Sherstov

Algebraic P vs NP and Chasms in the Arithmetic World
    Ankit Gupta (Chennai Mathematical Institute)

Room 1-312, FIT Building

11:05-11:40

Exponential Lower Bounds for Homogeneous Depth 4 Arithmetic Circuits
    Mrinal Kumar (Rutgers University)

12:00-14:00

Lunch

14:00-14:35

Chair:
Ran Duan

Nested Quantum Walks
    Stacey Jeffery (University of Waterloo)

Room 1-312, FIT Building

14:35-15:10

Lower Bounds in Quantum Property Testing
    John Wright (Carnegie Mellon University)

15:10-15:40

Coffee Break

Lobby of Room 1-312, FIT Building

15:40-16:15

Chair:
Ran Duan

Streaming Cryptography
    Yang Guang (Tsinghua University)

Room 1-312, FIT Building

16:15-16:50

The Security of Multiple Encryption in the Ideal Cipher Model
    Yuanxi Dai (Tsinghua University)

Thursday September 11, 2014

TIME

ACTIVITIES

VENUE

9:00-10:00

Keynote Talk 4     Chair: 
Pingzhong Tang

Representing Utilities at the Market
    Xiaotie Deng (Shanghai Jiaotong University)

Room 1-312, FIT Building

10:00-10:30

Coffee Break

Lobby of Room 1-312, FIT Building

10:30-11:05

Chair:
Jian Li

Siegel’s Theorem, Edge Coloring, and A Holant Dichotomy
    Heng Guo (University of Wisconsin – Madison)

Room 1-312, FIT Building

11:05-11:40

The Multi-shop Ski Rental Problem
    Ai Lingqing (Tsinghua University)

12:00-14:00

Lunch

14:00-14:35

Chair:
Jian Li

Small Value Parallel Repetition for General Games
    Ankit Garg (Princeton University)

Room 1-312, FIT Building

14:35-15:10

Sub-linear Time Hybrid Approximations for  Least Trimmed Squares Estimator and Related Problems
    Hu Ding (University at Buffalo, The State University of New York)

15:10-15:45

Computing with A Full Memory: Catalytic Space
    Florian Speelman (Centrum Wiskunde & Informatica)

15:45-16:00

Closing Ceremony