REVIEW 2 major objections 4 minor 21 references
Testing convexity of functions over finite domains
T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read The paper proves a matching $\Omega(\log(\epsilon n)/\epsilon)$ lower bound for line convexity testing, shows adaptivity is no help there, and exhibits an exponential adaptive-versus-non-adaptive gap on the stripe $[3]\times[n]$.
desk verdict A valuable line lower bound and high-dimensional lower bound, but the stripe adaptive tester that drives the paper's headline is wrong as written. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The line upper bound rests on the triple-test scheme: a root $a$ is paired with a hub $b$ at a distance that is a power of two, and the algorithm tests convexity on triples $(a,b,c)$ with $c\in\{a+1,b+1\}$; a local lemma shows that any non-convex triple $x<y<z$ produces a failed triple test of height at most $2\max\{y-x,z-y\}$, so the set of points passing all triple tests has a convex replacement. The stripe upper bound revolves around the envelope $h(x)=\min_\delta(\tilde f_0(x-\delta)+\tilde f_2(x+\delta))/2$ on the half-integer line; evaluating $h(x)$ is where adaptivity enters, since the minimizer $\delta^*$ is found by binary search after checking local convexity of the parametrized function, and the tester then verifies $f_1(x)\le h(x)$ together with $h-\beta_-\ge 0$ and $h-\beta_+\ge 0$ on the corresponding intervals, where $\beta_\pm$ are the affine interpolants of $f_1$ at $x-1,x$ or $x,x+1$. The lower bounds use a canonical convex function $g_B(x)=(x^B_1)^2+2\sum_{i=2}^d (x^B_i)^2$ expressed in a random lattice basis $B$, with random $\pm1$ perturbations chosen either constant along each lattice line to preserve convexity or alternating to create many disjoint violations; an algorithm that never queries two points on the same line in the hidden direction cannot distinguish the two distributions.
What would settle it
Construct a function on $[3]\times[n]$ whose only violation of convexity is a minimal centred simplex with vertices $(0,a),(1,b),(2,c)$ centred at $(1,x)$ with $(a+c)/2=x+\tfrac12$ (or $x-\tfrac12$), arrange every other triple and envelope inequality so that all steps of the stripe tester pass, and run it; acceptance would show the restricted function on the passing set is not convex and would refute the upper-bound claim.
Extended reading notes
Core claim
At the paper's center is a pair of matching bounds for one-dimensional convexity testing plus a first exponential adaptive/non-adaptive separation in convexity testing. For $f:[n]\to\mathbb{R}$ the paper designs a non-adaptive one-sided 'triple tester' that samples a root $a$ and a power-of-two-scaled hub $b$, checks the triple $(a,b,c)$ for $c=a+1$ or $c=b+1$, and repeats; it proves $O(\log(\epsilon n)/\epsilon)$ query complexity in the uniform model and $O(\log n/\epsilon)$ in the distribution-free model. It then proves that any $\epsilon$-tester, adaptive or not, needs $\Omega(\log(\epsilon n)/\epsilon)$ queries when $1/n\le\epsilon\le 1/9$, using scale-structured hard distributions whose violations are visible only at a particular ternary scale. On the stripe $[3]\times[n]$, the paper constructs an adaptive distribution-free tester that evaluates the convex envelope $h(x)=\min_\delta (\tilde f_0(x-\delta)+\tilde f_2(x+\delta))/2$ by binary search, checks $f_1(x)\le h(x)$, and checks $h$ against the affine interpolants of $f_1$ on two intervals, giving $O(\log^2 n/\epsilon)$ queries and $O(1/\epsilon)$ samples, while an $\Omega(\sqrt{n})$ lower bound is proved against all non-adaptive testers. Finally, the non-adaptive lower bound $\Omega((n/d)^{d/2})$ for $[n]^d$ is proved by hiding a slowly-increasing direction in a random lattice basis and perturbing values along it.
Load-bearing premise
The load-bearing premise is that verifying $h-\beta_-\ge 0$ on $x+1,x+\tfrac32,\dots,n-1$ and $h-\beta_+\ge 0$ on $0,\tfrac12,\dots,x-1$ certifies convexity on every minimal centred simplex centred at $(1,x)$, a premise that can fail when the simplex midpoint is $x\pm\tfrac12$.
Editorial extensions
If this is right
- The one-dimensional query complexity of $\epsilon$-testing convexity is $\Theta(\log(\epsilon n)/\epsilon)$ for both adaptive and non-adaptive algorithms when $1/n\le\epsilon\le 1/9$.
- Adaptivity is exponentially more powerful than non-adaptivity on the stripe $[3]\times[n]$: $O(\log^2 n/\epsilon)$ queries suffice adaptively while $\Omega(\sqrt{n})$ are necessary non-adaptively.
- Any non-adaptive tester for functions on $[n]^2$ needs $\Omega(n)$ queries for constant $\epsilon$, matching the previously known $O(n)$ upper bound.
- Quantum amplitude amplification applied to the line triple testers gives quadratic improvements: $O(\sqrt{\epsilon^{-1}\log(\epsilon n)})$ queries in the standard model and $O(\sqrt{\epsilon^{-1}\log n})$ in the distribution-free model.
- The hypergrid lower bound $\Omega((n/d)^{d/2})$ for non-adaptive testers implies a general $\Omega(d\log n)$ lower bound for adaptive convexity testers on $[n]^d$.
Reading between the lines
- Editorial inference: The stripe separation suggests that any polylogarithmic tester for $[n]^2$, if one exists, must be adaptive; a natural next step is to replace the half-integer envelope $h(x)$ with a recursive envelope over blocks, since the non-adaptive $\Omega(n)$ bound already rules out the obvious sampling approaches.
- Editorial inference: The random-lattice hidden-direction construction is a general template that could yield lower bounds for testing other lattice-invariant geometric properties, such as discrete midpoint-convexity or $L^\natural$-convexity, on grids of dimension at least two.
- Editorial inference: Because the line tester is a triple tester, its sampling distribution defines a natural importance-sampling estimator of distance to convexity; counting failed rooted triple tests may give a direct distance-approximation algorithm at the same $\Theta(\log(\epsilon n)/\epsilon)$ rate, a strengthening the paper only hints at via a cited distance-approximation result.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the query complexity of property testing convexity of functions on finite domains: the line [n], the stripe [3]×[n], and the hypergrid [n]^d. The main claimed results are: (1) a simplified non-adaptive 1D tester with O(log(εn)/ε) queries in the uniform model and O(log n/ε) in the distribution-free model; (2) a matching Ω(log(εn)/ε) lower bound for both adaptive and non-adaptive testers on the line; (3) an adaptive tester for the stripe with O(log^2 n/ε) queries together with an Ω(√n) lower bound for non-adaptive testers, giving an exponential separation; and (4) a non-adaptive lower bound of Ω((n/d)^{d/2}) for [n]^d. The proofs combine triple testers on the line, convex replacements, characterizations via minimal centred simplices, and Yao-style lower bound constructions based on lattice bases.
Significance. If correct, the 1D results would close the adaptivity question for convexity testing on the line and are a useful contribution: the triple-tester reformulation is clean, and the lower-bound machinery is applied carefully. The claimed exponential separation for the stripe would be a striking result, and the high-dimensional lower bound would significantly strengthen earlier work. Unfortunately, the stripe upper bound is false as stated: the algorithm misses violations whose simplex midpoint is the half-integer x+1/2, and a concrete function can be constructed that passes every test while being Ω(1)-far from convex. There are also numerical inconsistencies in the high-dimensional lower-bound proof. These issues affect two of the paper's four headline claims, so the paper cannot be accepted in its current form.
major comments (2)
- [Section 4.3, Algorithm 4 Steps 7 and 9] The proof of Theorem 1.5 requires that the set S of points that pass Algorithm 4 be convex. For a minimal centred simplex (0,a),(1,b),(2,c) with b<x<y=(a+c)/2, the proof asserts that Step 7 certifies convexity of g:{x−1,x,y} defined by g(y)=h(y). Step 7, however, minimizes h−β− only over {x+1,x+3/2,...,n−1}; the value y=x+1/2, which arises whenever a+c=2x+1, is not checked, and Step 9 has the symmetric omission of x−1/2. This is not merely a proof gap. Consider f on [3]×[7] with columns f0=(200,100,0,−100,200,500,800), f1=(100,0,−100,−50,0,100,200), and f2=(300,200,100,0,−100,200,500). Each column is convex. The minimal simplex (0,3),(1,2),(2,4) is centred at (1,3), and f(1,3)=−50 > (f(0,3)+f(1,2)+f(2,4))/3 = −100, so f is not convex; under the uniform distribution D on these four points, f is 1/4-far from convex. For root (1,3), the proof needs h(3.5)≥β−_3(3.5), where β−_3 is affine through (2,−100) and (3,−50); in fact h(3.5)=−100 and β−_3(3.5)=−25, so the required inequality fails at the omitted point. All points actually checked by Algorithm 4 for the sampled roots (1,2) and (1,3) satisfy the corresponding inequalities: for root (1,2), h(3.5)=−100≥β−_2(3.5)=−250, and for root (1,3), h(t)≥β−(t) for t∈{4,4.5,5,6}; the column tests and Step 4 also pass. Hence the algorithm accepts with probability 1 on D while the function is Ω(1)-far, invalidating Theorem 1.5's adaptive upper bound.
- [Section 5.5 and Claim 5.7] The proof of Theorem 1.6 states that Claim 5.7 shows the support of D_N is 1/10-far from convex, but Claim 5.7 proves only 1/20-far. Moreover, the displayed inequality in Claim 5.7, |L|/7 = 1/7(1−1/d)^d n^d ≥ n^d/20, is false for small d: for d=2 it reads n^2/28 ≥ n^2/20. Consequently, the proof as written does not establish the lower bound for ε as large as 1/10; it supports only a smaller constant (about 1/28 in dimension 2 under the stated construction).
minor comments (4)
- [Abstract and Theorem 1.5] The abstract states that the stripe tester has query complexity O(log^2 n), while Theorem 1.5 states O(log^2 n/ε); these differ when ε is not constant, and the statements should be harmonized.
- [Section 4.3, Algorithm 4 Steps 7 and 9] The half-integer interval notation such as {x+1, x+3/2, x+2, ..., n−1} is not formally defined; please specify the step size and the treatment of endpoints, especially when n−1 is not on the half-integer lattice.
- [Section 4.2, Algorithm 3] Algorithm 3 (Evaluate) is described for integer arguments, but Steps 7 and 9 of Algorithm 4 require evaluating h at half-integer points; the manuscript should clarify how δ* and the 1DTest calls are defined in that case.
- [Section 5.4, Claim 5.7] The assertion that the number of disjoint non-convexity witnesses in each L_s is at least |L_s|/7 is stated without derivation; a short explanation of the packing argument would help the reader verify the constant.
Circularity Check
No significant circularity: the derivation chain is self-contained; the self-citation to prior work provides an external combinatorial lemma rather than an assumed conclusion.
full rationale
The paper's results are derived from stated definitions and standard mathematical tools, not from circular reductions. The one-dimensional tester is proven via Lemma 3.2, which derives from Corollary 2.4 and the definition of triple tests; there is no fitted parameter or pre-supposed convexity conclusion. The line lower bound uses [1, Lemma 6] only as a combinatorial bound on conflicting prefix pairs in a decision-tree mapping; that lemma is a parameter-free statement from earlier independent published work and does not encode the convexity lower bound itself. The stripe upper bound is an algorithmic construction whose proof attempts to certify convexity conditions, and any alleged omission of half-integer points is a correctness concern, not a circularity. The high-dimensional lower bound constructs explicit distributions DY and DN and proves convexity/far-from-convexity directly. No prediction is equivalent to its inputs by construction, no uniqueness theorem is imported from the authors' prior work as a substitute for a proof, and no known result is merely renamed. The only self-citation appears as a technical lemma, which is real evidence and does not raise the circularity score.
Assumptions & free parameters
assumptions (5)
- standard math Convex functions on finite subsets of R^d extend to convex functions on R^d (Lemma 2.2).
- standard math Yao's minimax principle.
- standard math Hoeffding's inequality for negatively correlated random variables.
- standard math Theorem 332 in Hardy and Wright: random pairs are coprime with probability > 0.5.
- domain assumption Lemma 6 of Belovs [1] on decision tree adversaries for monotonicity.
Cite this review
Pith. "Pith review of Testing convexity of functions over finite domains." pith.science (2026). https://pith.science/paper/MYOXQNBZ
@misc{pith2026190802525,
author = {Pith},
title = {Pith review of: Testing convexity of functions over finite domains},
year = {2026},
howpublished = {\url{https://pith.science/paper/MYOXQNBZ}},
note = {Machine review of arXiv:1908.02525}
}
abstract
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}})$.
Figures
Reference graph
Works this paper leans on
-
[3]
Piotr Berman, Sofya Raskhodnikova, and Grigory Yarosla vtsev. lp testing. In STOC, pages 164–173, 2014. 2
work page 2014
- [7]
-
[1]
Adaptive lower bound for testing mon otonicity on the line
Aleksandrs Belovs. Adaptive lower bound for testing mon otonicity on the line. In Approx- imation, Randomization, and Combinatorial Optimization. A lgorithms and Techniques, AP- PROX/RANDOM 2018, pages 31:1–31:10, 2018. 6, 16, 19
work page 2018
-
[2]
Testing local properties of arrays
Omri Ben-Eliezer. Testing local properties of arrays. I n 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA , pages 11:1–11:20, 2019. 2, 3, 4
work page 2019
-
[4]
Lower bounds for testing proper- ties of functions over hypergrid domains
Eric Blais, Sofya Raskhodnikova, and Grigory Yaroslavt sev. Lower bounds for testing proper- ties of functions over hypergrid domains. In Proceedings of the 29th Conference on Computa- tional Complexity (CCC) , pages 309–320, 2014. 2, 3, 4, 22
work page 2014
-
[5]
Quantum amplitude amplifi- cation and estimation
Gilles Brassard, Peter Høyer, Michele Mosca, and Alain T app. Quantum amplitude amplifi- cation and estimation. In Quantum Computation and Quantum Information: A Millennium Volume, volume 305 of AMS Contemporary Mathematics Series , pages 53–74, 2002. 2
work page 2002
- [6]
-
[8]
Funda Erg¨ un, Sampath Kannan, Ravi Kumar, Ronitt Rubinf eld, and Mahesh Viswanathan. Spot-checkers. J. Comput. Syst. Sci. , 60(3):717–751, 2000. 2 21
work page 2000
Show all 21 references
-
[9]
Approximating the distance t o convexity
Shahar Fattal and Dana Ron. Approximating the distance t o convexity. 2010. 3
2010
-
[10]
On the strength of comparisons in proper ty testing
Eldar Fischer. On the strength of comparisons in proper ty testing. Inf. Comput. , 189(1):107– 116, 2004. 3
2004
-
[11]
Propert y testing and its connection to learning and approximation
Oded Goldreich, Shafi Goldwasser, and Dana Ron. Propert y testing and its connection to learning and approximation. J. ACM , 45(4):653–750, 1998. 2
1998
-
[12]
Distribution-fr ee property-testing
Shirley Halevy and Eyal Kushilevitz. Distribution-fr ee property-testing. SIAM J. Comput. , 37(4):1107–1138, 2007. 2
2007
-
[13]
An introduction to the theory of numbers
Godfrey Harold Hardy and Edward Maitland Wright. An introduction to the theory of numbers . Oxford University Press, 1979. 12
1979
-
[14]
A survey of quantum property testing
Ashley Montanaro and Ronald de Wolf. A survey of quantum property testing. Theory of Computing, Graduate Surveys , 7:1–81, 2016. 2
2016
-
[15]
Discrete convex analysis
Kazuo Murota. Discrete convex analysis. Math. Program., 83:313–371, 1998. 23
1998
-
[16]
Parameterized prop- erty testing of functions
Ramesh Krishnan S Pallavoor, Sofya Raskhodnikova, and Nithin Varma. Parameterized prop- erty testing of functions. ACM Transactions on Computation Theory (TOCT) , 9(4):17, 2018. 2
2018
-
[17]
Parnas, D
M. Parnas, D. Ron, and R. Rubinfeld. On testing convexit y and submodularity. SIAM Journal on Computing , 32(5):1158–1184, 2003. 2, 3, 4
2003
-
[18]
Integer optimization and lattices
Thomas Rothvoss. Integer optimization and lattices. 2 015. 12
-
[19]
Robust characteriza tions of polynomials with applications to program testing
Ronitt Rubinfeld and Madhu Sudan. Robust characteriza tions of polynomials with applications to program testing. SIAM J. Comput. , 25(2):252–271, 1996. 2
1996
-
[20]
Seshadhri and Jan Vondr´ ak
C. Seshadhri and Jan Vondr´ ak. Is submodularity testab le? Algorithmica, 69(1):1–25, 2014. 5
2014
-
[21]
Extension of convex function
Min Yan. Extension of convex function. arXiv preprint arXiv:1207.0944 , 2012. 24 A On convexity and line convexity In the introduction, we mentioned that the notion of linear convexity studied in [ 4] is not equivalent to the notion of convexity we study in this current work. ...
2012 arXiv
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.