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
Accepter Papers
Accepted papers in Random - Papers

  • A Chasm Between Identity and Equivalence Testing with Conditional Queries
    Jayadev Acharya, Clément Canonne and Gautam Kamath

  • Dynamics for the mean-field random-cluster model
    Antonio Blanca and Alistair Sinclair

  • The minimum bisection in the planted bisection model
    Amin Coja-Oghlan, Oliver Cooley, Mihyun Kang and Kathrin Skubch

  • Decomposing Overcomplete 3rd Order Tensors using Sum-of-Squares Algorithms
    Rong Ge and Tengyu Ma

  • Average Distance Queries through Weighted Samples in Graphs and Metric Spaces: High Scalability with Tight Statistical Guarantees
    Shiri Chechik, Edith Cohen and Haim Kaplan

  • Learning circuits with few negations
    Eric Blais, Clément Canonne, Igor Carboni Oliveira, Rocco Servedio and Li-Yang Tan

  • Separating decision tree complexity from subcube partition complexity
    Robin Kothari, David Racicot-Desloges and Miklos Santha

  • Deterministically Factoring Sparse Polynomials into Multilinear Factors and Sums of Univariate Polynomials
    Ilya Volkovich

  • 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

  • Zero-One Laws for Sliding Windows and Universal Sketches
    Vladimir Braverman, Rafail Ostrovsky and Alan Roytman

  • Spectral Norm of Random Kernel Matrices with Applications to Privacy
    Shiva Kasiviswanathan and Mark Rudelson

  • Distance-based species tree estimation: information-theoretic trade-off between number of loci and sequence length under the coalescent
    Elchanan Mossel and Sebastien Roch

  • A randomized online quantile summary in $O(\frac{1}{\varepsilon} \log \frac{1}{\varepsilon})$ words
    David Felber and Rafail Ostrovsky

  • Two Structural Results for Low Degree Polynomials and Applications
    Gil Cohen and Avishay Tal

  • Local convergence of random graph colorings
    Amin Coja-Oghlan, Charilaos Efthymiou and Nor Jaafari

  • Tighter Connections between Derandomization and Circuit Lower Bounds
    Marco Carmosino, Russell Impagliazzo, Valentine Kabanets and Antonina Kolokolova

  • Correlation in Hard Distributions in Communication Complexity
    Dmitry Gavinsky, Hartmut Klauck and Ralph Bottesch

  • Communication with partial noiseless feedback
    Bernhard Haeupler, Pritish Kamath and Ameya Velingker

  • On Constant Size Graphs That Preserve the Local Structure of High Girth Graphs
    Hendrik Fichtenberger, Pan Peng and Christian Sohler

  • Dimension Expanders via Rank Condensers
    Michael A. Forbes and Venkatesan Guruswami

  • Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness
    Mark Bun and Thomas Steinke

  • 24. Internal compression of protocols to entropy
    Shay Moran, Amir Yehudayoff and Balthazar Bauer

  • Deletion codes in the high-noise and high-rate regimes
    Venkatesan Guruswami and Carol Wang

  • Towards Resistance Sparsifiers
    Michael Dinitz, Robert Krauthgamer and Tal Wagner

  • Universal sketches for the frequency negative moments and other decreasing streaming sums
    Stephen Chestnut and Vladimir Braverman

  • Reconstruction/Non-reconstruction Thresholds for Colourings of General Galton-Watson Trees
    Charilaos Efthymiou

  • On Fortification of Projection Games
    Amey Bhangale, Ramprasad Saptharishi, Girish Varma and Rakesh Venkat

  • Negation-Limited Formulas
    Siyao Guo and Ilan Komargodski

  • Dependent Random Graphs and Multiparty Pointer Jumping
    Joshua Brody and Mario Sanchez

Accepted papers in Approx - Papers

  • Improved NP-inapproximability for 2-variable linear equations
    Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O'Donnell and John Wright

  • On Linear Programming Relaxations for Unsplittable Flow in Trees
    Zachary Friggstad and Zhihan Gao

  • Fully Dynamic Bin Packing Revisited
    Sebastian Berndt, Klaus Jansen and Kim-Manuel Klein

  • Sequential Importance Sampling Algorithms for Estimating the All-Terminal Reliability Polynomial of Sparse Graphs
    David Harris and Francis Sullivan

  • Inapproximability of H-Transversal/Packing
    Venkatesan Guruswami and Euiwoong Lee

  • On Approximating Node-Disjoint Paths in Grids
    Julia Chuzhoy and David Kim

  • Large Supports are required for Well-Supported Nash Equilibria
    Yogesh Anbalagan, Hao Huang, Shachar Lovett, Sergey Norin, Adrian Vetta and Hehui Wu

  • Approximate Nearest Neighbor Search in Metrics of Planar Graphs
    Ittai Abraham, Shiri Chechik, Robert Krauthgamer and Udi Wieder

  • Terminal Embeddings
    Michael Elkin, Arnold Filtser and Ofer Neiman

  • Stochastic and Robust Scheduling in the Cloud
    Lin Chen, Nicole Megow, Roman Rischke and Leen Stougie

  • Towards a Characterization of Approximation Resistance for Symmetric CSPs
    Venkatesan Guruswami and Euiwoong Lee.

  • Improved Bounds in Stochastic Matching and Optimization
    Alok Baveja, Amit Chavan, Andrei Nikiforov, Aravind Srinivasan and Pan Xu

  • The Container Selection Problem
    Viswanath Nagarajan, Kanthi Sarpatwar, Baruch Schieber, Hadas Shachnai and Joel Wolf

  • Approximating Hit Rate Curves using Streaming Algorithms
    Zachary Drudi, Nicholas Harvey, Stephen Ingram, Andrew Warfield and Jake Wires

  • How to Tame Rectangles: Solving Independent Set and Coloring of Rectangles via Shrinking
    Anna Adamaszek, Parinya Chalermsook and Andreas Wiese

  • On guillotine cutting sequences
    Fidaa Abed, Parinya Chalermsook, Jose Correa, Andreas Karrenbauer, Pablo Perez-Lantero, Jose Soto and Andreas Wiese

  • Minimizing maximum flow-time on related machines
    Bouke Cloostermans and Nikhil Bansal

  • A Tight Approximation Bound for the Stable Marriage Problem with Restricted Ties
    Chien-Chung Huang, Kazuo Iwama, Shuichi Miyazaki and Hiroki Yanagisawa

  • A 2-Competitive Algorithm For Online Convex Optimization With Switching Costs
    Nikhil Bansal, Anupam Gupta, Ravishankar Krishnaswamy, Kirk Pruhs, Kevin Schewior and Clifford Stein

  • Designing Overlapping Networks for Publish-Subscribe Systems
    Jennifer Iglesias, Rajmohan Rajaraman, R. Ravi and Ravi Sundaram

  • Tight Bounds for Graph Problems in Insertion Streams
    Xiaoming Sun and David Woodruff

  • Approximating Upper Degree-Constrained Partial Orientations
    Marek Cygan and Tomasz Kociumaka

  • 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

  • Approximate Hypergraph Coloring under Low-discrepancy and Related Promises
    V.S.P. Vijay Bhattiprolu, Venkatesan Guruswami and Euiwoong Lee

  • Non-Uniform Robust Network Design in Planar Graphs
    David Adjiashvili

Valid XHTML 1.0 Transitional Valid CSS!

Created by Marios Karagiannis - Maintained by Orestis Evangelatos