Property testing and its connection to learning and approximation

ABSTRACT

In this paper, we consider the question of determining whether a function f has property P or is &egr;-far from any function with property P. A property testing algorithm is given a sample of the value of f on instances drawn according to some distribution. In some cases, it is also allowed to query f on instances of its choice. We study this question for different properties and establish some connections to problems in learning theory and approximation.In particular, we focus our attention on testing graph properties. Given access to a graph G in the form of being able to query whether an edge exists or not between a pair of vertices, we devise algorithms to test whether the underlying graph has properties such as being bipartite, k-Colorable, or having a p-Clique (clique of density p with respect to the vertex set). Our graph property testing algorithms are probabilistic and make assertions that are correct with high probability, while making a number of queries that is independent of the size of the graph. Moreover, the property testing algorithms can be used to efficiently (i.e., in time linear in the number of vertices) construct partitions of the graph that correspond to the property being tested, if it holds for the input graph.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	N. Alon , R. A. Duke , H. Lefmann , V. Rödl , R. Yuster, The algorithmic aspects of the regularity lemma, Journal of Algorithms, v.16 n.1, p.80-109, Jan. 1994 [doi>10.1006/jagm.1994.1005]
	2	ALON, N., GOLDREICH, O., H#STAD, J., AND PERALTA, R. 1992. Simple constructions of almost k-wise independent random variables. J. Rand. Struct. Algorithms 33, 289-304.
	3	ANGLUIN, D. 1978. On the complexity of minimum inference of regular sets. Inf. Cont. 39, 337-350.
	4	A. Frieze, A new rounding procedure for the assignment problem with applications to dense graph arrangement problems, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.21, October 14-16, 1996
	5	Sanjeev Arora , David Karger , Marek Karpinski, Polynomial time approximation schemes for dense instances of NP-hard problems, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.284-293, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225140]
	6	ARORA, S., LUND, C., MOTWANI, R., SUDAN, M., AND SZEGEDY, M. 1992. Proof verification and intractability of approximation problems. In Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, pp. 14-23.
	7	ARORA, S., AND SAFRA, S. 1992. Probabilistic checkable proofs: A new characterization of NP. In Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, pp. 1-13.
	8	László Babai , Lance Fortnow , Leonid A. Levin , Mario Szegedy, Checking computations in polylogarithmic time, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.21-32, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103428]
	9	BABAI, L., FORTNOW, L., AND LUND, C. 1991b. Non-deterministic exponential time has two-prover interactive protocols. Computat. Complex. 1, 1, 3-40.
	10	M. Bellare , D. Coppersmith , J. Hastad , M. Kiwi , M. Sudan, Linearity testing in characteristic two, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.432, October 23-25, 1995
	11	M. Bellare , O. Goldreich , M. Sudan, Free bits, PCPs and non-approximability-towards tight results, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.422, October 23-25, 1995
	12	M. Bellare , S. Goldwasser , C. Lund , A. Russeli, Efficient probabilistically checkable proofs and applications to approximations, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.294-304, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167174]
	13	Mihir Bellare , Madhu Sudan, Improved non-approximability results, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.184-193, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195129]
	14	Shai Ben-David, Can finite samples detect singularities of real-valued functions?, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.390-399, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129749]
	15	Avrim Blum , Ronald L. Rivest, Training a 3-node neural network in NP-complete, Advances in neural information processing systems 1, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1989
	16	Manuel Blum , Michael Luby , Ronitt Rubinfeld, Self-testing/correcting with applications to numerical problems, Journal of Computer and System Sciences, v.47 n.3, p.549-595, Dec. 1993 [doi>10.1016/0022-0000(93)90044-W]
	17	Anselm Blumer , A. Ehrenfeucht , David Haussler , Manfred K. Warmuth, Learnability and the Vapnik-Chervonenkis dimension, Journal of the ACM (JACM), v.36 n.4, p.929-965, Oct. 1989 [doi>10.1145/76359.76371]
	18	Ran Canetti , Uri Feige , Oded Goldreich , Moni Naor, Adaptively secure multi-party computation, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.639-648, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.238015]
	19	CHERNOFF, H. 1952. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Stat. 23, 493-507.
	20	COVER, T.M. 1973. On determining the rationality of the mean of a random variable.Ann. Stat. 1, 862-871.
	21	W. Fernandez de la Vega, MAX-CUT has a randomized approximation scheme in dense graphs, Random Structures & Algorithms, v.8 n.3, p.187-198, May 1996 [doi>10.1002/(SICI)1098-2418(199605)8:3<187::AID-RSA3>3.0.CO;2-U]
	22	K Edwards, The complexity of colouring problems on dense graphs, Theoretical Computer Science, v.43 n.2-3, p.337-343, July 1986
	23	Funda Ergün , Sampath Kannan , S. Ravi Kumar , Ronitt Rubinfeld , Mahesh Viswanathan, Spot-checkers, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.259-268, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276757]
	24	U. Feige , S. Goldwasser , L. Lovász , S. Safra , M. Szegedy, Approximating clique is almost NP-complete (preliminary version), Proceedings of the 32nd annual symposium on Foundations of computer science, p.2-12, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185341]
	25	A. Frieze, The regularity lemma and approximation schemes for dense problems, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.12, October 14-16, 1996
	26	Peter Gemmell , Richard Lipton , Ronitt Rubinfeld , Madhu Sudan , Avi Wigderson, Self-testing/correcting for polynomials and for approximate functions, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.33-42, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103429]
	27	GOLD, M. E. 1978. Complexity of automation identification from given data. Inf. Cont. 37, 302-320.
	28	GOLDREICH, O. 1995. Foundations of Crytography--Fragments of a Book. Available from ECCC, http ://www. eccc.uni-trier, de/eccc/.
	29	Oded Goldreich , Dana Ron, Property testing in bounded degree graphs, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.406-415, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258627]
	30	Oded Goldreich , Dana Ron, A sublinear bipartiteness tester for bounded degree graphs, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.289-298, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276767]
	31	GROTSCHEL, M., LOVASZ, L., AND SCHRIJVER, A. 1988. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, New York.
	32	HAJNAL, P. 1991. An #(n4/3) lower bound on the randomized complexity of graph properties. Combinatorica 11, 2, 131-144.
	33	Johan Håstad, Testing of the long code and hardness for clique, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.11-19, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237820]
	34	J. Hastad, Clique is hard to approximate within n1-, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.627, October 14-16, 1996
	35	Johan Håstad, Some optimal inapproximability results, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.1-10, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258536]
	36	Dorit S. Hochbaum , David B. Shmoys, Using dual approximation algorithms for scheduling problems theoretical and practical results, Journal of the ACM (JACM), v.34 n.1, p.144-162, Jan. 1987 [doi>10.1145/7531.7535]
	37	Dorit s. Hochbaum , David B. Shmoys, A polynomial approximation scheme for scheduling on uniform processors: Using the dual approximation approach, SIAM Journal on Computing, v.17 n.3, p.539-551, June 1988 [doi>10.1137/0217033]
	38	HOEFFDING, W., AND WOLFOWITZ, J. 1958. Distinguishability of sets of distributions. Ann. Math. Stat. 29, 700-718.
	39	KARGER, D. R., MOTWANI, R., AND SUDAN, M. 1994. Approximate graph coloring by semidefinite programming. In Proceedings of the 35th Annual IEEE Symposium on the Foundation of Computer Science. ACM, New York, pp. 2-13.
	40	Michael Kearns , Yishay Mansour , Dana Ron , Ronitt Rubinfeld , Robert E. Schapire , Linda Sellie, On the learnability of discrete distributions, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.273-282, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195155]
	41	Michael Kearns , Dana Ron, Testing problems with sub-learning sample complexity, Proceedings of the eleventh annual conference on Computational learning theory, p.268-279, July 24-26, 1998, Madison, Wisconsin, United States [doi>10.1145/279943.279996]
	42	Michael J. Kearns , Robert E. Schapire , Linda M. Sellie, Toward efficient agnostic learning, Proceedings of the fifth annual workshop on Computational learning theory, p.341-352, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130424]
	43	KING, V. 1991. An O(n5/4) lower bound on the randomized complexity of graph properties. Combinatorica 11, 1, 23-32.
	44	Marcos Kiwi , Michael Sipser, Probabilistically checkable proofs and the testing of hadamard-like codes, 1996
	45	Sanjeev R. Kulkarni , Ofer Zeitouni, On probably correct classification of concepts, Proceedings of the sixth annual conference on Computational learning theory, p.111-116, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168318]
	46	LOVASZ, L., AND YOUNG, N. 1991. Lecture notes on evasiveness of graph properties. Tech. Rep. TR-317-91. Computer Science Department, Princeton Univ., Princeton, N.J.
	47	Joseph Naor , Moni Naor, Small-bias probability spaces: efficient constructions and applications, SIAM Journal on Computing, v.22 n.4, p.838-856, Aug. 1993 [doi>10.1137/0222053]
	48	Erez Petrank, The hardness of approximation: gap location, Computational Complexity, v.4 n.2, p.133-157, April 1994 [doi>10.1007/BF01202286]
	49	Leonard Pitt , Leslie G. Valiant, Computational limitations on learning from examples, Journal of the ACM (JACM), v.35 n.4, p.965-984, Oct. 1988 [doi>10.1145/48014.63140]
	50	Leonard Pitt , Manfred K. Warmuth, The minimum consistent DFA problem cannot be approximated within any polynomial, Journal of the ACM (JACM), v.40 n.1, p.95-142, Jan. 1993 [doi>10.1145/138027.138042]
	51	Arnold L. Rosenberg, On the time required to recognize properties of graphs: a problem, ACM SIGACT News, v.5 n.4, p.15-16, October 1973 [doi>10.1145/1008299.1008302]
	52	RUBINFELD, R. 1994. Robust functional equations and their applications to program testing. In Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, pp. 288-299.
	53	Ronitt Rubinfeld , Madhu Sudan, Robust Characterizations of Polynomials withApplications to Program Testing, SIAM Journal on Computing, v.25 n.2, p.252-271, February 1996 [doi>10.1137/S0097539793255151]
	54	J. T. Schwartz, Fast Probabilistic Algorithms for Verification of Polynomial Identities, Journal of the ACM (JACM), v.27 n.4, p.701-717, Oct. 1980 [doi>10.1145/322217.322225]
	55	SZEMEP, EDI, E. 1978. Regular partitions of graphs. In Proceedings of the Colloquim International CNRS. pp. 399-401.
	56	Luca Trevisan, Recycling queries in PCPs and in linearity tests (extended abstract), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.299-308, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276769]
	57	L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]
	58	VAPNIK, g. N., AND CHERVOENKIS, A.Y. 1971. On the uniform convergence of relative frequencies of events to their probabilities. Theory Prob. Applic. 17, 2, 264-280.
	59	Kenji Yamanishi, Probably Almost Discriminative Learning, Machine Learning, v.18 n.1, p.23-50, Jan. 1995 [doi>10.1023/A:1022870506888]
	60	YAO, A. C.C. 1987. Lower bounds to randomized algorithms for graph properties. In Proceedings of the 28th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, pp. 393-400.
	61	ZEITOUNI, 0., AND KULKARM, S.R. 1995. A general classification rule for probability measures. Ann. Stat. 23, 1393-1407.