Program

Wed August 21
8:4510:13 RANDOM (Property testing and sublineartime algorithms)
 An optimal lower bound for monotonicity testing over hypergrids  Deeparnab Chakrabarty and C. Seshadhri
 Testing Membership in Counter Automaton Languages  Yonatan Goldhirsh and Michael Viderman
 Tight lower bounds for testing linear isomorphism  Elena Grigorescu, Karl Wimmer and Ning Xie
 Local reconstructors and tolerant testers for connectivity and diameter  Andrea Campagna, Alan Guo and Ronitt Rubinfeld
10:1310:30 break
10:3011:30 Invited talk: Luca Trevisan  Title: Spectral Graph Theory
Abstract: Spectral graph theory is the study of the combinatorial graph properties that can be derived by considering the eigenvalues and eigenvectors of the adjacency matrix of a graph. Such study leads to fast (both in theory and practice) approximation algorithms for graph partitioning problems, and to sufficient conditions to prove that certain graphs are expanders and that certain random walks converge quickly. We survey recent progress in this area, and its applications to approximation algorithms for smallset expansion, sparsest cut, and clustering problem
11:3012:14 RANDOM (Differential privacy)
 Fast Private Data Release Algorithms for Sparse Queries  Avrim Blum and Aaron Roth
 Private Learning and Sanitization: Pure vs. Approximate Differential Privacy  Amos Beimel, Kobbi Nissim and Uri Stemmer
12:1413:45 lunch break
13:4515:13 APPROX
 Online Nonclairvoyant Scheduling to Simultaneously Minimize All Convex Functions  Kyle Fox, Sungjin Im, Janardhan Kulkarni and Benjamin Moseley
 The Online Stochastic Generalized Assignment Problem  Saeed Alaei, Mohammadtaghi Hajiaghayi and Vahid Liaghat
 Online Multidimensional Load Balancing  Adam Meyerson, Alan Roytman and Brian Tagiku
 Shrinking Maxima, Decreasing Costs: New Online Packing and Covering Problems  Pierre Fraigniaud, Magnus M. Halldorsson, Boaz PattShamir, Dror Rawitz and Adi Rosen
15:1315:30 Break
15:3016:36 RANDOM (Streaming, sampling and population recovery)
 A Tight Lower Bound for High Frequency Moment Estimation with Small Error  Yi Li and David Woodruff
 What you can do with Coordinated Samples  Edith Cohen and Haim Kaplan
 Finding Heavy Hitters from Partial or Noisy Data  Lucia Batman, Russell Impagliazzo, Cody Murray and Ramamohan Paturi
16:3616:55 Break
16:5518:01 APPROX
 On the total perimeter of homothetic convex bodies in a convex container 
Adrian Dumitrescu and Csaba Toth
 A pseudoapproximation for the genus of Hamiltonian graphs  Yury Makarychev, Amir Nayyeri and Anastasios Sidiropoulos
 Interdiction Problems on Planar Graphs  Feng Pan and Aaron Schild
18:3020:00 Reception
Thurs August 22
8:4510:13 APPROX
 Multiple Traveling Salesmen in Asymmetric Metrics  Zachary Friggstad
 Approximation Algorithms for Movement Repairmen  Mohammadtaghi Hajiaghayi, Rohit Khandekar, Reza Khani and Guy Kortsarz
 The Approximability of the Binary Paintshop Problem  Anupam Gupta, Satyen Kale, Viswanath Nagarajan, Rishi Saket and Baruch Schieber
 Capacitated Network Design on Undirected Graphs  Deeparnab Chakrabarty, Ravishankar Krishnaswamy, Shi Li and Srivatsan Narayanan
10:1310:30 Break
10:3011:30 Invited talk:Santosh Vempala
 Title: Highdimensional Sampling Algorithms
Abstract: Efficiently sampling highdimensional distributions is a basic algorithmic problem with applications to
optimization, integration/counting and learning. This talk will survey the stateoftheart of randomized
sampling algorithms and the main ideas involved, including geometric random walks, simulated annealing,
isoperimetric inequalities and concentration of measure.
11:3012:14 APPROX
 Improved Hardness of Approximating Chromatic Number  Sangxia Huang
 On the NPHardness of Approximating Ordering Constraint Satisfaction Problems  Per Austrin, Rajsekar Manokaran and Cenny Wenner
12:1413:45 Lunch break
13:4515:13 RANDOM (Random structures)
 The Power of Choice for Random Satisfiability  Varsha Dani, Josep Diaz, Thomas Hayes and Cristopher Moore
 On the average sensitivity and density of $k$CNF formulas  Dominik Scheder and LiYang Tan
 Conditional Random Fields, Planted Constraint Satisfaction and Entropy Concentration  Emmanuel Abbe and Andrea Montanari
 Connectivity of Random High Dimensional Geometric Graphs  Roee David and Uriel Feige
15:1315:30 Break
15:3016:36 APPROX
 Approximate Indexability and Bandit Problems with Concave Rewards and Delayed Feedback  Sudipto Guha and Kamesh Munagala
 Scheduling Subset Tests: Onetime, Continuous, and How They Relate  Edith Cohen, Haim Kaplan and Yishay Mansour
 Online SquareintoSquare Packing Sandor Fekete and HellaFranziska Hoffmann
16:3616:55 Break
16:5518:01 RANDOM (Multispin systems and the hardcore model)
 Improved FPTAS for MultiSpin Systems  Pinyan Lu and Yitong Yin
 Improved Bounds on the Phase Transition for the HardCore Model in 2Dimensions  Juan Vera, Eric Vigoda and Linji Yang
 Phase Coexistence and Slow Mixing for the HardCore Model on Z^2  Antonio Blanca, David Galvin, Dana Randall and Prasad Tetali
Fri August 23
8:4510:13 RANDOM 4 (ErrorCorrecting Codes)
 Absolutely Sound Testing of Lifted Codes  Noga RonZewi, Elad Haramaty and Madhu Sudan
 Zero Knowledge LTCs and Their Applications  Yuval Ishai, Amit Sahai, Michael Viderman and Mor Weiss
 MatchingVector Families and LDCs Over Large Modulo  Zeev Dvir and Guangda Hu
 Combinatorial limitations of averageradius list decoding  Venkatesan Guruswami and Srivatsan Narayanan
10:1310:30 Break
10:3011:30 Invited talk: Persi Diaconis
 Title: Connections between probability and algorithms
Abstract: Computer scientists sometimes use probability for analysis of average case behavior of algorithms. I will describe some examples going in the opposite directionalgorithms giving new probability theory. One example is drawn from my recent work with Bobbie Chen, Daniel Kane and Rob Rhoades: the distribution of the number of crossings in a typical set partition seemed intractable, a clever algorithm of Stam for random generation saves the day.
11:3012:14 RANDOM (Randomness expansion and derandomization)
 Robust Randomness Amplifiers: Upper and Lower Bounds  Matthew Coudron, Thomas Vidick and Henry Yuen
 RandomnessEfficient Curve Samplers  Zeyu Guo
12:1413:45 Lunch break
13:4515:13 APPROX
 Sketching EarthMover Distance on Graph Metrics  Andrew McGregor and Daniel Stubbs
 Spectral Sparsification in Dynamic Graph Streams  Kook Jin Ahn, Sudipto Guha and Andrew McGregor
 Generalizing the Layering Method of Indyk and Woodruff: Recursive Sketches for FrequencyBased Vectors on Streams  Vladimir Braverman and Rafail Ostrovsky
 Approximating Large Frequency Moments with PickandDrop Sampling  Vladimir Braverman and Rafail Ostrovsky
 A local computation approximation scheme to maximum matching  Yishay Mansour and Shai Vardi
15:1315:30 Break
15:3016:36 RANDOM (Derandomization and pseudorandomness)
 SmallBias Sets for Nonabelian Groups: Derandomizing the AlonRoichman Theorem  Sixia Chen, Cristopher Moore and Alexander Russell
 Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing Michael A. Forbes and Amir Shpilka
 Pseudorandomness for Regular Branching Programs via Fourier Analysis  Omer Reingold, Thomas Steinke and Salil Vadhan
16:3616:55 Break
16:5517:40 APPROX
 A New Regularity Lemma and Faster Approximation Algorithms for Low Threshold Rank Graphs  Shayan Oveis Gharan and Luca Trevisan
 Partial Interval Set Cover Tradeoffs Between Scalability and Optimality  Katherine Edwards, William Kennedy and Simon Griffiths



