Theory of Computing Systems

Papers
(The median citation count of Theory of Computing Systems is 0. The table below lists those papers that are above that threshold based on CrossRef citation counts [max. 250 papers]. The publications cover those that have been published in the past four years, i.e., from 2021-03-01 to 2025-03-01.)
ArticleCitations
On the Hierarchy of Swarm-automaton for the Number of Agents11
Foreword: a Commemorative Issue for Alan L. Selman9
On Triangle Estimation Using Tripartite Independent Set Queries7
Factorizing Strings into Repetitions6
One-Sided Markets with Externalities6
Linear Codes Correcting Repeated Bursts Equipped with Homogeneous Distance6
Revisiting the Distortion of Distributed Voting6
Obstructions to Return Preservation for Episturmian Morphisms6
Preface of the Special Issue Dedicated to Selected Papers from DLT 20225
Impartial Selection with Additive Approximation Guarantees4
The Solvability of Consensus in Iterated Models Extended with Safe-Consensus4
Restart Strategies in a Continuous Setting4
The Parameterized Complexity of s-Club with Triangle and Seed Constraints4
Typical Sequences Revisited — Computing Width Parameters of Graphs4
Observation and Distinction: Representing Information in Infinite Games4
Placing Green Bridges Optimally, with a Multivariate Analysis3
Synchronous Boolean Finite Dynamical Systems on Directed Graphs over XOR Functions3
Maximum Stable Matching with One-Sided Ties of Bounded Length3
A One Pass Streaming Algorithm for Finding Euler Tours2
The Power Word Problem in Graph Products2
Risk-Free Bidding in Complement-Free Combinatorial Auctions2
Polynomially Ambiguous Unary Weighted Automata over Fields2
Exact Multi-Covering Problems with Geometric Sets2
Complexity Limitations on One-turn Quantum Refereed Games2
Correction to: Parameterized Complexity of Min-Power Asymmetric Connectivity2
How to Play Old Maid with Virtual Players2
An Alternating Algorithm for Finding Linear Arrow-Debreu Market Equilibria2
The Complexity of Counting CSPd1
Reachability Problems on Reliable and Lossy Queue Automata1
Dynamic Multiple-Message Broadcast: Bounding Throughput in the Affectance Model1
Maximizing Rides Served for Dial-a-Ride on the Uniform Metric1
Fixed-Parameter Algorithms for Unsplittable Flow Cover1
On Forced Periodicity of Perfect Colorings1
Dimension and the Structure of Complexity Classes1
Univariate Ideal Membership Parameterized by Rank, Degree, and Number of Generators1
On the Cycle Augmentation Problem: Hardness and Approximation Algorithms1
On the Decidability of Infix Inclusion Problem1
Characterization of Ordered Semigroups Generating Well Quasi-Orders of Words1
Exact and Approximate Digraph Bandwidth1
Approximation Algorithms for the MAXSPACE Advertisement Problem1
Dichotomy for Non-negative Valued Holant Problems on 3-Regular Bipartite Graphs1
Arithmetic Circuits, Structured Matrices and (not so) Deep Learning1
Mechanism Design for Perturbation Stable Combinatorial Auctions1
Subgroup Membership in GL(2,Z)1
Arithmetical Hierarchy of the Besicovitch-Stability of Noisy Tilings1
The Complexity of Unavoidable Word Patterns1
Quantum Algorithm for Lexicographically Minimal String Rotation1
Ergodic Theorems and Converses for PSPACE Functions1
Decidability and Periodicity of Low Complexity Tilings1
Random Access in Persistent Strings and Segment Selection1
Expansivity and Periodicity in Algebraic Subshifts1
In Memoriam - Alan Selman (1941 - 2021)1
Rewindable Quantum Computation and Its Equivalence to Cloning and Adaptive Postselection1
Equation Satisfiability in Solvable Groups1
Preface1
Stable Multi-Level Monotonic Eroders1
How to Hide a Clique?1
Prediction and MDL for infinite sequences0
Approximation Results for Makespan Minimization with Budgeted Uncertainty0
Gathering on Rings for Myopic Asynchronous Robots with Lights0
Upper Bounds on Communication in Terms of Approximate Rank0
Polynomial-Time Axioms of Choice and Polynomial-Time Cardinality0
Local Deal-Agreement Algorithms for Load Balancing in Dynamic General Graphs0
Imperative Process Algebra and Models of Parallel Computation0
Non-Linear Ski Rental0
Automatic Abelian Complexities of Parikh-Collinear Fixed Points0
Can Local Optimality Be Used for Efficient Data Reduction?0
Farkas Bounds on Horn Constraint Systems0
Lossy Kernelization of Same-Size Clustering0
The Complexity of the Distributed Constraint Satisfaction Problem0
On the Existence of Three-Dimensional Stable Matchings with Cyclic Preferences0
The Space Complexity of Sum Labelling0
Lower-Bounds on the Growth of Power-Free Languages Over Large Alphabets0
Beyond the Existential Theory of the Reals0
Elastic-Degenerate String Matching with 1 Error or Mismatch0
On the Partial Vertex Cover Problem in Bipartite Graphs - a Parameterized Perspective0
The Complexity of Grid Coloring0
An Automaton Group with PSPACE-Complete Word Problem0
A Unifying Approximate Potential for Weighted Congestion Games0
On the Computational Complexity of Decision Problems About Multi-player Nash Equilibria0
Cluster Editing for Multi-Layer and Temporal Graphs0
The Power of the Weighted Sum Scalarization for Approximating Multiobjective Optimization Problems0
Risk-Robust Mechanism Design for a Prospect-Theoretic Buyer0
A Closer Look at the Expressive Power of Logics Based on Word Equations0
Characterizations and Directed Path-Width of Sequence Digraphs0
On Random Perfect Matchings in Metric Spaces with Not-too-large Diameters0
Representing the Integer Factorization Problem Using Ordered Binary Decision Diagrams0
What Goes Around Comes Around: Covering Tours and Cycle Covers with Turn Costs0
Effective Guessing Has Unlikely Consequences0
Refined Parameterizations for Computing Colored Cuts in Edge-Colored Graphs0
Note on Constrained Long Choice with Multiple Beginning Elements0
A Parameterized Complexity View on Collapsing k-Cores0
Second-Order Finite Automata0
On the Expressive Power of Stateless Ordered Restart-Delete Automata0
Special issue on algorithmic game theory (SAGT 2019)0
Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs0
Computationally Efficient Approach to Implementation of the Chinese Remainder Theorem Algorithm in Minimally Redundant Residue Number System0
Visit-Bounded Stack Automata0
International Colloquium on Automata, Languages and Programming (ICALP 2020)0
Reachability in Two-Parametric Timed Automata with one Parameter is EXPSPACE-Complete0
Lower Bounds on the Amortized Time Complexity of Shared Objects0
Correction to: Submodular Functions and Rooted Trees0
Correction to: On the Transformation of LL(k)-linear to LL(1)-linear Grammars0
One-Tape Turing Machine and Branching Program Lower Bounds for MCSP0
Routing and Wavelength Assignment Algorithm for Mesh-based Multiple Multicasts in Optical Network-on-chip0
Holographic Algorithms on Domains of General Size0
CNF Encodings of Symmetric Functions0
2-Balanced Sequences Coding Rectangle Exchange Transformation0
Max-plus Algebraic Description of Evolutions of Weighted Timed Event Graphs0
Online Unbounded Knapsack0
Reordered Computable Numbers0
Property Testing of the Boolean and Binary Rank0
Generating Visual Invariants −a New Approach to Invariant Recognition0
Greedy is Optimal for Online Restricted Assignment and Smart Grid Scheduling for Unit Size Jobs0
On the Parameterized Complexity of the Expected Coverage Problem0
Nonuniform Reductions and NP-Completeness0
Jumping Automata over Infinite Words0
Unit Read-once Refutations for Systems of Difference Constraints0
A Local Search Algorithm for the Radius-Constrained k-Median Problem0
Computing Colourful Simplicial Depth and Median in ℝ20
Preface of STACS 2019 Special Issue0
Toward Online Mobile Facility Location on General Metrics0
New Results on the Remote Set Problem and Its Applications in Complexity Study0
Complexity of the (Connected) Cluster Vertex Deletion Problem on H-free Graphs0
Subclasses of Ptime Interpreted by Programming Languages0
Rational Index of Languages Defined by Grammars with Bounded Dimension of Parse Trees0
Improved Bounds for Matching in Random-Order Streams0
(In)Existence of Equilibria for 2-Player, 2-Value Games with Semistrictly Quasiconcave Cost Functions0
On the Rejection Rate of Exact Sampling Algorithm for Discrete Gaussian Distributions over the Integers0
On the Solution Sets of Three-Variable Word Equations0
On learning down-sets in quasi-orders, and ideals in Boolean algebras0
Non-Constructive Upper Bounds for Repetition Thresholds0
Preface of STACS 2021 Special Issue0
Online Matching with Delays and Stochastic Arrival Times0
The Price of Fairness for Indivisible Goods0
A Framework for Memory Efficient Context-Sensitive Program Analysis0
Preface of the Special Issue Dedicated to Selected Papers from CSR 20200
Non-Existence of Stable Social Groups in Information-Driven Networks0
Radio k-chromatic Number of Full m-ary Trees0
Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms0
Small Vertex Cover Helps in Fixed-Parameter Tractability of Graph Deletion Problems over Data Streams0
Rudin-Shapiro Sums Via Automata Theory and Logic0
Correction to: Dynamic Multiple-Message Broadcast: Bounding Throughput in the Affectance Model0
Languages Generated by Conjunctive Query Fragments of FC[REG]0
Pumping Lemmas Can be “Harmful”0
Stability, Vertex Stability, and Unfrozenness for Special Graph Classes0
Disentangling the Computational Complexity of Network Untangling0
Finite Sequentiality of Unambiguous Max-Plus Tree Automata0
Performing Regular Operations with 1-Limited Automata0
Implicit Representation of Relations0
Computing a Partition Function of a Generalized Pattern-Based Energy over a Semiring0
Target Set Selection Parameterized by Vertex Cover and More0
On the structure of solution-sets to regular word equations0
String Attractors of Some Simple-Parry Automatic Sequences0
Stability and Welfare in (Dichotomous) Hedonic Diversity Games0
On Polynomial Recursive Sequences0
Subquadratic-time Algorithm for the Diameter and all Eccentricities on Median Graphs0
Good r-divisions Imply Optimal Amortized Decremental Biconnectivity0
Well-Covered Graphs With Constraints On $$\Delta $$ And $$\delta $$0
An Improved Deterministic Parameterized Algorithm for Cactus Vertex Deletion0
Multi-Pass Streaming Algorithms for Monotone Submodular Function Maximization0
The Minimum Tollbooth Problem in Atomic Network Congestion Games with Unsplittable Flows0
Multistage Vertex Cover0
On the Transformation of LL(k)-linear to LL(1)-linear Grammars0
Submodular Functions and Rooted Trees0
Optimizing Over Serial Dictatorships0
Digraph Coloring and Distance to Acyclicity0
On the Decision Tree Complexity of Threshold Functions0
Minimum Cut in $$O(m\log ^2 n)$$ Time0
On Embeddability of Unit Disk Graphs Onto Straight Lines0
Weighted Tree Automata with Constraints0
On Non-principal Arithmetical Numberings and Families0
Obvious Strategyproofness, Bounded Rationality and Approximation0
Approximation algorithms for node and element connectivity augmentation problems0
Kernelization of Arc Disjoint Cycle Packing in α-Bounded Digraphs0
Near-Optimal Auctions on Independence Systems0
Finite Sequentiality of Finitely Ambiguous Max-Plus Tree Automata0
The Declining Price Anomaly Is Not Universal in Multi-Buyer Sequential Auctions (but almost is)0
Preface of STACS 2020 Special Issue0
b-Coloring Parameterized by Clique-Width0
Improved Lower and Upper Bounds on the Tile Complexity of Uniquely Self-Assembling a Thin Rectangle Non-Cooperatively in 3D0
Graph Square Roots of Small Distance from Degree One Graphs0
FKT is Not Universal — A Planar Holant Dichotomy for Symmetric Constraints0
0.097763061523438