|
Program
|
Wed August 15
9:00-10:28 Session 1 (Approx)
- Approximation Algorithms for Generalized and Variable-sized Bin Covering - Matthias Hellwig and Alexander Souza
- Online Flow Time Scheduling in the Presence of Preemption Overhead - Ho-Leung Chan and Tak-Wah Lam and Rongbin Li
- Online scheduling of jobs with fixed start times on related machines - Leah Epstein and Lukasz Jez and Jiri Sgall and Rob van Stee
- Approximating Minimum Linear Ordering Problems - Satoru Iwata and Prasad Tetali and Pushkar Tripathi
10:28-10:50 coffee break
10:50-11:50 Invited talk
Speaker: Julia Chuzhoy
11:50-12:56 Session 2 (Random)
Chair: Rocco Servedio
- Extractors for Polynomials Sources over Constant-Size Fields of Small Characteristic - Eli Ben-Sasson and Ariel Gabizon
- Invertible Zero-Error Dispersers and Defective Memory with Stuck-At Errors - Ariel Gabizon and Ronen Shaltiel
- Extractors for Turing-machine sources - Emanuele Viola
12:56-14:30 lunch (on your own)
14:30-16:20 Session 3 (Approx)
- Approximating minimum-cost connected $T$-joins - Joseph Cheriyan and Zachary Friggstad and Zhihan Gao
- Improved Inapproximability for TSP - Michael Lampis
- Improved Hardness Results for Profit Maximization Pricing Problems with Unlimited Supply - Parinya Chalermsook and Julia Chuzhoy and Sampath Kannan and Sanjeev Khanna
- Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems - Per Austrin and Toniann Pitassi and Yu Wu
- New and Improved Bounds for the Minimum Set Cover Problem - Rishi Saket and Maxim Sviridenko
16:20-16:45 coffee break
16:45-18:57 Session 4 (Random)
- Rainbow Connectivity of Random Sparse Graphs - Alan Frieze and Charalampos E. Tsourakakis
- Tight bounds on the threshold for permuted k-colorability - Varsha Dani and Cristopher Moore and Anna Olson
- Multiple-choice Balanced Allocation in (almost) Parallel - Petra Berenbrink and Artur Czumaj and Matthias Englert and Tom Friedetzky and Lars Nagel
- Maximal empty boxes amidst random points - Adrian Dumitrescu and Minghui Jiang
- Analysis of k-means++ for Separable Data - Ragesh Jaiswal and Nitin Garg
- On the Coin Weighing Problem with the Presence of Noise - Nader H. Bshouty
19:00 Welcome Reception
Thurs August 16
9:00-10:50 Session 5 (Approx)
- A new point of NP-hardness for 2-to-1 Label Cover - Per Austrin and Ryan O'Donnell and John Wright
- Circumventing d-to-1 for Approximation Resistance of Satisfiable Predicates Strictly Containing Parity of Width Four - Cenny Wenner
- On the NP-hardness of Max-Not-2 - Johan Hastad
- The Projection Games Conjecture and The NP-Hardness of ln n-Approximating Set-Cover - Dana Moshkovitz
- Hardness of Vertex Deletion and Project Scheduling - Ola Svensson
10:50-11:15 coffee break
11:15-13:05 Session 6 (Random)
- Optimal Hitting Sets for Combinatorial Shapes - Aditya Bhaskara and Devendra Desai and Srikanth Srinivasan
- Almost k-wise vs. k-wise independent permutations, and uniformity for general group actions - Noga Alon and Shachar Lovett
- Pseudorandomness for linear length branching programs and stack machines - Andrej Bogdanov and Periklis A. Papakonstantinou and Andrew Wan
- An Explicit VC-Theorem for Low-Degree Polynomials - Eshan Chattopadhyay and Adam Klivans and Pravesh Kothari
- A Sharper Local Lemma with Improved Applications - Kashyap Kolipaka and Mario Szegedy and Yixin Xu
13:10-14:30 lunch (on your own)
14:30-16:20 Session 7 (Approx)
- Prize-collecting Survivable Network Design in Node-weighted Graphs - Chandra Chekuri and Alina Ene and Ali Vakilian
- Primal-dual approximation algorithms for node-weighted network design in planar graphs
Piotr Berman and Grigory Yaroslavtsev
- A systematic approach to bound factor revealing LPs and its application to the Metric and Squared Metric Facility Location Problems - Cristina G. Fernandes and Luis A. A. Meira and Flavio K. Miyazawa and Lehilton L. C.Pedrosa
- iBGP and Constrained Connectivity - Michael Dinitz and Gordon Wilfong
- New Approximation Results for Resource Replication Problems - Samir Khuller and Barna Saha and Kanthi K. Sarpatwar
16:20-16:45 coffee break
16:45-18:35 Session 8 (Random)
- Testing Lipschitz Functions on Hypergrid Domains - Pranjal Awasthi and Madhav Jha and Marco Molinaro and Sofya Raskhodnikova.
- Limitations of Local Filters of Lipschitz and Monotone Functions - Pranjal Awasthi and Madhav Jha and Marco Molinaro and Sofya Raskhodnikova.
- On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation - Jelani Nelson and Huy L. Nguyen and David P. Woodruff.
- Two-Sided Error Proximity Oblivious Testing - Oded Goldreich and Igor Shinkar.
- Tight Bounds for Testing k-Linearity - Eric Blais and Daniel Kane.
Fri August 17
9:00-10:28 Session 9 (Random)
- A Combination of Testability and Decodability by Tensor Products - Michael Viderman.
- A new upper bound on the query complexity for testing generalized Reed-Muller codes - Noga Ron-Zewi and Madhu Sudan.
- Mirror Descent based Interactive Database Privacy - Prateek Jain and Abhradeep Thakurta.
- Finding Small Sparse Cuts Locally by Random Walk - Tsz Chiu Kwok and Lap Chi Lau.
10:28-10:50 coffee break
10:50-11:50 Invited talk
Speaker: Yuval Peres
11:50-12:56 Session 10 (Approx)
Chair: Anupam Gupta
- Approximation Algorithm for Non-Boolean MAX k-CSP - Konstantin Makarychev and Yury Makarychev
- Approximating bounded occurrence ordering CSPs - Venkatesan Guruswami and Yuan Zhou
- Approximation Guarantees for the Minimum Linear Arrangement Problem by Higher Eigenvalues - Suguru Tamaki and Yuichi Yoshida
12:56-14:30 lunch (on your own)
14:30-16:20 Session 11 (Random)
- A discrepancy lower bound for information complexity - Mark Braverman and Omri Weinstein
- Information Complexity versus Corruption and Applications to Orthogonality and Gap-Hamming - Amit Chakrabarti and Ranganath Kondapally and Zhenghui Wang
- Sparse and Lopsided Set Disjointness via Information Theory - Anirban Dasgupta and Ravi Kumar and D. Sivakumar
- Downward Self-Reducibility of the Permanent - Revisited - Sanjeev Arora and Arnab Bhattacharyya and Rajsekar Manokaran and Sushant Sachdeva
- Spectral Norm of Symmetric Functions - Anil Ada and Omar Fawzi and Hamed Hatami
16:20-16:45 coffee break
16:45-18:57 Session 12 (Approx)
- Improved Spectral-Norm Bounds for Clustering - Pranjal Awasthi and Or Sheffet
- Planarizing an unknown surface - Yury Makarychev and Anastasios Sidiropoulos
- The Remote Set Problem on Lattices - Ishay Haviv
- Maximum Matching in Semi-Streaming with Few Passes - Christian Konrad and Frederic Magniez and Claire Mathieu
- What's the frequency, Kenneth?: Sublinear Fourier sampling off the grid - Petros Boufounos and Volkan Cevher and Anna C. Gilbert and Yi Li and Martin J. Strauss
- Additive Approximation for Near-Perfect Phylogeny Construction - Pranjal Awasthi and Avrim Blum and Jamie Morgenstern and Or Sheffet
|
|
|
|
PDF Format
Plain Text
(download the program in PDF here)