Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

RSS-FeedNext next

TR20-105 | 14th July 2020
Zoë Bell

Automating Regular or Ordered Resolution is NP-Hard

We show that is hard to find regular or even ordered (also known as Davis-Putnam) Resolution proofs, extending the breakthrough result for general Resolution from Atserias and Müller to these restricted forms. Namely, regular and ordered Resolution are automatable if and only if P = NP. Specifically, for a CNF ... more >>>

TR20-104 | 12th July 2020
Oded Goldreich

On Counting $t$-Cliques Mod 2

Revisions: 2

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 >>>

TR20-103 | 9th July 2020
Mahdi Cheraghchi, Shuichi Hirahara, Dimitrios Myrisiotis, Yuichi Yoshida

One-Tape Turing Machine and Branching Program Lower Bounds for MCSP

For a size parameter $s\colon\mathbb{N}\to\mathbb{N}$, the Minimum Circuit Size Problem (denoted by ${\rm MCSP}[s(n)]$) is the problem of deciding whether the minimum circuit size of a given function $f \colon \{0,1\}^n \to \{0,1\}$ (represented by a string of length $N := 2^n$) is at most a threshold $s(n)$. A ... more >>>

Next next

ISSN 1433-8092 | Imprint