Accepted papers

Track A: Algorithms, Automata, Complexity and Games

• Quasi-Randomness and Algorithmic Regularity for Graphs with General Degree Distributions
  Noga Alon, Amin Coja-Oghlan, Hiep Han, Mihyun Kang, Vojtech Rödl and Mathias Schacht
• Parameterized Algorithms for Directed Maximum Leaf Problems
  Noga Alon, Fedor V. Fomin, Gregory Gutin, Michael Krivelevich and Saket Saurabh
• Balanced Families of Perfect Hash Functions and Their Applications
  Noga Alon and Shai Gutner
• On the power of k-consistency
  Albert Atserias, Andrei Bulatov and Victor Dalmau
• Competitive Algorithms for Due Date Scheduling
  Nikhil Bansal, Kirk Pruhs and Ho-Leung Chan
• Online conflict-free colorings for hypergraphs
  Amotz Bar-Noy, Panagiotis Cheilaris, Svetlana Olonetsky and Shakhar Smorodinsky
• Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity
  Paul Beame, Matei David, Toniann Pitassi and Philipp Woelfel
• Minimum Weight 2-Edge-Connected Spanning Subgraphs in Planar Graphs
  Andre Berger and Michelangelo Grigni
• Reconciling data compression and Kolmogorov complexity
  Laurent Bienvenu and Wolfgang Merkle
• Complexity of the Cover Polynomial
  Markus Bläser and Holger Dell
• Sampling methods for shortest vectors, closest vectors and successive minima
  Johannes Blömer and Stefanie Naewe
• On Commutativity Based Edge Lean Search
  Dragan Bosnacki, Edith Elkind, Blaise Genest and Doron Peled
• Exotic quantifiers, complexity classes, and complete problems
  Peter Buergisser and Felipe Cucker
• Holographic Algorithms: The Power of Dimensionality Resolved
  Jin-Yi Cai and Pinyan Lu
• An exponential improvement on the MST heuristic for the Minimum Energy Broadcasting problem
  Ioannis Caragiannis, Michele Flammini and Luca Moscardelli
• Mechanism design for fractional scheduling on unrelated machines
  George Christodoulou, Elias Koutsoupias and Annamaria Kovacs
• Checking and Spot-Checking the Correctness of Priority Queues
  Matthew Chu, Sampath Kannan and Andrew McGregor
• On the Chromatic Number of Random Graphs
  Amin Coja-Oghlan, Konstantinos Panagiotou and Angelika Steger
• An Optimal Decomposition Algorithm for Tree Edit Distance
  Erik Demaine, Shay Mozes, Benjamin Rossman and Oren Weimann
• Complexity of Propositional Proofs under a Promise
  Nachum Dershowitz and Iddo Tzameret
• Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners
  Michael Elkin
• Strong Price of Anarchy for Machine Load Balancing
  Amos Fiat, Haim Kaplan, Meital Levy and Svetlana Olonetsky
• Distributed Computing with Advice: Information Sensitivity of Graph Coloring
  Pierre Fraigniaud, Cyril Gavoille, David Ilcinkas and Andrzej Pelc
• In-Place Suffix Sorting
  Gianni Franceschini and S. Muthukrishnan
• Parameterized Approximability of the Disjoint Cycle Problem
  Martin Grohe and Magdalena Grüber
• Lower Bounds for Quantile Estimation in Random-Order and Multi-Pass Streaming
  Sudipto Guha and Andrew McGregor
• Linear Problem Kernels for NP-Hard Problems on Planar Graphs
  Jiong Guo and Rolf Niedermeier
• A Framework for Dynamizing Succinct Data Structures
  Ankur Gupta, Wing-Kai Hon, Rahul Shah and Jeffrey Scott Vitter
• Succinct Ordinal Trees Based on Tree Covering
  Meng He, Ian Munro and S. Srinivasa Rao
• Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs
  Danny Hermelin, Michael Fellows, Guillaume Fertin and Stephane Vialette
• Unbounded-Error One-Way Classical and Quantum Communication Complexity
  Kazuo Iwama, Harumichi Nishimura, Rudy Raymond and Shigeru Yamashita
• Commitment Under Uncertainty: Two-Stage Stochastic Matching Problems
  Irit Katriel, Claire Kenyon and Eli Upfal
• Efficient Algorithms for Constant Well Supported Approximate Equilibria in Bimatrix Games
  Spyros Kontogiannis and Paul Spirakis
• Labeling Schemes for Vertex Connectivity
  Amos Korman
• Universal Algebra and Hardness Results for Constraint Satisfaction Problems
  Benoit Larose and Pascal Tesson
• On the Complexity of Hard-Core Set Constructions
  Chi-Jen Lu, Shi-Chun Tsai and Hsin-Lung Wu
• A lower bound on entanglement-assisted quantum communication complexity
  Ashley Montanaro and Andreas Winter
• Estimating Sum by Weighted Sampling
  Rajeev Motwani, Rina Panigrahy and Ying Xu
• Approximation by DNF: Examples and Counterexamples
  Ryan O'Donnell and Karl Wimmer
• Low Distortion Spanners
  Seth Pettie
• Size Competitive Meshing without Large Angles
  Todd Phillips, Don Sheehy and Gary Miller

Track B: Logic, Semantics, and Theory of Programming

• Regular Languages of Nested Words: Fixed Points, Automata, and Synchronization
  Marcelo Arenas, Pablo Barcelo and Leonid Libkin
• Affine Systems of Equations and Counting Infinitary Logic
  Albert Atserias, Andrei Bulatov and Anuj Dawar
• Maximal Infinite-Valued Constraint Languages
  Manuel Bodirsky, Hubie Chen, Jan Kara and Timo von Oertzen
• A Generalization of Cobham's Theorem to Automata over Real Numbers
  Bernard Boigelot and Julien Brusten
• Bounded depth data trees
  Mikolaj Bojanczyk and Henrik Bjoerklund
• Decision Problems for lower/upper bound Parametric Timed Automata
  Laura Bozzelli and Salvatore La Torre
• A combinatorial theorem for trees
  Thomas Colcombet
• Model theory makes formulas large
  Anuj Dawar, Martin Grohe, Stephan Kreutzer and Nicole Schweikardt
• Equational Systems and Free Constructions
  Marcelo Fiore and Chung-Kil Hur
• Perfect information stochastic priority games
  Hugo Gimbert and Wieslaw Zielonka
• Continuous Capacities on Continuous State Spaces
  Jean Goubault-Larrecq
• Reachability-time games on timed automata
  Marcin Jurdzinski and Ashutosh Trivedi
• Unranked Tree Automata with Sibling Equalities and Disequalities
  Wong Karianto and Christof Löding
• Undecidability of 2-Label BPP Equivalences and Behavioral Type Systems for the Pi-Calculus
  Naoki Kobayashi and Takashi Suto
• Boundedness of Monadic FO over Acyclic Structures
  Stephan Kreutzer, Martin Otto and Nicole Schweikardt
• A Fully Abstract Trace Semantics for General References
  James Laird
• Aliased Register Allocation for Straight-line Programs is NP-Complete
  Jonathan K. Lee, Jens Palsberg and Fernando Pereira
• Ready Simulation for Concurrency: It's Logical!
  Gerald Lüttgen and Walter Vogler
• On the Complexity of LTL Model-Checking of Recursive State
  Gennaro Parlato and Salvatore La Torre
• Minimum-Time Reachability in Timed Games
  Vinayak Prabhu, Thomas Henzinger, Thomas Brihaye and Jean-Francois Raskin
• Conservative Ambiguity Detection in Context-Free Grammars
  Sylvain Schmitz
• Compositional Algorithms for Heterogeneous Modal Logics
  Lutz Schröder and Dirk Pattinson
• Co-Logic Programming: Extending Logic Programming with Coinduction
  Luke Simon, Ajay Mallya, Ajay Bansal and Gopal Gupta
• Categorical Views on Computations on Trees
  Tarmo Uustalu, Ichiro Hasuo and Bart Jacobs

Track C: Security and Cryptography Foundations

• Hash Functions in the Dedicated-Key Setting: Design Choices and MPP Transforms
  Mihir Bellare and Thomas Ristenpart
• Offline/Online-Mixing
  Ben Adida and Douglas Wikström
• Unrestricted Aggregate Signatures
  Mihir Bellare and Chanathip Namprempre and Gregory Neven
• Ring Signatures of Sub-Linear Size without Random Oracles
  Nishanth Chandran and Jens Groth and Amit Sahai
• Constant-Round Private Database Queries
  Nenad Dedic and Payman Mohassel
• Fully Collusion Resistant Black-Box Traitor Revocable Broadcast Encryption with Short Private Keys
  Jun Furukawa and Nuttapong Attrapadung
• Private Multiparty Sampling and Approximation of Vector Combinations
  Yuval Ishai and Tal Malkin and Martin J. Strauss and Rebecca N. Wright
• A Characterization of Non-Interactive Instance-Dependent Commitment-Schemes
  Bruce Kapron and Lior Malka and Venkatesh Srinivasan
• Trading Static for Adaptive Security in Universally Composable Zero-Knowledge
  Aggelos Kiayias and Hong-Sheng Zhou
• Deterministic History-Independent Strategies for Storing Information on Write-Once Memories
  Tal Moran and Moni Naor and Gil Segev
• Private Locally Decodable Codes
  Rafail Ostrovsky and Omkant Pandey and Amit Sahai