Theoretical Computer Science

Article	Citations
How real is incomputability in physics?	46
Factorisation in the semiring of finite dynamical systems	38
Three remarks on W graphs	34
An optimal algorithm for 2-bounded delay buffer management with lookahead	32
Deterministic rendezvous in infinite trees	32
Algorithms for energy conservation in heterogeneous data centers	29
The parameterized complexity of welfare guarantees in Schelling segregation	28
A 5k-vertex kernel for 3-path vertex cover	26
Closed subsets in Bishop topological groups	24
On the power of threshold-based algorithms for detecting cycles in the CONGEST model	18
A new dynamic programming algorithm for the simplified partial digest problem	18
Parameterised approximation of the fixation probability of the dominant mutation in the multi-type Moran process	17
An algorithm for the secure total domination problem in proper interval graphs	17
On the solution bound of two-sided scaffold filling	17
Partial key exposure attacks on Prime Power RSA with non-consecutive blocks	16
A generalization of a theorem of Rothschild and van Lint	15
New (k,l,m)-verifiable multi-secret sharing schemes based on XTR public key system	15
CPA/CCA2-secure PKE with squared-exponential DFR from low-noise LPN	15
Sublinear P system solutions to NP-complete problems	14
Finer-grained reductions in fine-grained hardness of approximation	14
Editorial Board	14
Improvements in the computing efficiency of the probabilities of the LIL test for the PRNG evaluation	14
Editorial Board	14
Distributed coloring and the local structure of unit-disk graphs	14
Editorial Board	13

Improved upper bound for sorting permutations by prefix transpositions	13
A data structure for substring-substring LCS length queries	13
Editorial Board	13
Wildcarded identity-based encryption from lattices	13
A linear time algorithm for connected p-centdian problem on block graphs	12
Maximal degenerate palindromes with gaps and mismatches	12
A parametric worst-case approach to fairness in cooperative games with transferable utility	12
Complexity issues for timeline-based planning over dense time under future and minimal semantics	12
On the binary digits of n and n2	12
Editorial Board	12
Editorial Board	11
Editorial	11
An array P system based on a new variant of pure 2D context-free grammars	11
An algorithmic construction of union-intersection-bounded families	11
Cellular automata and bootstrap percolation	11
Oracle separations for non-adaptive collapse-free quantum computing	11
A linkable ring signature scheme with unconditional anonymity in the standard model	10
Preface	10
Call admission problems on grids with advice	10
Notes on Smyth-completes and local Yoneda-completes	10
Network control games played on graphs	10
Editorial Board	10
On 1-planar graphs with bounded cop-number	10
Reliability evaluation of complete graph-based recursive networks	10
Towards a general methodology for formal verification on spiking neural P systems	10
Editorial Board	10
Complexity and algorithms for neighbor-sum-2-distinguishing {1,3}-edge-weighting of graphs	10
Physical ZKP protocols for Nurimisaki and Kurodoko	10
Reliability measure of the n-th cartesian product of complete graph K4 on h-extra edge-connectivity	10
Linear Programming complementation	9
Grouped domination parameterized by vertex cover, twin cover, and beyond	9
Integer k-matching preclusion of some interconnection networks	9
Encoding Boolean networks into reaction systems for investigating causal dependencies in gene regulation	9
A tighter proof for CCA secure inner product functional encryption: Genericity meets efficiency	9
Dormancy-aware timed branching bisimilarity with an application to communication protocol analysis	9
A strongly polynomial time approximation algorithm for the min-max clustered cycle cover problem	9
Investigation of E-voting system using face recognition using convolutional neural network (CNN)	9
A substructure based lower bound for eternal vertex cover number	9
Generative abstraction of Markov population processes	9
Powers of low rank sparse matrices	9
On some FPT problems without polynomial Turing compressions	9
Identity-based matchmaking encryption with stronger security and instantiation on lattices	9
Computational complexity of normalizing constants for the product of determinantal point processes	8
Beyond pointwise submodularity: Non-monotone adaptive submodular maximization subject to knapsack and k-system constraints	8
The computational complexity of forced capture Hnefatafl	8
NP-hardness of m-dimensional weighted matching problems	8
Connectivity and diagnosability of the complete Josephus cube networks under h-extra fault-tolerant model	8
Algorithmic results in secure total dominating sets on graphs	8
Complexity of Scorpion Solitaire and applications to Klondike	8
Gacs – Kucera theorem	8

Editorial Board	8
Robustly reusable fuzzy extractor from isogeny	8
On additive approximate submodularity	8
Polynomial kernels for paw-free edge modification problems	8
On minimal critical exponent of balanced sequences	8
Near-optimal clustering in the k-machine model	8
The balanced connected subgraph problem for geometric intersection graphs	8
Fast and simple (1 + ε)Δ-edge-coloring of dense graphs	8
Complexity and approximation algorithms for two parallel dedicated machine scheduling with conflict constraints	8
Editorial Board	8
The classes PPA-k: Existence from arguments modulo k	8
Editorial Board	8
Editorial Board	8
Editorial Board	8
Generating Java code pairing with ChatGPT	7
Rational elements of summation semirings	7
Hierarchical decompositions of implicational bases for the enumeration of meet-irreducible elements	7
Embedding algorithm of spined cube into grid structure and its wirelength computation	7
Parallel Contextual Array Insertion Deletion Grammars, Pure 2D Context-Free Grammars and Associated P Systems	7
Relating randomized right-hand sides to communicating rewriting rules	7
Enhancing fault tolerance of balanced hypercube networks by the edge partition method	7
On computable numbers, with an application to the Druckproblem	7
The impact of core constraints on truthful bidding in combinatorial auctions	7
New approximation algorithms for RNA secondary structures prediction problems by local search	7
Disjoint paths and connected subgraphs for H-free graphs	7
Updatable searchable symmetric encryption: Definitions and constructions	7
Process-commutative distributed objects: From cryptocurrencies to Byzantine-Fault-Tolerant CRDTs	7
Greedy+Singleton: An efficient approximation algorithm for k-submodular knapsack maximization	7
Unified graphical co-modeling, analysis and verification of cyber-physical systems by combining AADL and Simulink/Stateflow	7
Optimization on the smallest eigenvalue of grounded Laplacian matrix via edge addition	7
Upper powerdomains of quasicontinuous dcpos	7
Alternation in two-way finite automata	7
Local fairness in hedonic games via individual threshold coalitions	7
Single- and multi-objective evolutionary algorithms for the knapsack problem with dynamically changing constraints	7
Enumeration of subtrees and BC-subtrees with maximum degree no more than k in trees	7
The existence and efficiency of PMMS allocations	7
Streaming approximation scheme for minimizing total completion time on parallel machines subject to varying processing capacity	7
On algorithmic applications of sim-width and mim-width of (H1,H2)-free graphs	7
Algebraic properties and transformations of monographs	7
On the complexity of nucleolus computation for bipartite b-matching games	7
A Myhill-Nerode theorem for register automata and symbolic trace languages	7
Modelling of DNA mismatch repair with a reversible process calculus	6
Nearly k-universal words – Investigating a part of Simon's congruence	6
Verifiable Crowd Computing: Coping with bounded rationality	6
Cascade products and Wheeler automata	6
Taming the knight's tour: Minimizing turns and crossings	6
Online coloring of disk graphs	6
Cutting bamboo down to size	6
Boundary sketching with asymptotically optimal distance and rotation	6
Exploring the gap between treedepth and vertex cover through vertex integrity	6
Differential logical relations, part II increments and derivatives	6
(k,p)-planarity: A relaxation of hybrid planarity	6
Building bridges – Honoring Nataša Jonoska on the occasion of her 60th birthday	6
Bisimilarity on Basic Parallel Processes	6
A categorial approach to reaction systems: First steps	6
Capacity planning for dependable services	6
Disjunctive sums of quasi-nimbers	6
A simple rounding scheme for multistage optimization	6
Component conditional fault tolerance of hierarchical folded cubic networks	6
Computational task offloading algorithm based on deep reinforcement learning and multi-task dependency	6
Fixed points and attractors of reactantless and inhibitorless reaction systems	6
Eliciting truthful reports with partial signals in repeated games	6
Multi-stage Proof-of-Works: Properties and vulnerabilities	6
Editorial Board	6
Exhaustive generation of some lattice paths and their prefixes	6
Extensional proofs in a propositional logic modulo isomorphisms	6
Editorial Board	6
Role colouring graphs in hereditary classes	6
Range minimum queries in minimal space	6
Self-stabilizing spanner topology control solutions in wireless ad hoc networks	6
On the complexity of local-equitable coloring of graphs	6
An approximate cost recovery scheme for the k-product facility location game with penalties	6
Editorial Board	6
An accelerated deterministic algorithm for maximizing monotone submodular minus modular function with cardinality constraint	6
Mutual witness Gabriel drawings of complete bipartite graphs	6
The g-component connectivity of graphs	6
Combinatorics of minimal absent words for a sliding window	5
Algorithmic aspects of paired disjunctive domination in graphs	5
Mutual visibility of luminous robots despite angular inaccuracy	5
Protocols with constant local storage and unreliable communication	5

Remarks on hyperspaces for Priestley spaces	5
Improved algorithms for bandit with graph feedback via regret decomposition	5
On the complexity of fair coin flipping	5
Almost envy-freeness for groups: Improved bounds via discrepancy theory	5
Location functions for self-stabilizing byzantine tolerant swarms	5
A categorical model for organic chemistry	5
Editorial Board	5
Order based algorithms for the core maintenance problem on edge-weighted graphs	5
From multivalued to Boolean functions: Preservation of soft nested canalization	5
Editorial Board	5
Self-similarity of communities of the ABCD model	5
Editorial Board	5
Approximation of the Double Traveling Salesman Problem with Multiple Stacks	5
Editorial Board	5
The complexity of bicriteria tree-depth	5
Linear-space S-table algorithms for the longest common subsequence problem	5
Sorting via shuffles with a cut after the longest increasing prefix	5
On finding maximum disjoint paths with different colors: Computational complexity and practical LP-based algorithms	5
Decision algorithms for reversibility of 1D cellular automata under reflective boundary conditions	5
Weighted forward looking adaptive coding	5
On a vertex-capturing game	5
Editorial Board	5
Approximation algorithm for prize-collecting sweep cover with base stations	5
TCS special issue: Combinatorics on Words – WORDS 2021	5
Securing data in the cloud using pairing-free inner product functional encryption with unbounded vector size	5
Editorial Board	5
Preface for the special issue of Theoretical Computer Science in honor of the 60th birthday of Yuxi Fu	5
A certifying and dynamic algorithm for the recognition of proper circular-arc graphs	5
A new fast root-finder for black box polynomials	5
Undecidability of the universal support problem for weighted automata over zero-sum-free commutative semirings	5
Editorial Board	5
Distributed transformations of Hamiltonian shapes based on line moves	5
Asynchronous fully-decentralized SGD in the cluster-based model	5
The unpaired many-to-many k-disjoint paths in bipartite hypercube-like networks	5
Complexity results on register context-free grammars and related formalisms	5
MODRED: A code-based non-interactive key exchange protocol	5
Threshold-based network structural dynamics	5
On the connectedness of arithmetic hyperplanes	5
How bad is the merger paradox?	5
Using edge contractions to reduce the semitotal domination number	5
Diagonal of pseudoinverse of graph Laplacian: Fast estimation and exact results	5
Languages generated by numerical P systems with thresholds	5
Editorial	5
Space efficient algorithm for solving reachability using tree decomposition and separators	5
Improved unbounded inner-product functional encryption	5
D_PSNI: Delimited persistent stochastic non-interference	5
Certification of an exact worst-case self-stabilization time	5
A weak semantic approach to bisimulation metrics in models with nondeterminism and continuous state spaces	5
In memory of Jérôme Monnot	5
Centralised connectivity-preserving transformations for programmable matter: A minimal seed approach	5
Linear-time computation of DAWGs, symmetric indexing structures, and MAWs for integer alphabets	4
Fast computations on ordered nominal sets	4
A decomposition theorem for number-conserving multi-state cellular automata on triangular grids	4
On the power of local graph expansion grammars with and without additional restrictions	4
Physical zero-knowledge proof for Ripple Effect	4
How majority-vote crossover and estimation-of-distribution algorithms cope with fitness valleys	4
Comparing reactions in reaction systems	4
Approximate distance oracles with improved stretch for sparse graphs	4
Visibility extension via reflection	4
2-colored point-set embeddings of partial 2-trees	4
Subnetwork reliability analysis of bubble-sort graph networks	4
Secret handshakes: Full dynamicity, deniability and lattice-based design	4
Varieties of contextuality based on probability and structural nonembeddability	4
Multi-key fully homomorphic encryption from NTRU and (R)LWE with faster bootstrapping	4
A Java-like calculus with heterogeneous coeffects	4
AbU: A calculus for distributed event-driven programming with attribute-based interaction	4
Repeatedly matching items to agents fairly and efficiently	4
Query answering over inconsistent knowledge bases: A probabilistic approach	4
Resource efficient stabilization for local tasks despite unknown capacity links	4
Constant amortized time enumeration of Eulerian trails	4
Better guarantees for k-median with service installation costs	4
Do additional target points speed up evolutionary algorithms?	4
Approximating power node-deletion problems	4
Corrigendum to “Complexity and approximability of the happy set problem” [Theor. Comput. Sci. 866 (2021) 123–144]	4
Stand up indulgent gathering	4
The work function algorithm for the paging problem	4
The equivalence between Galois and Fibonacci NFSRs	4
The Voting algorithm is robust to various noise models	4
On monochromatic arithmetic progressions in binary words associated with pattern sequences	4
On the complexity of distance-d independent set reconfiguration	4
Constrained flows in networks	4
A model of random industrial SAT	4
Tractability beyond β-acyclicity for conjunctive queries with negation and SAT	4
Sign-then-encrypt with security enhancement and compressed ciphertext	4
Query-competitive sorting with uncertainty	4
A tight bound for shortest augmenting paths on trees	4
Model checking differentially private properties	4
Threshold sampling	4
Query minimization under stochastic uncertainty	4
Decision on block size in blockchain systems by evolutionary equilibrium analysis	4
Removing algorithmic discrimination (with minimal individual error)	4
Intrinsic universality in automata networks III: On symmetry versus asynchrony	4
Signatures of knowledge for Boolean circuits under standard assumptions	4
Polynomial-time checking of generalized Sahlqvist syntactic shape	4
Quantum and classical query complexities for generalized Simon's problem	4