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(frac{log(epsilon n)}{epsilon})$ in the usual uniform model, and prove an $O(frac{log n}{epsilon})$ upper bound in the distribution-free setting. 2. We show a tight lower bound of $Omega(frac{log(epsilon n)}{epsilon})$ queries for testing convexity of functions $f: [n] rightarrow mathbb{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] times [n]$. We construct an emph{adaptive} tester for convexity of functions $fcolon [3] times [n] to mathbb R$ with query complexity $O(log^2 n)$. We also show that any emph{non-adaptive} tester must use $Omega(sqrt{n})$ queries in this setting. Thus, adaptivity yields an exponential improvement for this problem. 4. For functions $fcolon [n]^d to mathbb R$ over domains of dimension $d geq 2$, we show a non-adaptive query lower bound $Omega((frac{n}{d})^{frac{d}{2}})$.
Download