Skip to main content
main-content

Theory of Computing Systems OnlineFirst articles

31.08.2021

The Complexity of Counting CSPd

Counting CSPd is the counting constraint satisfaction problem (# CSP in short) restricted to the instances where every variable occurs a multiple of d times. This paper revisits tractable structures in # CSP and gives a complexity classification …

09.08.2021 Open Access

FKT is Not Universal — A Planar Holant Dichotomy for Symmetric Constraints

We prove a complexity classification for Holant problems defined by an arbitrary set of complex-valued symmetric constraint functions on Boolean variables. This is to specifically answer the question: Is the Fisher-Kasteleyn-Temperley (FKT) …

02.08.2021

Risk-Robust Mechanism Design for a Prospect-Theoretic Buyer

Consider the revenue maximization problem of a risk-neutral seller with m heterogeneous items for sale to a single additive buyer, whose values for the items are drawn from known distributions. If the buyer is also risk-neutral, it is known that a …

02.08.2021

Radio k-chromatic Number of Full m-ary Trees

For a simple connected graph G = (V (G),E(G)) and a positive integer k, a radio k-labelling of G is a mapping f : V ( G ) → { 0 , 1 , 2 , … } $f \colon V(G)\rightarrow \{0,1,2,\ldots \}$ such that | f ( u ) − f ( v ) | ≥ k + 1 − d ( u , v ) …

21.07.2021

Exact Multi-Covering Problems with Geometric Sets

The b-Exact Multicover problem takes a universe U of n elements, a family F $\mathcal {F}$ of m subsets of U, a function dem : U → { 1 , … , b } ${\textsf {dem}}: U \rightarrow \{1,\ldots ,b\}$ and a positive integer k, and decides whether there …

Aktuelle Ausgaben

Über diese Zeitschrift

Statement of Scope

TOCS is devoted to publishing original research from all areas of theoretical computer science, ranging from foundational areas such as computational complexity, to fundamental areas such as algorithms and data structures, to focused areas such as parallel and distributed algorithms and architectures.

Weitere Informationen

Premium Partner