| Invited Lectures |
| Assigning Papers to Referees / Kurt Mehlhorn |
| Algorithmic Game Theory: A Snapshot / Christos H. Papadimitriou |
| Contributed Papers |
| SDP-Based Algorithms for Maximum Independent Set Problems on Hypergraphs / Geir Agnarsson ; Magnús M. Halldórsson ; Elena Losievskaja |
| Correlation Clustering Revisited: The "True" Cost of Error Minimization Problems / Nir Ailon ; Edo Liberty |
| Sorting and Selection with Imprecise Comparisons / Miklós Ajtai ; Vitaly Feldman ; Avinatan Hassidim ; Jelani Nelson |
| Fast FAST / Noga Alon ; Daniel Lokshtanov ; Saket Saurabh |
| Bounds on the Size of Small Depth Circuits for Approximating Majority / Kazuyuki Amano |
| Counting Subgraphs via Homomorphisms / Omid Amini ; Fedor V. Fomin |
| External Sampling / Alexandr Andoni ; Piotr Indyk ; Krzysztof Onak ; Ronitt Rubinfeld |
| Functional Monitoring without Monotonicity / Chrisil Arackaparambil ; Joshua Brody ; Amit Chakrabarti |
| De-amortized Cuckoo Hashing: Provable Worst-Case Performance and Experimental Results / Yuriy Arbitman ; Moni Naor ; Gil Segev |
| Towards a Study of Low-Complexity Graphs / Sanjeev Arora ; David Steurer ; Avi Wigderson |
| Decidability of Conjugacy of Tree-Shifts of Finite Type / Nathalie Aubrun ; Marie-Pierre Béal |
| Improved Bounds for Speed Scaling in Devices Obeying the Cube-Root Rule / Nikhil Bansal ; Ho-Leung Chan ; Kirk Pruhs ; Dmitriy Katz |
| Competitive Analysis of Aggregate Max in Windowed Streaming / Luca Becchetti ; Elias Koutsoupias |
| Faster Regular Expression Matching / Philip Bille ; Mikkel Thorup |
| A Fast and Simple Parallel Algorithm for the Monotone Duality Problem / Endre Boros ; Kazuhisa Makino |
| Unconditional Lower Bounds against Advice / Harry Buhrman ; Lance Fortnow ; Rahul Santhanam |
| Approximating Decision Trees with Multiway Branches / Venkatesan T. Chakaravarthy ; Vinayaka Pandit ; Sambuddha Roy ; Yogish Sabharwal |
| Annotations in Data Streams / Graham Cormode ; Andrew McGregor |
| The Tile Complexity of Linear Assemblies / Harish Chandran ; Nikhil Gopalkrishnan ; John Reif |
| A Graph Reduction Step Preserving Element-Connectivity and Applications / Chandra Chekuri ; Nitish Korula |
| Approximating Matches Made in Heaven / Ning Chen ; Nicole Immorlica ; Anna R. Karlin ; Mohammad Mahdian ; Atri Rudra |
| Strong and Pareto Price of Anarchy in Congestion Games / Steve Chien ; Alistair Sinclair |
| A Better Algorithm for Random k-SAT / Amin Coja-Oghlan |
| Exact and Approximate Bandwidth / Marek Cygan ; Marcin Pilipczuk |
| Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs / Erik D. Demaine ; MohammadTaghi Hajiaghayi ; Ken-ichi Kawarabayashi |
| Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs / Philip N. Klein |
| On Cartesian Trees and Range Minimum Queries / Gad M. Landau ; Oren Weimann |
| Applications of a Splitting Trick / Martin Dietzfelbinger ; Michael Rink |
| Quasirandom Rumor Spreading: Expanders, Push vs. Pull, and Robustness / Benjamin Doerr ; Tobias Friedrich ; Thomas Sauerwald |
| Incompressibility through Colors and IDs / Michael Dom |
| Partition Arguments in Multiparty Communication Complexity / Jan Draisma ; Eyal Kushilevitz ; Enav Weinreb |
| High Complexity Tilings with Sparse Errors / Bruno Durand ; Andrei Romashchenko ; Alexander Shen |
| Tight Bounds for the Cover Time of Multiple Random Walks / Robert Elsässer |
| Online Computation with Advice / Yuval Emek ; Pierre Fraigniaud ; Amos Korman ; Adi Rosén |
| Dynamic Succinct Ordered Trees / Arash Farzan ; J. Ian Munro |
| Universal Succinct Representations of Trees? / Rajeev Raman ; S. Srinivasa Rao |
| Distortion Is Fixed Parameter Tractable / Michael R. Fellows ; Frances A. Rosamond |
| Towards Optimal Range Medians / Beat Gfeller ; Peter Sanders |
| B-Treaps: A Uniquely Represented Alternative to B-Trees / Daniel Golovin |
| Testing Fourier Dimensionality and Sparsity / Parikshit Gopalan ; Ryan O'Donnell ; Rocco A. Servedio ; Amir Shpilka ; Karl Wimmer |
| Revisiting the Direct Sum Theorem and Space Lower Bounds in Random Order Streams / Sudipto Guha ; Zhiyi Huang |
| Wireless Communication Is in APX / Roger Wattenhofer |
| The Ehrenfeucht-Silberger Problem / Štepán Holub ; Dirk Nowotka |
| Applications of Effective Probability Theory to Martin-Löf Randomness / Mathieu Hoyrup ; Cristóbal Rojas |
| An EPTAS for Scheduling Jobs on Uniform Processors: Using an MILP Relaxation with a Constant Number of Integral Variables / Klaus Jansen |
| Popular Mixed Matchings / Telikepalli Kavitha ; Julián Mestre ; Meghana Nasre |
| Factoring Groups Efficiently / Neeraj Kayal ; Timur Nezhmetdinov |
| On Finding Dense Subgraphs / Samir Khuller ; Barna Saha |
| Learning Halfspaces with Malicious Noise / Adam R. Klivans ; Philip M. Long |
| General Scheme for Perfect Quantum Network Coding with Free Classical Communication / Hirotada Kobayashi ; François Le Gall ; Harumichi Nishimura ; Martin Rütteler |
| Greedy ?-Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost / Christos Koufogiannakis ; Neal E. Young |
| Limits and Applications of Group Algebras for Parameterized Problems / Ioannis Koutis ; Ryan Williams |
| Sleep with Guilt and Work Faster to Minimize Flow Plus Energy / Tak-Wah Lam ; Lap-Kei Lee ; Hing-Fung Ting ; Isaac K.K. To ; Prudence W.H. Wong |
| Improved Bounds for Flow Shop Scheduling / Monaldo Mastrolilli ; Ola Svensson |
| A 3/2-Approximation Algorithm for General Stable Marriage / Eric McDermid |
| Limiting Negations in Formulas / Hiroki Morizumi |
| Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems / Jesper Nederlof |
| Superhighness and Strong Jump Traceability / André Nies |
| Amortized Communication Complexity of Distributions / Jérémie Roland ; Mario Szegedy |
| The Number of Symbol Comparisons in QuickSort and QuickSelect / Brigitte Vallée ; Julien Clément ; James Allen Fill ; Philippe Flajolet |
| Computing the Girth of a Planar Graph in O(n log n) Time / Raphael Yuster |
| Elimination Graphs / Yuli Ye ; Allan Borodin |
| Author Index |
| Invited Lectures |
| Assigning Papers to Referees / Kurt Mehlhorn |
| Algorithmic Game Theory: A Snapshot / Christos H. Papadimitriou |
ＥＢ
