Theory of Computing Systems

Article	Citations
The Parameterized Complexity of s-Club with Triangle and Seed Constraints	9
Linear Codes Correcting Repeated Bursts Equipped with Homogeneous Distance	7
Strategic Candidacy Equilibria for Common Voting Rules	6
Complexity Limitations on One-turn Quantum Refereed Games	4
Beyond the Existential Theory of the Reals	3
Reachability in Two-Parametric Timed Automata with one Parameter is EXPSPACE-Complete	3
New Results on the Remote Set Problem and Its Applications in Complexity Study	3
Arithmetical Hierarchy of the Besicovitch-Stability of Noisy Tilings	3
An Lp-rounding Based Algorithm for Soft Capacitated Facility Location Problem with Submodular Penalties	3
Subquadratic-time Algorithm for the Diameter and all Eccentricities on Median Graphs	3
On the Transformation of LL(k)-linear to LL(1)-linear Grammars	3
Rational Index of Languages Defined by Grammars with Bounded Dimension of Parse Trees	2
The Declining Price Anomaly Is Not Universal in Multi-Buyer Sequential Auctions (but almost is)	2
Label Ranking Through Nonparametric Regression	2
Stability, Vertex Stability, and Unfrozenness for Special Graph Classes	2
Space-Efficient SLP Encoding for $$O(\log N)$$-Time Random Access	2
Small Vertex Cover Helps in Fixed-Parameter Tractability of Graph Deletion Problems over Data Streams	2
Rudin-Shapiro Sums Via Automata Theory and Logic	2
Preface of the Special Issue Dedicated to Selected Papers from CSR 2020	2
Algebraically Enhanced 3D Chaotic Map with Hash-Based Initialization for Secure Image Encryption	2
A Local Search Algorithm for the Radius-Constrained k-Median Problem	2
Non-Existence of Stable Social Groups in Information-Driven Networks	2
Cluster Editing for Multi-Layer and Temporal Graphs	1
On the Solution Sets of Three-Variable Word Equations	1
Computing String Covers in Sublinear Time	1

Degree 2 Lower Bound for Permanent in Arbitrary Characteristic	1
Maximum Stable Matching with One-Sided Ties of Bounded Length	1
Submodular Functions and Rooted Trees	1
International Colloquium on Automata, Languages and Programming (ICALP 2020)	1
Gathering on Rings for Myopic Asynchronous Robots with Lights	1
The Complexity of the Distributed Constraint Satisfaction Problem	1
The Power Word Problem in Graph Products	1
Sampling and Optimal Preference Elicitation in Simple Mechanisms	1
Generalization of Repetitiveness Measures for Two-Dimensional Strings	1
Max-plus Algebraic Description of Evolutions of Weighted Timed Event Graphs	1
Online Matching with Delays and Stochastic Arrival Times	1
Preface of STACS 2020 Special Issue	1
The Complexity of Unavoidable Word Patterns	1
Jumping Automata over Infinite Words	1
Space-Efficient B Trees via Load-Balancing	1
Minimum-Cost Mixed Graph Covers with Targeted Weight Constraints	1
Testing Intersectingness of Uniform Families	1
Control Structures in Computable Numberings and the Completion Operator	1
String Attractors of Some Simple-Parry Automatic Sequences	1
One-Sided Markets with Externalities	1
Improved Methods to Solve Nonlinear Invariants with Low Algebraic Degree for Linear Transformation	1
The Solvability of Consensus in Iterated Models Extended with Safe-Consensus	1
Approximation algorithms for node and element connectivity augmentation problems	1
Longest Common Subsequence with Gap Constraints	1
b-Coloring Parameterized by Clique-Width	1
(In)Existence of Equilibria for 2-Player, 2-Value Games with Semistrictly Quasiconcave Cost Functions	1
Preface of STACS 2021 Special Issue	1
Ergodic Theorems and Converses for PSPACE Functions	1
Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms	1
Preface of the Special Issue Dedicated to Selected Papers from DLT 2022	1
Faster Algorithms for Ranking/Unranking Bordered and Unbordered Words	1
Good r-divisions Imply Optimal Amortized Decremental Biconnectivity	1
How to Play Old Maid with Virtual Players	1
Decision Problems Concerning L Systems	1
Placing Green Bridges Optimally, with a Multivariate Analysis	1
Symmetric Linear Arc Monadic Datalog and Gadget Reductions	1
Subsequence Matching and LCS under Cartesian-Tree Equivalence	1
Greedy Minimum-Energy Scheduling	1
Correction to: How to Play Old Maid with Virtual Players	1
Correction to: Farkas Bounds on Horn Constraint Systems	1
A Geometric Programming Approach to Solve the Restricted Assignment Case of the Santa Claus Problem	0
On Random Perfect Matchings in Metric Spaces with Not-too-large Diameters	0
CNF Encodings of Symmetric Functions	0
Complexity of the (Connected) Cluster Vertex Deletion Problem on H-free Graphs	0
Correction to: Dynamic Multiple-Message Broadcast: Bounding Throughput in the Affectance Model	0
The ceBWT Index: An Index for Circular Cartesian Tree Matching on Multiple Texts	0
On learning down-sets in quasi-orders, and ideals in Boolean algebras	0
On the Decision Tree Complexity of Threshold Functions	0
A Unifying Approximate Potential for Weighted Congestion Games	0
A Practical Extension of Computational Complexity Theory for Applications in Mathematics and Sciences	0

Kleene Theorems for Lasso Languages and $$\omega $$-Languages	0
Optimizing Over Serial Dictatorships	0
Improved Bounds for Matching in Random-Order Streams	0
Toward Online Mobile Facility Location on General Metrics	0
Computing a Partition Function of a Generalized Pattern-Based Energy over a Semiring	0
Online Unbounded Knapsack	0
Correction to: Submodular Functions and Rooted Trees	0
Unit Read-once Refutations for Systems of Difference Constraints	0
On Forced Periodicity of Perfect Colorings	0
Well-Covered Graphs With Constraints On $$\Delta $$ And $$\delta $$	0
Automatic Abelian Complexities of Parikh-Collinear Fixed Points	0
The Complexity of Pre-assignment Problem for Unique Minimum Vertex Cover on Bipartite Graphs	0
Revisiting the Distortion of Distributed Voting	0
Completely Distinguishable Automata and the Set of Synchronizing Words	0
On the Partial Vertex Cover Problem in Bipartite Graphs - a Parameterized Perspective	0
Can Local Optimality Be Used for Efficient Data Reduction?	0
Lower Bounds on the Amortized Time Complexity of Shared Objects	0
2-Balanced Sequences Coding Rectangle Exchange Transformation	0
On the Hierarchy of Swarm-automaton for the Number of Agents	0
Target Set Selection Parameterized by Vertex Cover and More	0
Total Completion Time Scheduling Under Scenarios	0
On the Decidability of Infix Inclusion Problem	0
On the Potential and Limitations of Proxy Voting: Delegation with Incomplete Votes	0
Fast Approximation Algorithms for Euclidean Minimum Weight Perfect Matching	0
Unveiling Order in Chaos: A Systematic Approach Based on Graph Theory in Enumerating Sudoku Grids of Rank n	0
LZ78 Substring Compression in Compressed Space	0
Bit Catastrophes for the Burrows-Wheeler Transform	0
Dichotomy for Non-negative Valued Holant Problems on 3-Regular Bipartite Graphs	0
Dynamic Multiple-Message Broadcast: Bounding Throughput in the Affectance Model	0
Approximation Algorithms for the MAXSPACE Advertisement Problem	0
Rewindable Quantum Computation and Its Equivalence to Cloning and Adaptive Postselection	0
Dimension and the Structure of Complexity Classes	0
Reordered Computable Numbers	0
The Complexity of Grid Coloring	0
Nonuniform Reductions and NP-Completeness	0
The Reflection Complexity of Sequences Over Finite Alphabets	0
Non-Constructive Upper Bounds for Repetition Thresholds	0
A One Pass Streaming Algorithm for Finding Euler Tours	0
Elastic-Degenerate String Matching with 1 Error or Mismatch	0
Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths	0
Refined Parameterizations for Computing Colored Cuts in Edge-Colored Graphs	0
Holographic Algorithms on Domains of General Size	0
Frequency-Competitive Query Strategies to Maintain Low Congestion Potential Among Moving Entities	0
Disentangling the Computational Complexity of Network Untangling	0
The Ground-Set-Cost Budgeted Maximum Coverage Problem	0
Pumping Lemmas Can be “Harmful”	0
Effective Guessing Has Unlikely Consequences	0
Lossy Kernelization of Same-Size Clustering	0
Some Symmetrical Planar Structures with their Fault-Tolerant Metric Dimension	0
On Strings Having the Same Length-k Substrings	0
Correction to: On the Transformation of LL(k)-linear to LL(1)-linear Grammars	0
Algorithms for the Online Power Cover Problem on a Line	0
On Non-principal Arithmetical Numberings and Families	0
Note on Constrained Long Choice with Multiple Beginning Elements	0
A Framework for Memory Efficient Context-Sensitive Program Analysis	0
FullSynesth: Syntenic Reconciliation of a Set of Consistent Gene Trees	0
Subclasses of Ptime Interpreted by Programming Languages	0
Implicit Representation of Relations	0
Improved Parameterized Algorithms for Cluster Vertex Deletion	0
Second-Order Finite Automata	0
Characterizations and Directed Path-Width of Sequence Digraphs	0
Imperative Process Algebra and Models of Parallel Computation	0
Routing and Wavelength Assignment Algorithm for Mesh-based Multiple Multicasts in Optical Network-on-chip	0
Local Deal-Agreement Algorithms for Load Balancing in Dynamic General Graphs	0
Obstructions to Return Preservation for Episturmian Morphisms	0
Individual Preference Facility Location: A Dual-Fitting Framework and Its Extensions	0
Maximizing Rides Served for Dial-a-Ride on the Uniform Metric	0
Special issue on algorithmic game theory (SAGT 2019)	0
Characterization of Ordered Semigroups Generating Well Quasi-Orders of Words	0
Expansivity and Periodicity in Algebraic Subshifts	0
Random Access in Persistent Strings and Segment Selection	0
One-Tape Turing Machine and Branching Program Lower Bounds for MCSP	0
Quantum Algorithm for Lexicographically Minimal String Rotation	0
Subgroup Membership in GL(2,Z)	0
Near-Optimal Auctions on Independence Systems	0
Minimum Cut in $$O(m\log ^2 n)$$ Time	0
Non-Linear Ski Rental	0
NP-Completeness on the Length of Double-Arrays and the Sparse Matrix Problem with at Least Logarithmic Alphabets/Widths	0
Improved Bounds for Twin-Width Parameter Variants with Algorithmic Applications to Counting Graph Colorings	0
Microbribery in Group Identification	0

What Goes Around Comes Around: Covering Tours and Cycle Covers with Turn Costs	0
On the Computational Complexity of Decision Problems About Multi-player Nash Equilibria	0
Improved Online Scheduling with Restarts on a Single Machine	0
Upper Bounds on Communication in Terms of Approximate Rank	0
Digraph Coloring and Distance to Acyclicity	0
Scheduling with Speed Predictions	0
Kernelization of Arc Disjoint Cycle Packing in α-Bounded Digraphs	0
Foreword: a Commemorative Issue for Alan L. Selman	0
High Multiplicity Strip Packing with Three Rectangle Types	0
2-Colorable Perfect Matching is NP-complete in 2-Connected 3-Regular Planar Graphs	0
Visit-Bounded Stack Automata	0
Weighted Tree Automata with Constraints	0
Stability and Welfare in (Dichotomous) Hedonic Diversity Games	0
A Closer Look at the Expressive Power of Logics Based on Word Equations	0
Farkas Bounds on Horn Constraint Systems	0
The Space Complexity of Sum Labelling	0
(Worst-case) Optimal Adaptive Dynamic Bitvectors	0
Polynomial-Time Axioms of Choice and Polynomial-Time Cardinality	0
Languages Generated by Conjunctive Query Fragments of FC[REG]	0
Performing Regular Operations with 1-Limited Automata	0
Representing the Integer Factorization Problem Using Ordered Binary Decision Diagrams	0
On Embeddability of Unit Disk Graphs Onto Straight Lines	0
Logarithmic-Time Internal Pattern Matching Queries in Compressed and Dynamic Texts	0
An Optimal and Practical Algorithm for the Planar 2-center Problem	0
Synchronous Boolean Finite Dynamical Systems on Directed Graphs over XOR Functions	0
Online Deterministic Minimum Cost Bipartite Matching with Delays on a Line	0
Normality, Relativization, and Randomness	0
Improved Lower and Upper Bounds on the Tile Complexity of Uniquely Self-Assembling a Thin Rectangle Non-Cooperatively in 3D	0
Polynomially Ambiguous Unary Weighted Automata over Fields	0
Arithmetic Circuits, Structured Matrices and (not so) Deep Learning	0
Prediction and MDL for infinite sequences	0
Exact and Approximate Digraph Bandwidth	0
Equation Satisfiability in Solvable Groups	0
Mechanism Design for Perturbation Stable Combinatorial Auctions	0
How to Hide a Clique?	0
On the Rejection Rate of Exact Sampling Algorithm for Discrete Gaussian Distributions over the Integers	0