Navigation

Program Committee


APPROX

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)

RANDOM

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


APPROX
Claire Mathieu
CNRS and École Normale Supérieure Paris
cmathieu@di.ens.fr

RANDOM
Chris Umans
Caltech
umans@cs.caltech.edu

Workshop Chairs


José Rolim,
U. of Geneva
jose.rolim@unige.ch
Klaus Jansen,
U. of Kiel
kj@informatik.uni-kiel.de
                                                      


Local Organisation


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

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


Notification to authors
By June 22, 2016

Camera ready
July 1, 2016

Conference
Sept 7-9, 2016
Call for papers
IRIF

CNRS

Université Paris Diderot - Paris 7

FILOFOCS

IHP

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