TY - GEN
T1 - Optimal unateness testers for real-valued functions
T2 - 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017
AU - Baleshzar, Roksana
AU - Chakrabarty, Deeparnab
AU - Pallavoor, Ramesh Krishnan S.
AU - Raskhodnikova, Sofya
AU - Seshadhri, C.
N1 - Publisher Copyright:
© Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and C. Seshadhri;.
PY - 2017/7/1
Y1 - 2017/7/1
N2 - We study the problem of testing unateness of functions f: {0, 1}d → ℝ. We give an O(d/ϵ · log O(d/ϵ)- query nonadaptive tester and an O(O(d/ϵ)-query adaptive tester and show that both testers are optimal for a fixed distance parameter ϵ. Previously known unateness testers worked only for Boolean functions, and their query complexity had worse dependence on the dimension both for the adaptive and the nonadaptive case. Moreover, no lower bounds for testing unateness were known. We generalize our results to obtain optimal unateness testers for functions f: [n]d → ℝ. Our results establish that adaptivity helps with testing unateness of real-valued functions on domains of the form {0, 1}d and, more generally, [n]d. This stands in contrast to the situation for monotonicity testing where there is no adaptivity gap for functions f: [n]d → ℝ.
AB - We study the problem of testing unateness of functions f: {0, 1}d → ℝ. We give an O(d/ϵ · log O(d/ϵ)- query nonadaptive tester and an O(O(d/ϵ)-query adaptive tester and show that both testers are optimal for a fixed distance parameter ϵ. Previously known unateness testers worked only for Boolean functions, and their query complexity had worse dependence on the dimension both for the adaptive and the nonadaptive case. Moreover, no lower bounds for testing unateness were known. We generalize our results to obtain optimal unateness testers for functions f: [n]d → ℝ. Our results establish that adaptivity helps with testing unateness of real-valued functions on domains of the form {0, 1}d and, more generally, [n]d. This stands in contrast to the situation for monotonicity testing where there is no adaptivity gap for functions f: [n]d → ℝ.
UR - http://www.scopus.com/inward/record.url?scp=85027271164&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85027271164&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ICALP.2017.5
DO - 10.4230/LIPIcs.ICALP.2017.5
M3 - Conference contribution
AN - SCOPUS:85027271164
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017
A2 - Muscholl, Anca
A2 - Indyk, Piotr
A2 - Kuhn, Fabian
A2 - Chatzigiannakis, Ioannis
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Y2 - 10 July 2017 through 14 July 2017
ER -