Theoretical Computer Science

Article	Citations
An algorithm for the secure total domination problem in proper interval graphs	64
Finer-grained reductions in fine-grained hardness of approximation	53
An algorithmic construction of union-intersection-bounded families	49
Oracle separations for non-adaptive collapse-free quantum computing	39
Maximal degenerate palindromes with gaps and mismatches	38
Sublinear P system solutions to NP-complete problems	37
A tighter proof for CCA secure inner product functional encryption: Genericity meets efficiency	32
A linkable ring signature scheme with unconditional anonymity in the standard model	28
Matching cut and variants on bipartite graphs of bounded radius and diameter	28
Editorial Board	24
How real is incomputability in physics?	24
Editorial Board	24
On CNF formulas irredundant with respect to unit clause propagation	24
Preface	23
Parameterised approximation of the fixation probability of the dominant mutation in the multi-type Moran process	22
The 1-good-neighbour diagnosability of modified bubblesort graphs under the PMC and	20
Reliability measure of the n-th cartesian product of complete graph K4 on h-extra edge-connectivity	20
On 1-planar graphs with bounded cop-number	19
The parameterized complexity of welfare guarantees in Schelling segregation	19
Editorial Board	19
Axiomatising weak bisimulation congruences over CCS with left merge and communication merge	18
Partial key exposure attacks on Prime Power RSA with non-consecutive blocks	18
A linear time algorithm for connected p-centdian problem on block graphs	17
On the power of threshold-based algorithms for detecting cycles in the CONGEST model	17
Closed subsets in Bishop topological groups	17

A parametric worst-case approach to fairness in cooperative games with transferable utility	16
A generalization of a theorem of Rothschild and van Lint	16
A new dynamic programming algorithm for the simplified partial digest problem	16
Integer k-matching preclusion of some interconnection networks	15
Editorial Board	15
Editorial Board	15
Editorial Board	15
Editorial Board	14
Three remarks on W graphs	14
Cellular automata and bootstrap percolation	14
Editorial Board	13
Editorial Board	13
Deterministic rendezvous in infinite trees	13
Network control games played on graphs	13
Reliability evaluation of complete graph-based recursive networks	13
Distributed coloring and the local structure of unit-disk graphs	13
On the binary digits of n and n2	13
Towards a general methodology for formal verification on spiking neural P systems	13
Factorisation in the semiring of finite dynamical systems	12
Weakly leveled planarity with bounded span	12
Dynamic debt swapping in financial networks	12
Decreasing verification radius in local certification	12
Editorial Board	12
Physical ZKP protocols for Nurimisaki and Kurodoko	12
An array P system based on a new variant of pure 2D context-free grammars	12
Call admission problems on grids with advice	12
On the Weisfeiler algorithm of depth-1 stabilization	12
The g-good-neighbor diagnosability of lexicographic product networks under the PMC model	12
Editorial Board	12
A 5k-vertex kernel for 3-path vertex cover	12
Notes on Smyth-completes and local Yoneda-completes	12
Investigation of E-voting system using face recognition using convolutional neural network (CNN)	12
Linear Programming complementation	12
Approximation algorithms for maximum weighted throughput on unrelated machines	12
On the existence of EFX (and Pareto-optimal) allocations for binary chores	11
Editorial Board	11
A strongly polynomial time approximation algorithm for the min-max clustered cycle cover problem	11
On properties of languages accepted by deterministic pushdown automata with translucent input letters	11
Generating Java code pairing with ChatGPT	11
Dormancy-aware timed branching bisimilarity with an application to communication protocol analysis	11
Identity-based matchmaking encryption with stronger security and instantiation on lattices	11
A categorical approach to reversible Turing machines and Brin-Thompson groups	11
Hypergraph burning, matchings, and zero forcing	11
The computational complexity of forced capture Hnefatafl	11
Computational complexity of normalizing constants for the product of determinantal point processes	10
On the complexity of winner determination and strategic control in conditional approval voting	10
Generative abstraction of Markov population processes	10
The impact of core constraints on truthful bidding in combinatorial auctions	10
New approximation algorithms for RNA secondary structures prediction problems by local search	10
Connectivity and diagnosability of the complete Josephus cube networks under h-extra fault-tolerant model	10

On the detection of local and global amoebas: Theoretical insights and practical algorithms	10
Gacs – Kucera theorem	10
Editorial Board	10
Powers of low rank sparse matrices	10
On the complexity of nucleolus computation for bipartite b-matching games	10
Updatable searchable symmetric encryption: Definitions and constructions	10
The balanced connected subgraph problem for geometric intersection graphs	10
Analysis of key reuse security for Aigis.KEM	9
Subtyping context-free session types	9
Hierarchical decompositions of implicational bases for the enumeration of meet-irreducible elements	9
On additive approximate submodularity	9
Grouped domination parameterized by vertex cover, twin cover, and beyond	9
A weak inverse of language neighborhoods and its properties	9
Fast and simple (1 + ε)Δ-edge-coloring of dense graphs	9
Complexity and approximation algorithms for two parallel dedicated machine scheduling with conflict constraints	9
Editorial Board	9
Beyond pointwise submodularity: Non-monotone adaptive submodular maximization subject to knapsack and k-system constraints	9
Turing video-based cognitive tests to handle entangled concepts	9
Robustly reusable fuzzy extractor from isogeny	9
On computable numbers, with an application to the Druckproblem	9
Algorithmic results in secure total dominating sets on graphs	9
NP-hardness of m-dimensional weighted matching problems	9
Single- and multi-objective evolutionary algorithms for the knapsack problem with dynamically changing constraints	9
Editorial Board	8
Threshold-based network structural dynamics	8
Approximation algorithm for prize-collecting sweep cover with base stations	8
How bad is the merger paradox?	8
Editorial Board	8
Self-stabilizing spanner topology control solutions in wireless ad hoc networks	8
The existence and efficiency of PMMS allocations	8
Parallel Contextual Array Insertion Deletion Grammars, Pure 2D Context-Free Grammars and Associated P Systems	8
Relating randomized right-hand sides to communicating rewriting rules	8
Complexity results on register context-free grammars and related formalisms	8
Certification of an exact worst-case self-stabilization time	8
Protocols with constant local storage and unreliable communication	8
On minimal critical exponent of balanced sequences	8
Algebraic properties and transformations of monographs	8
Optimization on the smallest eigenvalue of grounded Laplacian matrix via edge addition	8
Improved algorithms for bandit with graph feedback via regret decomposition	8
Almost envy-freeness for groups: Improved bounds via discrepancy theory	8
Extensional proofs in a propositional logic modulo isomorphisms	8
Streaming approximation scheme for minimizing total completion time on parallel machines subject to varying processing capacity	8
Upper powerdomains of quasicontinuous dcpos	8
Lower bounds for the sum of small-size algebraic branching programs	8
Boundary sketching with asymptotically optimal distance and rotation	7
Cascade products and Wheeler automata	7
Capacity planning for dependable services	7
Online coloring of disk graphs	7
Diagonal of pseudoinverse of graph Laplacian: Fast estimation and exact results	7
Nearly k-universal words – Investigating a part of Simon's congruence	7
Disjunctive sums of quasi-nimbers	7
Verifiable Crowd Computing: Coping with bounded rationality	7
An accelerated deterministic algorithm for maximizing monotone submodular minus modular function with cardinality constraint	7
Exploring the gap between treedepth and vertex cover through vertex integrity	7
Eliciting truthful reports with partial signals in repeated games	7
Greedy+Singleton: An efficient approximation algorithm for k-submodular knapsack maximization	7
Decision algorithms for reversibility of 1D cellular automata under reflective boundary conditions	7
(Definitely not) Boring interaction abstract machines	7
Fixed points and attractors of reactantless and inhibitorless reaction systems	7
Editorial Board	7
An approximate cost recovery scheme for the k-product facility location game with penalties	7
Asynchronous fully-decentralized SGD in the cluster-based model	7
Multi-stage Proof-of-Works: Properties and vulnerabilities	7
Mutual witness Gabriel drawings of complete bipartite graphs	7
A categorical model for organic chemistry	7
Securing data in the cloud using pairing-free inner product functional encryption with unbounded vector size	7
On a vertex-capturing game	7
A new fast root-finder for black box polynomials	7
Improved unbounded inner-product functional encryption	7
Editorial Board	6
Order based algorithms for the core maintenance problem on edge-weighted graphs	6
On algorithmic applications of sim-width and mim-width of (H1,H2)-free graphs	6
Computational task offloading algorithm based on deep reinforcement learning and multi-task dependency	6
Approximate distance oracles with improved stretch for sparse graphs	6
Partial and constrained level planarity	6
Editorial Board	6
Refined computational complexities of Hospitals/Residents problem with regional caps	6
Editorial Board	6
Linear-space S-table algorithms for the longest common subsequence problem	6
The complexity of bicriteria tree-depth	6

Efficiency and inefficiency of Nash equilibrium for scheduling games on batching-machines with activation cost	6
MODRED: A code-based non-interactive key exchange protocol	6
Quantum collision search for ternary LWE keys	6
Process-commutative distributed objects: From cryptocurrencies to Byzantine-Fault-Tolerant CRDTs	6
Remarks on hyperspaces for Priestley spaces	6
Editorial Board	6
On the connectedness of arithmetic hyperplanes	6
Combinatorics of minimal absent words for a sliding window	6
Sorting via shuffles with a cut after the longest increasing prefix	6
Location functions for self-stabilizing byzantine tolerant swarms	6
Using edge contractions to reduce the semitotal domination number	6
TCS special issue: Combinatorics on Words – WORDS 2021	6
Space efficient algorithm for solving reachability using tree decomposition and separators	6
On the power of local graph expansion grammars with and without additional restrictions	6
Editorial Board	6
Modelling of DNA mismatch repair with a reversible process calculus	6
Renaming in distributed certification	6
Enhancing fault tolerance of balanced hypercube networks by the edge partition method	6
Preface for the special issue of Theoretical Computer Science in honor of the 60th birthday of Yuxi Fu	6
Kolmogorov-Loveland betting strategies lose the Betting game on open sets	6
From multivalued to Boolean functions: Preservation of soft nested canalization	6
Undecidability of the universal support problem for weighted automata over zero-sum-free commutative semirings	6
Editorial Board	6
In memory of Jérôme Monnot	6
Constant amortized time enumeration of Eulerian trails	6
Algorithmic aspects of paired disjunctive domination in graphs	6
Threshold sampling	5
Editorial Board	5
Constrained flows in networks	5
Clustering under a knapsack constraint: Parameterized approximation for the knapsack median problem	5
Quantum and classical query complexities for generalized Simon's problem	5
Distributed transformations of Hamiltonian shapes based on line moves	5
Random generation of source vectors with a fixed preponderant property	5
Editorial Board	5
Intrinsic universality in automata networks III: On symmetry versus asynchrony	5
Self-similarity of communities of the ABCD model	5
Elastic founder graphs improved and enhanced	5
Theoretical design of decentralized auction framework under mobile crowdsourcing environment	5
Integer-valued martingales and cl-Turing reductions	5
Support preorder on finitely supported Cb	5
A decomposition theorem for number-conserving multi-state cellular automata on triangular grids	5
Connectivity and constructive algorithms of disjoint paths in dragonfly networks	5
Perfectly matched sets in graphs: Parameterized and exact computation	5
Resource efficient stabilization for local tasks despite unknown capacity links	5
Editorial	5
Computational power of autonomous robots: Transparency vs. opaqueness	5
Varieties of contextuality based on probability and structural nonembeddability	5
The Convex Set Forming Game	5
Query answering over inconsistent knowledge bases: A probabilistic approach	5
Subnetwork reliability analysis about complete-transposition graph networks	5
The work function algorithm for the paging problem	5
Chess is hard even for a single player	5
Do additional target points speed up evolutionary algorithms?	5
Move-optimal arbitrary pattern formation by mobile robots on rectangular grid using near-optimal spatial area	5
#P-Hardness proofs of matrix immanants evaluated on restricted matrices	5
A logarithmic-sized accountable ring signature scheme in the standard model	5
Searching in trees with monotonic query times	5
An efficient PMC model-based local diagnosis structure and algorithm	5
Centralised connectivity-preserving transformations for programmable matter: A minimal seed approach	5
Weighted forward looking adaptive coding	5
On the complexity of distance-d independent set reconfiguration	5
On the traceability of group signatures: Uncorrupted user must exist	5
Linear-time computation of DAWGs, symmetric indexing structures, and MAWs for integer alphabets	5
On the complexity of fair coin flipping	5
Visibility extension via reflection	5
Mutual visibility of luminous robots despite angular inaccuracy	5
Better guarantees for k-median with service installation costs	5
How majority-vote crossover and estimation-of-distribution algorithms cope with fitness valleys	5
Signatures of knowledge for Boolean circuits under standard assumptions	5
A fault diagnosis method to defend scapegoating attack in network tomography	5
Repeatedly matching items to agents fairly and efficiently	5
Model checking differentially private properties	5
Tractability beyond β-acyclicity for conjunctive queries with negation and SAT	5
The equivalence between Galois and Fibonacci NFSRs	5
Learning algebraic structures with the help of Borel equivalence relations	5
On monochromatic arithmetic progressions in binary words associated with pattern sequences	5
The non-inclusive diagnosability of a kind of networks	5
A Java-like calculus with heterogeneous coeffects	5
Corrigendum to “Complexity and approximability of the happy set problem” [Theor. Comput. Sci. 866 (2021) 123–144]	5
Finitely ambiguous and finitely sequential weighted automata over fields	5
Optimal L-algorithms for rendezvous of asynchronous mobile robots with extern	5
Efficient and reliable post-quantum authentication	5
Languages generated by numerical P systems with thresholds	5
Decision on block size in blockchain systems by evolutionary equilibrium analysis	5
Sign-then-encrypt with security enhancement and compressed ciphertext	5
Fast computations on ordered nominal sets	5
An anomaly-based intrusion detection system using recursive feature elimination technique for improved attack detection	5
The Voting algorithm is robust to various noise models	5
Approximating power node-deletion problems	5
Removing algorithmic discrimination (with minimal individual error)	5
Time and energy driven online scheduling problem in EV charging	5
Editorial Board	5
Stagnation detection meets fast mutation	4
An FPT algorithm for node-disjoint subtrees problems parameterized by treewidth	4
Parking problem by oblivious mobile robots in infinite grids	4