All reports by Author Anuj Dawar:

__
TR12-015
| 22nd February 2012
__

Albert Atserias, Anuj Dawar#### Degree Lower Bounds of Tower-Type for Approximating Formulas with Parity Quantifiers

Revisions: 2

__
TR09-131
| 2nd December 2009
__

Stephan Kreutzer, Anuj Dawar#### Parameterized Complexity of First-Order Logic

Revisions: 2

Albert Atserias, Anuj Dawar

Kolaitis and Kopparty have shown that for any first-order formula with

parity quantifiers over the language of graphs there is a family of

multi-variate polynomials of constant-degree that agree with the

formula on all but a $2^{-\Omega(n)}$-fraction of the graphs with $n$

vertices. The proof yields a bound on the ...
more >>>

Stephan Kreutzer, Anuj Dawar

We show that if $\mathcal C$ is a class of graphs which is

"nowhere dense" then first-order model-checking is

fixed-parameter tractable on $\mathcal C$. As all graph classes which exclude a fixed minor, or are of bounded local tree-width or locally exclude a minor are nowhere dense, this generalises algorithmic ...
more >>>