Accepted Papers

(as they appear in the proceedings, number in front is the LIPICs article ID)

 

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