UNATENESS TESTING

Author:

Baleshzar, Roksana

Graduate Program:

Computer Science and Engineering

Degree:

Master of Science

Document Type:

Master Thesis

Date of Defense:

November 17, 2017

Committee Members:

Sofya Raskhodnikova, Thesis Advisor/Co-Advisor
Paul Medvedev, Committee Member

Keywords:

Sublinear-time algorithm
property testing
unateness
monotonicity

Abstract:

We study the problem of testing unateness of functions f:[n]^d -> R. A function f is unate if for every coordinate i in [d], the function is either nonincreasing in the i-th coordinate or nondecreasing in the i-th coordinate. A unateness tester is a randomized algorithm which, given parameter epsilon in (0,1) and oracle access to the input function f, accepts f with probability at least 2/3 if it is unate, and rejects f with probability at least 2/3 if it is epsilon-far from being unate. A unateness tester is adaptive if its queries depend on the answers to its previous queries. Otherwise, it is nonadaptive. We solve the unateness testing problem completely for functions f:[n]^d -> R by giving an optimal O(d (log d + log n)) query nonadaptive tester and a O(d log n) query adaptive tester. We also prove that adaptivity helps for testing unateness of real-valued functions, whereas it does not help for a large class of similar properties including monotonicity.