Accepted Papers

  1. Hasan Abasi, Nader Bshouty, Ariel Gabizon and Elad Haramaty: On r-simple k-path
  2. Eric Allender, Nikhil Balaji and Samir Datta: Low-Depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs
  3. Eric Allender and Bireswar Das: Zero Knowledge and Circuit Minimization
  4. Andris Ambainis and Krišjānis Prūsis: A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity
  5. Tetsuo Asano, David Kirkpatrick, Koutaro Nakagawa and Osamu Watanabe: O(sqrt(n))-space and polynomial-time algorithm for the planar directed graph reachability
  6. Marie-Pierre Béal, Michel Blockelet and Catalin Dima: Sofic-Dyck shifts
  7. Rémy Belmonte, Pim Van ‘T Hof, Marcin Kamiński and Daniel Paulusma: Forbidden Induced Subgraphs and the Price of Connectivity for Feedback Vertex Set
  8. Marcello M. Bersani, Matteo Rossi and Pierluigi San Pietro: Logic Characterization of Timed (non-)Regular Languages
  9. Olaf Beyersdorff, Leroy Chew and Mikolas Janota: On Unification of QBF Resolution-Based Calculi
  10. Ivona Bezakova and Zachary Langley: Minimum planar multi-sink cuts with connectivity priors
  11. Vittorio Bilo’, Angelo Fanelli, Michele Flammini, Gianpiero Monaco and Luca Moscardelli: The Price of Envy-Freeness in Machine Scheduling
  12. Achim Blumensath, Thomas Colcombet and Olivier Carton: Asymptotic Monadic Second-Order Logic
  13. Beate Bollig: On the Complexity of Some Ordering Problems
  14. Pierre Bourhis, Michael Morak and Andreas Pieris: Towards Efficient Reasoning Under Guarded-based Disjunctive Existential Rules
  15. Joan Boyar and Magnus Gausdal Find: The Relationship Between Multiplicative Complexity and Nonlinearity
  16. Florian Bruse: Alternating Parity Krivine Automata
  17. Daniel Bundala and Joel Ouaknine: Advances in Parametric Real-Time Reasoning
  18. Leizhen Cai and Junjie Ye: Dual Connectedness of Edge-Bicolored Graphs and Beyond
  19. Arturo Carpi, Gabriele Fici, Stepan Holub, Jakub Oprsal and Marinella Sciortino: Universal Lyndon Words
  20. Julien Cassaigne, Gabriele Fici, Marinella Sciortino and Luca Quadro Zamboni: Cyclic Complexity of Words
  21. Julien Cassaigne, Anna Frid, Svetlana Puzynina and Luca Zamboni: Subword complexity and decomposition of the set of factors
  22. Namit Chaturvedi and Marcus Gelderie: Classifying Regular Infinitary Trace Languages Using Word Automata
  23. Jiehua Chen, Piotr Faliszewski, Rolf Niedermeier and Nimrod Talmon: Combinatorial Voter Control in Elections
  24. Ruiwen Chen, Valentine Kabanets and Nitin Saurabh: An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas
  25. Yijia Chen and Moritz Mueller: Bounded variable logic, parameterized logarithmic space, and Savitch’s theorem
  26. Suryajith Chillara and Partha Mukhopadhyay: On the Limits of Depth Reduction at Depth-3 Over Small Finite Fields
  27. Christian Choffrut and Bruno Guillon: An algebraic characterization of unary two-way transducers
  28. Thomas Colcombet, Laure Daviaud and Florian Zuleger: Size-Change Abstraction and Max-Plus Automata
  29. Jean-Baptiste Courtois and Sylvain Schmitz: Alternating Vector Addition Systems with States
  30. Cewei Cui, Zhe Dang, Thomas R. Fischer and Oscar Ibarra: Information Rate of Some Classes of Non-regular Languages: An Automata-theoretic Approach
  31. Marek Cygan, Dániel Marx, Marcin Pilipczuk and Michal Pilipczuk: Hitting forbidden subgraphs in graphs of bounded treewidth
  32. Maurits de Graaf and Bodo Manthey: Probabilistic Analysis of Power Assignments
  33. Julie De Pril, János Flesch, Jeroen Kuipers, Gijs Schoenmakers and Koos Vrieze: Existence of Secure Equilibrium in Multi-Player Games with Perfect Information
  34. Nicolas Delfosse, Zhentao Li and Stéphan Thomassé: A note on the minimum distance of quantum LDPC codes
  35. Josep Diaz and George Mertzios: Minimum Bisection is NP-hard on Unit Disk Graphs
  36. Jesus Dominguez and Maribel Fernandez: Relating nominal and higher-order rewriting
  37. Kord Eickmeyer, Michael Elberfeld and Frederik Harwath: Expressivity and Succinctness of Order-Invariant Logics on Depth-Bounded Structures
  38. Thomas Erlebach, Michael Hoffmann and Frank Kammer: Query-Competitive Algorithms for Cheapest Set Problems under Uncertainty
  39. Stefan Fafianie and Stefan Kratsch: Streaming Kernelization
  40. Stefan Felsner, Kolja Knauer, George Mertzios and Torsten Ueckerdt: Intersection Graphs of L-Shapes and Segments in the Plane
  41. Nathanaël Fijalkow, Hugo Gimbert, Florian Horn and Youssouf Oualhadj: Two Recursively Inseparable Problems for Probabilistic Automata
  42. Nathanaël Fijalkow and Charles Paperman: Monadic Second-Order Logic with Arbitrary Monadic Predicates
  43. Viliam Geffert and Alexander Okhotin: Transforming two-way alternating finite automata to one-way nondeterministic automata
  44. Christian Glasser and Maximilian Witek: Autoreducibility and Mitoticity of Logspace-Complete Sets for NP and Other Classes
  45. Tomasz Gogacz, Henryk Michalewski, Matteo Mio and Michał Skrzypczak: Measure Properties of Game Tree Languages
  46. Petr Golovach: Editing to a Connected Graph of Given Degrees
  47. Kristoffer Arnsfelt Hansen, Balagopal Komarath, Jayalal Sarma, Sven Skyum and Navid Talebanfard: Circuit Complexity of Properties of Graphs with Constant Planar Cutwidth
  48. Shuichi Hirahara and Akitoshi Kawamura: On Characterizations of Randomized Computation Using Plain Kolmogorov Complexity
  49. Furio Honsell, Luigi Liquori and Ivan Scagnetto: LLFP: Side Conditions and External Evidence as Monads
  50. Chien-Chung Huang and Sebastian Ott: New Results for Non-Preemptive Speed Scaling
  51. Martin Huschenbett, Dietrich Kuske and Georg Zetzsche: The monoid of queue actions
  52. Dmitry Itsykson and Dmitry Sokolov: Lower bounds for splittings by linear combinations
  53. Gábor Ivanyos, Raghav Kulkarni, Youming Qiao and Miklos Santha: An efficient quantum algorithm for finding hidden parabolic subgroups in the general linear group
  54. Riko Jacob, Tobias Lieber and Nodari Sitchinava: On the Complexity of List Ranking in the Parallel External Memory Model
  55. Galina Jiraskova and Tomas Masopust: On Upper and Lower Bounds on the Length of Alternating Towers
  56. Matthew Johnson, Daniel Paulusma and Carl Feghali: A Reconfigurations Analogue of Brook’s Theorem
  57. Matthew Johnson, Daniel Paulusma and Anthony Stewart: Knocking Out P_k-free Graphs
  58. Timo Jolivet and Jarkko Kari: Undecidable properties of self-affine sets and multi-tape automata
  59. Peter Jonsson, Victor Lagerkvist, Johannes Schmidt and Hannes Uppman: Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis
  60. Peter Jonsson and Johan Thapper: Affine consistency and the complexity of semilinear constraints
  61. Akitoshi Kawamura and Hiroyuki Ota: Small complexity classes for computable analysis
  62. Hartmut Klauck and Supartha Podder: Two Results about Quantum Messages
  63. Ivan Kováč, Ivana Selečéniová and Monika Steinová: On the Clique Editing Problem
  64. Gergely Kovásznai, Helmut Veith, Andreas Fröhlich and Armin Biere: On the Complexity of Symbolic Verification and Decision Problems in Bit-Vector Logic
  65. Jan Kratochvil, Jan Arne Telle and Marek Tesař: Computatio nal Complexity of Covering Three-Vertex Multigraphs
  66. Nils Kriege and Petra Mutzel: Finding Maximum Common Biconnected Subgraphs in Series-Parallel Graphs
  67. Jeremy Kun and Lev Reyzin: On Coloring Resilient Graphs
  68. Antti Kuusisto and Emanuel Kieronski: Complexity and expressivity of uniform one-dimensional fragment with equality
  69. Salvatore La Torre, Margherita Napoli and Gennaro Parlato: A Unifying Approach for Multistack Pushdown Automata
  70. Martin Lang, Christof Löding and Amaldev Manuel: Definability and Transformations for Cost Logics and Automatic Structures
  71. Moshe Lewenstein, Ian Munro, Yakov Nekrich and Sharma V. Thankachan: Document Retrieval with One Wildcard
  72. Akaki Mamageishvili, Matus Mihalak and Simone Montemezzani: An H_{n/2} Upper Bound on the Price of Stability of Undirected Network Design Games
  73. Florin Manea, Mike Müller, Dirk Nowotka and Shinnosuke Seki: Generalised Lyndon-Schützenberger Equations
  74. Ines Marusic and James Worrell: Complexity of Equivalence and Learning for Multiplicity Tree Automata
  75. Filip Mazowiecki, Filip Murlak and Adam Witkowski: Monadic datalog and regular tree pattern queries
  76. Roy Mennicke: Model Checking Concurrent Recursive Programs using Local Temporal Logics
  77. Othon Michail and Paul Spirakis: Traveling Salesman Problems in Temporal Graphs
  78. Angelo Montanari, Gabriele Puppis and Pietro Sala: Decidability of the interval temporal logic AA ̄BB ̄ over the rationals
  79. Andrzej Murawski, Steven Ramsay and Nikos Tzevelekos: Reachability in pushdown register automata
  80. Yuto Nakashima, Takashi Okabe, Tomohiro I, Shunsuke Inenaga, Hideo Bannai and Masayuki Takeda: Inferring Strings from Lyndon factorization
  81. Wied Pakusa, Erich Grädel, Faried Abu Zaid and Martin Grohe: Choiceless Polynomial Time on structures with small Abelian colour classes
  82. Ron Y. Pinter, Hadas Shachnai and Meirav Zehavi: Deterministic Parameterized Algorithms for the Graph Motif Problem
  83. Matteo Pontecorvi, Vijaya Ramachandran and Meghana Nasre: Betweenness Centrality – Incremental and Faster
  84. Ramanujan M. S., Sudeshna Kolay, Pranabendu Misra and Saket Saurabh: Parameterized Approximations via d-Skew Symmetric Multicut
  85. Abhisekh Sankaran, Bharat Adsul and Supratik Chakraborty: A Generalization of the \Lo\’s-Tarski Preservation Theorem over Classes of Finite Structures
  86. Sven Schewe and Thomas Methrayil Varghese: Determinising Parity Automata
  87. Sven Schewe and Thomas Methrayil Varghese: Tight Bounds for Complementing Parity Automata
  88. Vyas Ram Selvam: The Two Queries Assumption and Arthur-Merlin Classes
  89. Hadas Shachnai, Ariella Voloshin and Shmuel Zaks: Flexible Bandwidth Assignment with Application to Optical Networks
  90. Tim Smith: A Pumping Lemma for Two-Way Finite Transducers
  91. Tim Smith: On Infinite Words Determined by Indexed Languages
  92. Georgios Stamoulis: Approximation Algorithms For Bounded Color Matchings via Convex Decompositions
  93. René Van Bevern, Robert Bredereck, Jiehua Chen, Vincent Froese, Rolf Niedermeier and Gerhard Woeginger: Network-Based Dissolution
  94. Michał Wrona: Tractability Frontier for Dually-Closed Ord-Horn Quantified Constraint Satisfaction Problems
  95. Thomas Zeume: The Dynamic Descriptive Complexity of k-Clique

Comments are closed.