Accepted Papers

(in the order of submission)

  • Mahdi Cheraghchi, Shuichi Hirahara, Dimitrios Myrisiotis and Yuichi Yoshida. One-tape Turing machine and branching program lower bounds for MCSP
  • Jacob Holm and Eva Rotenberg. Good r-divisions Imply Optimal Amortized Decremental Biconnectivity
  • Hans-Joachim Boeckenhauer, Elisabet Burjons, Juraj Hromkovic, Henri Lotze and Peter Rossmanith. Online Simple Knapsack with Reservation Costs
  • Marta Piecyk and Paweł Rzążewski. Fine-grained complexity of the list homomorphism problem: feedback vertex set and cutwidth
  • Daniel Gibney and Sharma V. Thankachan. Finding an Optimal Alphabet Ordering for Lyndon Factorization is Hard
  • Pedro Paredes. Spectrum preserving short cycle removal on regular graphs
  • Amin Coja-Oghlan, Philipp Loick, Max Hahn-Klimroth, Noela Müller, Konstantinos Panagiotou and Matija Pasch. Inference and mutual information on random factor graphs
  • Guilhem Gamard, Pierre Guillon, Kévin Perrot and Guillaume Theyssier. Rice-like theorems for automata networks
  • Lars Jaffke, Paloma de Lima and Daniel Lokshtanov. b-Coloring Parameterized by Clique-Width
  • Timothy M. Chan and Saladi Rahul. Simple Multi-Pass Streaming Algorithms for Skyline Points and Extreme Points
  • Meike Neuwohner. An Improved Approximation Algorithm for the Maximum Weight Independent Set Problem in d-Claw Free Graphs
  • Md Lutfar Rahman and Thomas Watson. 6-Uniform Maker-Breaker Game Is PSPACE-Complete
  • Thomas Erlebach, Michael Hoffmann and Murilo de Lima. Round-Competitive Algorithms for Uncertainty Problems with Parallel Queries
  • Zhengyang Guo and Yi Li. Geometric Cover with Outliers Removal
  • Karolina Okrasa and Paweł Rzążewski. Complexity of the list homomorphism problem in hereditary graph classes
  • Andreas Björklund. An Asymptotically Fast Polynomial Space Algorithm for Hamiltonicity Detection in Sparse Directed Graphs
  • Pascal Bergsträßer, Moses Ganardi and Georg Zetzsche. A characterization of wreath products where knapsack is decidable
  • Sujoy Bhore and Csaba Toth. On Euclidean Steiner (1+epsilon)-Spanners
  • Nikolaos Melissinos, Michael Lampis and Ararat Harutyunyan. Digraph Coloring and Distance to Acyclicity
  • Divesh Aggarwal, Yanlin Chen, Rajendra Kumar and Yixin Shen. Improved (Provable) Algorithms for the Shortest Vector Problem via Bounded Distance Decoding
  • Jugal Garg, Edin Husić and László A. Végh. Auction Algorithms for Market Equilibrium with Weak Gross Substitute Demands and their Applications
  • Robert Ferens and Artur Jeż. Solving one variable word equations in free groups in cubic time
  • William Lochet, Daniel Lokshtanov, Saket Saurabh and Meirav Zehavi. Exploiting Dense Structures in Parameterized Complexity
  • Pascal Schweitzer and Constantin Seebach. Resolution with Symmetry Rule applied to Linear Equations
  • Anna Arutyunova and Melanie Schmidt. Achieving anonymity via weak lower bound constraints for k-median and k-means
  • Markus Lohrey. Subgroup membership in GL(2,Z)
  • Mikhail Berlinkov, Robert Ferens, Andrew Ryzhikov and Marek Szykuła. Synchronizing Strongly Connected Partial DFAs
  • Joshua Grochow, Youming Qiao and Gang Tang. On testing isomorphism of polynomials, algebras, and multilinear forms
  • John Fearnley and Rahul Savani. A faster algorithm for finding Tarski fixed points
  • Joel Day, Pamela Fleischmann, Maria Kosche, Tore Koss, Florin Manea and Stefan Siemer. The Edit Distance to $k$-Subsequence Universality
  • Pavel Dvořák and Michal Koucký. Barrington Plays Cards: The Complexity of Card-based Protocols
  • Keren Censor-Hillel, Dean Leitersdorf and Volodymyr Polosukhin. Distance Computations in the Hybrid Network Model via Oracle Simulations
  • Siddharth Barman, Omar Fawzi and Paul Fermé. Tight Approximation Guarantees for Concave Coverage Problems
  • Ismaël Jecker. A Ramsey Theorem for Finite Monoids
  • Tomohiro Koana, Vincent Froese and Rolf Niedermeier. Binary Matrix Completion Under Diameter Constraints
  • Simon Apers, András Gilyén and Stacey Jeffery. A Unified Framework of Quantum Walk Search
  • Fedor Fomin, Petr Golovach, Fahad Panolan, Geevarghese Philip and Saket Saurabh. Diverse Collections in Matroids and Graphs
  • Lorenzo Clemente and Corentin Barloy. Bidimensional linear recursive sequences and universality of unambiguous register automata (Extended abstract)
  • Pawel Gawrychowski, Maria Kosche, Tore Koss, Florin Manea and Stefan Siemer. Efficiently Testing Simon’s Congruence
  • Haim Kaplan and Jay Tenenbaum. Locality-sensitive hashing for efficient similar polygon retrieval
  • Ulrich A. Brodowsky and Stefan Hougardy. The Approximation Ratio of the 2-Opt Heuristic for the Euclidean Traveling Salesman Problem
  • Florent Koechlin and Pablo Rotondo. Absorbing patterns in BST-like expression-trees
  • Ramgopal Venkateswaran and Ryan O’Donnell. Quantum approximate counting with nonadaptive Grover iterations
  • Silvia Butti and Victor Dalmau. The Complexity of the Distributed Constraint Satisfaction Problem
  • Anselm Haak, Arne Meier, Om Prakash and Raghavendra Rao B V. Parameterised Counting in Logspace
  • Olga Martynova and Alexander Okhotin. Lower bounds for graph-walking automata
  • Édouard Bonnet. Inapproximability of Diameter in super-linear time: Beyond the 5/3 ratio
  • Marcin Bienkowski, Björn Feldkord and Paweł Schmidt. A Nearly Optimal Deterministic Online Algorithm for Non-Metric Facility Location
  • Shaohua Li, Marcin Pilipczuk and Manuel Sorge. Cluster Editing parameterized above modification-disjoint P_3-packings
  • Ramanujan M. Sridharan, Fahad Panolan, Akanksha Agrawal, Saket Saurabh and Lawqueen Kanesh. An FPT Algorithm for Elimination Distance to Bounded Degree Graphs
  • Libor Barto, Diego Battistelli and Kevin M. Berg. Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean Case
  • Harry Buhrman, Subhasree Patro and Florian Speelman. A Framework of Quantum Strong Exponential-Time Hypotheses
  • Petr Golovach, Christian Komusiewicz, Dieter Kratsch and Van Bang Le. Refined Notions of Parameterized Enumeration Kernels with Applications to Matching Cut Enumeration
  • Léo Exibard, Emmanuel Filiot and Ayrat Khalimov. Church Synthesis on Register Automata over Infinite Ordered Data Domains
  • Ce Jin, Jelani Nelson and Kewen Wu. An Improved Sketching Bound for Edit Distance
  • Stefan Göller and Mathieu Hilaire. Reachability in two-parametric timed automata with one parameter is EXPSPACE-complete