All reports by Author Angsheng Li:

__
TR11-101
| 26th July 2011
__

Angsheng Li, Yicheng Pan, Pan Peng#### Testing Conductance in General Graphs

Angsheng Li, Yicheng Pan, Pan Peng

In this paper, we study the problem of testing the conductance of a

given graph in the general graph model. Given distance parameter

$\varepsilon$ and any constant $\sigma>0$, there exists a tester

whose running time is $\mathcal{O}(\frac{m^{(1+\sigma)/2}\cdot\log

n\cdot\log\frac{1}{\varepsilon}}{\varepsilon\cdot\Phi^2})$, where

$n$ is the number of vertices and $m$ is the number ...
more >>>