Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > REGULARITY LEMMA:
Reports tagged with Regularity Lemma:
TR00-083 | 18th September 2000
Eldar Fischer

#### Testing graphs for colorability properties

Revisions: 1

Let $P$ be a property of graphs. An $\epsilon$-test for $P$ is a
randomized algorithm which, given the ability to make queries whether
a desired pair of vertices of an input graph $G$ with $n$ vertices are
adjacent or not, distinguishes, with high probability, between the
case of $G$ satisfying ... more >>>

TR05-085 | 5th August 2005
Asaf Shapira, Noga Alon

#### Homomorphisms in Graph Property Testing - A Survey

Property-testers are fast randomized algorithms for distinguishing
between graphs (and other combinatorial structures) satisfying a
certain property, from those that are far from satisfying it. In
many cases one can design property-testers whose running time is in
fact {\em independent} of the size of the input. In this paper we
more >>>

TR08-103 | 22nd November 2008
that if $D$ is a distribution over $\{ 0,1\}^n$ of min-entropy at least $n-k$,
then for every $S$ and $\epsilon$ there is a circuit $C$ of size at most