default search action
52nd ICALP 2025: Aarhus, Denmark
- Keren Censor-Hillel
, Fabrizio Grandoni
52nd International Colloquium on Automata, Languages, and Programming, ICALP 2025, July 8-11, 2025, Aarhus, Denmark. LIPIcs 334, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2025, ISBN 978-3-95977-372-0 - Front Matter, Table of Contents, Preface, Conference Organization. 0:i-0:xliv
- Anupam Gupta:
Online Algorithm Design Beyond the Worst Case (Invited Talk). 1:1-1:1 - Dana Ron:
Let's Try to Be More Tolerant: On Tolerant Property Testing and Distance Approximation (Invited Talk). 2:1-2:10 - Anders Aamand, Allen Liu, Shyam Narayanan:
Near-Optimal Trace Reconstruction for Mildly Separated Strings. 3:1-3:20 - Pierre Aboulker, Édouard Bonnet, Timothé Picavet, Nicolas Trotignon:
Induced Disjoint Paths Without an Induced Minor. 4:1-4:14 - Deeksha Adil, Shunhua Jiang, Rasmus Kyng:
Acceleration Meets Inverse Maintenance: Faster ℓ∞-Regression. 5:1-5:16 - Deeksha Adil, Thatchaphol Saranurak
Decremental (1+ε)-Approximate Maximum Eigenvector: Dynamic Power Method. 6:1-6:19 - Panagiotis Aivasiliotis, Andreas Göbel, Marc Roth, Johannes Schmitt:
Parameterised Holant Problems. 7:1-7:14 - Hessa Al-Thani, Viswanath Nagarajan:
Identifying Approximate Minimizers Under Stochastic Uncertainity. 8:1-8:18 - Jonathan Allcock, Jinge Bao, Aleksandrs Belovs, Troy Lee, Miklos Santha:
On the Quantum Time Complexity of Divide and Conquer. 9:1-9:20 - Aida Aminian, Shahin Kamali
On the Complexity of Telephone Broadcasting from Cacti to Bounded Pathwidth Graphs. 10:1-10:17 - Prashanth Amireddy, Amik Raj Behera
A Near-Optimal Polynomial Distance Lemma over Boolean Slices. 11:1-11:17 - Aditya Anand, Euiwoong Lee, Jason Li, Thatchaphol Saranurak
All-Subsets Important Separators with Applications to Sample Sets, Balanced Separators and Vertex Sparsifiers in Directed Graphs. 12:1-12:20 - Simon Apers, Minbo Gao, Zhengfeng Ji, Chenghua Liu:
Quantum Speedup for Sampling Random Spanning Trees. 13:1-13:21 - Per Austrin, Ioana O. Bercea, Mayank Goswami, Nutan Limaye, Adarsh Srinivasan:
Algorithms for the Diverse-k-SAT Problem: The Geometry of Satisfying Assignments. 14:1-14:17 - Christine Awofeso, Patrick Greaves, Oded Lachish, Amit Levi, Felix Reidl:
Testing C_k-Freeness in Bounded Admissibility Graphs. 15:1-15:20 - Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn, Augusto Modanese
Shared Randomness Helps with Local Distributed Problems. 16:1-16:18 - Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov, Dániel Marx
Robust Contraction Decomposition for Minor-Free Graphs and Its Applications. 17:1-17:19 - Kiril Bangachev, S. Matthew Weinberg:
q-Partitioning Valuations: Exploring the Space Between Subadditive and Fractionally Subadditive Valuations. 18:1-18:20 - Kiarash Banihashem, Leyla Biabani, Samira Goudarzi, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, Morteza Monemizadeh:
Dynamic Algorithms for Submodular Matching. 19:1-19:21 - Ishan Bansal, Joe Cheriyan, Sanjeev Khanna, Miles Simmons:
Improved Approximation Algorithms for Capacitated Network Design and Flexible Graph Connectivity. 20:1-20:20 - Paul Beame, Michael Whitmeyer:
Multiparty Communication Complexity of Collision-Finding and Cutting Planes Proofs of Concise Pigeonhole Principles. 21:1-21:20 - Amik Raj Behera
New Bounds for the Ideal Proof System in Positive Characteristic. 22:1-22:20 - Omri Ben-Eliezer, Tomer Grossman, Moni Naor:
On the Instance Optimality of Detecting Collisions and Subgraphs. 23:1-23:14 - Gal Beniamini, Nir Lavee
Counting Permutation Patterns with Multidimensional Trees. 24:1-24:18 - Benjamin Bergougnoux, Édouard Bonnet, Julien Duron:
Mim-Width Is paraNP-Complete. 25:1-25:17 - Gaétan Berthe
Pushing the Frontiers of Subexponential FPT Time for Feedback Vertex Set. 26:1-26:15 - Koustav Bhanja:
Minimum+1 Steiner Cut and Dual Edge Sensitivity Oracle: Bridging Gap between Global and (s, t)-cut. 27:1-27:20 - Vishwas Bhargava, Devansh Shringi:
Faster & Deterministic FPT Algorithm for Worst-Case Tensor Decomposition. 28:1-28:20 - Aditya Bhaskara, Sepideh Mahabadi, Madhusudhan Reddy Pittu, Ali Vakilian, David P. Woodruff:
Guessing Efficiently for Constrained Subspace Approximation. 29:1-29:20 - Sujoy Bhore, Lazar Milenkovic:
Light Spanners with Small Hop-Diameter. 30:1-30:16 - Péter Biró, Gergely Csáji, Ildikó Schlotter:
Stable Hypergraph Matching in Unimodular Hypergraphs. 31:1-31:20 - Greg Bodwin, Michael Dinitz, Ama Koranteng, Lily Wang:
Light Edge Fault Tolerant Graph Spanners. 32:1-32:20 - Itai Boneh, Shay Golan, Shay Mozes, Daniel Prigan, Oren Weimann:
Faster Construction of a Planar Distance Oracle with Õ(1) Query Time. 33:1-33:21 - Alex Bortolotti, Monaldo Mastrolilli
On the Degree Automatability of Sum-Of-Squares Proofs. 34:1-34:19 - Karl Bringmann, Nick Fischer, Bernhard Haeupler, Rustam Latypov:
Near-Optimal Directed Low-Diameter Decompositions. 35:1-35:18 - Kevin Buchin
Faster Fréchet Distance Under Transformations. 36:1-36:20 - Andrei A. Bulatov, Stanislav Zivný:
Satisfiability of Commutative vs. Non-Commutative CSPs. 37:1-37:18 - Silvia Butti, Alberto Larrauri, Stanislav Zivný:
Optimal Inapproximability of Promise Equations over Finite Groups. 38:1-38:14 - Baris Can Esmer, Ariel Kulik:
Sampling with a Black Box: Faster Parameterized Approximation Algorithms for Vertex Deletion Problems. 39:1-39:20 - Nairen Cao, Shi Li, Jia Ye:
Simultaneously Approximating All Norms for Massively Parallel Correlation Clustering. 40:1-40:20 - Agustín Caracci, Christoph Dürr, José Verschae:
Randomized Binary and Tree Search Under Pressure. 41:1-41:19 - Amir Carmel, Debarati Das, Evangelos Kipouridis, Evangelos Pipis:
Fitting Tree Metrics and Ultrametrics in Data Streams. 42:1-42:21 - Karthekeyan Chandrasekaran, Chandra Chekuri, Shubhang Kulkarni:
On Deleting Vertices to Reduce Density in Graphs and Supermodular Functions. 43:1-43:20 - Karthekeyan Chandrasekaran, Chandra Chekuri, Weihao Zhu:
Online Disjoint Spanning Trees and Polymatroid Bases. 44:1-44:20 - Karthekeyan Chandrasekaran, Yuri Faenza, Chengyue He, Jay Sethuraman:
Scarf's Algorithm on Arborescence Hypergraphs. 45:1-45:18 - Karthekeyan Chandrasekaran, Siyue Liu, R. Ravi:
Minimum Cost Nowhere-Zero Flows and Cut-Balanced Orientations. 46:1-46:21 - Arnab Chatterjee, Amin Coja-Oghlan, Mihyun Kang, Lena Krieg, Maurice Rolvien, Gregory B. Sorkin:
Belief Propagation Guided Decimation on Random k-XORSAT. 47:1-47:21 - Shiri Chechik, Hongyi Chen, Tianyi Zhang:
Improved Streaming Edge Coloring. 48:1-48:18 - Antares Chen, Lorenzo Orecchia, Erasmo Tani:
Submodular Hypergraph Partitioning: Metric Relaxations and Fast Algorithms via an Improved Cut-Matching Game. 49:1-49:16 - Kuowen Chen, Jian Li, Yuval Rabani
New Results on a General Class of Minimum Norm Optimization Problems. 50:1-50:20 - Lin Chen, Jiayi Lian, Yuchen Mao, Guochuan Zhang:
Weakly Approximating Knapsack in Subquadratic Time. 51:1-51:18 - Xi Chen, William Pires, Toniann Pitassi, Rocco A. Servedio:
Relative-Error Testing of Conjunctions and Decision Lists. 52:1-52:18 - Yu Chen, Zihan Tan:
Cut-Preserving Vertex Sparsifiers for Planar and Quasi-Bipartite Graphs. 53:1-53:20 - Zejia Chen, Yulin Wang, Chihao Zhang, Zihan Zhang:
Decay of Correlation for Edge Colorings When q > 3Δ. 54:1-54:18 - Shabarish Chenakkod
Optimal Oblivious Subspace Embeddings with Near-Optimal Sparsity. 55:1-55:20 - Jiaqi Cheng, Rishab Goyal:
Boosting SNARKs and Rate-1 Barrier in Arguments of Knowledge. 56:1-56:20 - Shucheng Chi, Ran Duan, Benyu Wang, Tianle Xie:
Undirected 3-Fault Replacement Path in Nearly Cubic Time. 57:1-57:20 - Flavio Chierichetti, Mirko Giacchini, Alessandro Panconesi, Andrea Vattani:
A New Impossibility Result for Online Bipartite Matching Problems. 58:1-58:20 - Nathan Claudet, Simon Perdrix:
Deciding Local Unitary Equivalence of Graph States in Quasi-Polynomial Time. 59:1-59:20 - Roni Con, Zeyu Guo, Ray Li, Zihan Zhang:
Random Reed-Solomon Codes Achieve the Half-Singleton Bound for Insertions and Deletions over Linear-Sized Alphabets. 60:1-60:21 - Arjan Cornelissen, Simon Apers, Sander Gribling:
How to Compute the Volume in Low Dimension? 61:1-61:18 - Martín Costa, Ermiya Farokhnejad:
Deterministic k-Median Clustering in Near-Optimal Time. 62:1-62:20 - Luís Felipe I. Cunha, Ignasi Sau, Uéverton S. Souza, Mario Valencia-Pabon:
Computing Distances on Graph Associahedra Is Fixed-Parameter Tractable. 63:1-63:19 - Artur Czumaj, Guichen Gao, Mohsen Ghaffari, Shaofeng H.-C. Jiang:
Fully Scalable MPC Algorithms for Euclidean k-Center. 64:1-64:20 - Gianluca De Marco, Dariusz R. Kowalski:
Ultra-Resilient Superimposed Codes: Near-Optimal Construction and Applications. 65:1-65:20 - Mahsa Derakhshan, Andisheh Ghasemi, Rajmohan Rajaraman:
One-Way Communication Complexity of Minimum Vertex Cover in General Graphs. 66:1-66:19 - Mahsa Derakhshan, Mohammad Saneian:
Query Efficient Weighted Stochastic Matching. 67:1-67:20 - Stéphane Devismes, Yoann Dieudonné, Arnaud Labourel:
Graph Exploration: The Impact of a Distance Constraint. 68:1-68:18 - Michael Dinitz, Ama Koranteng, Yasamin Nazari
Approximation Algorithms for Optimal Hopsets. 69:1-69:20 - Sahar Diskin, Ilay Hoshen, Maksim Zhukovskii:
Tiling Random Regular Graphs Efficiently. 70:1-70:17 - Dani Dorfman, Haim Kaplan, Robert E. Tarjan, Mikkel Thorup, Uri Zwick:
Faster All-Pairs Optimal Electric Car Routing. 71:1-71:18 - Max Dupré la Tour, Manuel Lafond, Ndiamé Ndiaye, Adrian Vetta:
k-Leaf Powers Cannot Be Characterized by a Finite Set of Forbidden Induced Subgraphs for k ≥ 5. 72:1-72:17 - Koppány István Encz, Monaldo Mastrolilli
Branch-And-Bound Algorithms as Polynomial-Time Approximation Schemes. 73:1-73:19 - Sándor P. Fekete, Peter Kramer, Jan-Marc Reinhardt, Christian Rieck, Christian Scheffer:
Drainability and Fillability of Polyominoes in Diverse Models of Global Control. 74:1-74:19 - Shiyuan Feng, William Swartworth, David P. Woodruff:
Tight Bounds for Heavy-Hitters and Moment Estimation in the Sliding Window Model. 75:1-75:19 - Ying Feng, Piotr Indyk:
Even Faster Algorithm for the Chamfer Distance. 76:1-76:18 - Adi Fine, Haim Kaplan, Uri Stemmer:
Minimizing Recourse in an Adaptive Balls and Bins Game. 77:1-77:19 - Nick Fischer, Marvin Künnemann, Mirza Redzic, Julian Stieß:
The Role of Regularity in (Hyper-)Clique Detection and Implications for Optimizing Boolean CSPs. 78:1-78:18 - Maxime Flin, Magnús M. Halldórsson:
Faster Dynamic (Δ+1)-Coloring Against Adaptive Adversaries. 79:1-79:21 - Pierre Fraigniaud, Maël Luce, Frédéric Magniez, Ioan Todinca:
Deterministic Even-Cycle Detection in Broadcast CONGEST. 80:1-80:19 - Cheng-Hao Fu, Andrea Lincoln, Rene Reyes
Worst-Case and Average-Case Hardness of Hypercycle and Database Problems. 81:1-81:20 - Harmender Gahlawat, Abhishek Rathod, Meirav Zehavi:
(Almost-)Optimal FPT Algorithm and Kernel for T-Cycle on Planar Graphs. 82:1-82:18 - Andreas Galanis, Leslie Ann Goldberg, Paulina Smolarova:
Low-Temperature Sampling on Sparse Random Graphs. 83:1-83:20 - Andreas Galanis, Leslie Ann Goldberg, Xusheng Zhang:
One-Shot Learning for k-SAT. 84:1-84:15 - Dániel Garamvölgyi, Ryuhei Mizutani, Taihei Oki, Tamás Schwarcz, Yutaro Yamaguchi:
Towards the Proximity Conjecture on Group-Labeled Matroids. 85:1-85:17 - Pawel Gawrychowski, Wojciech Janczewski:
Optimal Distance Labeling for Permutation Graphs. 86:1-86:18 - Giordano Giambartolomei, Frederik Mallmann-Trenn, Raimundo Saona:
IID Prophet Inequality with Random Horizon: Going Beyond Increasing Hazard Rates. 87:1-87:21 - Daniel Gibney, Jackson Huffstutler, Mano Prakash Parthasarathi
Repetition Aware Text Indexing for Matching Patterns with Wildcards. 88:1-88:20 - Valentin Gledel, Nacim Oijid, Sébastien Tavenas, Stéphan Thomassé:
On the Complexity of Client-Waiter and Waiter-Client Games. 89:1-89:18 - Guilherme de C. M. Gomes, Raul Lopes, Ignasi Sau:
Revisiting Directed Disjoint Paths on Tournaments (And Relatives). 90:1-90:20 - Gramoz Goranci, Monika Henzinger, Harald Räcke, A. R. Sricharan:
Incremental Approximate Maximum Flow via Residual Graph Sparsification. 91:1-91:20 - Gramoz Goranci, Adam Karczmarz, Ali Momeni, Nikos Parotsidis:
Fully Dynamic Algorithms for Transitive Reduction. 92:1-92:20 - Adam Górkiewicz, Adam Karczmarz:
On Incremental Approximate Shortest Paths in Directed Graphs. 93:1-93:20 - Tsubasa Harada, Toshiya Itoh:
A Nearly Optimal Deterministic Algorithm for Online Transportation Problem. 94:1-94:17 - Sebastian Haslebacher
ARRIVAL: Recursive Framework & ℓ1-Contraction. 95:1-95:17 - Shuichi Hirahara, Naoto Ohsaka:
Asymptotically Optimal Inapproximability of Maxmin k-Cut Reconfiguration. 96:1-96:18 - Shuichi Hirahara, Nobutaka Shimizu
An Optimal Error-Correcting Reduction for Matrix Multiplication. 97:1-97:17 - Zhiyi Huang, Chui Shan Lee, Xinkai Shu, Zhaozi Wang:
The Long Arm of Nashian Allocation in Online p-Mean Welfare Maximization. 98:1-98:18 - Yuni Iwamasa, Taihei Oki, Tasuku Soma:
Algorithmic Aspects of Semistability of Quiver Representations. 99:1-99:18 - Ragesh Jaiswal, Amit Kumar, Jatin Yadav:
Robust-Sorting and Applications to Ulam-Median. 100:1-100:19 - Shaofeng H.-C. Jiang, Jianing Lou:
Coresets for Robust Clustering via Black-Box Reductions to Vanilla Case. 101:1-101:18 - Chris Jones, Lucas Pesenti:
Fourier Analysis of Iterative Algorithms. 102:1-102:21 - Michael Kapralov, Akash Kumar, Silvio Lattanzi, Aida Mousavifar, Weronika Wrzos-Kaminska:
Approximating Dasgupta Cost in Sublinear Time from a Few Random Seeds. 103:1-103:19 - Debajyoti Kar, Arindam Khan, Malin Rau:
Improved Approximation Algorithms for Three-Dimensional Bin Packing. 104:1-104:20 - Prem Nigam Kar
NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability. 105:1-105:19 - Sanjeev Khanna, Christian Konrad, Jacques Dark:
Streaming Maximal Matching with Bounded Deletions. 106:1-106:20 - Sanjeev Khanna, Aaron Putterman, Madhu Sudan:
A Theory of Spectral CSP Sparsification. 107:1-107:12 - Sanjeev Khanna, Aaron Putterman, Madhu Sudan:
Near-Optimal Hypergraph Sparsification in Insertion-Only and Bounded-Deletion Streams. 108:1-108:11 - Kacper Kluk, Marcin Pilipczuk, Michal Pilipczuk, Giannos Stamoulis:
Faster Diameter Computation in Graphs of Bounded Euler Genus. 109:1-109:19 - Evangelos Kosinas:
An Optimal 3-Fault-Tolerant Connectivity Oracle. 110:1-110:20 - Rasmus Kyng, Simon Meierhans, Gernot Zöcklein:
A Simple Dynamic Spanner via APSP. 111:1-111:11 - Alexandra Lassota
Parameterized Algorithms for Matching Integer Programs with Additional Rows and Columns. 112:1-112:18 - Lvzhou Li, Jingquan Luo:
Nearly Optimal Circuit Size for Sparse Quantum State Preparation. 113:1-113:19 - Jingxun Liang, Renfei Zhou:
Optimal Static Fully Indexable Dictionaries. 114:1-114:20 - Leah London Arazi, Amir Shpilka:
On the Complexity of Hazard-Free Formulas. 115:1-115:19 - Sepideh Mahabadi, Mohammad Roghani, Jakub Tarnawski:
A 0.51-Approximation of Maximum Matching in Sublinear n^{1.5} Time. 116:1-116:17 - Samuel McCauley, Benjamin Moseley, Aidin Niaparast, Helia Niaparast, Shikha Singh:
Incremental Approximate Single-Source Shortest Paths with Predictions. 117:1-117:20 - Boning Meng, Juqiu Wang, Mingji Xia:
P-Time Algorithms for Typical #EO Problems. 118:1-118:17 - Slobodan Mitrovic, Anish Mukherjee
Faster Semi-Streaming Matchings via Alternating Trees. 119:1-119:19 - Hendrik Molter
Treewidth Parameterized by Feedback Vertex Number. 120:1-120:20 - Tamio-Vesa Nakajima, Stanislav Zivný:
Maximum Bipartite vs. Triangle-Free Subgraph. 121:1-121:16 - Naoto Ohsaka:
Yet Another Simple Proof of the PCRP Theorem. 122:1-122:18 - Chirag Pabbaraju, Ali Vakilian
New and Improved Bounds for Markov Paging. 123:1-123:20 - Daniel Paul-Pena, C. Seshadhri:
Subgraph Counting in Subquadratic Time for Bounded Degeneracy Graphs. 124:1-124:18 - Aditya Potukuchi, Shikha Singh:
Unbalanced Random Matching Markets with Partial Preferences. 125:1-125:16 - Lars Rohwedder
ETH-Tight FPT Algorithm for Makespan Minimization on Uniform Machines. 126:1-126:13 - Lars Rohwedder
Cost Preserving Dependent Rounding for Allocation Problems. 127:1-127:20 - Lars Rohwedder
3.415-Approximation for Coflow Scheduling via Iterated Rounding. 128:1-128:19 - Thomas Schneider
An Upper Bound on the Weisfeiler-Leman Dimension. 129:1-129:18 - Ahmed Shalaby, Damien Woods
An Efficient Algorithm to Compute the Minimum Free Energy of Interacting Nucleic Acid Strands. 130:1-130:20 - Aleksandros Sobczyk:
Deterministic Complexity Analysis of Hermitian Eigenproblems. 131:1-131:21 - Aurelio L. Sulser, Maximilian Probst Gutenberg:
Near-Optimal Algorithm for Directed Expander Decompositions. 132:1-132:20 - Ivor van der Hoog, Thijs van der Horst
Faster, Deterministic and Space Efficient Subtrajectory Clustering. 133:1-133:18 - Penghui Yao, Mingnan Zhao
A Pseudorandom Generator for Functions of Low-Degree Polynomial Threshold Functions. 134:1-134:20 - Daniel Ye:
Deterministic Independent Sets in the Semi-Streaming Model. 135:1-135:17 - Ben Young:
The Converse of the Real Orthogonal Holant Theorem. 136:1-136:20 - Junyao Zhao:
Universal Online Contention Resolution with Preselected Order. 137:1-137:17 - Michal Ajdarów, James C. A. Main, Petr Novotný, Mickael Randour:
Taming Infinity One Chunk at a Time: Concisely Represented Strategies in One-Counter MDPs. 138:1-138:19 - Djamel Eddine Amir, Benjamin Hellouin de Menibus:
Minimality and Computability of Languages of G-Shifts. 139:1-139:19 - Alexey Barsukov, Michael Pinsker, Jakub Rydval
Containment for Guarded Monotone Strict NP. 140:1-140:20 - Gabriel Bathie, Nathanaël Fijalkow, Corto Mascle:
The Trichotomy of Regular Property Testing. 141:1-141:21 - Nikolay Bazhenov, Dariusz Kalocinski, Michal Wroclawski:
Online and Feasible Presentability: From Trees to Modal Algebras. 142:1-142:20 - Valérie Berthé, Herman Goulet-Ouellet, Dominique Perrin:
Density of Rational Languages Under Shift Invariant Measures. 143:1-143:20 - Markus Bläser, Julian Dörfler, Maciej Liskiewicz, Benito van der Zander:
Probabilistic and Causal Satisfiability: Constraining the Model. 144:1-144:20 - Manuel Bodirsky, Georg Loho, Mateusz Skomra:
Reducing Stochastic Games to Semidefinite Programming. 145:1-145:15 - León Bohn, Yong Li, Christof Löding, Sven Schewe:
Saturation Problems for Families of Automata. 146:1-146:19 - Édouard Bonnet, Samuel Braunfeld, Ioannis Eleftheriadis, Colin Geniet, Nikolas Mählmann, Michal Pilipczuk, Wojciech Przybyszewski, Szymon Torunczyk:
Separability Properties of Monadically Dependent Graph Classes. 147:1-147:19 - Jin-Yi Cai, Jin Soo Ihm:
Holant* Dichotomy on Domain Size 3: A Geometric Perspective. 148:1-148:18 - Antonio Casares, Pierre Ohlmann:
The Memory of ω-Regular and BC(Σ⁰₂) Objectives. 149:1-149:18 - Krishnendu Chatterjee, Laurent Doyen, Jean-François Raskin, Ocan Sankur:
The Value Problem for Multiple-Environment MDPs with Parity Objective. 150:1-150:17 - Miroslav Chodil, Antonín Kucera:
The Satisfiability and Validity Problems for Probabilistic Computational Tree Logic Are Highly Undecidable. 151:1-151:20 - Thomas Colcombet, Amina Doumane, Denis Kuperberg:
Tree Algebras and Bisimulation-Invariant MSO on Finite Graphs. 152:1-152:16 - Wojciech Czerwinski, Ismaël Jecker, Slawomir Lasota, Lukasz Orlikowski:
Reachability in 3-VASS Is Elementary. 153:1-153:20 - Ruiwen Dong
Submonoid Membership in n-Dimensional Lamplighter Groups and S-Unit Equations. 154:1-154:20 - Emmanuel Filiot, Ismaël Jecker, Khushraj Madnani, Saina Sunny:
Approximate Problems for Finite Transducers. 155:1-155:19 - Lukas Fleischer, Florian Stober
Membership and Conjugacy in Inverse Semigroups. 156:1-156:19 - Christina Gehnen
Bayesian Inference in Quantum Programs. 157:1-157:18 - Santiago Guzmán-Pro, Barnaby Martin:
Restricted CSPs and F-Free Digraph Algorithmics. 158:1-158:21 - Fugen Hagihara
The Ultimate Signs of Second-Order Holonomic Sequences. 159:1-159:20 - Olivier Idir, Karoliina Lehtinen:
Using Games and Universal Trees to Characterise the Nondeterministic Index of Tree Languages. 160:1-160:19 - Pawel M. Idziak, Piotr Kawalek, Jacek Krzaczkowski
Nonuniform Deterministic Finite Automata over Finite Algebraic Structures. 161:1-161:14 - Simon Iosti, Denis Kuperberg, Quentin Moreau:
Positive and Monotone Fragments of FO and LTL. 162:1-162:17 - Toghrul Karimov:
Verification of Linear Dynamical Systems via O-Minimality of the Real Numbers. 163:1-163:17 - Karoliina Lehtinen, Nathan Lhote:
A Collapse of the Parity Index Hierarchy of Tree Automata, Based on Cantor-Bendixson Ranks. 164:1-164:20 - Fabian Lenke, Stefan Milius, Henning Urbat, Thorsten Wißmann:
Algebraic Language Theory with Effects. 165:1-165:20 - Moritz Lichter, Benedikt Pago:
Limitations of Affine Integer Relaxations for Solving Constraint Satisfaction Problems. 166:1-166:17 - Nikolas Mählmann:
Forbidden Induced Subgraphs for Bounded Shrub-Depth and the Expressive Power of MSO. 167:1-167:18 - Olga Martynova, Alexander Okhotin:
Nondeterministic Tree-Walking Automata Are Not Closed Under Complementation. 168:1-168:17 - Tamio-Vesa Nakajima, Zephyr Verwimp, Marcin Wrochna, Stanislav Zivný:
Complexity of Approximate Conflict-Free, Linearly-Ordered, and Nonmonochromatic Hypergraph Colourings. 169:1-169:10 - Tikhon Pshenitsyn:
First-Order Intuitionistic Linear Logic and Hypergraph Languages. 170:1-170:19 - Philippe Schnoebelen, Julien Veron, Isa Vialard
A Tropical Approach to the Compositional Piecewise Complexity of Words and Compressed Words. 171:1-171:19 - Spencer Van Koevering, Wojciech Rozowski, Alexandra Silva:
Weighted GKAT: Completeness and Complexity. 172:1-172:18
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-11-14 22:25 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: