{"id":"bca18505-04e7-4576-8837-6e8736858e05","arxiv_id":"1908.02525","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"Testing convexity on the line is tightly Θ(log(εn)/ε), with no adaptivity advantage, but the paper's adaptive stripe tester has a flaw that breaks the exponential separation as stated.","lead":"This paper proves new query complexity bounds for testing convexity of discrete functions, including a tight bound on the line and an exponential adaptive advantage on a 3-by-n stripe. The stripe tester as written is incorrect, accepting a concrete non-convex function, so the paper needs significant revision.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Stripe tester's Steps 7 and 9 omit the half-integer midpoints x±1/2, so Theorem 1.5's adaptive upper bound is false as stated.","rationale":"The paper's headline contribution is the exponential separation in Theorem 1.5: an adaptive O(log^2 n/ε) tester for the stripe versus an Ω(√n) non-adaptive lower bound. The reader's verdict identifies the weakest point as the assertion, in the proof of Theorem 1.5 in Section 4.3, that Steps 7 and 9 of Algorithm 4 certify convexity on all minimal centred simplices. My independent reading confirms this is exactly where the proof breaks. The checked intervals begin at x+1 and x−1 respectively, so the half-integer midpoints x±1/2 are skipped. Since a and c are integers, those midpoints are precisely the ones produced by minimal simplices with a+c odd; the proof's bridge from the checked inequalities to convexity of g:{x−1,x,y} fails at that point. The provided counterexample on [3]×[3] is concrete and decisive: the violated simplex ((0,1),(1,0),(2,2)) centred at (1,1) has y=3/2, and h(3/2)=−1 while β−(3/2)=0, yet the intervals checked by Algorithm 4 contain {2} and {0}, so no branch detects the violation. This is not a constant-factor or edge-case quibble; it invalidates the claimed upper bound and with it the exponential gap. Secondary issues, such as the distance bound in Claim 5.7 (the construction gives 1/28 rather than 1/20 for d=2, undermining the ε≤1/10 range in Theorem 1.6), reinforce that the paper needs substantial revision, but the stripe counterexample alone justifies rejection. The line results (Theorems 1.1–1.3) appear sound and are not the subject of this objection.","tokens_in":21696,"tokens_out":5806,"duration_ms":59076,"concrete_test":"Fix n=3, let D be uniform over [3]×[3], and implement Algorithm 4 exactly as written, including the interval endpoints in Steps 7 and 9. Run it exhaustively on the function f0=(0,−4,0), f1=(0,0,0), f2=(10,6,2), enumerating every sample point (i,x) and every branch of the minimization and 1DTest subroutines. Check whether any run outputs 'not convex'. Separately compute h(3/2)=min_δ(f0(3/2−δ)+f2(3/2+δ))/2 and β−(3/2) from the affine function through f1(0)=0 and f1(1)=0; verify that h(3/2)<β−(3/2), so the simplex ((0,1),(1,0),(2,2)) centred at (1,1) is a convexity violation. If Algorithm 4 accepts the function at every sample point while this violation exists, Theorem 1.5's upper bound is refuted.","verdict_should_be":"REJECT","load_bearing_attack":"The central claim requiring scrutiny is the adaptive stripe tester in Theorem 1.5. Its correctness proof in Section 4.3 asserts that if f is ε-far from convex, then the set S of points passing Algorithm 4 is convex, giving an ε/constant rejection probability. The load-bearing step is the claim that Step 7 certifies convexity of g:{x−1,x,y} for every minimal centred simplex (0,a),(1,b),(2,c) centred at (1,x) with b<x<y, where y=(a+c)/2. However, Step 7 minimizes h−β− over the interval {x+1, x+3/2, x+2, ..., n−1}, which excludes the half-integer point y=x+1/2. This omission is not harmless: y=x+1/2 occurs whenever a+c=2x+1, so the midpoint of the outer vertices lies exactly on the skipped point. Step 9 has the symmetric omission for y=x−1/2. The proof then uses the (uncertified) convexity of g to infer convexity of g′ on {b,x−1,x,y} and finally convexity of the simplex. Without the missing half-integer, that chain breaks. A concrete counterexample on [3]×[3] confirms the problem: f0=(0,−4,0), f1=(0,0,0), f2=(10,6,2). The minimal simplex with vertices (0,1),(1,0),(2,2) centred at (1,1) has midpoint y=3/2, and computing h(3/2)=−1 while β−(3/2)=0 shows a convexity violation that Algorithm 4's checked intervals {2} and {0} do not detect. Every branch of the algorithm passes this function, yet it is positive distance from convex. Thus the exponential separation claimed in Theorem 1.5 is unsupported and false as stated.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":21921,"tokens_out":59621,"duration_ms":550420,"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":[{"comment":"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":"Section 4.3, Algorithm 4 Steps 7 and 9"},{"comment":"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).","section":"Section 5.5 and Claim 5.7"}],"minor_comments":[{"comment":"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":"Abstract and Theorem 1.5"},{"comment":"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":"Section 4.3, Algorithm 4 Steps 7 and 9"},{"comment":"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":"Section 4.2, Algorithm 3"},{"comment":"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.","section":"Section 5.4, Claim 5.7"}],"recommendation":"reject","confidential_remarks":"The reader's stress-test concern about the stripe tester is real, although the specific [3]×[3] example in that note is complicated by boundary undefinedness. I verified a clean counterexample on [3]×[7] that avoids boundary issues: the algorithm accepts with probability 1 on a distribution over the four points of a violated simplex, while the function is 1/4-far from convex. This is a load-bearing failure of Theorem 1.5. The separate 1/20-versus-1/10 inconsistency in Theorem 1.6's proof is also worth fixing in any future revision. The 1D results appear sound and may be publishable separately."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThe short version: the paper's most eye-catching claim—an exponential adaptivity gap on the stripe [3]×[n]—is false as written. The line lower bound and the high-dimensional non-adaptive lower bound look real and valuable.\n\nWhat is actually good: Theorem 1.3 closes the adaptive gap for convexity testing on the line, matching the known O(log(εn)/ε) upper bound. The simplified triple tester and its distribution-free version are clean. The Ω((n/d)^{d/2}) non-adaptive lower bound for hypergrids is a genuine advance, even with the constant issues I mention below. The paper also uses standard tools properly and does not appear circular.\n\nThe soft spot is not soft. In Algorithm 4, Steps 7 and 9 verify non-negativity of h−β− on intervals that omit the half-integer points x±1/2. But those are exactly the midpoints y=(a+c)/2 of minimal simplices (0,a),(1,b),(2,c) with a+c odd, and the proof of Theorem 1.5 relies on certifying convexity of g:{x−1,x,y}. The counterexample on [3]×[3] with f0=(0,−4,0), f1=(0,0,0), f2=(10,6,2) works: the simplex (0,1),(1,0),(2,2) centred at (1,1) violates convexity, h(1.5)=−1, and every branch of Algorithm 4 passes. So the upper bound in Theorem 1.5 is false, and the claimed exponential separation is unsupported.\n\nThere are also two smaller issues. Claim 5.7 asserts distance 1/20, but the proof's inequality gives only 1/28 for d=2, so the ε≤1/10 range in Theorem 1.6 is not supported—fixable by adjusting constants. Claim 5.8's counting of exposed bases also looks loose; I suspect the bound goes through with a more careful argument, but as written it is not quite right.\n\nBottom line: this deserves a serious referee, but not acceptance. The line lower bound is a solid result on its own; the high-dimensional lower bound is promising. I would send it to peer review with the expectation of major revision, asking the authors to correct or remove the stripe upper bound and tighten the constants. I would not cite it in its current form.","headline":"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.","tokens_in":22613,"tokens_out":9366,"would_cite":false,"duration_ms":85385,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68Q25"],"pacs":[],"model":"deepseek-v4-flash","headline":"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]$.","keywords":["convexity testing","property testing","query complexity","adaptive vs non-adaptive","distribution-free testing","triple tester","hypergrid","discrete convexity"],"falsifier":"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.","tokens_in":21335,"feed_emoji":"📐","tokens_out":16933,"duration_ms":150831,"temperature":0.7,"pith_summary":"This paper determines, up to constant factors, how many value queries are needed to tell whether a function on a finite grid is convex or far from convex. On the line $[n]$, it gives a simplified non-adaptive tester that uses $O(\\log(\\epsilon n)/\\epsilon)$ queries in the standard model and $O(\\log n/\\epsilon)$ queries in the distribution-free model, and it proves a matching $\\Omega(\\log(\\epsilon n)/\\epsilon)$ lower bound that applies to adaptive algorithms as well; adaptivity therefore buys nothing in one dimension. On the stripe $[3]\\times[n]$, the situation reverses: an adaptive tester with $O(\\log^2 n/\\epsilon)$ queries exists, while every non-adaptive tester requires $\\Omega(\\sqrt{n})$ queries, an exponential separation. For hypergrids $[n]^d$ with $d\\ge 2$, the paper shows any non-adaptive tester needs $\\Omega((n/d)^{d/2})$ queries. Taken together, these results settle the line case and identify adaptivity as the source of an exponential query-complexity gap on the stripe.","feed_headline":"Line convexity testing is tight; adaptivity is no help","feed_subtitle":"Matching Ω(log(εn)/ε) lower bound closes 1D; on a stripe, adaptive beats non-adaptive exponentially.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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$."],"supporting_citations":[{"why":"Introduced the line convexity testing problem and the first O(log n/epsilon) tester that the new algorithm improves and re-proves.","marker":"[17]"},{"why":"Gave the prior O(log(epsilon n)/epsilon) line bound and the O(n) array-testing upper bound that the new results simplify or tighten.","marker":"[2]"},{"why":"Provided the previous non-adaptive lower bounds for line and hypergrid convexity testing that the new lower bounds strengthen.","marker":"[4]"},{"why":"Contributed the scale-based adaptive lower-bound technique for monotonicity on the line that the 1D convexity lower bound adapts.","marker":"[1]"},{"why":"Defined the distribution-free testing model used by the line and stripe upper bounds.","marker":"[12]"},{"why":"Supplied the bound on the fraction of coprime pairs used to count hidden lattice directions in the lower-bound construction.","marker":"[13]"},{"why":"Provided the extension result used in Lemma 2.2 to pass from convexity on a finite set to a convex function on all of R^d.","marker":"[21]"}],"fun_headline_variants":["Tight convexity testing on the line; adaptivity zero gain","Stripe convexity: adaptive beats non-adaptive exponentially","Matching bounds for 1D convexity; exponential gap in 2D","Convexity testing: sharp line bound, adaptive leap on stripes","1D convexity tested tightly; stripe adaptivity gives exponential win"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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$.","fun_headline_variants_meta":{"raw":{"variants":["Tight convexity testing on the line; adaptivity zero gain","Stripe convexity: adaptive beats non-adaptive exponentially","Matching bounds for 1D convexity; exponential gap in 2D","Convexity testing: sharp line bound, adaptive leap on stripes","1D convexity tested tightly; stripe adaptivity gives exponential win"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000217,"raw_usage":{"total_tokens":1570,"prompt_tokens":1211,"completion_tokens":359,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":827,"completion_tokens_details":{"reasoning_tokens":267}},"tokens_in":827,"tokens_out":359,"duration_ms":3919,"temperature":1.0,"reasoning_tokens":267,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:47:52.079423+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Parnas, D","cited_arxiv_id":null,"evidence_quote":"Introduced the line convexity testing problem and the first O(log n/epsilon) tester that the new algorithm improves and re-proves."},{"cited_title":"Testing local properties of arrays","cited_arxiv_id":null,"evidence_quote":"Gave the prior O(log(epsilon n)/epsilon) line bound and the O(n) array-testing upper bound that the new results simplify or tighten."},{"cited_title":"Lower bounds for testing proper- ties of functions over hypergrid domains","cited_arxiv_id":null,"evidence_quote":"Provided the previous non-adaptive lower bounds for line and hypergrid convexity testing that the new lower bounds strengthen."},{"cited_title":"Adaptive lower bound for testing mon otonicity on the line","cited_arxiv_id":null,"evidence_quote":"Contributed the scale-based adaptive lower-bound technique for monotonicity on the line that the 1D convexity lower bound adapts."},{"cited_title":"Distribution-fr ee property-testing","cited_arxiv_id":null,"evidence_quote":"Defined the distribution-free testing model used by the line and stripe upper bounds."},{"cited_title":"An introduction to the theory of numbers","cited_arxiv_id":null,"evidence_quote":"Supplied the bound on the fraction of coprime pairs used to count hidden lattice directions in the lower-bound construction."},{"cited_title":"Extension of Convex Function","cited_arxiv_id":"1207.0944","evidence_quote":"Provided the extension result used in Lemma 2.2 to pass from convexity on a finite set to a convex function on all of R^d."}],"review_version":1}