Program Committee


Anna Adamaszek (Copenhagen)
Shiri Chechik (Tel Aviv)
Anne Driemel (TUE)
Lee-Ad Gottlieb (Ariel)
Varun Kanade (Oxford)
Nitish Korula (Google)
Stefano Leonardi (Sapienza)
Daniel Lokshtanov (Bergen)
Claire Mathieu (ENS Paris, chair)
Nicole Megow (TUM)
Tobias Moemke (Saarland)
Shayan Oveis Gharan (Washington)
Debmalya Panigrahi (Duke)
Richard Peng (Georgia Tech)
Ely Porat (Bar-Ilan)
Adi Rosén (CNRS & Paris 7)
Adrian Vetta (McGill)
Rico Zenklusen (ETH Zurich)


Mahdi Cheraghchi (Imperial College, London)
Elena Grigorescu (Purdue)
Neeraj Kayal (MSR Bangalore)
Adam Klivans (Austin)
Swastik Kopparty (Rutgers)
Ravi Kumar (Google)
Dana Moshkovitz (MIT)
Ashwin Nayak (Waterloo)
Ryan O'Donnell (CMU)
Asaf Shapira (Tel Aviv)
Ronen Shaltiel (Haifa)
Alexander Sherstov (UCLA)
Thomas Thierauf (Aalen)
Chris Umans (Caltech, chair)
Eric Vigoda (Georgia Tech)

Program Chairs

Claire Mathieu
CNRS and École Normale Supérieure Paris

Chris Umans

Workshop Chairs

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

Local Organisation

Sophie Laplante
Frédéric Magniez
Marc Renault
Adi Rosén, chair                                            

Important dates
Submission deadline
Tues, April 19, 2016
15:00 PDT

Notification to authors
By June 22, 2016

Camera ready
July 1, 2016

Sept 7-9, 2016
Call for papers


Université Paris Diderot - Paris 7



Accepted Papers

Accepted Papers for Approx 2016
  • Noah Stephens-Davidowitz.
    Search-to-Decision Reductions for Lattice Problems with Approximation Factors (Slightly) Greater Than One

  • Guy Kortsarz and Zeev Nutov.
    LP-relaxations for Tree Augmentation

  • Nir Halman.
    A Deterministic Fully Polynomial Time Approximation Scheme For Counting Integer Knapsack Solutions Made Easy

  • Pasin Manurangsi, Preetum Nakkiran and Luca Trevisan.
    Near-Optimal UGC-hardness of Approximating Max \(k\)-CSP\(_R\)

  • Konstantin Makarychev, Yury Makarychev, Maxim Sviridenko and Justin Ward.
    A Bi-Criteria Approximation Algorithm for \(k\)-Means

  • Ivan Bliznets, Marek Cygan, Paweł Komosa and Michał Pilipczuk.
    Hardness of Approximation for H-free Edge Modification Problems

  • Andrew McGregor and Sofya Vorotnikova.
    Planar Matching in Streams Revisited

  • Lin Chen, Deshi Ye and Guochuan Zhang.
    Approximation Algorithms for Parallel Machine Scheduling with Speed-up Resources

  • Amitabh Basu, Michael Dinitz and Xin Li.
    Computing approximate PSD factorizations

  • Sharath Raghvendra.
    Robust and Optimal Online Algorithm for Minimum Metric Bipartite Matching

  • Michael B. Cohen, Cameron Musco and Jakub Pachocki.
    Online Row Sampling

  • Ridwan Syred and Madhur Tulsiani.
    Proving Weak Approximability without Algorithms

  • Uriel Feige, Michal Feldman and Inbal Talgam-Cohen.
    Oblivious Rounding and the Integrality Gap

  • Anthony Kim, Vahid Liaghat, Junjie Qin and Amin Saberi.
    Online Energy Storage Management: an Algorithmic Approach

  • Daniel Marx, Ario Salmasi and Anastasios Sidiropoulos.
    Constant-Factor Approximations for Asymmetric TSP on Nearly-Embeddable Graphs

  • Sungjin Im, Janardhan Kulkarni, Benjamin Moseley and Kamesh Munagala.
    A Competitive Flow Time Algorithm for Heterogeneous Clusters under Polytope Constraints

  • Eden Chlamtac, Michael Dinitz, Christian Konrad, Guy Kortsarz and George Rabanca.
    The Densest \(k\)-Subhypergraph Problem

  • Samir Khuller and Sheng Yang.
    Revisiting Connected Dominating Sets: An Optimal Local Algorithm?

  • Arturs Backurs and Anastasios Sidiropoulos.
    Constant-distortion embeddings of Hausdorff metrics into constant-dimensional \(\ell_p\) spaces

  • Moses Charikar, Yonatan Naamad and Anthony Wirth.
    On Approximating Target Set Selection

Accepted Papers for Random 2016
  • Victor Bapst and Amin Coja-Oghlan.
    The Condensation Phase Transition in the Regular \(k\)-SAT Model

  • Renjie Song, Yitong Yin and Jinman Zhao.
    Counting Hypergraph Matchings up to Uniqueness Threshold

  • Yitong Yin and Chihao Zhang.
    Sampling in Potts Model on Sparse Random Graphs

  • Jan Hązła, Thomas Holenstein and Elchanan Mossel.
    Lower Bounds on Same-Set Inner Product in Correlated Spaces

  • Heng Guo and Pinyan Lu.
    Uniqueness, Spatial Mixing, and Approximation for Ferromagnetic 2-Spin Systems

  • Esther Ezra and Shachar Lovett.
    On the Beck-Fiala Conjecture for Random Set Systems

  • Subhash Khot and Igor Shinkar.
    An \(\tilde{O}(n)\) Queries Adaptive Tester for Unateness

  • Varun Kanade, Nikos Leonardos and Frederic Magniez.
    Stable Matching with Evolving Preferences

  • Cyril Nicaud.
    Fast Synchronization of Random Automata

  • Prahladh Harsha and Srikanth Srinivasan.
    On Polynomial Approximations to AC\(^0\)

  • Ravi Boppana, Johan Hastad, Chin Ho Lee and Emanuele Viola.
    Bounded Independence vs Moduli

  • Anup Rao and Makrand Sinha.
    A Direct-sum Theorem for Read-Once Branching Programs

  • Vladimir Braverman, Alan Roytman and Greg Vorsanger.
    Approximating Subadditive Hadamard Functions on Implicit Matrices

  • Arnab Bhattacharyya, Abhishek Bhowmick and Chetan Gupta.
    Higher-order Fourier Analysis over non-prime fields

  • Yi Li and David P. Woodruff.
    Tight Bounds for Sketching the Operator Norm, Schatten Norms, and Subspace Embeddings

  • Reut Levi, Dana Ron and Ronitt Rubinfeld.
    A Local Algorithm for Constructing Spanners in Minor-Free Graphs

  • Jasine Babu, Areej Khoury and Ilan Newman.
    Every Property of Outerplanar Graphs is Testable

  • Ronen Shaltiel and Jad Silbak.
    Explicit List-Decodable Codes with Optimal Rate for Computationally Bounded Channels

  • Bernd Gärtner and Antonis Thomas.
    The Niceness of Unique Sink Orientations

  • Ryuhei Mori and David Witmer.
    Lower Bounds for CSP Refutation by SDP Hierarchies

  • Dana Moshkovitz, Govind Ramnarayan and Henry Yuen.
    A No-Go Theorem for Derandomized Parallel Repetition: Beyond Feige-Kilian

  • Amin Coja-Oghlan and Will Perkins.
    Belief Propagation on Replica Symmetric Random Factor Graph Models

  • Guillaume Chapuy and Guillem Perarnau.
    Local Convergence and Stability of Tight Bridge-Addable Graph Classes

  • Pooya Hatami.
    On the Structure of Quintic Polynomials

  • Aaron Potechin and Dhruv Medarametla.
    Bounds on the Norms of Uniform Low Degree Graph Matrices

  • Carlos Hoppen, Richard Lang, Hanno Lefmann, Yoshiharu Kohayakawa and Henrique Stagni.
    Estimating Parameters Associated with Monotone Properties

  • Daniel Dadush, Aleksandr Nikolov, Shachar Lovett and Shashwat Garg.
    Towards a Constructive Version of Banaszczyk's Vector Balancing Theorem

Valid XHTML 1.0 Transitional Valid CSS!

Created by Marios Karagiannis - Maintained by Marc Renault and Orestis Evangelatos