We initiate a systematic study of a special type of property testers. These testers consist of repeating a basic test ?for a number of times that depends on the proximity parameters, whereas the basic test is oblivious of the proximity parameter. We refer to such basic tests by the term proximity-oblivious testers.

While proximity-oblivious testers were studied before - most notably in the algebraic setting - the current study seems to be the first one to focus on graph properties. We provide a mix of positive and negative results,and in particular characterizations of the graph properties that have constant-query proximity-oblivious testers in the two standard models (i.e., the adjacency matrix and the bounded-degree models). Furthermore, we show that constant-query proximity-oblivious testers do not exist for many easily testable properties, and that even when proximity-oblivious testers exist repeating themdoes not necessarily yield the best standard testers for the corresponding property.

Biography

Oded Goldreich was born on February 4th, 1957 in Israel. He received B.A., M.Sc., and D.Sc. degrees in Computer Science at the Technion -- Israel Institute of Technology in 1980, 1982 and 1983, respectively. He was a post-doctoral fellow at MIT's Laboratory for Computer Science (1983--86). Since 1995, he is on the faculty of the Department of Mathematics and Computer Science of the Weizmann Institute of Science (Israel), where he is the incumbent of the Meyer W. Weisgal Professorial Chair.

Oded Goldreich is the author of the books "Modern Cryptography, Probabilistic Proofs and Pseudorandomness" (Springer 1999),"Foundations of Cryptography: Volumes 1 and 2"(Cambridge University Press, 2001 and 2004), and "Computational Complexity: A Conceptual Perspective"(Cambridge University Press, 2008).

He is editor of "Journal of Cryptology", "Computational Complexity" and "SIAM Journal on Computing", and was an invited speaker at various conferences including the "International Congress of Mathematicians (ICM) 1994" and the "Crypto97" conference. He is a Corresponding Fellow of the Bavarian Academy of Sciences and Humanities.

Back