PDF Format
Plain TextProgram
- Alan Frieze, Pall Melsted and Michael Mitzenmacher. An Analysis of Random-Walk Cuckoo Hashing
- Klim Efremenko and Omer Reingold. How Well Do Random Walks Parallelize?
- Brendan Lucier, Michael Molloy and Yuval Peres. The Glauber dynamics for colourings of bounded degree trees
- Karthekeyan Chandrasekaran, Amit Deshpande and Santosh Vempala. Sampling Harmonic Concave Functions: The Limit of Convexity Based Isoperimetry
- Adam Klivans, Philip Long and Alex Tang. Baum's Algorithm Learns Intersections of Halfspaces with respect to Log-Concave Distributions
10h20-10h40am Coffee Break
10h40 -12h30pm Approx
- Ashkan Aazami, Joseph Cheriyan and Krishnam Raju Jampani. Approximation Algorithms and Hardness Results for Packing Element-Disjoint Steiner Trees in Planar Graphs
- Gaurav Kanade, Matt Gibson, Kasturi Varadarajan and Erik Krohn. An Approximation Scheme for Terrain Guarding
- Rolf Harren and Rob van Stee. Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems
- Brian Tagiku, Adam Meyerson and Douglas Carroll. Approximations for Aligned Coloring and Spillage Minimization in Interval and Chordal Graphs
- Brian Tagiku and Adam Meyerson. Minimizing Average Shortest Path Distances via Shortcut Edge Addition
Lunch break (at your own)
2pm-3h50pm Random
- T.S. Jayram. Hellinger Strikes Back: A Note on the Multi-Party Information Complexity of AND
- Boaz Barak, Anup Rao, Ran Raz, Ricky Rosen and Ronen Shaltiel. Strong Parallel Repetition Theorem for Free Projection Games
- Anindya De and Luca Trevisan. Extractors using hardness amplification
- Andrej Bogdanov and Youming Qiao. On the Security of Goldreich's One-Way Function
- Ido Ben Eliezer, Rani Hod and Shachar Lovett. Random low degree polynomials are hard to approximate
3h50pm-4h10pm Coffee Break
4h10pm-6pm Approx
- Uriel Feige, Nicole Immorlica, Vahab Mirrokni and Hamid Nazerzadeh. Pass Approximation: A Framework for Analyzing and Designing Heuristics
- Chandra Chekuri, Alina Ene and Nitish Korula. Unsplittable Flow in Paths and Trees and Column-Restricted Packing Integer Programs
- Thomas Rothvoss and Laura Sanita. On the complexity of the asymmetric VPN problem
- Ronald Koch, Britta Peis, Martin Skutella and Andreas Wiese. Real-Time Message Routing and Scheduling
- Jose R. Correa, Martin Skutella and Jose Verschae. The Power of Preemption on Unrelated Machines and Applications to Scheduling Orders
6h30pm Welcome reception
Aug. 22
8h30-10h20am Approx
- Chandra Chekuri and Iftah Gamzu. Truthful Mechanisms via Greedy Iterative Packing
- Rohit Khandekar, Tracy Kimbrel, Konstantin Makarychev and Maxim Sviridenko. On Hardness of Pricing Items for Single-Minded Bidders
- Venkatesan Guruswami and Ali Kemal Sinop. Improved Inapproximability Results for Maximum k-Colorable Subgraph
- Friedrich Eisenbrand and Thomas Rothvoss. New Hardness Results for Diophantine Approximation
- Ankit Aggarwal, Amit Deshpande and Ravi Kannan. Adaptive Sampling for k-means Clustering
Coffee Break: 10h20-10h40am
10h40 -12h30pm Random
- Amir Shpilka and Ilya Volkovich. Improved Polynomial Identity Testing for Read-Once Formulas
- Oded Goldreich and Dana Ron. Algorithmic Aspects of Property Testing in The Dense Graphs Model
- Oded Goldreich, Michael Krivelevich, Ilan Newman and Eyal Rozenberg. Hierarchy Theorems for Property Testing
- Dana Ron and Gilad Tsur. Testing Computability by Width Two OBDDs
- Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld and Rocco Servedio. Testing {-1,1}-Weight Halfspaces
Lunch break (at your own)
2pm-3h50pm Approx
- Jon Lee, Maxim Sviridenko and Jan Vondrak. Submodular Maximization Over Multiple Matroids via Generalized Exchange Properties
- Konstantinos Georgiou, Avner Magen and Madhur Tulsiani. Optimal Sherali-Adams Gaps from Pairwise Independence
- Avner Magen and Mohammad Moharrami. Robust algorithms for Maximum Independent Set on Minor-free graphs based on the Sherali-Adams Hierarchy
- Zeev Nutov. Approximating Node-Connectivity Augmentation Problems
- Guy Kortsraz and Zeev Nutov. Approximating some network design problems with node costs
3h50pm-4h10pm Coffee Break
4h10pm-6pm Random
- Van Vu and Terence Tao. Smooth analysis of the condition number and the least singular value
- Aram Harrow and Richard Low. Efficient Quantum Tensor Product Expanders and k-designs
- S. Charles Brubaker and Santosh Vempala. Random Tensors and Planted Cliques
- Lorenz Minder and Danny Vilenchik. Small clique detection and approximate Nash equilibria
- Prasad Chebolu, Alan Frieze, Pall Melsted and Gregory Sorkin. Average-case
analyses of Vickrey costs
Aug. 23
9h00-10h50am Random
- Shubhangi Saraf and Swastik Kopparty. Tolerant Linearity Testing and Locally Testable Codes
- Elena Grigorescu, Tali Kaufman and Madhu Sudan. Succinct Representation of Codes with Applications to Testing
- Eli Ben-Sasson and Michael Viderman. Composition of semi-LTCs by two-wise Tensor Products
- Noga Alon, Rina Panigrahy and Sergey Yekhanin. Deterministic Approximation Algorithms for the Nearest Codeword Problem
- Victor Chen. A Hypergraph Dictatorship Test with Perfect Completeness
10h50-11h10am Coffee Break
11h10-12pm - Special tribute session to Rajeev Motwani by Prabhakar Raghavan
Lunch break (at your own)
2h-3h50pm Approx - Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar and Danny Segev. Scheduling with Outliers
- Katarzyna Paluch, Marcin Mucha and Aleksander Madry. A 7/9 Approximation Algorithm for the Maximum Traveling Salesman Problem
- Saurav Pandit, Sriram Pemmaraju and Kasturi Varadarajan. Approximation Algorithms for Domatic Partitions
- Alexander Jaffe, James Lee and Mohammad Moharrami. On the optimality of gluing over scales
- Julia Chuzhoy and Paolo Codenotti. Resource Minimization Job Scheduling
3h50-4h10pm Coffee Break
4h10-5h20 Random - Raghu Meka and David Zuckerman. Small-Bias Spaces for Group Products
- Shachar Lovett, Omer Reingold, Luca Trevisan and Salil Vadhan. Pseudorandom Bit Generators that Fool Modular Sums
- Jeff Kinne, Dieter van Melkebeek and Ronen Shaltiel. Pseudorandom Generators and Typically-Correct Derandomization
|
Aug. 21 8h30-10h20am Random |