Theory of Computing Systems

Article	Citations
Token Sliding on Split Graphs	12
Faster Parameterized Algorithm for Cluster Vertex Deletion	12
Forward Looking Huffman Coding	10
The Price of Fairness for Indivisible Goods	10
On the Existence of Three-Dimensional Stable Matchings with Cyclic Preferences	6
FKT is Not Universal — A Planar Holant Dichotomy for Symmetric Constraints	6
Multi-Pass Streaming Algorithms for Monotone Submodular Function Maximization	6
Derandomization for Sliding Window Algorithms with Strict Correctness∗	6
The Power of the Weighted Sum Scalarization for Approximating Multiobjective Optimization Problems	5
Computability of Products of Chainable Continua	5
Fast Algorithms for the Shortest Unique Palindromic Substring Problem on Run-Length Encoded Strings	5
Semi-Oblivious Chase Termination: The Sticky Case	5
On the Complexity of the Smallest Grammar Problem over Fixed Alphabets	5
Approximation Results for Makespan Minimization with Budgeted Uncertainty	5
On the Computational Complexity of Decision Problems About Multi-player Nash Equilibria	5
Multistage Vertex Cover	4
Consistent Query Answering for Primary Keys in Datalog	4
A Parameterized Complexity View on Collapsing k-Cores	4
First-Order Orbit Queries	4
Parameterized Complexity of Min-Power Asymmetric Connectivity	4
Streaming Algorithms for Bin Packing and Vector Scheduling	3
An Improved Deterministic Parameterized Algorithm for Cactus Vertex Deletion	3
Impartial Selection with Additive Approximation Guarantees	3
An Improved FPT Algorithm for Independent Feedback Vertex Set	3
Fast Scheduling in Distributed Transactional Memory	3

Effective Categoricity of Automatic Equivalence and Nested Equivalence Structures	3
Unpopularity Factor in the Marriage and Roommates Problems	3
On the Relation Between Structured d-DNNFs and SDDs	3
Finite Sequentiality of Unambiguous Max-Plus Tree Automata	3
On the Expressive Power of Linear Algebra on Graphs	3
On the Cycle Augmentation Problem: Hardness and Approximation Algorithms	3
Restart Strategies in a Continuous Setting	3
Fixed-Parameter Tractability of (n − k) List Coloring	2
Computing the k-Visibility Region of a Point in a Polygon	2
On Triangle Estimation Using Tripartite Independent Set Queries	2
Target Set Selection Parameterized by Vertex Cover and More	2
Parameterized Complexity of Conflict-Free Set Cover	2
Computing the Number of Affine Equivalent Classes on $\mathcal {R}(s,n)/\mathcal {R}(k,n)$	2
Index-based, High-dimensional, Cosine Threshold Querying with Optimality Guarantees	2
Constructing Antidictionaries of Long Texts in Output-Sensitive Space	2
Computationally Efficient Approach to Implementation of the Chinese Remainder Theorem Algorithm in Minimally Redundant Residue Number System	2
Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs	2
Dichotomy for Holant∗ Problems on the Boolean Domain	2
The Non-hardness of Approximating Circuit Size	2
Typical Sequences Revisited — Computing Width Parameters of Graphs	2
Managing Multiple Mobile Resources	2
Santha-Vazirani sources, deterministic condensers and very strong extractors	2
Multiplication Algorithm Based on Collatz Function	1
Weighted Tree Automata with Constraints	1
Nearly Linear Time Isomorphism Algorithms for Some Nonabelian Group Classes	1
Beyond the Existential Theory of the Reals	1
Dynamic Multiple-Message Broadcast: Bounding Throughput in the Affectance Model	1
Decidability and Periodicity of Low Complexity Tilings	1
Maximum Stable Matching with One-Sided Ties of Bounded Length	1
Subclasses of Ptime Interpreted by Programming Languages	1
Transition Property for Cube-Free Words	1
Finite Sequentiality of Finitely Ambiguous Max-Plus Tree Automata	1
On Envy-Free Revenue Approximation for Combinatorial Buyers with Budgets	1
On the structure of solution-sets to regular word equations	1
The Declining Price Anomaly Is Not Universal in Multi-Buyer Sequential Auctions (but almost is)	1
The Space Complexity of Sum Labelling	1
Satisfiability Algorithm for Syntactic Read-k-times Branching Programs	1
On the Rejection Rate of Exact Sampling Algorithm for Discrete Gaussian Distributions over the Integers	1
Fixed-Parameter Algorithms for Unsplittable Flow Cover	1
Reachability Problems on Reliable and Lossy Queue Automata	1
Factorizing Strings into Repetitions	1
On the Average Case of MergeInsertion	1
Stable Divisorial Gonality is in NP	1
A Framework for Memory Efficient Context-Sensitive Program Analysis	1
On Polynomial Recursive Sequences	1
Complexity of Fall Coloring for Restricted Graph Classes	1
The Minimum Tollbooth Problem in Atomic Network Congestion Games with Unsplittable Flows	1
The Containment Problem for Unambiguous Register Automata and Unambiguous Timed Automata	1
On Tseitin Formulas, Read-Once Branching Programs and Treewidth	1
Nonuniform Reductions and NP-Completeness	1

Expansivity and Periodicity in Algebraic Subshifts	1
Analyzing Clustering and Partitioning Problems in Selected VLSI Models	1
Exploration of Dynamic Cactuses with Sub-logarithmic Overhead	1
A One Pass Streaming Algorithm for Finding Euler Tours	1
An Automaton Group with PSPACE-Complete Word Problem	1
On Decidability of Theories of Regular Languages	1
Improved Bounds for Matching in Random-Order Streams	1
Greedy is Optimal for Online Restricted Assignment and Smart Grid Scheduling for Unit Size Jobs	1
(In)Existence of Equilibria for 2-Player, 2-Value Games with Semistrictly Quasiconcave Cost Functions	0
In Memoriam - Alan Selman (1941 - 2021)	0
A Closer Look at the Expressive Power of Logics Based on Word Equations	0
Random Access in Persistent Strings and Segment Selection	0
Well-Covered Graphs With Constraints On $$\Delta $$ And $$\delta $$	0
Special Issue on Database Theory	0
Risk-Free Bidding in Complement-Free Combinatorial Auctions	0
Farkas Bounds on Horn Constraint Systems	0
Subquadratic-time Algorithm for the Diameter and all Eccentricities on Median Graphs	0
The Complexity of Counting CSPd	0
Improved Lower and Upper Bounds on the Tile Complexity of Uniquely Self-Assembling a Thin Rectangle Non-Cooperatively in 3D	0
b-Coloring Parameterized by Clique-Width	0
Arithmetical Hierarchy of the Besicovitch-Stability of Noisy Tilings	0
Exact Multi-Covering Problems with Geometric Sets	0
On the Expressive Power of Stateless Ordered Restart-Delete Automata	0
Special Issue on Computer Science Symposium in Russia (2019)	0
On the Transformation of LL(k)-linear to LL(1)-linear Grammars	0
On the Hierarchy of Swarm-automaton for the Number of Agents	0
Correction to: Submodular Functions and Rooted Trees	0
The Solvability of Consensus in Iterated Models Extended with Safe-Consensus	0
Second-Order Finite Automata	0
Non-Linear Ski Rental	0
On Non-principal Arithmetical Numberings and Families	0
Observation and Distinction: Representing Information in Infinite Games	0
Graph Square Roots of Small Distance from Degree One Graphs	0
Upper Bounds on Communication in Terms of Approximate Rank	0
Unit Read-once Refutations for Systems of Difference Constraints	0
Preface	0
Digraph Coloring and Distance to Acyclicity	0
One-Tape Turing Machine and Branching Program Lower Bounds for MCSP	0
Characterizations and Directed Path-Width of Sequence Digraphs	0
The Complexity of Unavoidable Word Patterns	0
Characterizing Tractability of Simple Well-Designed Pattern Trees with Projection	0
Generating Visual Invariants −a New Approach to Invariant Recognition	0
Dimension and the Structure of Complexity Classes	0
The subset sum game revisited	0
Correction to: On the Expressive Power of Linear Algebra on Graphs	0
Subgroup Membership in GL(2,Z)	0
Small Vertex Cover Helps in Fixed-Parameter Tractability of Graph Deletion Problems over Data Streams	0
On Forced Periodicity of Perfect Colorings	0
Toward Online Mobile Facility Location on General Metrics	0
Lossy Kernelization of Same-Size Clustering	0
Complexity Limitations on One-turn Quantum Refereed Games	0
Visit-Bounded Stack Automata	0
Minimum Reload Cost Graph Factors	0
Complexity of the (Connected) Cluster Vertex Deletion Problem on H-free Graphs	0
Stable Multi-Level Monotonic Eroders	0
On the Parameterized Complexity of the Expected Coverage Problem	0
On the Partial Vertex Cover Problem in Bipartite Graphs - a Parameterized Perspective	0
Radio k-chromatic Number of Full m-ary Trees	0
Synchronous Boolean Finite Dynamical Systems on Directed Graphs over XOR Functions	0
Preface of the Special Issue Dedicated to Selected Papers from CSR 2020	0
Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms	0
Obvious Strategyproofness, Bounded Rationality and Approximation	0
The Parameterized Complexity of s-Club with Triangle and Seed Constraints	0
Local Deal-Agreement Algorithms for Load Balancing in Dynamic General Graphs	0
On the Fixed-Parameter Tractability of the Maximum Connectivity Improvement Problem	0
Special issue on algorithmic game theory (SAGT 2019)	0
Belga B-Trees	0
Holographic Algorithms on Domains of General Size	0
Correction to: Parameterized Complexity of Min-Power Asymmetric Connectivity	0
On the Complexity of the Clone Membership Problem	0
A Unifying Approximate Potential for Weighted Congestion Games	0
Computing Colourful Simplicial Depth and Median in ℝ2	0
Rational Index of Languages Defined by Grammars with Bounded Dimension of Parse Trees	0
Univariate Ideal Membership Parameterized by Rank, Degree, and Number of Generators	0
On Embeddability of Unit Disk Graphs Onto Straight Lines	0
Preservation of Normality by Non-Oblivious Group Selection	0
Quantum Algorithm for Lexicographically Minimal String Rotation	0
Preface of STACS 2019 Special Issue	0
Refined Parameterizations for Computing Colored Cuts in Edge-Colored Graphs	0
Arithmetic Circuits, Structured Matrices and (not so) Deep Learning	0

Stability, Vertex Stability, and Unfrozenness for Special Graph Classes	0
On the Decision Tree Complexity of Threshold Functions	0
On the Decidability of Infix Inclusion Problem	0
Implicit Representation of Relations	0
Mechanism Design for Perturbation Stable Combinatorial Auctions	0
Stability and Welfare in (Dichotomous) Hedonic Diversity Games	0
Computing a Partition Function of a Generalized Pattern-Based Energy over a Semiring	0
Equation Satisfiability in Solvable Groups	0
Lower-Bounds on the Growth of Power-Free Languages Over Large Alphabets	0
Representing the Integer Factorization Problem Using Ordered Binary Decision Diagrams	0
Disentangling the Computational Complexity of Network Untangling	0
An Alternating Algorithm for Finding Linear Arrow-Debreu Market Equilibria	0
Property Testing of the Boolean and Binary Rank	0
Polynomial-Time Axioms of Choice and Polynomial-Time Cardinality	0
Correction to: Dynamic Multiple-Message Broadcast: Bounding Throughput in the Affectance Model	0
Foreword: a Commemorative Issue for Alan L. Selman	0
Correction to: On the Transformation of LL(k)-linear to LL(1)-linear Grammars	0
Preface of STACS 2020 Special Issue	0
The Complexity of Grid Coloring	0
The Complexity of the Distributed Constraint Satisfaction Problem	0
Polynomially Ambiguous Unary Weighted Automata over Fields	0
Non-Existence of Stable Social Groups in Information-Driven Networks	0
Space Lower Bounds for the Signal Detection Problem	0
Effective Guessing Has Unlikely Consequences	0
Reachability in Two-Parametric Timed Automata with one Parameter is EXPSPACE-Complete	0
Approximability of open k-monopoly problems	0
Editorial: Special Issue on International Workshop on Combinatorial Algorithms (IWOCA 2019)	0
Kernelization of Arc Disjoint Cycle Packing in α-Bounded Digraphs	0
On Random Perfect Matchings in Metric Spaces with Not-too-large Diameters	0
Complexity and Algorithms for Semipaired Domination in Graphs	0
Risk-Robust Mechanism Design for a Prospect-Theoretic Buyer	0
Ergodic Theorems and Converses for PSPACE Functions	0
Submodular Functions and Rooted Trees	0