Testing graphs against an unknown distribution
Testing graphs against an unknown distribution
复制标题
针对未知分布测试图表
DOI：
10.1145/3313276.3316308
复制
发表时间：
2019
影响因子：
1
通讯作者：
A. Shapira
中科院分区：
文献类型：
--
作者：
Lior Gishboliner;A. Shapira
The area of graph property testing seeks to understand the relation between the global properties of a graph and its local statistics. In the classical model, the local statistics of a graph is defined relative to a uniform distribution over the graph’s vertex set. A graph property P\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\cal P}$$\end{document} is said to be testable if the local statistics of a graph can allow one to distinguish between graphs satisfying P\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\cal P}$$\end{document} and those that are far from satisfying it. Goldreich recently introduced a generalization of this model in which one endows the vertex set of the input graph with an arbitrary and unknown distribution, and asked which of the properties that can be tested in the classical model can also be tested in this more general setting. We completely resolve this problem by giving a (surprisingly “clean ”) characterization of these properties. To this end, we prove a removal lemma for vertex weighted graphs which is of independent interest.
The area of graph property testing seeks to understand the relation between the global properties of a graph and its local statistics. In the classical model, the local statistics of a graph is defined relative to a uniform distribution over the graph’s vertex set. A graph property P\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\cal P}$$\end{document} is said to be testable if the local statistics of a graph can allow one to distinguish between graphs satisfying P\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\cal P}$$\end{document} and those that are far from satisfying it. Goldreich recently introduced a generalization of this model in which one endows the vertex set of the input graph with an arbitrary and unknown distribution, and asked which of the properties that can be tested in the classical model can also be tested in this more general setting. We completely resolve this problem by giving a (surprisingly “clean ”) characterization of these properties. To this end, we prove a removal lemma for vertex weighted graphs which is of independent interest.
普通树木着色的芒硝动力学混合时间
影响因子：
1
作者：
Goldberg L
通讯作者：
Goldberg L