Testing convexity of functions over finite domains

08/07/2019
by   Aleksandrs Belovs, et al.
0

We establish new upper and lower bounds on the number of queries required to test convexity of functions over various discrete domains. 1. We provide a simplified version of the non-adaptive convexity tester on the line. We re-prove the upper bound O(log(ϵ n)/ϵ) in the usual uniform model, and prove an O(log n/ϵ) upper bound in the distribution-free setting. 2. We show a tight lower bound of Ω(log(ϵ n)/ϵ) queries for testing convexity of functions f: [n] →R on the line. This lower bound applies to both adaptive and non-adaptive algorithms, and matches the upper bound from item 1, showing that adaptivity does not help in this setting. 3. Moving to higher dimensions, we consider the case of a stripe [3] × [n]. We construct an adaptive tester for convexity of functions f [3] × [n] →R with query complexity O(log^2 n). We also show that any non-adaptive tester must use Ω(√(n)) queries in this setting. Thus, adaptivity yields an exponential improvement for this problem. 4. For functions f [n]^d →R over domains of dimension d ≥ 2, we show a non-adaptive query lower bound Ω((n/d)^d/2).

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset