Program

Monday, August 20

8:00-8:50 Breakfast

8:50-9:40 Invited talk: Sanjeev Khanna, Disjoint Paths in Networks (abstract)

9:40-10:30 APPROX

      ·         Anupam Gupta, MohammadTaghi Hajiaghayi and Amit Kumar. Stochastic Steiner Tree with Non-Uniform Inflation

      ·         Raphael Yuster. Almost exact matchings

10:30-10:45 break

10:45-12:25 RANDOM

·         Mira Gonen and Dana Ron. On the Benefits of Adaptivity in Property Testing of Dense Graphs

·         Oded Goldreich and Or Sheffet. On the Randomness Complexity of Property Testing

·         Dana Glasner and Rocco Servedio. Distribution-Free Testing Lower Bounds for Basic Boolean Functions

·         Eyal Rozenberg and Eldar Fischer. Lower bounds for testing forbidden induced subgraphs in bipartite-graph-like combinatorial objects

12:25- 2:00 Lunch

2:00- 3:15 APPROX

·         Johan Hastad. On the approximation resistance of a random predicate

·         Ashkan Aazami and Michael Stilp. Approximation algorithms and hardness for domination with propagation

·         Subhash Khot and Rishi Saket. Hardness of Embedding Metric Spaces of Equal Size

3:15- 3:30 break

3:30- 4:45 RANDOM

·         Graham Cormode and Sumit Ganguly. On Estimating Frequency Moments of  Data Streams

·         Rina Panigrahy and Ravi Kumar. On finding frequent elements in a data stream

·         Sam Greenberg and Dana Randall. Slow mixing of Markov chains using fault lines and fat contours

4:45- 5:00 break

5:00- 6:15 APPROX

·         Greg Frederickson and Barry Wittman. Approximation Algorithms for the Traveling Repairman and Speeding Deliveryman Problems with Unit-Time Windows

·         Viswanath Nagarajan and R Ravi. Poly-logarithmic Approximation Algorithms for Directed Vehicle Routing Problems

·         Uriel Feige and Mohit Singh. Improved approximation ratios for traveling salesperson tours and paths in directed graphs

 6:30-8:00 Wine and Cheese Reception (Convocation room)

Tuesday, August 21

8:00-8:50 Breakfast

8:50-9:40 Invited talk: Rocco Servedio, Learning, Testing, and Approximation (abstract)

9:40-10:30 RANDOM

·         Mohsen Bayati, Jeong Han Kim and Amin Saberi. A Sequential Algorithm for Generating Random Graphs

·         Moni Naor and Asaf Nussboim. Implementing Huge Sparse Random Graphs

10:30-10:45 break

10:45-12:25 APPROX

·         Jaroslaw Byrka. An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem

·         Victor Chepoi and Bertrand Estellon. Packing and covering delta-hyperbolic spaces by balls

·         Chadi Kari, Yoo-Ah Kim, Seungjoon Lee, Alexander Russell and Min-ho Shin. Soft Edge Coloring

·         Ning Chen, Roee Engelberg, C. Thach Nguyen, Prasad Raghavendra, Atri Rudra and Gyanit Singh. Improved Approximation Algorithms for the Spanning Star Forest Problem

12:25- 2:00 Lunch

2:00- 3:15 RANDOM

·         Arkadev Chattopadhyay and Bruce Reed. Properly 2-Colouring Linear Hypergraphs

·         Harry Buhrman, Matthias Christandl, Michal Koucky, Zvi Lotker, Boaz Patt-Shamir and Nikolai Vereshchagin. High Entropy Random Selection Protocols

·         Jacek Cichon, Marek Klonowski, Lukasz Krzywiecki, Pawel Zielinski, Przemyslaw Kobylanski and Bartlomiej Rozanski. Random Subsets of the Interval and P2P protocols

3:15- 3:30 break

3:30- 4:45 APPROX

·         Shahar Dobzinski. Two Randomized Mechanisms for Combinatorial Auctions

·         Subhash Khot and Ashok Kumar Ponnuswami. Approximation Algorithms for the Max-Min Allocation problem

·         Andreas S. Schulz and Nelson Uhan. Encouraging Cooperation in Sharing Supermodular Costs

4:45- 5:00 break

5:00- 6:15 RANDOM

·         Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Amir Shpilka and Adam Smith. Sublinear Algorithms for Approximating String Compressibility

·         Kfir Barhum, Oded Goldreich and Adi Shraibman. On approximating the average distance between points

·         Arie Matsliah, Eldar Fischer, Sourav Chakraborty, ilan newman and Oded Lachish. Testing $st$-Connectivity

Wednesday, August 22

8:00-8:50 Breakfast

8:50-9:40 Invited talk: Charles Fefferman, Interpolation of C^m Functions in n dimensions (abstract)

9:40-10:30 APPROX

·         James Lee and Prasad Raghavendra. Coarse differentiation and multi-flows in planar graphs

·         Manor Mendel and Assaf Naor. Maximum gradient embeddings and monotone clustering

10:30-10:45 break

10:45-12:25 RANDOM

·         Omer Barkol, Yuval Ishai and Enav Weinreb. On Locally Decodable Codes, Self-Correctable Codes, and $t$-private PIR

·         Venkatesan Guruswami and Atri Rudra. Better binary list-decodable codes via multilevel concatenation

·         Dan Gutfreund and Amnon Ta-Shma. Worst-case to average-case reductions revisited

·         Scott Diehl. Lower Bounds for Swapping Arthur and Merlin

12:25- 2:00 Lunch

2:00- 3:40 APPROX

·         Hamed Hatami, Avner Magen and Evangelos Markakis. Integrality gaps of semidefinite programs for Vertex Cover and relations to $\ell_1$ embeddability of negative type metrics

·         Ilias Diakonikolas and Mihalis Yannakakis. Small Approximate Pareto Sets for Biobjective Shortest Paths and Other Problems

·         Kazuo Iwama and Guochuan Zhang. Optimal Resource Augmentations for Online Knapsack

·         Moshe Babaioff, Nicole Immorlica, David Kempe and Robert Kleinberg. A Knapsack Secretary Problem with Applications

3:40- 3:55 break

3:55- 5:35 RANDOM

·         Michael Behrisch, Mihyun Kang and Amin Coja-Oghlan. Local Limit Theorems for the Giant Component of Random Hypergraphs

·         Yael Dekel, James Lee and Nati Linial. Eigenvectors of random graphs: Nodal domains

·         Colin Cooper and Alan Frieze. The cover time of random digraphs

·         Ilia Binder and Mark Braverman. Derandomization of Euclidean Random Walks