  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
$f\colon [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 $f\colon [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}})$.
