|
Program
|
APPROX + RANDOM 2018 Program
Friend Center Lecture Hall 101
Monday August 20
8:00-8:30 Registration
8:30-10:10 Session 1 (RANDOM):
- Igor Oliveira and Rahul Santhanam - Pseudo-derandomizing learning and approximation.
- William Hoza and Adam Klivans - Preserving Randomness for Adaptive Algorithms.
- Salman Beigi, Andrej Bogdanov, Omid Etesami and Siyao Guo - Optimal Deterministic Extractors for Generalized Santha-Vazirani Sources.
- Yotam Dikstein, Irit Dinur, Yuval Filmus and Prahladh Harsha. Boolean function analysis on high-dimensional expanders.
- Xin Li, Shachar Lovett and Jiapeng Zhang - Sunflowers and Quasi-sunflowers from Randomness Extractors.
10:10-10:30 Coffee Break
10:30-12:10 Session 2 (APPROX):
- Chandra Chekuri and Shalmoli Gupta - Perturbation Resilient Clustering for k-Center and Related Problems via LP Relaxations.
- Shyam Narayana - Deterministic O(1)-Approximation Algorithms to 1-Center Clustering with Outliers.
- Mark Braverman and Young Kun Ko - Semi-Direct Sum Theorem and Nearest Neighbor under l infinity.
- Talya Eden and Will Rosenbaum - Lower Bounds for Approximating Graph Parameters via Communication Complexity.
- Anat Ganor and Karthik C. S. - Communication Complexity of Correlated Equilibrium with Small Support.
12:10-13:30 Lunch break
13:30 - 15:10 Session 3 (RANDOM):
- Shai Vard - Randomly coloring graphs of logarithmically bounded pathwidth.
- Ishay Haviv - On Minrank and Forbidden Subgraphs.
- Fotis Iliopoulos - Commutative Algorithms Approximate the LLL distribution.
- Tali Kaufman and Izhar Oppenhein - High Order Random Walks: Beyond Spectral Gap.
- Tony Johansson - The cover time of a biased random walk on a random regular graph of odd degree.
15:10-15:30 Coffee Break
15:30 - 17:10 Session 4 (APPROX):
- Akanksha Agrawal, Daniel Lokshtanov, Pranabendu Misra, Saket Saurabh and Meirav Zehavi - Polylogarithmic Approximation Algorithms for Weighted-F-Deletion Problems.
- Pasin Manurangsi and Luca Trevisan - Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut.
- Hao-Ting Wei, Wing-Kai Hon, Paul Horn, Chung-Shou Liao and Kunihiko Sadakane - An O(1)-Approximation Algorithm for Dynamic Weighted Vertex Cover with Soft Capacity.
- Parinya Chalermsook, Syamantak Das, Guy Even, Bundit Laekhanukit and Daniel Vaz - Survivable Network Design for Group Connectivity in Low-Treewidth Graphs.
- Amariah Becker - A Tight 4/3 Approximation for Capacitated Vehicle Routing in Trees.
17:00-20:00 Reception
Tuesday August 21
8:30-10:10 Session 5 (APPROX):
- Amit Levi and Yuichi Yoshida - Sublinear-Time Quadratic Minimization via Spectral Decomposition of Matrices.
- Yi Li and Vasileios Nakos - Deterministic Heavy Hitters with Sublinear Query Time.
- Vladimir Braverman, Elena Grigorescu, Harry Lang, David Woodruff and Samson Zhou - Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows.
- Vasileios Nakos, Yi Li and David Woodruff - On Low-Risk Heavy Hitters and Sparse Recovery Schemes.
- Aditya Krishnan, Sidhanth Mohanty and David P. Woodruff - On Sketching the q to p Norms.
10:10-10:30 Coffee Break
10:30-12:10 Session 6 (RANDOM):
- Jaroslaw Blasiok, Venkatesan Guruswami and Madhu Sudan - Polar codes with exponentially small error at finite block length
- Venkatesan Guruswami, Chaoping Xing and Chen Yuan - How long can optimal locally repairable codes be?
- Ray Li and Mary Wootters - Improved list-decodability of random linear binary codes.
- Michael Viderman - Explicit Strong LTCs with inverse poly-log rate and constant soundness.
- Laszlo Babai, Timothy Black and Angela Wuu - List-decoding homomorphism codes with arbitrary codomains.
12:10-13:30 Lunch break
13:30 - 15:10 Session 7 (APPROX):
- Richard Santiago and F. Bruce Shepherd - Multi-Agent Submodular Optimization.
- Sayan Bandyapadhyay, Neeraj Kumar, Subhash Suri and Kasturi Varadarajan - Improved Approximation Bounds for the Minimum Constraint Removal Problem.
- Goonwanth Reddy and Rahul Vaze - Robust Online Speed Scaling With Deadline Uncertainty.
- Allan Borodin, Christodoulos Karavasilis and Denis Pankratov - Greedy Bipartite Matching in Random Type Poisson Arrival Model.
- Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu and Yuhao Zhang - Online Makespan Minimization: The Power of Restart.
15:10-15:30 Coffee Break
15:30 - 16:20 Session 8: Invited talk by Ronitt Rubinfeld, MIT - "Local algorithms for sparse connected subgraphs"
16:20 - 18:00 Session 9 (RANDOM):
- Tianyu Liu - Torpid Mixing of Markov Chains for the Six-vertex Model on Z2.
- Pieter Kleer and Corrie Jacobien Carstens - Speeding up switch Markov chains for sampling bipartite graphs with given degree sequence.
- Antonio Blanca et al. - Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs.
- Peter Gracar and Alexandre Stauffer - Percolation of Lipschitz surface and tight bounds on the spread of information among mobile agents.
- Antonio Blanca, Zongchen Chen and Eric Vigoda - Swendsen-Wang Dynamics for General Graphs in the Tree Uniqueness Region.
Wednesday August 22
8:30-10:10 Session 10 (RANDOM):
- Maya Leshkowitz - Round Complexity Versus Randomness Complexity in Interactive Proofs.
- Aleksandrs Belovs - Adaptive Lower Bound for Testing Monotonicity on the Line.
- Ryan O'Donnell and Yu Zhao - On closeness to k-wise uniformity.
- Elena Grigorescu, Akash Kumar and Karl Wimmer - Flipping out with many flips: hardness of testing k-monotonicity.
- Yonatan Nakar and Dana Ron - On the Testability of Graph Partition Properties.
10:10-10:30 Coffee Break
10:30-12:10 Session 11 (APPROX):
- Ishay Haviv - On Minrank and the Lovasz Theta Function.
- Eden Chlamtac and Pasin Manurangsi - Sherali-Adams Integrality Gaps Matching the Log-Density Threshold.
- Joseph Swernofsky - Tensor Rank is Hard to Approximate.
- Suvrit Sra, Nisheeth K. Vishnoi and Ozan Yıldız - On Geodesically Convex Formulations for the Brascamp-Lieb Constant.
- Aditya Bhaskara and Srivatsan Kumar - Low Rank Approximation in the Presence of Outliers.
12:10-13:30 Lunch break
13:30 - 15:10 Session 12 (RANDOM):
- Rocco Servedio and Li-Yang Tan - Luby-Velickovic-Wigderson revisited: Improved correlation bounds and pseudorandom generators for depth-two circuits.
- Valentine Kabanets and Zhenjian Lu - Satisfiability and Derandomization for Small Polynomial Threshold Circuits.
- Kuan Cheng and Xin Li - Randomness Extraction in AC0 and with Small Locality.
- Mark Bun and Justin Thaler - Approximate Degree and the Complexity of Depth Three Circuits.
- Sajin Koroth and Or Meir - Improved composition theorems for functions and relations.
15:10-15:30 Coffee Break
15:30 - 16:20 Session 13: Invited talk by Subhash Khot, NYU - "2-to-2 Games Theorem via Expansion in the Grassmann Graph"
16:20 - 17:20 Session 14 (APPROX):
- Andreas Wiese - Fixed-parameter approximation schemes for weighted flowtime.
- Kanthi Sarpatwar, Baruch Schieber and Hadas Shachnai - Generalized Assignment of Time-Sensitive Item Groups.
- Janardhan Kulkarni and Shi Li - Flow-time Optimization For Concurrent Open-Shop and Precedence Constrained Scheduling Models.
|
|
|
|
CFP.pdf 