论文摘要资料文件与下载

Property Testing and Related Problems

博士研究生：吴成钢

指导教师：姚期智 院士

所属院系：交叉信息研究院

论文摘要

    This thesis studies three fundamental property testing and related problems. Property Testing is the study of ultra-efficient algorithms which distinguish between objects having a specific property and objects far from having that property. It has been extensively and intensively studied in the literature, and is a special type of sub-linear algorithms.

    First, we consider the geometric problem of estimating the surface area of an unknown set F in R^n given membership oracle access. In contrast to previous work, we do not assume that F is convex. By necessity we work in the property testing model. Our task is to seek for an algorithm which, given parameters A and epsilon, satisfies: (i) If the surface area of F is at most A, then accepts with high probability; (ii) If F is epsilon-far in volume from all sets with surface area at most kappa*A, then rejects with high probability. We call kappa the ``approximation factor'' of the testing algorithm. For every n and kappa>4/pi, we give an algorithm that uses O(1/\epsilon) queries. For smaller n, we have improved bounds. For n=1, we can achieve kappa=1 with O(1/\epsilon^{3.5}) queries (slightly improving [BBBY12]), or any kappa>1 with O(1/\epsilon) queries (improving[KR98]). For n = 2,3 we can achieve kappa = 1.08 and 1.13 respectively, with O(1/\epsilon) queries.

    Second, we consider the problem of testing whether a Boolean function f:\{0,1\}^n--> \{0,1\} is computable by a read-once, width-w ordered binary decision diagrams for a small constant w. This problem has two variants: one where the variables must appear in a fixed and known order, and one where the variables are allowed to appear in an arbitrary order. We prove tight query complexity lower bounds for several settings including: (i) For w=2, we prove that for both variants, Omega(n) non-adaptive queries are required, thus Omega(\log n) adaptive queries are required by any testing algorithm, which matches known upper bounds in [RT09]; (ii) For any constant w>3, we prove that Omega(n) adaptive queries are required if the variables must appear in a fixed order, which answers a conjecture of Goldreich[Gol10] affirmatively.

    Third, we consider the problem of distinguishing between almost isomorphic graph pairs and graph pairs that are far from being isomorphic, which is quite related to testing graph isomorphism, except that we work under the classical computational complexity setting. We prove that the problem is hard under either of the two following widely-believed complexity-theoretical assumptions: (i) Feige's random 3XOR hypothesis; (ii) NP does not equal to RP. Along the way, we prove robust asymmetry of random graphs, which qualitatively generalize the asymmetry of random graphs by Erdos and Renyi[ER63], and may be of independent interest. Roughly speaking, a graph is robustly asymmetric if every permutation over vertices which is far from the identity is actually far from being an automorphism.