Loading...
Please wait, while we are loading the content...
Similar Documents
On the lowest level of query complexity in testing graph properties
| Content Provider | Semantic Scholar |
|---|---|
| Author | Avigad, Lidor Goldreich, Oded |
| Copyright Year | 2009 |
| Abstract | In this thesis, we continue the work of Goldreich and Ron in (ECCC 2008) by presenting an in nite family of natural properties of dense graphs having non-adaptive testers of query complexity of Õ(1/2) , where 2 is the proximity parameter. Speci cally, for every xed graph H , we show a non-adaptive tester of query complexity Õ(2−1) for the property of being a blow-up H . This considerably extends the result of Goldreich and Ron that corresponds to the special case in which H consists of a complete graph. Our techniques signi cantly extend those of Goldreich and Ron, while coping with di culties that emerge from the "non forcing" structure of a blow-up of a non-clique. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.wisdom.weizmann.ac.il/~oded/PDF/msc-la.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
