|
Program
|
Wed August 21
8:45-10:13 RANDOM (Property testing and sublinear-time 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:13-10:30 break
10:30-11: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 small-set expansion, sparsest cut, and clustering problem
11:30-12: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:14-13:45 lunch break
13:45-15:13 APPROX
- Online Non-clairvoyant 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 Patt-Shamir, Dror Rawitz and Adi Rosen
15:13-15:30 Break
15:30-16: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:36-16:55 Break
16:55-18:01 APPROX
- On the total perimeter of homothetic convex bodies in a convex container -
Adrian Dumitrescu and Csaba Toth
- A pseudo-approximation for the genus of Hamiltonian graphs - Yury Makarychev, Amir Nayyeri and Anastasios Sidiropoulos
- Interdiction Problems on Planar Graphs - Feng Pan and Aaron Schild
18:30-20:00 Reception
Thurs August 22
8:45-10: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:13-10:30 Break
10:30-11:30 Invited talk:Santosh Vempala
- Title: High-dimensional Sampling Algorithms
Abstract: Efficiently sampling high-dimensional distributions is a basic algorithmic problem with applications to
optimization, integration/counting and learning. This talk will survey the state-of-the-art of randomized
sampling algorithms and the main ideas involved, including geometric random walks, simulated annealing,
isoperimetric inequalities and concentration of measure.
11:30-12:14 APPROX
- Improved Hardness of Approximating Chromatic Number - Sangxia Huang
- On the NP-Hardness of Approximating Ordering Constraint Satisfaction Problems - Per Austrin, Rajsekar Manokaran and Cenny Wenner
12:14-13:45 Lunch break
13:45-15: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 Li-Yang 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:13-15:30 Break
15:30-16:36 APPROX
- Approximate Indexability and Bandit Problems with Concave Rewards and Delayed Feedback - Sudipto Guha and Kamesh Munagala
- Scheduling Subset Tests: One-time, Continuous, and How They Relate - Edith Cohen, Haim Kaplan and Yishay Mansour
- Online Square-into-Square Packing -Sandor Fekete and Hella-Franziska Hoffmann
16:36-16:55 Break
16:55-18:01 RANDOM (Multi-spin systems and the hard-core model)
- Improved FPTAS for Multi-Spin Systems - Pinyan Lu and Yitong Yin
- Improved Bounds on the Phase Transition for the Hard-Core Model in 2-Dimensions - Juan Vera, Eric Vigoda and Linji Yang
- Phase Coexistence and Slow Mixing for the Hard-Core Model on Z^2 - Antonio Blanca, David Galvin, Dana Randall and Prasad Tetali
Fri August 23
8:45-10:13 RANDOM 4 (Error-Correcting Codes)
- Absolutely Sound Testing of Lifted Codes - Noga Ron-Zewi, Elad Haramaty and Madhu Sudan
- Zero Knowledge LTCs and Their Applications - Yuval Ishai, Amit Sahai, Michael Viderman and Mor Weiss
- Matching-Vector Families and LDCs Over Large Modulo - Zeev Dvir and Guangda Hu
- Combinatorial limitations of average-radius list decoding - Venkatesan Guruswami and Srivatsan Narayanan
10:13-10:30 Break
10:30-11: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 direction---algorithms 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:30-12:14 RANDOM (Randomness expansion and derandomization)
- Robust Randomness Amplifiers: Upper and Lower Bounds - Matthew Coudron, Thomas Vidick and Henry Yuen
- Randomness-Efficient Curve Samplers - Zeyu Guo
12:14-13:45 Lunch break
13:45-15:13 APPROX
- Sketching Earth-Mover 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 Frequency-Based Vectors on Streams - Vladimir Braverman and Rafail Ostrovsky
- Approximating Large Frequency Moments with Pick-and-Drop Sampling - Vladimir Braverman and Rafail Ostrovsky
- A local computation approximation scheme to maximum matching - Yishay Mansour and Shai Vardi
15:13-15:30 Break
15:30-16:36 RANDOM (Derandomization and pseudorandomness)
- Small-Bias Sets for Nonabelian Groups: Derandomizing the Alon-Roichman 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:36-16:55 Break
16:55-17: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 Trade-offs Between Scalability and Optimality - Katherine Edwards, William Kennedy and Simon Griffiths
|
|
|
|
PDF Format
Plain Text
(download the program in PDF here)