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
Accepted Papers
RANDOM 2017 Accepted Papers

RANDOM 2017 Accepted Papers

Abbas Mehrabian, Omer Angel and Yuval Peres. The string of diamonds is tight for rumor spreading
Sarah Cannon, David A. Levin and Alexandre Stauffer. Polynomial Mixing of the Edge-Flip Markov Chain for Unbiased Dyadic Tilings
Alan Frieze and Wesley Pegden. Traveling in randomly embedded random graphs
Jaroslaw Blasiok, Jian Ding and Jelani Nelson. Continuous monitoring of $\ell_p$ norms in data streams
Thomas Watson. Communication Complexity of Statistical Distance
V.S.P. Vijay Bhattiprolu, Venkatesan Guruswami and Euiwoong Lee. Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere
Naman Agarwal, Karthekeyan Chandrasekaran, Alexandra Kolla, Vivek Madan. On the Expansion of Group–based Lifts
Joshua Brakensiek. Vertex Isoperimetry and Independent Set Stability for Tensor Powers of Cliques
S. Luna Frank-Fischer, Venkatesan Guruswami and Mary Wootters. Locality via partially lifted codes
Noga Alon and Omri Ben-Eliezer. Efficient Removal Lemmas for Matrices
Xi Chen, Rocco Servedio, Li-Yang Tan and Erik Waingarten. Adaptivity is exponentially powerful for testing monotonicity of halfspaces
Ilya Volkovich. On some Computations on Sparse Polynomials
Alexander Golovnev, Oded Regev and Omri Weinstein. The Minrank of Random Graphs
Venkatesan Guruswami and Ray Li. Efficiently decodable codes for the binary deletion channel
Marco Carmosino, Russel Impagliazzo, Valentine Kabanets and Antonina Kolokolova. Agnostic Learning from Tolerant Natural Proofs
Dean Doron, Francois Le Gall and Amnon Ta-Shma. Probabilistic logarithmic-space algorithms for Laplacian solvers
Alessandro Chiesa, Peter Manohar and Igor Shinkar. On Axis-Parallel Tests for Tensor Product Codes
Arnab Bhattacharyya, Sivakanth Gopi and Avishay Tal. Lower bounds for 2-query LCCs over large alphabet
Anna Ben-Hamou and Yuval Peres. Cutoff for a stratified random walk on the hypercube
L. Elisa Celis, Amit Deshpande, Tarun Kathuria, Damian Straszak and Nisheeth K. Vishnoi. On the Complexity of Constrained Determinantal Point Processes
Xi Chen, Adam Freilich, Rocco Servedio and Timothy Sun. Sample-based high-dimensional convexity testing
Funda Ergun, Elena Grigorescu, Erfan Sadeqi Azer and Samson Zhou. Streaming Periodicity with Mismatches
Jess Banks, Cristopher Moore and Robert Kleinberg. The Lovasz Theta Function for Random Regular Graphs and Community Detection in the Hard Regime
Haim Avron, Ken Clarkson and David P. Woodruff. Sharper Bounds for Regularized Data Fitting
Rupam Acharyya and Daniel Stefankovic. Glauber Dynamics for Ising Model on Convergent Dense Graph Sequence
Cody Freitag, Eric Price and William Swartworth. Testing Hereditary Properties of Sequences

APPROX 2017 Accepted Papers

APPROX 2017 Accepted Papers

Chien-Chung Huang, Naonori Kakimura and Yuichi Yoshida. Streaming Algorithms for Maximizing Monotone Submodular Functions under a Knapsack Constraint
Sagar Kale and Sumedh Tirodkar. Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams
Vedat Alev and Lap Chi Lau. Approximating Unique Games Using Low Diameter Graph Decompositions
Joshua Brakensiek and Venkatesan Guruswami. The Quest for Strong Inapproximability Results with Perfect Completeness
Andreas Tönnis and Thomas Kesselheim. Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints
Glencora Borradaile and Baigong Zheng. A PTAS for Three-Edge Connectivity in Planar Graphs
Edo Liberty and Maxim Sviridenko. Greedy Minimization of Weakly Supermodular Set Functions
Anupam Gupta and Archit Karandikar. Stochastic Unsplittable Flows
David Harris, Thomas Pensyl, Aravind Srinivasan and Khoa Trinh. A Lottery Model for Center-type Problems With Outliers
Yuval Rabani and Rakesh Venkat. Approximating Sparsest Cut in Low Rank Graphs via Embeddings from Approximately Low Dimensional Spaces
Maciej Obremski and Maciej Skorski. Renyi Entropy Estimation Revisited
Klaus Jansen, Kim-Manuel Klein, Maria Kosche and Leon Ladewig. Online Strip Packing with Polynomial Migration
Zachary Friggstad, Arnoosh Golestanian, Kamyar Khodamoradi, Christopher Martin, Mirmahdi Rahgoshay, Mohsen Rezapour, Mohammad Salavatipour and Yifeng Zhang. Scheduling Problems over Network of Machines
Kristof Berczi, Karthekeyan Chandrasekaran, Tamas Kiraly, Euiwoong Lee and Chao Xu. Global and Fixed-Terminal Cuts in Digraphs
Tim Roughgarden, Inbal Talgam-Cohen and Jan Vondrák. When Are Welfare Guarantees Robust?
Samuel Haney, Debmalya Panigrahi, Rajmohan Rajaraman, Ravi Sundaram, Bruce Maggs and Biswaroop Maiti. Symmetric Interdiction for Matching Problems
Itai Ashlagi, Yossi Azar, Moses Charikar, Ashish Chiplunkar, Ofir Geri, Haim Kaplan, Rahul Makhijani, Yuyi Wang and Roger Wattenhofer. Lower Bounds and Two-Sided Markets in Min-Cost Perfect Matching with Delays
Jochen Koenemann, Neil Olver, Kanstantsin Pashkovich, R Ravi, Chaitanya Swamy and Jens Vygen. On the Integrality Gap of the Prize-Collecting Steiner Forest LP
Piotr Indyk, Sepideh Mahabadi, Ronitt Rubinfeld, Jonathan Ullman, Ali Vakilian and Anak Yodpinyanee. Fractional Set Cover in the Streaming Model
Venkatesan Guruswami, Ameya Velingker and Santhoshini Velusamy. Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph
Francisco Unda and Michel Goemans. Approximating Incremental Combinatorial Optimization Problems
Pavel Kolev, Richard Peng, Saurabh Sawlani and Gorav Jindal. Density Independent Algorithms for Sparsifying $k$-Step Random Walks