Program Committee


Andreas Wiese
Fabrizio Grandoni
Parinya Chalermsook
Harald Raecke
Chaitanya Swamy
Nicole Megow
Amit Kumar
Lap Chi Lau
Roy Schwarz
Rene Sitters
David Steurer
Sungjin Im
Michael Dinitz
Rishi Saket
Piotr Sankowski
Naveen Garg


Alex Andoni
Aleksander Madry
Anindya De
David Woodruff
Dimitris Achlioptas
Madur Tulsiani
Mohit Singh
Nick Harvey
Raghu Meka
Xin Li
Eric Price
Mary Wootters
Aaron Roth
Hu Fu
Ken Clarkson
Ali Sinop

Program Chairs

Naveen Garg,
IIT Delhi

Anup Rao,
University of Washington

Workshop Chairs

José Rolim,
U. of Geneva
Klaus Jansen,
U. of Kiel
Important dates
Submission deadline
April 17, 2015

Notification to authors
June 8, 2015

Camera ready
June 24, 2015

August 24-26, 2015
Call for papers


    APPROX + RANDOM 2015 Program

    (download the program in PDF here)

      Monday August 24

      8:00-8:25 Registration

      8:25-8:30 Welcome

      8:30-9:25 Session 1: Invited talk from Raghu Meka (University of California, Los Angeles)

      "Pseudorandomness - old problems, new methods, and current challenges"

      The focus of this talk will be the survey of recent results related to two classical questions in complexity theory: derandomizing small-space algorithms and lower bounds for constant-depth circuits. Along the way, two recent techniques will be highlighted ---"mild pseudorandom restrictions" and "iterative dimension reduction"---for building pseudorandom generators (PRGs) leading up to nearly-optimal PRGs for halfspaces and read-once CNFs. There will be also emphasis on a few open problems and challenges (among many) that seem to test the limits of our knowledge and tools in derandomization.

      9:25-9:45 Coffee Break

      9:45-10:50 Session 2: RANDOM

    • Dynamics for the mean-field random-cluster model - Antonio Blanca and Alistair Sinclair.
    • Swendsen-Wang Algorithm on the Mean-Field Potts Model - Andreas Galanis, Daniel Stefankovic and Eric Vigoda.
    • Harnessing the Bethe free energy - Victor Bapst and Amin Coja-Oghlan.

    • 10:55 - 12:00 Session 3: APPROX

    • Improved NP-inapproximability for 2-variable linear equations - Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O'Donnell and John Wright
    • Inapproximability of H-Transversal/Packing - Venkatesan Guruswami and Euiwoong Lee.
    • Approximate Hypergraph Coloring under Low-discrepancy and Related Promises - V.S.P. Vijay Bhattiprolu, Venkatesan Guruswami and Euiwoong Lee.

    • 12:05 - 13:10 Session 4: RANDOM

    • Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness - Mark Bun and Thomas Steinke.
    • Towards Resistance Sparsifiers - Michael Dinitz, Robert Krauthgamer and Tal Wagner.
    • Spectral Norm of Random Kernel Matrices with Applications to Privacy - Shiva Kasiviswanathan and Mark Rudelson.

    • 13:10-14:30 Lunch break

      14:30 - 15:35 Session 5: APPROX

    • Towards a Characterization of Approximation Resistance for Symmetric CSPs - Venkatesan Guruswami and Euiwoong Lee.
    • Approximating Dense Max 2-CSPs - Pasin Manurangsi and Dana Moshkovitz.
    • Beating the random assignment on constraint satisfaction problems of bounded degree - Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer and John Wright.

    • 15:35 - 15:55 Coffee break

      15:55 - 17:00 Session 6: RANDOM

    • On Constant Size Graphs That Preserve the Local Structure of High Girth Graphs - Hendrik Fichtenberger, Pan Peng and Christian Sohler.
    • Average Distance Queries through Weighted Samples in Graphs and Metric Spaces: High Scalability with Tight Statistical Guarantees - Shiri Chechik, Edith Cohen and Haim Kaplan.
    • A Chasm Between Identity and Equivalence Testing with Conditional Queries - Jayadev Acharya, Clément Canonne and Gautam Kamath.

    • 17:00 - 18:30 Session 7: APPROX

    • Stochastic and Robust Scheduling in the Cloud - Lin Chen, Nicole Megow, Roman Rischke and Leen Stougie.
    • Minimizing maximum flow-time on related machines - Bouke Cloostermans and Nikhil Bansal.
    • A 2-Competitive Algorithm For Online Convex Optimization With Switching CostsNikhil Bansal, Anupam Gupta, Ravishankar Krishnaswamy, Kirk Pruhs, Kevin Schewior and Clifford Stein.
    • The Container Selection Problem - Viswanath Nagarajan, Kanthi Sarpatwar, Baruch Schieber, Hadas Shachnai and Joel Wolf.

    • Tuesday August 25

      8:30-9:25 Session 8: Invited talk from R. Ravi (Carnegie Mellon University)

      " Improved Approximations for Graph-TSP in Regular Graphs"

      A tour in a graph is a connected walk that visits every vertex at least once, and returns to the starting vertex. We describe improved approximation results for a tour with the minimum number of edges in regular graphs. En route we illustrate the main ideas used recently in designing improved approximation algorithms for graph TSP.

      9:25-9:45 Coffee Break

      9:45-10:50 Session 9: APPROX

    • On Linear Programming Relaxations for Unsplittable Flow in Trees - Zachary Friggstad and Zhihan Gao.
    • On Approximating Node-Disjoint Paths in Grids - Julia Chuzhoy and David Kim.
    • Terminal Embeddings - Michael Elkin, Arnold Filtser and Ofer Neiman.

    • 10:55 - 12:00 Session 10: RANDOM

    • Deletion codes in the high-noise and high-rate regimes - Venkatesan Guruswami and Carol Wang.
    • Communication with partial noiseless feedback - Bernhard Haeupler, Pritish Kamath and Ameya Velingker.
    • On Fortification of Projection Games - Amey Bhangale, Ramprasad Saptharishi, Girish Varma and Rakesh Venkat.

    • 12:05 - 13:10 Session 11: APPROX

    • Fully Dynamic Bin Packing Revisited - Sebastian Berndt, Klaus Jansen and Kim-Manuel Klein.
    • How to Tame Rectangles: Solving Independent Set and Coloring of Rectangles via Shrinking - Anna Adamaszek, Parinya Chalermsook and Andreas Wiese.
    • SOn guillotine cutting sequences - Fidaa Abed, Parinya Chalermsook, Jose Correa, Andreas Karrenbauer, Pablo Perez-Lantero, Jose Soto and Andreas Wiese.

    • 13:10-14:30 Lunch break

      14:30 - 15:35 Session 12: RANDOM

    • A randomized online quantile summary in $O(\frac{1}{\varepsilon} \log \frac{1}{\varepsilon})$ words - David Felber and Rafail Ostrovsky.
    • A Zero-One Laws for Sliding Windows and Universal Sketches - Vladimir Braverman, Rafail Ostrovsky and Alan Roytman.
    • Universal sketches for the frequency negative moments and other decreasing streaming sums - Stephen Chestnut and Vladimir Braverman.

    • 15:35 - 15:55 Coffee break

      15:55 - 17:00 Session 13: APPROX

    • Approximating Hit Rate Curves using Streaming Algorithms - Zachary Drudi, Nicholas Harvey, Stephen Ingram, Andrew Warfield and Jake Wires.
    • Tight Bounds for Graph Problems in Insertion Streams - Xiaoming Sun and David Woodruff.
    • Large Supports are required for Well-Supported Nash Equilibria - Yogesh Anbalagan, Hao Huang, Shachar Lovett, Sergey Norin, Adrian Vetta and Hehui Wu.

    • 17:00 - 18:30 Session 14: RANDOM

    • Separating decision tree complexity from subcube partition complexity - Robin Kothari, David Racicot-Desloges and Miklos Santha.
    • Internal compression of protocols to entropy - Shay Moran, Amir Yehudayoff and Balthazar Bauer.
    • Correlation in Hard Distributions in Communication Complexity - Dmitry Gavinsky, Hartmut Klauck and Ralph Bottesch.
    • Dependent Random Graphs and Multiparty Pointer Jumping - Joshua Brody and Mario Sanchez.

    • 18:30 - 20:00 Reception

      Wednesday August 26
      8:30-9:55 Session 15: RANDOM

    • Deterministically Factoring Sparse Polynomials into Multilinear Factors and Sums of Univariate Polynomials - Ilya Volkovich.
    • Two Structural Results for Low Degree Polynomials and Applications - Gil Cohen and Avishay Tal.
    • Decomposing Overcomplete 3rd Order Tensors using Sum-of-Squares Algorithms - Rong Ge and Tengyu Ma.
    • Dimension Expanders via Rank Condensers - Michael A. Forbes and Venkatesan Guruswami.

    • 9:55 - 10:15 Coffee break

      10:15 - 11:40 Session 16: APPROX

    • Improved Bounds in Stochastic Matching and Optimization - Alok Baveja, Amit Chavan, Andrei Nikiforov, Aravind Srinivasan and Pan Xu.
    • A Tight Approximation Bound for the Stable Marriage Problem with Restricted Ties - Chien-Chung Huang, Kazuo Iwama, Shuichi Miyazaki and Hiroki Yanagisawa.
    • Approximate Nearest Neighbor Search in Metrics of Planar Graphs - Ittai Abraham, Shiri Chechik, Robert Krauthgamer and Udi Wieder
    • Non-Uniform Robust Network Design in Planar Graphs - David Adjiashvili.

    • 11:45 - 12:50 Session 17: RANDOM

    • Learning circuits with few negations - Eric Blais, Clément Canonne, Igor Carboni Oliveira, Rocco Servedio and Li-Yang Tan.
    • Negation-Limited Formulas - Siyao Guo and Ilan Komargodski.
    • Tighter Connections between Derandomization and Circuit Lower Bounds - Marco Carmosino, Russell Impagliazzo, Valentine Kabanets and Antonina Kolokolova.

    • 12:50-14:00 Lunch break

      14:00 - 15:05 Session 18: APPROX

    • Designing Overlapping Networks for Publish-Subscribe Systems - Jennifer Iglesias, Rajmohan Rajaraman, R. Ravi and Ravi Sundaram.
    • Approximating Upper Degree-Constrained Partial Orientations - Marek Cygan and Tomasz Kociumaka.
    • Sequential Importance Sampling Algorithms for Estimating the All-Terminal Reliability Polynomial of Sparse Graphs - David Harris and Francis Sullivan.

    • 15:10 - 16:35 Session 19: RANDOM

    • The minimum bisection in the planted bisection model - Amin Coja-Oghlan, Oliver Cooley, Mihyun Kang and Kathrin Skubch.
    • Local convergence of random graph colorings - Amin Coja-Oghlan, Charilaos Efthymiou and Nor Jaafari.
    • Reconstruction/Non-reconstruction Thresholds for Colourings of General Galton-Watson Trees - Charilaos Efthymiou.
    • Distance-based species tree estimation: information-theoretic trade-off between number of loci and sequence length under the coalescent - Elchanan Mossel and Sebastien Roch.


Valid XHTML 1.0 Transitional Valid CSS!

Created by Marios Karagiannis - Maintained by Orestis Evangelatos