Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with First-Order Logic:
TR09-033 | 16th April 2009
Phokion G. Kolaitis, Swastik Kopparty

Random Graphs and the Parity Quantifier

The classical zero-one law for first-order logic on random graphs says that for every first-order property $\varphi$ in the theory of graphs and every $p \in (0,1)$, the probability that the random graph $G(n, p)$ satisfies $\varphi$ approaches either $0$ or $1$ as $n$ approaches infinity. It is well known ... more >>>

TR16-053 | 6th April 2016
Jiawei Gao, Russell Impagliazzo

Orthogonal Vectors is hard for first-order properties on sparse graphs

Revisions: 3

Fine-grained reductions, introduced by Vassilevska-Williams and Williams, preserve any improvement in the known algorithms. These have been used very successfully in relating the exact complexities of a wide range of problems, from NP-complete problems like SAT to important quadratic time solvable problems within P such as Edit Distance. However, until ... more >>>

ISSN 1433-8092 | Imprint