Program

Paul G. Spirakis. A Guided Tour in Random Intersection Graphs.

Dániel Marx. The square root phenomenon in planar graphs

Susanne Albers. Recent Advances for a Classical Scheduling Problem

Orna Kupferman. Formalizing and Reasoning about Quality

1. Radu Curticapean. Counting matchings of size k is #W[1]-hard

2. Hans Bodlaender, Marek Cygan, Stefan Kratsch and Jesper Nederlof. Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth

3. Michael Lampis. Model Checking Lower Bounds for Simple Graphs

4. Dániel Marx and László A. Végh. Fixed-parameter algorithms for minimum cost edge-connectivity augmentation

5. Eun Jung Kim, Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, Ignasi Sau and Somnath Sikdar. Linear kernels and single-exponential algorithms via protrusion decompositions

1. Stéphane Demri, Amit Kumar Dhar and Arnaud Sangnier. On the Complexity of Verifying Regular Properties on Flat Counter Systems

2. Markus Lohrey, Benjamin Steinberg and Georg Zetzsche. Rational subsets and submonoids of wreath products

3. Emilie Charlier, Teturo Kamae, Svetlana Puzynina and Luca Q. Zamboni. Self-Shuffling Words

4. Artur Jeż. One-variable word equations in linear time

5. Georg Zetzsche. Silent Transitions in Automata with Storage

1. Tomasz Jurdzinski, Dariusz Kowalski and Grzegorz Stachowiak.  Distributed Deterministic Broadcasting in Wireless Networks of Weak Devices

2. Seth Pettie and Hsin-Hao Su.  Fast Distributed Coloring Algorithms for Triangle-Free Graphs

3. Monika Henzinger, Sebastian Krinninger and Danupon Nanongkai. Sublinear-Time Maintenance of Breadth-First Spanning Tree in Partially Dynamic Networks

4. David G. Harris, Ehab Morsy, Gopal Pandurangan, Peter Robinson and Aravind Srinivasan.  Efficient Computation of Balanced Structures

1. Vladimir Kolmogorov. The power of linear programming for finite-valued CSPs: a constructive characterization

2. Heng Guo and Tyson Williams. The Complexity of Planar Boolean #CSP with Complex Weights

3. Arnab Bhattacharyya and Yuichi Yoshida. An Algebraic Characterization of Testable CSP's

4. Hannes Uppman. The Complexity of Three-element Min-Sol and Conservative Min-Cost-Hom

1. Gregory M. Kobele and Sylvain Salvati. The IO and OI hierarchies revisited

2. James Worrell. On the Complexity of Multitape Automata Equivalence

3. Udi Boker, Denis Kuperberg, Orna Kupferman and Michał Skrzypczak. Nondeterminism in the Presence of a Diverse or Unknown Future

4. Marcus Gelderie. Strategy Composition in Compositional Games

1. Per Austrin, Petteri Kaski, Mikko Koivisto and Jussi Määttä. Space-Time Tradeoffs for Subset Sum: An Improved Worst Case Algorithm

2. Amir Abboud and Kevin Lewi. Exact Weight Subgraphs and the k-Sum Conjecture

3. Marek Cygan and Marcin Pilipczuk. Faster exponential-time algorithms in graphs of bounded average degree

4. Massimo Lauria, Pavel Pudlák, Vojtěch Rödl and Neil Thapen. The complexity of proving that a graph is Ramsey

1. Andrew Goldberg, Maxim Babenko, Anupam Gupta and Viswanath Nagarajan. Algorithms for Hub Label Optimization

2. Oren Weimann and Raphael Yuster. Approximating the Diameter of Planar Graphs in Near Linear Time

3. Reinhard Bauer, Tobias Columbus, Ignaz Rutter and Dorothea Wagner. Search-Space Size in Contraction Hierarchies

4. Claire Mathieu and Hang Zhou. Graph reconstruction via distance oracles

5. Reut Levi and Dana Ron. A Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor

1.Irit Dinur and Elazar Goldenberg. Clustering in the Boolean Hypercube in a List Decoding Regime

2. Mrinal Kumar, Gaurav Maheshwari and Jayalal Sarma. Arithmetic Circuit Lower Bounds via MaxRank

3. Christian Glasser, Dung T. Nguyen, Christian Reitwießner, Alan L. Selman and Maximilian Witek. Autoreducibility of Complete Sets for Log-Space and Polynomial-Time Reductions

4. Yuval Filmus, Massimo Lauria, Mladen Miksa, Jakob Nordstrom and Marc Vinyals. Towards an Understanding of Polynomial Calculus: New Separations and Lower Bounds (Extended Abstract)

5. Nikos Leonardos. An improved lower bound for the randomized decision tree complexity of recursive majority

1. Helger Lipmaa and Tomas Toft.  Secure Equality and Greater-Than Tests with Sublinear Online Complexity

2. Sebastian Faust, Carmit Hazay and Daniele Venturi.  Outsourced Pattern Matching

3. Sepp Hartung, André Nichterlein, Rolf Niedermeier and Ondrej Suchy.  A Refined Complexity Analysis of Identity Anonymization on Graphs

1. Vladimir Braverman, Rafail Ostrovsky and Dan Vilenchik. How Hard is Counting Triangles in the Streaming Model

2. Christian Konrad and Adi Rosén. Approximating Semi-Matchings in Streaming and in Two-Party Communication

3. Tom Gur and Ran Raz. Arthur-Merlin Streaming Complexity

4. Alexandr Andoni, Huy Nguyen, Yury Polyanskiy and Yihong Wu. Tight Lower Bound for Linear Sketches of Moments

5. Markus Blaeser. Noncommutativity makes determinants hard

1. Nicolas Basset. A maximal entropy stochastic process for a timed automaton

2. Kousha Etessami, Alistair Stewart and Mihalis Yannakakis. Stochastic Context-Free Grammars, Regular Languages, and Newton's method

3. Rémy Chrétien, Véronique Cortier and Stephanie Delaune. From security protocols to pushdown automata

4. Gilles Barthe and Federico Olmedo. Beyond differential privacy: Composition theorems and Relational Logic for f-divergences between Probabilistic Programs

5. Yuxi Fu. Checking Equality and Regularity for Normed BPA with Silent Moves

1. Ran Duan and Kurt Mehlhorn. A Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market

2. Dimitris Fotakis and Christos Tzamos. On the Power of Deterministic Mechanisms for Facility Location Games

3. T-H. Hubert Chan, Mingfei Li, Li Ning and Shay Solomon. New Doubling Spanners: Better and Simpler

4. Telikepalli Kavitha and Nithin Varma. Small Stretch Pairwise Spanners

5. Piotr Indyk and Ilya Razenshteyn. On Model-Based RIP-1 Matrices

1. S. Anand, Karl Bringmann, Tobias Friedrich, Naveen Garg and Amit Kumar. Minimizing maximum (weighted) flow-time on related and unrelated machines

2. Marcin Mucha and Maxim Sviridenko. No-Wait Flowshop Scheduling is as Hard as Asymmetric Traveling Salesman Problem

3. Nicole Megow and José Verschae. Dual techniques for scheduling on a machine with varying speed

4. Klaus Jansen and Kim-Manuel Klein. A Robust AFPTAS for Online Bin Packing with Polynomial Migration

5. Marcin Bieńkowski, Jarek Byrka, Marek Chrobak, Neil Dobbs, Tomasz Nowicki, Maxim Sviridenko, Grzegorz Świrszcz and Neal Young. Approximation Algorithms for the Joint Replenishment Problem with Deadlines

1. Hubie Chen and Daniel Marx. Block-Sorted Quantified Conjunctive Queries

2. Robert Ganian, Petr Hlineny, Daniel Kral, Jan Obdrzalek, Jarett Schwartz and Jakub Teska. FO Model Checking of Interval Graphs

3. Wojciech Czerwiński, Wim Martens and Tomas Masopust. Efficient Separability of Regular Languages by Subsequences and Suffixes

4. Saguy Benaim, Michael Benedikt, Witold Charatonik, Emanuel Kieronski, Rastislav Lenhardt, Filip Mazowiecki and James Worrell. Complexity of two-variable logic over finite trees

5. Georg Gottlob, Andreas Pieris and Lidia Tendera. Querying the Guarded Fragment with Transitivity

1. Susanne Albers and Achim Passen.  New Online Algorithms for Story Scheduling in Web Advertising

2. George Mertzios, Othon Michail, Ioannis Chatzigiannakis and Paul Spirakis.  Temporal Network Optimization Subject to Connectivity Constraints

3. Martin Hoefer and Lisa Wagner.  Locally Stable Marriage with Strict Preferences

4. Yoram Bachrach and Ely Porat.  Sketching For Big Data Recommender Systems Using Fast Pseudo-Random Fingerprints

1. Roberto Grossi, Rajeev Raman, Srinivasa Rao Satti and Rossano Venturini. Dynamic Compressed Strings with Random Access

2. Gregory Kucherov and Yakov Nekrich. Full-fledged Real-Time Indexing for Constant Size Alphabets

3. Ozgur Ozkan, John Iacono, Stefan Langerman and Erik D. Demaine. Combining Binary Search Trees

4. Philip Bille, Inge Li Gørtz, Gad Landau and Oren Weimann. Tree Compression with Top Trees

5. Philip Bille, Johannes Fischer, Inge Li Gørtz, Tsvi Kopelowitz, Benjamin Sach and Hjalte Wedel Vildhøj. Sparse Suffix Tree Construction in Small Space

1. Mohammadhossein Bateni, Mohammadtaghi Hajiaghayi and Vahid Liaghat. Improved Approximation Algorithms for (Budgeted) Node-weighted Steiner Problems

2. Chandra Chekuri, Guyslain Naves and Bruce Shepherd. Maximum Edge-Disjoint Paths in $k$-Sums of Graphs

3. Maxim Sviridenko and Justin Ward. Large Neighborhood Local Search for the Maximum Set Packing Problem

4. Joseph Cheriyan, Zhihan Gao, Konstantinos Georgiou and Sahil Singla. On Integrality Ratios for Asymmetric TSP in the Sherali-Adams Hierarchy

5. Petr Golovach, Pinar Heggernes, Dieter Kratsch and Yngve Villanger. An incremental polynomial time algorithm to enumerate all minimal edge dominating sets

1. Yoann Dieudonne and Andrzej Pelc.  Deterministic Polynomial Approach in the Plane

2. Emanuele Guido Fusco, Andrzej Pelc and Rossella Petreschi.  Learning a ring cheaply and fast

3. Jurek Czyzowicz, Evangelos Kranakis and Eduardo Pacheco.  Localization For a System of Colliding Robots

4. Luca Becchetti, Vincenzo Bonifaci, Michael Dirnberger, Andreas Karrenbauer and Kurt Mehlhorn.  Physarum Can Compute Shortest Paths: Convergence Proofs and Complexity Bounds

5. George Mertzios and Paul Spirakis.  Strong Bounds for Evolution in Networks

1. Karl Bringmann and Tobias Friedrich. Exact and Efficient Generation of Geometric Random Variates and Random Graphs

2. Thomas Bläsius, Ignaz Rutter and Dorothea Wagner. Optimal Orthogonal Graph Drawing with Convex Bend Costs

3. Cecilia Bohler, Rolf Klein, Chih-Hung Liu, Evanthia Papadopoulou, Panagiotis Cheilaris and Maksym Zavershynskyi. On the Complexity of Higher Order Abstract Voronoi Diagrams

4. Anindya De, Ilias Diakonikolas and Rocco Servedio. A robust Khintchine inequality, and algorithms for computing optimal constants in Fourier analysis and high-dimensional geometry

1. Pierre-Malo Denielou and Nobuko Yoshida. Multiparty Compatibility in Communicating Automata: Characterisation and Synthesis of Global Session Types

2. Luca Padovani. Fair Subtyping for Open Session Types

3. Hyeonseung Im, Keiko Nakata and Sungwoo Park. Contractive Signatures with Recursive Types, Type Parameters, and Abstract Types

4. Roberto Di Cosmo, Jacopo Mauro, Stefano Zacchiroli and Gianluigi Zavattaro. Component Reconfiguration in the Presence of Conflicts

5. Tomas Petricek, Dominic Orchard and Alan Mycroft. Coeffects: Unified static analysis of context-dependence

1. Yaron Velner. The Complexity of Infinitely Repeated Alternating Move Games

2. Endre Boros, Khaled Elbassioni, Vladimir Gurvich and Kazuhisa Makino. A Pseudo-Polynomial Algorithm for Mean Payoff Stochastic Games with Perfect Information and a Few Random Positions

3. Daniel Grier. Deciding the Winner of an Arbitrary Finite Poset Game is PSPACE-Complete

4. Martin Hirt and Pavel Raykov. On the Complexity of Broadcast Setup

5. Anna Gilbert, Hung Ngo, Ely Porat, Atri Rudra and Martin Strauss. l2/l2-foreach sparse recovery with low risk

1. Karl Bringmann, Benjamin Doerr, Adrian Neumann and Jakub Sliacan. Online Checkpointing with Improved Worst-Case Guarantees

2. Andrei Negoescu and Gabriel Moruz. Improved Space Bounds for Strongly Competitive Randomized Paging Algorithms

3. Martin Aumüller and Martin Dietzfelbinger. Optimal Partitioning for Dual Pivot Quicksort

4. Xin Li, Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Manoj Prabhakaran, Amit Sahai and David Zuckerman. Robust Pseudorandom Generators

5. Jan Bulánek, Michal Koucký and Michael Saks. On Randomized Online Labeling with Polynomially Many Labels

1. Blaise Genest, Hugo Gimbert, Anca Muscholl and Igor Walukiewicz Asynchronous Games over Tree Architectures

2. Colin Stirling. Proof Systems for Retracts in Simply Typed Lambda Calculus

3. Oliver Friedmann, Felix Klaedtke and Martin Lange Ramsey Goes Visibly Pushdown

4. Daniel Leivant and Jean-Yves Marion. Evolving graph-structures and their implicit computational complexity

5. Facundo Carreiro, Daniel Gorín and Lutz Schröder. Coalgebraic announcement logics

1. Brett Hemenway, Rafail Ostrovsky and Mary Wootters. Local Correctability of Expander Codes

2. Karl Wimmer and Yuichi Yoshida. Testing Linear-Invariant Function Isomorphism

3. Omri Weinstein, Mark Braverman, Amir Yehudayoff and Anup Rao. Direct product via round-preserving compression

4. Aleksandrs Belovs, Andrew M. Childs, Stacey Jeffery, Robin Kothari and Frederic Magniez. Time-efficient quantum walks for 3-distinctness

5. Matthew Patitz, Scott Summers, Damien Woods, Erik Demaine, Robert Schweller and Trent Rogers. The two-handed tile assembly model is not intrinsically universal

1. David Avis and Hans Raj Tiwary. On the extension complexity of combinatorial polytopes

2. Tobias Brunsch and Heiko Röglin. Finding Short Paths on Polytopes by the Shadow Vertex Algorithm

3. Ryan O'Donnell and Li-Yang Tan. A composition theorem for the Fourier Entropy-Influence conjecture

1. David Janin. Algebras, automata and logic for languages of labeled birooted trees

2. Rajeev Alur and Mukund Raghothaman. Decision Problems for Additive Regular Functions

3. Kevin Woods. Presburger Arithmetic, Rational Generating Functions, and Quasi-polynomials

1. L. Elisa Celis, Dimitrios C. Gklezakos and Anna R. Karlin.  On Revenue Maximization for Agents with Costly Information Acquisition

2. George Christodoulou and Martin Gairing.  Price of Stability in Polynomial Congestion Games

3. Nikolay Gravin and Pinyan Lu.  Competitive Auctions for Markets with Positive Externalities