Table of Contents

Session 1A

1Computing all maps into a sphere

Martin Čadek, Marek Krčál, Jiří Matoušek, Francis Sergeraert, Lukáš Vokřínek and Uli Wagner.

11The maximum number of faces of the Minkowski sum of two convex polytopes

Menelaos I. Karavelas and Eleni Tzanaki.

29Polytope Approximation and the Mahler Volume

Sunil Arya, Guilherme D. Da Fonseca and David Mount.

43Dimension reduction for finite trees in l_1

James Lee, Arnaud De Mesmay and Mohammad Moharrami.

51On Multiplicative λ-Approximations and some Geometric Applications

Ilan Newman and Yuri Rabinovich.

Session 1B

68Kernelization of Packing Problems

Holger Dell and Dániel Marx.

82Linear Kernels for (Connected) Dominating Set on H-minor-free graphs

Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh and Dimitrios Thilikos.

94Compression via Matroids: A Randomized Polynomial Kernel for Odd Cycle Transversal

Stefan Kratsch and Magnus Wahlström.

104Weak Compositions and Their Applications to Polynomial Lower-Bounds for Kernelization

Danny Hermelin and Xi Wu.

114Co-nondeterminism in compositions: A kernelization lower bound for a Ramsey-type problem

Stefan Kratsch.

Session 1C

123Popularity vs Maximum cardinality in the stable marriage setting

Telikepalli Kavitha.

135A Matroid Approach to Stable Matchings with Lower Quotas

Tamas Fleiner and Naoyuki Kamiyama.

143On the (In)security of Hash-based Oblivious RAM and a New Balancing Scheme

Eyal Kushilevitz, Steve Lu and Rafail Ostrovsky.

157Privacy-Preserving Group Data Access via Stateless Oblivious RAM Simulation

Michael Goodrich, Michael Mitzenmacher, Olga Ohrimenko and Roberto Tamassia.

168Private Data Release Via Learning Thresholds

Moritz Hardt, Guy Rothblum and Rocco Servedio.

IP1

188Structural and Logical Approaches to the Graph Isomorphism Problem.

Martin Grohe

Session 2A

189Near Linear Time (1 + ε)-Approximation for Restricted Shortest Paths in Undirected Graphs

Aaron Bernstein.

202Approximate Distance Oracles with Improved Preprocessing Time

Christian Wulff-Nilsen.

209Exact Distance Oracles for Planar Graphs

Shay Mozes and Christian Sommer

223Single source distance oracle for planar digraphs avoiding a failed node or link

Surender Baswana, Utkarsh Lath and Anuradha Mehta.

233Physarum Can Compute Shortest Paths

Vincenzo Bonifaci, Kurt Mehlhorn and Girish Varma.

Session 2B

241The condensation transition in random hypergraph 2-coloring

Amin Coja-Oghlan and Lenka Zdeborova.

251A new approach to the orientation of random hypergraphs

Marc Lelarge.

265The MAX-CUT of sparse random graphs

Hervé Daudé, Conrado Martinez, Vonjy Rasendrahasina and Vlady Ravelomanana.

272A simple algorithm for random colouring G(n, d/n) using (2+\ε)d colours.

Charilaos Efthymiou.

281The Maximum Degree of Random Planar Graphs

Michael Drmota, Omer Gimenez, Marc Noy, Konstantinos Panagiotou and Angelika Steger.

Session 2C

288Computing distance between piecewise linear bivariate functions

Guillaume Moroz and Boris Aronov.

294Packing anchored rectangles

Adrian Dumitrescu and Csaba Toth.

306Algorithms and Data Structures for the Transportation Problem in Geometric Settings

R Sharathkumar and Pankaj Agarwal.

318Jaywalking your Dog - Computing the Fréchet Distance with Shortcuts

Anne Driemel and Sariel Har-Peled.

338Submatrix maximum queries in Monge matrices and Monge partial matrices, and their applications

Haim Kaplan, Shay Mozes, Yahav Nussbaum and Micha Sharir.

Session 3A

356The Entropy Rounding Method in Approximation Algorithms

Thomas Rothvoss.

373Approximating CSPs with Global Cardinality Constraints Using SDP Hierarchies

Prasad Raghavendra and Ning Tan.

388Polynomial integrality gaps for strong SDP relaxations of Densest k-Subgraph

Aditya Bhaskara, Moses Charikar, Venkatesan Guruswami, Aravindan Vijayaraghavan and Yuan Zhou.

406Linear Index Coding via Semidefinite Programming

Eden Chlamtac and Ishay Haviv.

420Concentration Inequalities for Nonlinear Matroid Intersection

Konstantin Makarychev, Warren Schudy and Maxim Sviridenko.

437Concentration and Moment Inequalities for Polynomials of Independent Random Variables

Warren Schudy and Maxim Sviridenko

Session 3B

447Width of Points in the Streaming Model

Alexandr Andoni and Huy Nguyen.

453The Shifting Sands Algorithm

Andrew Mcgregor and Paul Valiant.

459Analyzing Graph Structure via Linear Measurements

Kook Jin Ahn, Sudipto Guha and Andrew Mcgregor.

468On the communication and streaming complexity of maximum bipartite matching

Ashish Goel, Michael Kapralov and Sanjeev Khanna.

486Lower Bounds for Number-in-Hand Multiparty Communication Complexity, Made Easy

Jeff Phillips, Elad Verbin and Qin Zhang.

Session 3C

502SINR Diagram with Interference Cancellation

Chen Avin, Asaf Cohen, Yoram Haddad, Erez Kantor, Zvi Lotker, Merav Parter and David Peleg.

516Wireless Connectivity and Capacity

Magnus Halldorsson and Pradipta Mitra.

527Gathering despite mischief

Yoann Dieudonne, Andrzej Pelc and David Peleg.

541Stochastic coalescence in logarithmic time

Po-Shen Loh and Eyal Lubetzky.

551Towards Robust and Efficient Computation in Dynamic Peer-to-Peer Networks

John Augustine, Gopal Pandurangan, Peter Robinson and Eli Upfal.

Session 4A

570Using Hashing to Solve the Dictionary Problem (In External Memory)

John Iacono and Mihai Patrascu.

583I/O-Efficient Data Structures for Colored Range and Prefix Reporting

Kasper Green Larsen and Rasmus Pagh.

593Confluent Persistence Revisited

Sebastien Collette, John Iacono and Stefan Langerman.

602Fully Persistent B-trees

Gerth Stølting Brodal, Spyros Sioutas, Konstantinos Tsakalidis and Kostas Tsichlas.

615A Little Advice Can Be Very Helpful

Arkadev Chattopadhyay, Jeff Edmonds, Faith Ellen and Toniann Pitassi.

Session 4B

626An efficient polynomial-time approximation scheme for Steiner forest in planar graphs

David Eisenstat, Philip Klein and Claire Mathieu.

639A Polynomial-time Approximation Scheme for Planar Multiway Cut

Mohammadhossein Bateni, Mohammadtaghi Hajiaghayi, Philip Klein and Claire Mathieu.

656Finding an induced path of given parity in planar graphs in polynomial time

Marcin Kaminski and Naomi Nishimura.

671Spanning closed walks and TSP in 3-connected planar graphs

Ken-Ichi Kawarabayashi and Kenta Ozeki.

683Approximate Tree Decompositions of Planar Graphs in Linear Time

Frank Kammer and Torsten Tholey.

Session 4C

699Bypassing UGC from some Optimal Geometric Inapproximability Results

Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket and Yi Wu.

718Inapproximability Results for the Multi-level Uncapacitated Facility Location Problem

Ravishankar Krishnaswamy and Maxim Sviridenko.

735On the hardness of pricing loss leaders

Preyas Popat and Yi Wu.

750The complexity of conservative valued CSPs

Vladimir Kolmogorov and Stanislav Zivny.

760The Set of Solutions of Random XORSAT Formulae

Dimitris Achlioptas, Yashodhan Kanoria, Mike Molloy, Andrea Montanari, Morteza Ibrahimi and Matt Kraning.

IP2

Belief Propagation Algorithms: From Matching to Cancer Genomics.

Jennifer Chayes

Session 5A

780Approximation Algorithms and Hardness of the k-Route Cut Problem

Julia Chuzhoy, Yury Makarychev, Aravindan Vijayaraghavan and Yuan Zhou.

800Approximate Duality of Multicommodity Multiroute Flows and Cuts: Single Source Case

Christian Scheideler and Petr Kolman.

811On a Linear Program for Minimum-Weight Triangulation

Arman Yousefi and Neal Young.

824Constant Factor Approximation Algorithm for the Knapsack Median Problem

Amit Kumar.

833Subquadratic time approximation algorithms for the girth

Liam Roditty and Virginia Vassilevska Williams.

Session 5B

846A Universally-truthful Approximation Scheme for Multi-unit Auctions

Berthold Vöcking.

856Optimal Crowdsourcing Contests

Shuchi Chawla, Jason D. Hartline and Balasubramanian Sivan.

869Sequential Auctions and Externalities

Renato Paes Leme, Vasilis Syrgkanis and Eva Tardos.

887Mechanism Designs via Consensus Estimate and Cross-Check

Bach Ha and Jason Hartline.

896Black-Box Reductions for Cost-Sharing Mechanism Design

Konstantinos Georgiou and Chaitanya Swamy.

Session 5C

914Counting Perfect Matchings as Fast as Ryser

Andreas Björklund.

922Approximate Counting via Correlation Decay in Spin Systems

Liang Li, Pinyan Lu and Yitong Yin.

941Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs

Alistair Sinclair, Piyush Srivastava and Marc Thurley.

954Approximating Fixation Probabilities in the Generalized Moran Process

Josep Diaz, Leslie Ann Goldberg, George Mertzios, David Richerby, Maria Serna and Paul Spirakis.

961A Satisfiability Algorithm for AC0

Russel Impagliazzo, William Matthews and Ramamohan Paturi.

Session 6A

973The Notion of a Rational Convex Program, and an Algorithm for the Arrow-Debreu Nash Bargaining Game

Vijay Vazirani.

993Beyond Myopic Best Response (in Cournot Competition)

Amos Fiat, Elias Koutsoupias, Katrina Ligett, Yishay Mansour and Svetlana Olonetsky.

1006Metastability of Logit Dynamics for Coordination Games

Vincenzo Auletta, Diodato Ferraioli, Francesco Pasquale and Giuseppe Persiano.

1025Sketching Valuation Functions

Ashwinkumar Badanidiyuru, Shahar Dobzinski, Hu Fu, Robert Kleinberg, Noam Nisan and Tim Roughgarden.

1036Voting with Limited Information and Many Alternatives

Flavio Chierichetti and Jon Kleinberg.

Session 6B

1056Partial match queries in random quadtrees

Nicolas Broutin, Ralph Neininger and Henning Sulzbach.

1066Top-κ Document Retrieval in Optimal Time and Linear Space

Gonzalo Navarro and Yakov Nekrich.

1078LSH-Preserving Functions and Their Applications

Flavio Chierichetti and Ravi Kumar.

1095A Linear Time Algorithm for Seeds Computation

Tomasz Kociumaka, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter and Tomasz Walen.

1113Tight bounds on the maximum size of a set of permutations with bounded VC-dimension

Josef Cibulka and Jan Kyncl.

Session 6C

1123A Near-Optimal Sublinear-Time Algorithm for Approximating the Minimum Vertex Cover Size

Krzysztof Onak, Dana Ron, Michal Rosen and Ronitt Rubinfeld.

1132Space-efficient Local Computation Algorithms

Noga Alon, Ronitt Rubinfeld, Shai Vardi and Ning Xie.

1140Testing Odd-Cycle-Freeness in Boolean Functions

Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra and Asaf Shapira.

1150Networks Cannot Compute Their Diameter in Sublinear Time

Silvio Frischknecht, Stephan Holzer and Roger Wattenhofer.

1163Parallelism and Time in Hierarchical Self-Assembly

Ho-Lin Chen and David Doty.

Session 7A

1183Simple and Practical Algorithm for Sparse Fourier Transform

Haitham Hassanieh, Piotr Indyk, Dina Katabi and Eric Price.

1195Sparser Johnson-Lindenstrauss Transforms

Daniel Kane and Jelani Nelson.

1207Optimal Column-Based Low-Rank Matrix Reconstruction

Venkatesan Guruswami and Ali Sinop.

1215Sublinear Time, Measurement-Optimal, Sparse Recovery For All

Ely Porat and Martin Strauss.

Session 7B

1228Resource Augmentation for Weighted Flow-time explained by Dual Fitting

S. Anand, Naveen Garg and Amit Kumar.

1242Scheduling Heterogeneous Processors Isn't As Easy As You Think

Anupam Gupta, Sungjin Im, Ravishankar Krishnaswamy, Benjamin Moseley and Kirk Pruhs.

1254Online Scheduling with General Cost Functions

Sungjin Im, Benjamin Moseley and Kirk Pruhs.

1266Race to Idle: New Algorithms for Speed Scaling with a Sleep State

Susanne Albers and Antonios Antoniadis.

Session 7C

1286A Faster Algorithm to Recognize Even-Hole-Free Graphs

Hsien-Chih Chang and Hsueh-I Lu.

1298Separating stable sets in claw-free graphs via Padberg-Rao and compact linear programs

Yuri Faenza, Gianpaolo Oriolo and Gautier Stauffer.

1309Global Minimum Cuts in Surface Embedded Graphs

Jeff Erickson, Kyle Fox and Amir Nayyeri.

1319Competitive Routing in the Half-θ6-Graph

Prosenjit Bose, Sander Verdonschot, Rolf Fagerberg and Andre Van Renssen.

Session 8A

1329A Near-Linear Algorithm for Projective Clustering Integer Points

Kasturi Varadarajan and Xin Xiao.

1343Data reduction for weighted and outlier-resistant clustering

Dan Feldman and Leonard J. Schulman.

1355Local Homology Transfer and Stratification Learning

Paul Bendich, Bei Wang and Sayan Mukherjee.

1371Learning k-Modal Distributions via Testing

Constantinos Daskalakis, Ilias Diakonikolas and Rocco Servedio.

Session 8B

1386An O(n2) Time Algorithm for Alternating Büchi Games

Krishnendu Chatterjee and Monika Henzinger.

1400Efficient Algorithms for Maximum Weight Matchings in General Graphs with Small Edge Weights

Chien-Chung Huang and Telikepalli Kavitha.

1413A Scaling Algorithm for Maximum Weight Matching in Bipartite Graphs

Ran Duan and Hsin-Hao Su.

1425List-Coloring Graphs without Subdivisions and without Immersions

Ken-Ichi Kawarabayashi and Yusuke Kobayashi.

Session 8C

1436Fast zeta transforms for point lattices

Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto, Jesper Nederlof and Pekka Parviainen.

1445Deterministic Construction of l-type Ellipsoids and its Application to Derandomizing Lattice Algorithms

Daniel Dadush and Santosh Vempala.

1457Constructing high order elements through subspace polynomials

Qi Cheng, Shuhong Gao and Daqing Wan.

1464Improved Output-Sensitive Quantum Algorithms for Boolean Matrix Multiplication

Francois Le Gall.

Session 9A

1477A Proof of the Boyd-Carr Conjecture

Frans Schalekamp, David Williamson and Anke Van Zuylen.

1487Traffic-redundancy aware network design

Siddharth Barman and Shuchi Chawla.

1499Approximating Rooted Steiner Networks

J. Cheriyan, Bundit Laekhanukit, Guyslain Naves and Adrian Vetta.

1512Matroidal Degree-Bounded Minimum Spanning Trees

Rico Zenklusen.

1522Approximation Algorithms for Stochastic Orienteering

Anupam Gupta, Ravishankar Krishnaswamy, Viswanath Nagarajan and R. Ravi.

Session 9B

1539Expanders are Universal for the Class of all Spanning Trees

Daniel Johannsen, Michael Krivelevich and Wojciech Samotij.

1552Directed Nowhere Dense Classes of Graphs

Stephan Kreutzer and Siamak Tazari.

1563Bidimensionality and Geometric Graphs

Fedor V. Fomin, Daniel Lokshtanov and Saket Saurabh.

1576Weighted Capacitated, Priority, and Geometric Set Cover via Improved Quasi-Uniform Sampling

Timothy Chan, Elyot Grant, Jochen Koenemann and Malcolm Sharpe.

1586Submodular Functions are Noise Stable

Mahdi Cheraghchi, Adam Klivans, Pravesh Kothari and Homin Lee.

Session 9C

1593Random Walks, Electric Networks and The Transience Class problem of Sandpiles

Ayush Choure and Sundar Vishwanathan.

1612Information Dissemination via Random Walks in d-Dimensional Space

Henry Lam, Zhenming Liu, Michael Mitzenmacher, Xiaorui Sun and Yajun Wang.

1623Rumor Spreading and Vertex Expansion

George Giakkoupis and Thomas Sauerwald.

1642Ultra-Fast Rumor Spreading in Social Networks

Nikolaos Fountoulakis, Konstantinos Panagiotou and Thomas Sauerwald.

1661The mixing time of the Newman--Watts small world

Louigi Addario-Berry and Tao Lei.

Session 10A

1669Outperforming LRU via Competitive Analysis on Parametrized Inputs for Paging

Gabriel Moruz and Andrei Negoescu.

1681An O(log k)-competitive Algorithm for Generalized Caching

Anna Adamaszek, Artur Czumaj, Matthias Englert and Harald Räcke.

1690Simultaneous Approximations for Adversarial and Stochastic Online Budgeted Allocation

Vahab Mirrokni, Shayan Oveis Gharan and Morteza Zadimoghaddam.

1702Improved Competitive Ratio for the Matroid Secretary Problem

Sourav Chakraborty and Oded Lachish.

Session 10B

1713Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset

Rajesh Chitnis, Mohammadtaghi Hajiaghayi and Dániel Marx.

1726Erd\H{o}s-P\'osa property and its algorithmic applications --- parity constraints, subset feedback set, and subset packing

Naonori Kakimura, Ken-Ichi Kawarabayashi and Yusuke Kobayashi.

1737Subexponential Parameterized Algorithm for Minimum Fill-in

Fedor V. Fomin and Yngve Villanger.

1747Shortest Cycle Through Specified Elements

Andreas Björklund, Thore Husfeldt and Nina Taslaman.