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