CFP.pdf 
CFP.doc
Program
- Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph - Venkatesan Guruswami, Ameya Velingker and Santhoshini Velusamy.
- Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams - Sagar Kale and Sumedh Tirodkar.
- Fractional Set Cover in the Streaming Model - Piotr Indyk, Sepideh Mahabadi, Ronitt Rubinfeld, Jonathan Ullman, Ali Vakilian and Anak Yodpinyanee.
- Continuous monitoring of ℓp norms in data streams - Jaroslaw Blasiok, Jian Ding and Jelani Nelson.
- Streaming Periodicity with Mismatches - Funda Ergun, Elena Grigorescu, Erfan Sadeqi Azer and Samson Zhou.
- Sharper Bounds for Regularized Data Fitting - Haim Avron, Ken Clarkson and David P. Woodruff.
- Title: Semi-random NP-hard problems
- Testing Hereditary Properties of Sequences - Cody Freitag, Eric Price and William Swartworth.
- Adaptivity is exponentially powerful for testing monotonicity of halfspaces - Xi Chen, Rocco Servedio, Li-Yang Tan and Erik Waingarten.
- Sample-based high-dimensional convexity testing - Xi Chen, Adam Freilich, Rocco Servedio and Timothy Sun.
- When Are Welfare Guarantees Robust? - Tim Roughgarden, Inbal Talgam-Cohen and Jan Vondrák.
- Lower Bounds and Two-Sided Markets in Min-Cost Perfect Matching with Delay - Itai Ashlagi, Yossi Azar, Moses Charikar, Ashish Chiplunkar, Ofir Geri, Haim Kaplan, Rahul Makhijani, Yuyi Wang and Roger Wattenhofer.
- Symmetric Interdiction for Matching Problems - Samuel Haney, Bruce Maggs, Biswaroop Maiti, Debmalya Panigrahi, Rajmohan Rajaraman, Ravi Sundaram.
- Efficient Removal Lemmas for Matrices - Noga Alon and Omri Ben-Eliezer.
- Probabilistic logarithmic-space algorithms for Laplacian solvers - Dean Doron, Francois Le Gall and Amnon Ta-Shma.
- On the Expansion of Group–based Lifts - Naman Agarwal, Karthekeyan Chandrasekaran, Alexandra Kolla and Vivek Madan.
- Charting the replica symmetric phase - Amin Coja-Oghlan, Charilaos Efthymiou, Nor Jaafari, Mihyun Kang and Tobias Kapetanopoulos.
- Polynomial Mixing of the Edge-Flip Markov Chain for Unbiased Dyadic Tilings - Sarah Cannon, David A. Levin and Alexandre Stauffer.
- Cutoff for a stratified random walk on the hypercube - Anna Ben-Hamou and Yuval Peres.
- Glauber Dynamics for Ising Model on Convergent Dense Graph Sequence - Rupam Acharyya and Daniel Stefankovic.
- On the Complexity of Constrained Determinantal Point Processes - L. Elisa Celis, Amit Deshpande, Tarun Kathuria, Damian Straszak and Nisheeth K. Vishnoi.
- On the Integrality Gap of the Prize-Collecting Steiner Forest LP - Jochen Koenemann, Neil Olver, Kanstantsin Pashkovich, R Ravi, Chaitanya Swamy and Jens Vygen.
- Stochastic Unsplittable Flows - Anupam Gupta and Archit Karandikar.
- A PTAS for Three-Edge Connectivity in Planar Graphs - Glencora Borradaile and Baigong Zheng.
- Approximating Incremental Combinatorial Optimization Problems - Francisco Unda and Michel Goemans.
- Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere - V.S.P. Vijay Bhattiprolu, Venkatesan Guruswami and Euiwoong Lee.
- Vertex Isoperimetry and Independent Set Stability for Tensor Powers of Cliques - Joshua Brakensiek.
- On Axis-Parallel Tests for Tensor Product Codes - Alessandro Chiesa, Peter Manohar and Igor Shinkar.
- Scheduling Problems over Network of Machines - Zachary Friggstad, Arnoosh Golestanian, Kamyar Khodamoradi, Christopher Martin, Mirmahdi Rahgoshay, Mohsen Rezapour, Mohammad Salavatipour and Yifeng Zhang.
- Online Strip Packing with Polynomial Migration - Klaus Jansen, Kim-Manuel Klein, Maria Kosche and Leon Ladewig.
- A Lottery Model for Center-type Problems With Outliers - David Harris, Thomas Pensyl, Aravind Srinivasan and Khoa Trinh.
- Communication Complexity of Statistical Distance - Thomas Watson.
- Lower bounds for 2-query LCCs over large alphabet - Arnab Bhattacharyya, Sivakanth Gopi and Avishay Tal.
- Agnostic Learning from Tolerant Natural Proofs - Marco Carmosino, Russel Impagliazzo, Valentine Kabanets and Antonina Kolokolova.
- The string of diamonds is tight for rumor spreading - Abbas Mehrabian, Omer Angel and Yuval Peres.
- Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints - Andreas Tönnis and Thomas Kesselheim.
- Greedy Minimization of Weakly Supermodular Set Functions - Edo Liberty and Maxim Sviridenko.
- Streaming Algorithms for Maximizing Monotone Submodular Functions under a Knapsack Constraint - Chien-Chung Huang, Naonori Kakimura and Yuichi Yoshida.
- Traveling in randomly embedded random graphs - Alan Frieze and Wesley Pegden.
- The Minrank of Random Graphs - Alexander Golovnev, Oded Regev and Omri Weinstein.
- The Lovasz Theta Function for Random Regular Graphs and Community Detection in the Hard Regime - Jess Banks, Cristopher Moore and Robert Kleinberg.
- Old Dog, New Tricks: Hashing-based-Estimators for Kernel Density in High Dimensions
- Renyi Entropy Estimation Revisited - Maciej Obremski and Maciej Skorski.
- The Quest for Strong Inapproximability Results with Perfect Completeness - Joshua Brakensiek and Venkatesan Guruswami.
- Density Independent Algorithms for Sparsifying k-Step Random Walks - Pavel Kolev, Richard Peng, Saurabh Sawlani and Gorav Jindal.
- Locality via partially lifted codes - S. Luna Frank-Fischer, Venkatesan Guruswami and Mary Wootters.
- Efficiently decodable codes for the binary deletion channel - Venkatesan Guruswami and Ray Li.
- On some Computations on Sparse Polynomials - Ilya Volkovich.
- Approximating Unique Games Using Low Diameter Graph Decompositions - Vedat Alev and Lap Chi Lau.
- Global and Fixed-Terminal Cuts in Digraphs - Kristof Berczi, Karthekeyan Chandrasekaran, Tamas Kiraly, Euiwoong Lee and Chao Xu.
- Approximating Sparsest Cut in Low Rank Graphs via Embeddings from Approximately Low Dimensional Spaces - Yuval Rabani and Rakesh Venkat.
|
APPROX + RANDOM 2017 Program HP Auditorium 306 Soda HallWednesday August 16 8:00-8:30 Registration 8:30-9:45 Session 1 (APPROX): 9:45-10:00 Coffee Break 10:00-11:15 Session 2 (RANDOM): 11:15 - 12:15 Session 3: Invited talk by Uriel Feige 12:15-13:30 Lunch break 13:30 - 14:45 Session 4 (RANDOM): 14:45 - 16:00 Session 5 (APPROX): 16:00 - 16:20 Coffee break 16:20 - 18:00 Session 6 (RANDOM): 18:00-20:00 – Reception at the Theory Lounge (Soda Hall – 6th floor) Thursday August 17
8:30-10:10 Session 7 (RANDOM): 10:10-10:30 Coffee Break 10:30-12:10 Session 8 (APPROX): 12:10-13:30 Lunch break 13:30 - 14:45 Session 9 (RANDOM): 14:45 - 16:00 Session 10 (APPROX): 16:00 - 16:20 Coffee break 16:20 - 18:00 Session 11 (RANDOM): Friday August 18
8:30-9:45 Session 12 (APPROX): 9:45-10:00 Coffee Break 10:00-11:15 Session 13 (RANDOM): 11:15 - 12:15 Session 14: Invited talk by Moses Charikar Abstract: Given a set of points in d dimensions, imagine putting a Gaussian distribution around each of them. How quickly can we evaluate the sum of these Gaussian densities at a new point? This computational problem (and its generalization for densities other than the Gaussian) is called kernel density estimation. This problem arises as a basic primitive in statistics (non-parametric density estimation), machine learning (kernel methods) and scientific computing (physical simulations). The batch version of this question (compute the sum of n kernels at m given query points) is addressed by the celebrated fast multiple method from the late 80s which has linear or near-linear complexity for points in 2 and 3 dimensions. The high dimensional case has been challenging because at a high level, typical space partitioning approaches have an exponential dependence on the dimension. In this talk, I will show that locality sensitive hashing (introduced in the late 90s for the approximate nearest neighbor problem in high dimensions) can be adapted to devise unbiased estimators for kernel density in high dimensions. 12:15-13:30 Lunch break 13:30 - 14:45 Session 14 (APPROX): 14:45 - 16:00 Session 15 (RANDOM): 16:00 - 16:20 Coffee break 16:20 - 17:35 Session 16 (APPROX): |
|