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: Semirandom NPhard 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, LiYang Tan and Erik Waingarten.
 Samplebased highdimensional convexity testing  Xi Chen, Adam Freilich, Rocco Servedio and Timothy Sun.
 When Are Welfare Guarantees Robust?  Tim Roughgarden, Inbal TalgamCohen and Jan Vondrák.
 Lower Bounds and TwoSided Markets in MinCost 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 BenEliezer.
 Probabilistic logarithmicspace algorithms for Laplacian solvers  Dean Doron, Francois Le Gall and Amnon TaShma.
 On the Expansion of Group–based Lifts  Naman Agarwal, Karthekeyan Chandrasekaran, Alexandra Kolla and Vivek Madan.
 Charting the replica symmetric phase  Amin CojaOghlan, Charilaos Efthymiou, Nor Jaafari, Mihyun Kang and Tobias Kapetanopoulos.
 Polynomial Mixing of the EdgeFlip Markov Chain for Unbiased Dyadic Tilings  Sarah Cannon, David A. Levin and Alexandre Stauffer.
 Cutoff for a stratified random walk on the hypercube  Anna BenHamou 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 PrizeCollecting 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 ThreeEdge Connectivity in Planar Graphs  Glencora Borradaile and Baigong Zheng.
 Approximating Incremental Combinatorial Optimization Problems  Francisco Unda and Michel Goemans.
 SumofSquares 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 AxisParallel 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, KimManuel Klein, Maria Kosche and Leon Ladewig.
 A Lottery Model for Centertype Problems With Outliers  David Harris, Thomas Pensyl, Aravind Srinivasan and Khoa Trinh.
 Communication Complexity of Statistical Distance  Thomas Watson.
 Lower bounds for 2query 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  ChienChung 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: HashingbasedEstimators 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 kStep Random Walks  Pavel Kolev, Richard Peng, Saurabh Sawlani and Gorav Jindal.
 Locality via partially lifted codes  S. Luna FrankFischer, 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 FixedTerminal 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:008:30 Registration 8:309:45 Session 1 (APPROX): 9:4510:00 Coffee Break 10:0011:15 Session 2 (RANDOM): 11:15  12:15 Session 3: Invited talk by Uriel Feige 12:1513: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:0020:00 – Reception at the Theory Lounge (Soda Hall – 6th floor) Thursday August 17
8:3010:10 Session 7 (RANDOM): 10:1010:30 Coffee Break 10:3012:10 Session 8 (APPROX): 12:1013: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:309:45 Session 12 (APPROX): 9:4510:00 Coffee Break 10:0011: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 (nonparametric 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 nearlinear 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:1513: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): 
