Program Committee


Niv Buchbinder
Deeparnab Chakrabarty
Siu On Chan
Shuchi Chawla
Eden Chlamtac
Nikhil Devanur (chair)
Alina Ene
Konstantinos Georgiu
Telikepalli Kavitha
Ken Ichi Kawarabayashi
Jochen Koenemann
Amit Kumar
Konstantin Makarychev
Debmalya Panigrahi
Thomas Rothvoss
Barna Saha
Bruce Shepherd
Aravind Srinvasan
David Williamson


Louigi Addario-Berry
Nayantara Bhatnagar
Amin Coja-Oghlan
David Galvin
Valentine Kabanets
Michael Molloy
Cris Moore (chair)
Assaf Naor
Krzysztof Onak
Dana Ron
Alex Russell
Dominik Scheder
Devavrat Shah
Perla Sousi
Mario Szegedy
Amnon Ta-Shma
Thomas Vidick

Program Chairs

Nikhil Devanur,
Microsoft Research, Redmond

Cris Moore,
Santa Fe Institute

Workshop Chairs

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

Organizing Comitee Chair

Carme Alvarez,
Universitat Politècnica de Catalunya
Important dates
Submission deadline
April 17, 2014

Notification to authors
June 6, 2014

Camera ready
June 20, 2014
Call for papers
Random-Approx 2014 Accepted Papers

Approx-2014 Accepted Papers

Adrian Dumitrescu, Minghui Jiang and Csaba Toth . Computing opaque interior barriers \`{a} la Shermer
Alan Soper and Vitaly Strusevich . Power of Preemption on Uniform Parallel Machines
Suguru Tamaki and Yuichi Yoshida. Robust Approximation of Temporal CSP
Stavros Kolliopoulos and Yannis Moysoglou. Sherali-Adams gaps, flow-cover inequalities and generalized configurations for capacity-constrained Facility Location
Takuro Fukunaga, Afshin Nikzad and R Ravi. Deliver or Hold: Approximation Algorithms for the Periodic Inventory Routing Problem
Moran Feldman and Rani Izsak. Constrained Monotone Function Maximization and the Supermodular Degree
Michal Feldman, Nicole Immorlica, Brendan Lucier and S. Matthew Weinberg. Reaching Consensus via non-Bayesian Asynchronous Learning in Social Networks
Anand Louis and Yury Makarychev. Approximation Algorithms for Hypergraph Small Set Expansion and Small Set Vertex Expansion
Noga Alon, Troy Lee and Adi Shraibman. The cover number of a matrix and its algorithmic applications
Kshipra Bhawalkar, Sreenivas Gollapudi and Debmalya Panigrahi. Online Set Cover with Set Requests
Shanfei Li. An Improved Approximation Algorithm for the Hard Uniform Capacitated k-median Problem
Shlomo Jozeph. Universal Factor Graphs for every NP-hard Boolean CSP
Eden Chlamtac and Michael Dinitz. Lowest Degree k-Spanner: Approximation and Hardness
Chaitanya Swamy. Improved Approximation Algorithms for Matroid and Knapsack Median Problems and Applications
Michael Crouch and Daniel Stubbs. Improved Streaming Algorithms for Weighted Matching, via Unweighted Matching
Jeremy Karp and R Ravi. A 9/7-Approximation Algorithm for Graphic TSP in Cubic Bipartite Graphs
Tsz Chiu Kwok and Lap Chi Lau. Lower Bounds on Expansion of Graph Powers
Siddharth Barman, Shuchi Chawla and Seeun Umboh. Network Design with Coverage Costs
Andreas Emil Feldmann, Jochen Koenemann, Neil Olver and Laura Sanita. On the Equivalence of the Bidirected and Hypergraphic Relaxations for Steiner Tree
Michael Dinitz, Guy Kortsarz and Zeev Nutov. Improved Approximation Algorithm for Steiner $k$-Forest with Nearly Uniform Weights
Christoph Hansknecht, Max Klimm and Alexander Skopalik. Approximate pure Nash equilibria in weighted congestion games
Sara Ahmadian, Babak Behsaz, Zachary Friggstad, Amin Jorati, Mohammad Salavatipour and Chaitanya Swamy. Approximation Algorithms for Minimum-Load $k$-Facility Location
Alina Ene and Jan Vondrak. Hardness of Submodular Cost Allocation: Lattice Matching and a Simplex Coloring Conjecture
Martin Gairing, Tobias Harks and Max Klimm. Complexity and Approximation of the Continuous Network Design Problem
Amit Deshpande and Rakesh Venkat. Guruswami-Sinop Rounding without Higher Level Lasserre
Prasad Raghavendra and Tselil Schramm. Gap Amplification for Small-Set Expansion via Random Walks
Abhiram Natarajan and Yi Wu. Complexity of Certifying Restricted Isometry Property and Sparse Cheeger's Inequality
Shashi Mittal, Andreas Schulz and Sebastian Stiller. Robust appointment scheduling
Ittai Abraham, Shiri Chechik and Kunal Talwar. Fully Dynamic All-Pairs Shortest Paths: Breaking the $O(n)$ Barrier
Nicholas Harvey, Roy Schwartz and Mohit Singh. Discrepancy Without Partial Colorings
Cenny Wenner. Parity is Positively Useless

Random-2014 Accepted Papers

Michael Krivelevich, Daniel Reichman and Wojciech Samotij . Smoothed analysis on connected graphs
Josep Díaz, Leslie Ann Goldberg, David Richerby and Maria Serna . Absorption Time of the Moran Process
Oded Goldreich . On Multiple Input Problems in Property Testing
Hu Fu and Robert Kleinberg . Improved Lower Bounds for Testing Triangle-freeness in Boolean Functions via Fast Matrix Multiplication
Alan Guo and Madhu Sudan . List decoding group homomorphisms between solvable groups
Gil Cohen, Anat Ganor and Ran Raz . Two Sides of the Coin Problem
Abbas Mehrabian and Nick Wormald . It's a Small World for Random Surfers
Anat Ganor and Ran Raz . Space Pseudorandom Generators by Communication Complexity Lower Bounds
Gábor Braun, Samuel Fiorini and Sebastian Pokutta . Average case polyhedral complexity of the maximum stable set problem
Venkatesan Guruswami and Carol Wang . Explicit rank-metric codes list-decodable with optimal redundancy
Nathanaël François, Frederic Magniez and Rahul Jain . Unidirectional Input/Output Streaming Complexity of Reversal and Sorting
Jin-Yi Cai, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Mark Jerrum, Daniel Stefankovic and Eric Vigoda . #BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Nonuniqueness Region
Julia Böttcher, Jan Hladký, Diana Piguet and Anusch Taraz . An approximate version of the tree packing conjecture via random embeddings
Milan Bradonjic and Will Perkins . On sharp thresholds in random geometric graphs
Jingcheng Liu, Pinyan Lu and Chihao Zhang . The Complexity of Ferromagnetic Two-spin Systems with External Fields
Vladimir Braverman, Jonathan Katzman, Charles Seidell and Greg Vorsanger . An Optimal Algorithm for Large Frequency Moments Using O(n^1-2/k) Bits
Chandan Dubey and Thomas Holenstein . Sampling a Uniform Solution of a Quadratic Equation Modulo a Prime Power
Arkadev Chattopadhyay and Michael E Saks . The Power of Super-logarithmic Number of Players
Reut Levi, Dana Ron and Ronitt Rubinfeld . Local Algorithms for Sparse Spanning Graphs
Omer Reingold, Raghu Meka and Yuan Zhou . Deterministic Coupon Collection and Better Strong Dispersers
Victor Bapst, Amin Coja-Oghlan, Samuel Hetterich, Felicia Rassmann and Dan Vilenchik . The condensation phase transition in random graph coloring
Mika Göös and Thomas Watson . Communication Complexity of Set-Disjointness for All Probabilities
Thomas Steinke, Salil Vadhan and Andrew Wan . Pseudorandomness and Fourier Growth Bounds for Width 3 Branching Programs
Flavio Chierichetti, Anirban Dasgupta, Ravi Kumar and Silvio Lattanzi . On Reconstructing a Hidden Permutation
Andreas Galanis, Daniel Stefankovic, Eric Vigoda and Linji Yang . Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
Joshua Brody, Amit Chakrabarti, Ranganath Kondapally, David P . Woodruff and Grigory Yaroslavtsev . Certifying Equality With Limited Interaction
Varun Kanade, Elchanan Mossel and Tselil Schramm . Global and Local Information in Clustering Labeled Block Models
Eric Blais, Joshua Brody and Badih Ghazi . The Information Complexity of Hamming Distance
Adam Klivans and Pravesh Kothari . Embedding Hard Learning Problems into Gaussian Space
T.S. Jayram and Jan Vondrak . Exchangeability and realizability: de Finetti theorems on graphs