UNATENESS TESTING

Open Access
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
  • 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.