Program

Monday August 24
8:008:25 Registration
8:258:30 Welcome
8:309:25 Session 1: Invited talk from Raghu Meka (University of California, Los Angeles)
Title:
"Pseudorandomness  old problems, new methods, and current challenges"
Abstract:
The focus of this talk will be the survey of recent results related to two classical questions in complexity theory: derandomizing smallspace algorithms and lower bounds for constantdepth circuits. Along the way, two recent techniques will be highlighted "mild pseudorandom restrictions" and "iterative dimension reduction"for building pseudorandom generators (PRGs) leading up to nearlyoptimal PRGs for halfspaces and readonce CNFs. There will be also emphasis on a few open problems and challenges (among many) that seem to test the limits of our knowledge and tools in derandomization.
9:259:45 Coffee Break
9:4510:50 Session 2: RANDOM
 Dynamics for the meanfield randomcluster model  Antonio Blanca and Alistair Sinclair.
 SwendsenWang Algorithm on the MeanField Potts Model  Andreas Galanis, Daniel Stefankovic and Eric Vigoda.
 Harnessing the Bethe free energy  Victor Bapst and Amin CojaOghlan.
10:55  12:00 Session 3: APPROX
 Improved NPinapproximability for 2variable linear equations  Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O'Donnell and John Wright
 Inapproximability of HTransversal/Packing  Venkatesan Guruswami and Euiwoong Lee.
 Approximate Hypergraph Coloring under Lowdiscrepancy and Related Promises  V.S.P. Vijay Bhattiprolu, Venkatesan Guruswami and Euiwoong Lee.
12:05  13:10 Session 4: RANDOM
 Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness  Mark Bun and Thomas Steinke.
 Towards Resistance Sparsifiers  Michael Dinitz, Robert Krauthgamer and Tal Wagner.
 Spectral Norm of Random Kernel Matrices with Applications to Privacy  Shiva Kasiviswanathan and Mark Rudelson.
13:1014:30 Lunch break
14:30  15:35 Session 5: APPROX
 Towards a Characterization of Approximation Resistance for Symmetric CSPs  Venkatesan Guruswami and Euiwoong Lee.
 Approximating Dense Max 2CSPs  Pasin Manurangsi and Dana Moshkovitz.
 Beating the random assignment on constraint satisfaction problems of bounded degree  Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer and John Wright.
15:35  15:55 Coffee break
15:55  17:00 Session 6: RANDOM
 On Constant Size Graphs That Preserve the Local Structure of High Girth Graphs  Hendrik Fichtenberger, Pan Peng and Christian Sohler.
 Average Distance Queries through Weighted Samples in Graphs and Metric Spaces: High Scalability with Tight Statistical Guarantees  Shiri Chechik, Edith Cohen and Haim Kaplan.
 A Chasm Between Identity and Equivalence Testing with Conditional Queries  Jayadev Acharya, Clément Canonne and Gautam Kamath.
17:00  18:30 Session 7: APPROX
 Stochastic and Robust Scheduling in the Cloud  Lin Chen, Nicole Megow, Roman Rischke and Leen Stougie.
 Minimizing maximum flowtime on related machines  Bouke Cloostermans and Nikhil Bansal.
 A 2Competitive Algorithm For Online Convex Optimization With Switching CostsNikhil Bansal, Anupam Gupta, Ravishankar Krishnaswamy, Kirk Pruhs, Kevin Schewior and Clifford Stein.
 The Container Selection Problem  Viswanath Nagarajan, Kanthi Sarpatwar, Baruch Schieber, Hadas Shachnai and Joel Wolf.
Tuesday August 25
8:309:25 Session 8: Invited talk from R. Ravi (Carnegie Mellon University)
Title:
" Improved Approximations for GraphTSP in Regular Graphs"
Abstract:
A tour in a graph is a connected walk that visits every vertex at least once, and returns to the starting vertex. We describe improved approximation results for a tour with the minimum number of edges in regular graphs. En route we illustrate the main ideas used recently in designing improved approximation algorithms for graph TSP.
9:259:45 Coffee Break
9:4510:50 Session 9: APPROX
 On Linear Programming Relaxations for Unsplittable Flow in Trees  Zachary Friggstad and Zhihan Gao.
 On Approximating NodeDisjoint Paths in Grids  Julia Chuzhoy and David Kim.
 Terminal Embeddings  Michael Elkin, Arnold Filtser and Ofer Neiman.
10:55  12:00 Session 10: RANDOM
 Deletion codes in the highnoise and highrate regimes  Venkatesan Guruswami and Carol Wang.
 Communication with partial noiseless feedback  Bernhard Haeupler, Pritish Kamath and Ameya Velingker.
 On Fortification of Projection Games  Amey Bhangale, Ramprasad Saptharishi, Girish Varma and Rakesh Venkat.
12:05  13:10 Session 11: APPROX
 Fully Dynamic Bin Packing Revisited  Sebastian Berndt, Klaus Jansen and KimManuel Klein.
 How to Tame Rectangles: Solving Independent Set and Coloring of Rectangles via Shrinking  Anna Adamaszek, Parinya Chalermsook and Andreas Wiese.
 SOn guillotine cutting sequences  Fidaa Abed, Parinya Chalermsook, Jose Correa, Andreas Karrenbauer, Pablo PerezLantero, Jose Soto and Andreas Wiese.
13:1014:30 Lunch break
14:30  15:35 Session 12: RANDOM
 A randomized online quantile summary in $O(\frac{1}{\varepsilon} \log \frac{1}{\varepsilon})$ words  David Felber and Rafail Ostrovsky.
 A ZeroOne Laws for Sliding Windows and Universal Sketches  Vladimir Braverman, Rafail Ostrovsky and Alan Roytman.
 Universal sketches for the frequency negative moments and other decreasing streaming sums  Stephen Chestnut and Vladimir Braverman.
15:35  15:55 Coffee break
15:55  17:00 Session 13: APPROX
 Approximating Hit Rate Curves using Streaming Algorithms  Zachary Drudi, Nicholas Harvey, Stephen Ingram, Andrew Warfield and Jake Wires.
 Tight Bounds for Graph Problems in Insertion Streams  Xiaoming Sun and David Woodruff.
 Large Supports are required for WellSupported Nash Equilibria  Yogesh Anbalagan, Hao Huang, Shachar Lovett, Sergey Norin, Adrian Vetta and Hehui Wu.
17:00  18:30 Session 14: RANDOM
 Separating decision tree complexity from subcube partition complexity  Robin Kothari, David RacicotDesloges and Miklos Santha.
 Internal compression of protocols to entropy  Shay Moran, Amir Yehudayoff and Balthazar Bauer.
 Correlation in Hard Distributions in Communication Complexity  Dmitry Gavinsky, Hartmut Klauck and Ralph Bottesch.
 Dependent Random Graphs and Multiparty Pointer Jumping  Joshua Brody and Mario Sanchez.
18:30  20:00 Reception
Wednesday August 26
8:309:55 Session 15: RANDOM
 Deterministically Factoring Sparse Polynomials into Multilinear Factors and Sums of Univariate Polynomials  Ilya Volkovich.
 Two Structural Results for Low Degree Polynomials and Applications  Gil Cohen and Avishay Tal.
 Decomposing Overcomplete 3rd Order Tensors using SumofSquares Algorithms  Rong Ge and Tengyu Ma.
 Dimension Expanders via Rank Condensers  Michael A. Forbes and Venkatesan Guruswami.
9:55  10:15 Coffee break
10:15  11:40 Session 16: APPROX
 Improved Bounds in Stochastic Matching and Optimization  Alok Baveja, Amit Chavan, Andrei Nikiforov, Aravind Srinivasan and Pan Xu.
 A Tight Approximation Bound for the Stable Marriage Problem with Restricted Ties  ChienChung Huang, Kazuo Iwama, Shuichi Miyazaki and Hiroki Yanagisawa.
 Approximate Nearest Neighbor Search in Metrics of Planar Graphs  Ittai Abraham, Shiri Chechik, Robert Krauthgamer and Udi Wieder
 NonUniform Robust Network Design in Planar Graphs  David Adjiashvili.
11:45  12:50 Session 17: RANDOM
 Learning circuits with few negations  Eric Blais, Clément Canonne, Igor Carboni Oliveira, Rocco Servedio and LiYang Tan.
 NegationLimited Formulas  Siyao Guo and Ilan Komargodski.
 Tighter Connections between Derandomization and Circuit Lower Bounds  Marco Carmosino, Russell Impagliazzo, Valentine Kabanets and Antonina Kolokolova.
12:5014:00 Lunch break
14:00  15:05 Session 18: APPROX
 Designing Overlapping Networks for PublishSubscribe Systems  Jennifer Iglesias, Rajmohan Rajaraman, R. Ravi and Ravi Sundaram.
 Approximating Upper DegreeConstrained Partial Orientations  Marek Cygan and Tomasz Kociumaka.
 Sequential Importance Sampling Algorithms for Estimating the AllTerminal Reliability Polynomial of Sparse Graphs  David Harris and Francis Sullivan.
15:10  16:35 Session 19: RANDOM
 The minimum bisection in the planted bisection model  Amin CojaOghlan, Oliver Cooley, Mihyun Kang and Kathrin Skubch.
 Local convergence of random graph colorings  Amin CojaOghlan, Charilaos Efthymiou and Nor Jaafari.
 Reconstruction/Nonreconstruction Thresholds for Colourings of General GaltonWatson Trees  Charilaos Efthymiou.
 Distancebased species tree estimation: informationtheoretic tradeoff between number of loci and sequence length under the coalescent  Elchanan Mossel and Sebastien Roch.



