Program Committee


Nikhil Bansal (Eindhoven)
Siu On Chan (CUHK)
Moses Charikar (Stanford)
Michel Goemans (MIT)
Venkatesan Guruswami (CMU)
Sungjin Im (UC Merced)
Sanjeev Khanna (U Penn)
Jochen Koenemann (Waterloo)
Shi Li (Buffalo)
Nicole Megow (Bremen)
Viswanath Nagarajan (Michigan)
Laura Sanità (Waterloo)
Ola Svensson (EPFL)
Seeun William Umboh (Eindhoven)
David Williamson (Cornell, CHAIR)
Anke van Zuylen (William and Mary)


Shipra Agrawal (Columbia)
Arnab Bhattacharya (IISc)
Sebastien Bubeck (MSR)
Alan Frieze (CMU)
Anna Gilbert (Michigan)
Thomas Hansen (Aarhus)
Anna Karlin (UW)
Yin Tat Lee (MSR and UW)
Adam Marcus (Princeton)
Ankur Moitra (MIT)
Richard Peng (GaTech)
Will Perkins (Birmingham)
Barna Saha (UMass)
Alistair Sinclair (Berkeley)
Santosh Vempala (GaTech, CHAIR)
David Woodruff (IBM Almaden)

Program Chairs

David Williamson
Cornell, USA

Santosh Vempala
Gatech, USA

Local Organizing Committee Chair
Neha Dave
Berkeley, USA

Workshop Chairs

José Rolim,
U. of Geneva
Klaus Jansen,
U. of Kiel

Local Organisation

Important dates
Submission deadline
Friday, April 21, 2017
15:00 PDT

Notification to authors
By June 2, 2017

Camera ready
June 19, 2017

August 16-18, 2017
Call for papers


    APPROX + RANDOM 2017 Program

    HP Auditorium 306 Soda Hall

      Wednesday August 16

      8:00-8:30 Registration

      8:30-9:45 Session 1 (APPROX):

    • 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.

    • 9:45-10:00 Coffee Break

      10:00-11:15 Session 2 (RANDOM):

    • 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.

    • 11:15 - 12:15 Session 3: Invited talk by Uriel Feige

    • Title: Semi-random NP-hard problems

    • 12:15-13:30 Lunch break

      13:30 - 14:45 Session 4 (RANDOM):

    • 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.

    • 14:45 - 16:00 Session 5 (APPROX):

    • 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.

    • 16:00 - 16:20 Coffee break

      16:20 - 18:00 Session 6 (RANDOM):

    • 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.

    • 18:00-20:00 – Reception at the Theory Lounge (Soda Hall – 6th floor)

      Thursday August 17

      8:30-10:10 Session 7 (RANDOM):

    • 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.

    • 10:10-10:30 Coffee Break

      10:30-12:10 Session 8 (APPROX):

    • 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.

    • 12:10-13:30 Lunch break

      13:30 - 14:45 Session 9 (RANDOM):

    • 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.

    • 14:45 - 16:00 Session 10 (APPROX):

    • 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.

    • 16:00 - 16:20 Coffee break

      16:20 - 18:00 Session 11 (RANDOM):

    • 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.

    • Friday August 18

      8:30-9:45 Session 12 (APPROX):

    • 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.

    • 9:45-10:00 Coffee Break

      10:00-11:15 Session 13 (RANDOM):

    • 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.

    • 11:15 - 12:15 Session 14: Invited talk by Moses Charikar

    • Old Dog, New Tricks: Hashing-based-Estimators for Kernel Density in High Dimensions

    • 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):

    • 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.

    • 14:45 - 16:00 Session 15 (RANDOM):

    • 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.

    • 16:00 - 16:20 Coffee break

      16:20 - 17:35 Session 16 (APPROX):

    • 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.