Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with clique problem:
TR98-041 | 27th July 1998
Stasys Jukna

Combinatorics of Monotone Computations

We consider a general model of monotone circuits, which
we call d-local. In these circuits we allow as gates:
(i) arbitrary monotone Boolean functions whose minterms or
maxterms (or both) have length at most <i>d</i>, and
(ii) arbitrary real-valued non-decreasing functions on ... more >>>

TR20-104 | 12th July 2020
Oded Goldreich

On Counting $t$-Cliques Mod 2

Revisions: 3

For a constant integer $t$, we consider the problem of counting the number of $t$-cliques $\bmod 2$ in a given graph.
We show that this problem is not easier than determining whether a given graph contains a $t$-clique, and present a simple worst-case to average-case reduction for it. The ... more >>>

ISSN 1433-8092 | Imprint