Accepted Papers 

Track A: Algorithms, Complexity, and Games

• Iddo Tzameret, Sparser Random 3-SAT Refutation Algorithms and the Interpolation Problem
• Mehdi Tibouchi and Pierre-Alain Fouque, Close to Uniform Prime Number Generation With Fewer Random Bits
• Dmitry Gavinsky and Shachar Lovett, En Route to the log-rank Conjecture: New Reductions and Equivalent Formulations
• Pawel Gawrychowski, Shay Mozes, and Oren Weimann, Improved Submatrix Maximum Queries in Monge Matrices
• Hossein Esfandiari, Mohammadtaghi Hajiaghayi, Reza Khani, Vahid Liaghat, Hamid Mahini, and Harald Räcke, Online Stochastic Reordering Buffer Scheduling
• Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, and Somnath Sikdar, A Faster Parameterized Algorithm for Treedepth
• Noga Ron-Zewi, Eli Ben-Sasson, Julia Wolf, and Madhur Tulsiani, Sampling-based proofs of almost-periodicity results and algorithmic applications
• Scott Aaronson, Andris Ambainis, Kaspars Balodis, and Mohammad Bavarian, Weak Parity
• Mitsuru Kusumoto and Yuichi Yoshida, Testing Forest-Isomorphism in the Adjacency List Model
• Jop Briët, Zeev Dvir, Guangda Hu, and Shubhangi Saraf, Lower Bounds for Approximate LDCs
• René Van Bevern, Robert Bredereck, Laurent Bulteau, Jiehua Chen, Vincent Froese, Rolf Niedermeier, and Gerhard J. Woeginger, Star Partitions of Perfect Graphs
• Andreas Björklund and Thore Husfeldt, Shortest Two Disjoint Paths in Polynomial Time
• Justin Hsu, Aaron Roth, Tim Roughgarden, and Jonathan Ullman, Privately Solving Linear Programs
• Gábor Ivanyos, Raghav Kulkarni, Youming Qiao, Miklos Santha, and Aarthi Sundaram, On the complexity of trial and error for constraint satisfaction problems
• David Adjiashvili, Sandro Bosio, Robert Weismantel and, Rico Zenklusen, Time-Expanded Packings
• Spyros Kontogiannis and Christos Zaroliagis, Distance Oracles for Time-Dependent Networks
• Uriel Feige and Shlomo Jozeph, Demand Queries with Preprocessing
• Jin-Yi Cai, Heng Guo, and Tyson Williams, Holographic Algorithms Beyond Matchgates
• Therese Biedl, On Area-Optimal Planar Graph Drawings
• Barnaby Martin, Petar Markovic, and Petar Dapic, QCSP on semicomplete digraphs
• Wiebke Höhn, Julian Mestre, and Andreas Wiese, How Unsplittable-Flow-Covering helps Scheduling with Job-Dependent Cost Functions
• Jens M. Schmidt, The Mondshein Sequence
• Subhash Khot, Madhur Tulsiani, and Pratik Worah, The Complexity of Somewhat Approximation Resistant Predicates
• Richard Cole and Howard Karloff, Fast Algorithms for Constructing Maximum Entropy Summary Trees
• Konstantin Makarychev and Yury Makarychev, Nonuniform Graph Partitioning with Unrelated Weights
• Ilya Volkovich, On Learning, Lower Bounds and (un)Keeping Promises
• Mohammadtaghi Hajiaghayi, Vahid Liaghat, and Debmalya Panigrahi, Near-optimal Online Algorithms for Prize-collecting Steiner Problems
• Yuval Ishai and Hoeteck Wee, Partial Garbling Schemes and Their Applications
• Pinyan Lu, Menghui Wang, and Chihao Zhang, FPTAS for Weighted Fibonacci Gates and Its Applications
• Surender Baswana and Shahbaz Khan, Incremental Algorithm for Maintaining DFS Tree for Undirected Graphs
• Gillat Kol, Shay Moran, Amir Shpilka, and Amir Yehudayoff, Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound
• György Dósa and Jiří Sgall, Optimal analysis of Best Fit bin packing
• Ved Prakash and Hartmut Klauck, An Improved Interactive Streaming Algorithm for the Distinct Elements Problem
• Alexander Golovnev, Alexander Kulikov, and Ivan Mihajlin, Families with infants: a general approach to solve hard partition problems
• George Mertzios, Sotiris Nikoletseas, Christoforos Raptopoulos, and Paul Spirakis, Determining Majority in Networks with Local Interactions and very Small Local Memory
• Xavier Allamigeon, Pascal Benchimol, and Stephane Gaubert, The Tropical Shadow-Vertex Algorithm Solves Mean Payoff Games in Polynomial Time On Average
• Sune K. Jakobsen, Information Theoretical Cryptogenography
• Peyman Afshani, Timothy M. Chan, and Konstantinos Tsakalidis, Deterministic Rectangle Enclosure and Offline Dominance Reporting on the RAM
• Jelani Nelson and Huy Nguyen, Lower bounds for oblivious subspace embeddings
• Eli Ben-Sasson and Emanuele Viola, Short PCPs with projection queries
• Sayan Bhattacharya, Vahab Mirrokni, and Janardhan Kulkarni, Coordination Mechanisms for (Selfish) Routing over Time on a Tree
• Amihood Amir, Timothy M. Chan, Moshe Lewenstein and, Noa Lewenstein, On Hardness of Jumbled Indexing
• Shahar Dobzinski and Renato Paes Leme, Efficiency Guarantees in Auctions with Budgets
• Karl Bringmann, Fabian Kuhn, Konstantinos Panagiotou, Ueli Peter, and Henning Thomas, Internal DLA: Efficient Simulation of a Physical Growth Model
• Samir Datta, William Hesse and, Raghav Kulkarni, Dynamic Complexity of Directed Rechability and Other Problems
• Michael Lampis, Parameterized Approximation Schemes using Graph Widths
• Erik D. Demaine, Yamming Huang, Chung-Shou Liao, and Kunihiko Sadakane, Canadians Should Travel Randomly
• Laura Mancinska and Thomas Vidick, Unbounded entanglement can be needed to achieve the optimal success probability
• Omer Reingold, Ron Rothblum, and Udi Wieder, Pseudorandom Graphs in Data Structures
• Jiri Fiala, Pavel Klavík, Jan Kratochvil and, Roman Nedela, Algorithmic Aspects of Regular Graph Covers with Applications to Planar Graphs
• Michael Elkin, Ofer Neiman, and Shay Solomon, Light Spanners
• Zeev Dvir, Rafael Mendes de Oliveira, and Amir Shpilka, Testing Equivalence of Polynomials under Shifts
• Richard Cleve and Rajat Mittal, Characterization of Binary Constraint System Games.
• Raghu Meka, Omer Reingold, Guy Rothblum and, Ron Rothblum, Fast Pseudorandomness for Independence and Load Balancing
• Anna Gilbert, Yi Li, Ely Porat, and Martin Strauss, For-all Sparse Recovery in Near-Optimal Time
• Andreas Björklund, Rasmus Pagh, Virginia Vassilevska Williams, and Uri Zwick, Listing Triangles
• Andrew Childs, David Gosset, and Zak Webb, The Bose-Hubbard model is QMA-complete
• Konstantin Makarychev and Debmalya Panigrahi, Precedence-constrained Scheduling of Malleable Jobs with Preemption
• Yitong Yin, Spatial Mixing of Coloring Random Graphs
• Timon Hertli, Breaking the PPSZ Barrier for Unique 3-SAT
• Yaoyu Wang and Yitong Yin, Certificates in Data Structures
• John Iacono, Why some heaps support constant-amortized-time decrease-key operations, and others do not
• Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann, Consequences of Faster Alignment of Sequences
• Ramanujan M. S., Saket Saurabh, Pranabendu Misra, Manu Basavaraju, Fedor Fomin, and Petr Golovach, Parameterized Algorithms to Preserve Connectivity
• Clément Canonne and Ronitt Rubinfeld, Testing probability distributions underlying aggregated data
• Eric Blais, Johan Håstad, Rocco Servedio, and Li-Yang Tan, On DNF approximators for monotone Boolean functions
• Yuval Emek and Adi Rosen, Semi-Streaming Set Cover
• Markus Sortland Dregi and Daniel Lokshtanov, Parameterized Complexity of Bandwidth on Trees
• Mrinal Kumar and Shubhangi Saraf, Superpolynomial lower bounds for general homogeneous depth 4 arithmetic circuits
• Erik D. Demaine, Martin Demaine, Sandor Fekete, Matthew Patitz, Robert Schweller, Andrew Winslow, and Damien Woods, One Tile to Rule Them All: Simulating Any Tile Assembly System with a Single Universal Tile
• Andris Ambainis, Mohammad Bavarian, Yihan Gao, Jieming Mao, Xiaoming Sun, and Song Zuo, Tighter relations between sensitivity and other complexity measures
• Manoj Prabhakaran, Amit Sahai, and Akshay Wadia, Secure Computation using Leaky Tokens
• André Chailloux and Giannicola Scarpa, Parallel Repetition of Entangled Games with Exponential Decay via the Superposed Information Cost
• Mohammad Bavarian, Dmitry Gavinsky, and Tsuyoshi Ito, On the role of shared randomness in simultaneous communication
• Ankit Garg and Mark Braverman, Public vs private coin in bounded-round information
• Rafail Ostrovsky, Giuseppe Persiano, and Ivan Visconti, On Input Indistinguishable Proof Systems
• Artur Czumaj and Berthold Voecking, Thorp Shuffling, Butterflies, and Non-Markovian Couplings
• Kunal Talwar and Udi Wieder, Balanced Allocations: A Simple Proof for the Heavily Loaded Case
• Anupam Gupta, Kunal Talwar, and Udi Wieder, Changing Bases: Multistage Optimization for Matroids and Matchings
• Swastik Kopparty, Mrinal Kumar, and Michael Saks, Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields
• Karl Wimmer, Yi Wu, and Peng Zhang, Optimal query complexity for estimating the trace of a matrix
• Chinmay Hegde, Piotr Indyk, and Ludwig Schmidt, Nearly Linear-Time Model-Based Compressive Sensing
• Tomasz Krawczyk and Bartosz Walczak, Coloring Relatives of Interval Overlap Graphs Via On-Line Games
• Christian Wulff-Nilsen, Faster Separators for Shallow Minor-Free Graphs via Dynamic Approximate Distance Oracles
• Ittai Abraham and Shiri Chechik, Distance Labels with Optimal Local Stretch
• Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, and Vincenzo Roselli, Morphing Planar Graph Drawings Optimally
• Madur Tulsiani, John Wright, and Yuan Zhou, Optimal strong parallel repetition for projection games on low threshold rank graphs

Track B: Logic, Semantics, Automata, and Theory of Programming

• Jason Bell, Janusz Brzozowski, Nelma Moreira, and Rogério Reis, Symmetric Groups and Quotient Complexity of Boolean Operations
• Mikolaj Bojanczyk, Transducers with origin information
• Chris Heunen, Domain theory in quantum logic
• Jerzy Marcinkowski and Tomasz Gogacz, All--instances termination of chase is undecidable
• Joel Ouaknine and James Worrell, On the Positivity Problem for Simple Linear Recurrence Sequences
• Krishnendu Chatterjee and Rasmus Ibsen-Jensen, The Complexity of Ergodic Mean-payoff Games
• Alex Borello, Julien Cervelle, and Pascal Vanier, Turing degrees of limit sets of cellular automata
• Joel Ouaknine and James Worrell, Ultimate Positivity is Decidable for Simple Linear Recurrence Sequences
• Yuval Emek, Jochen Seidel, and Roger Wattenhofer, Computability in Anonymous Networks: Revocable vs. Irrecovable Outputs
• Radha Jagadeesan and James Riely, Between Linearizability and Quiescent Consistency: Quantitative Quiescent Consistency
• Marcello Bonsangue, Jurriaan Rot, Davide Ancona, Frank De Boer, and Jan Rutten, A Coalgebraic Foundation for Coinductive Union Types
• Artur Jeż, Context unification is in PSPACE
• Jean Christoph Jung, Carsten Lutz, Sergey Goncharov, and Lutz Schröder, Monodic Fragments of Probabilistic First-order Logic
• Qiang Yin, Yuxi Fu, Chaodong He, Mingzhang Huang, and Xiuting Tao, Branching Bisimilarity Checking for PRS
• Egor Derevenetc and Roland Meyer, Robustness against Power is PSpace-complete
• Manfred Droste and Vitaly Perevoshchikov, A Nivat Theorem for Weighted Timed Automata and Weighted Relative Distance Logic
• Mikołaj Bojańczyk, Tomasz Gogacz, Henryk Michalewski, and Michał Skrzypczak, On the decidability of MSO+U on infinite trees
• Andrea Cerone, Alexey Gotsman, and Hongseok Yang, Parameterised Linearisability
• Mikolaj Bojanczyk, Weak MSO+U with Path Quantifiers over Infinite Trees
• Stefan Kiefer and Björn Wachter, Stability and Complexity of Minimising Probabilistic Automata
• Thomas Place and Marc Zeitoun, Going higher in the First-order Quantifier Alternation Hierarchy on Words
• Michael Blondin, Alain Finkel, and Pierre McKenzie, Handling Infinitely Branching WSTS
• Dexter Kozen and Konstantinos Mamouras, Kleene Algebra with Equations
• Krishnendu Chatterjee and Laurent Doyen, Games with a Weak Adversary
• Dmitry Chistikov and Rupak Majumdar, Unary Pushdown Automata and Straight-Line Programs
• Namit Chaturvedi, Toward a Structure Theory of Regular Infinitary Trace Languages
• Daniel Bundala and Joel Ouaknine, On the Complexity of Temporal-Logic Path Checking
• Michael Wehar, Hardness Results for Intersection Non-Emptiness
• Sergey Goncharov and Dirk Pattinson, Coalgebraic Weak Bisimulation from Recursive Equations over Monads
• Petr Jancar, Bisimulation Equivalence and Semantic Finiteness of First-Order Grammars
• Damiano Mazza, Non-Uniform Polytime Computation in\\the Infinitary Affine Lambda-Calculus

Track C: Foundations of Networked Computation

• Yuval Emek, Tobias Langner, Jara Uitto, and Roger Wattenhofer, Solving the ANTS problem with Asynchronous Finite State Machines
• Johannes Dams, Martin Hoefer, and Thomas Kesselheim, Jamming-Resistant Learning in Wireless Networks
• Mohsen Ghaffari, Near-Optimal Distributed Approximation of Minimum-Weight Connected Dominating Set
• Jérémie Chalopin, Yoann Dieudonne, Arnaud Labourel, and Andrzej Pelc, Fault-Tolerant Rendezvous in Networks
• Afshin Nikzad and R Ravi, Sending Secrets Swiftly: Approximation Algorithms for Generalized Multicast Problems
• Merav Parter, Bypassing Erdős' Girth Conjecture: Hybrid Stretch and Sourcewise Spanners
• Rom Aschner and Matthew Katz, Bounded-Angle Spanning Tree: Modeling Networks with Angular Constraints
• Oliver Göbel, Martin Hoefer, Thomas Kesselheim, Thomas Schleiden, and Berthold Voecking, Online Independent Set Beyond the Worst-Case: Secretaries, Prophets, and Periods
• David Eisenstat, Claire Mathieu, and Nicolas Schabanel, Facility Location in Evolving Metrics
• Chen Avin, Michael Borokhovich, Zvi Lotker, and David Peleg, Distributed Computing on Core-Periphery Networks: Axiom-based Design
• Tsvi Kopelowitz, Robert Krauthgamer, Ely Porat, and Shay Solomon, Orienting Fully Dynamic Graphs with Worst-Case Time Bounds
• David Adjiashvili and Noy Rotbart, Labeling Schemes for Bounded Degree Graphs
• Erez Kantor and Shay Kutten, Optimal competitiveness for Symmetric Rectilinear Steiner Arborescence and related problems
• Olga Ohrimenko, Michael Goodrich, Roberto Tamassia, and Eli Upfal, The Melbourne Shuffle: Improving Oblivious Storage in the Cloud
• Jérémie Chalopin, Riko Jacob, Matus Mihalak, and Peter Widmayer, Data Delivery by Energy-Constrained Mobile Agents on a Line
• George Giakkoupis, Thomas Sauerwald, and Alexandre Stauffer, Randomized Rumor Spreading in Dynamic Graphs
• Adrian Kosowski and Dominik Pajak, Does Adding More Agents Make a Difference? A Case Study of Cover Time for the Rotor-Router
• Colin Cooper, Robert Elsässer, and Tomasz Radzik, The power of two choices in distributed voting

Abstracts