Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with order-invariance:
TR11-158 | 25th November 2011
Matthew Anderson, Dieter van Melkebeek, Nicole Schweikardt, Luc Segoufin

Locality from Circuit Lower Bounds

We study the locality of an extension of first-order logic that captures graph queries computable in AC$^0$, i.e., by families of polynomial-size constant-depth circuits. The extension considers first-order formulas over relational structures which may use arbitrary numerical predicates in such a way that their truth value is independent of the ... more >>>

ISSN 1433-8092 | Imprint