{"id":"0fac4cf2-3260-415c-aa58-80682b08f2c4","arxiv_id":"2511.02082","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Convex feasibility under bit or inner-product first-order oracles requires Ω(2^n d² log(R/ρ)) queries—quadratic in the continuous dimension d—matching known upper bounds up to logs for n=0.","lead":"This paper proves that any algorithm solving convex feasibility by querying bits of separating hyperplanes must ask at least d² questions when the problem has d continuous dimensions. The result closes a long-standing gap in the information complexity of convex optimization and is tight up to logarithmic factors in the continuous case.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Missing recursive consistency invariant for out-of-region queries leaves the log(R/ρ) amplification in Thms 3–4 unsupported","rationale":"The reader's weakest assumption identifies exactly the load-bearing gap in the central lower-bound theorems. The paper's base adversary is carefully constructed, and the d^2 terms are supported by the orthant/cube counting arguments. But the claimed Ω(2^n d^2 log(R/ρ)) (Thm 3) and Ω(2^n d^2(1 + log(R/ρ)/log d)) (Thm 4) depend on iterating the base argument inside a shrinking region. Each iteration must handle queries outside the current surviving region without breaking consistency with earlier responses and with all instances in the region. The proof does not supply the required invariant; it gestures at it with 'simply repeat the argument' and 'simply report inner products'. This is a correctness risk, not a disagreement with consensus. The upper bounds (Thm 2) show the log factor is what makes the bounds tight, so losing it would leave only the single-scale d^2 lower bound. The concrete test proposed would settle whether the gap is real: if the invariant can be written down, the theorems stand; if a counterexample exists, the R/ρ dependence is unsupported. The reader's CONDITIONAL verdict is appropriate: the results are likely correct but the presentation is incomplete. My pass does not change that verdict.","tokens_in":10913,"tokens_out":25522,"duration_ms":256310,"concrete_test":"Work out the recursive step for Theorem 3 (or 4) explicitly for K=2 in d=2: after the base stage, fix the surviving orthant O and a subcube Q ⊂ O of side R/3. Specify the adversary's response for every query y ∉ Q, distinguishing (i) y ∈ O, (ii) y outside O but inside the original box, and (iii) y that were queried in the parent stage and answered 0. Then verify by induction that for every closed convex ρ-fat C ⊆ Q there exists a first-order map G_C reproducing the full transcript. If some y and direction v from the parent stage admit no separating normal a with ⟨a,v⟩=0, the recursion fails; if none do, state the general invariant.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The base single-scale lower bounds (d^2/16 for Thm 3, d^2/8 for Thm 4) are plausible: the adversary maintains a fully consistent orthant/cube by only answering 0 in orthants with <d/4 queries (Thm 3) or by constructing split sets (Thm 4). The recursive amplification to log(R/ρ), however, requires the adversary to respond to queries falling outside the currently surviving region while preserving consistency with all earlier answers and with every candidate instance in that region. The paper only asserts this can be done: §2.1 says 'simply repeat the argument (with appropriate translations)', and §2.2 says 'the oracle can simply report inner products with one of the canonical vectors ±e_1,...,±e_d'. No formal invariant is stated or proved. In particular, a query point that was earlier answered 0 (for some direction v) may later fall outside the shrunken cube; any new response must be realizable by a single first-order map along with the earlier 0 answer. It is not obvious that a canonical-vector response always satisfies this—e.g., if v has positive support on all coordinates separating y from the cube, the normal cone at y may contain no vector orthogonal to v. Without this invariant, the adversary cannot guarantee two disjoint instances survive the recursion, so the R/ρ term in the lower bounds is not established.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the information complexity of the feasibility problem for mixed-integer convex sets under two binary first-order oracles: the bit oracle, which returns a bit of a coordinate of a separating hyperplane normal, and the inner-product oracle, which returns the sign of an inner product of a queried direction with the normal. The main results, Theorems 3 and 4, claim lower bounds of Ω(2^n d² log(R/ρ)) for the bit/coordinate oracle and Ω(2^n d²(1 + log(R/ρ)/log d)) for the inner-product oracle on the class I_{n,d,R,ρ}, matching—up to logarithmic factors—the upper bounds previously given in [1]. The proofs are adversarial: in a first phase, an oracle strategy forces a surviving orthant (Theorem 3) or a surviving cube (Theorem 4) that is consistent with all answers; this phase is then iterated to obtain the dependence on R/ρ. Integer variables are handled by a fiber-wise argument. The paper also observes that the lower bounds hold even if the oracle returns a full coordinate of the normal or the full inner product, which strengthens the results.","tokens_in":11251,"tokens_out":24900,"duration_ms":265435,"significance":"If the main theorems are correct, they close a genuine gap in the oracle-complexity literature: for the natural bit-wise and inner-product first-order oracles, the dependence on the number of continuous variables is quadratic, not merely superlinear. This matches the naive bit-approximation strategy for cutting-plane methods and thus resolves the previously open question for constrained convex feasibility. The single-scale adversarial constructions in §2.1 and §2.2 are elegant and appear sound in their core counting arguments. The paper also usefully proves the lower bounds for the stronger full-coordinate and full-inner-product oracles, making the negative result more robust. The upper bounds from [1] show that the new lower bounds are tight up to logarithmic factors, so the overall contribution is significant. However, the recursive amplification step—which is essential for the R/ρ dependence—is not yet written at the level of rigor required for a journal proof.","major_comments":[{"comment":"The recursive amplification to obtain the log(R/ρ) factors is asserted rather than proved. In §2.1 the text says 'one can simply repeat the argument (with appropriate translations)', and in §2.2 it says 'the oracle can simply report inner products with one of the canonical vectors ±e_1,...,±e_d' for queries outside the surviving cube. No formal invariant is stated that would guarantee these out-of-region responses remain consistent with all earlier answers and with every candidate instance in the surviving region. Because the stated lower bounds depend on the log(R/ρ) term, this is a load-bearing gap. The gap appears repairable: for an axis-aligned cube, any outside query can be separated from the cube by some coordinate normal, and since G(C,·) may depend on the query point, one can fix a normal per point. But this lemma and its interaction with the recursive phase need to be written do","section":"§2.1, Theorem 3 and §2.2, Theorem 4"},{"comment":"The split-set construction for the inner-product oracle assumes that each batch of queries can be assigned a fresh normal a_j. The proof does not address what happens when the algorithm re-queries a point that already has a fixed normal from an earlier batch. In that case the oracle must answer the new query using the previously fixed normal, not the current batch's a_j. For example, if a point queried in the first batch is later queried again with a new direction, the answer is v^T a_1, which need not be the 'report 0' answer required by the second-batch construction. The proof's statement 'For any subsequent queries, if they are made outside P_1 ∩ [−R,R]^d, the oracle simply reports inner products with a_1 or −a_1' handles some repeats, but the general invariant for points that move between the 'inside' and 'outside' categories is not established. A per-point invariant is needed to mak","section":"§2.2, Theorem 4"}],"minor_comments":[{"comment":"The proof uses quantities such as d/4 and d²/16 without ceilings or integrality assumptions. For d < 4, the threshold 'd/4 − 1' is negative and the adversarial strategy is undefined, even though the theorem states d ≥ 1. Use ceiling conventions and treat the finitely many small d separately, or restrict the theorem to d ≥ 4 with a separate small-d argument.","section":"§2.1, Theorem 3"},{"comment":"The sentence 'we have C_1 ∩ C_2 ∩ (Z^n × R^d), i.e., C_1 and C_2 have no common mixed-integer point' is missing the equality symbol; it should be 'C_1 ∩ C_2 ∩ (Z^n × R^d) = ∅'. Also, the text uses log_3(R/(2ρ)) in one place and log_2(R/(2ρ)) in the next; the bases should be consistent.","section":"§2.1, integer variables"},{"comment":"In the description of the oracle responses for queries outside P_1 ∩ [−R,R]^d, the text says 'report inner products with a_1 or −a_1, depending on which side of P_1 the queried point is.' If the queried point lies inside P_1 but outside the box [−R,R]^d, neither a_1 nor −a_1 separates it from P_1 ∩ [−R,R]^d; a coordinate normal is needed. This is a special case of the missing invariant in the first major comment.","section":"§2.2"},{"comment":"There are minor typos, e.g., 'Similarly, let M_2 > 0 be such that such that' in §2.1. The title in the full text differs slightly from the arXiv title; please harmonize.","section":"General"}],"recommendation":"major_revision","confidential_remarks":"The paper addresses a significant open gap and the high-level strategy is credible. The single-scale arguments are the main strength. However, the recursive amplification—the only source of the log(R/ρ) terms—is not yet a rigorous proof: the consistency of out-of-region queries and repeated queries at the same point is not established. The gaps are concrete and should be fixable with a more detailed invariant-based write-up, but they are load-bearing for the main theorems. I would ask the authors to rewrite §2.1 and §2.2 with a formal invariant that covers all query points, including repeats, and to add the small-d/integrality caveats. The paper fits the journal's scope and, after a careful revision, would be a strong contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the short version: the paper has a real result hiding in it — an Ω(d²) lower bound at fixed scale for both the bit and inner-product oracles — but the stated log(R/ρ) amplification is not established, and the mixed-integer tightness claim is oversold. The stress-test note is on target.\n\nWhat's new: Previous best for arbitrary binary first-order queries was Ω(d^{8/7}) from the authors' earlier paper. Getting quadratic in d closes the gap to the natural d² upper bound up to logs, at least for continuous feasibility. The orthant-counting adversary (Thm 3) and the orthogonal split-set construction (Thm 4) are genuinely new and convincing at the single-scale level. The counting in Thm 3 — after d²/16 queries, at least one orthant stays consistent — checks out. The split-set argument in Thm 4, building orthogonal vectors and a surviving cube, is also plausible. So the fixed-scale part deserves serious attention.\n\nThe soft spot is the recursion. Both theorems claim a log(R/ρ) factor by repeating the argument inside a shrunken cube or orthant. But the oracle's responses to queries outside the surviving region are only hand-waved: 'simply repeat the argument' in Thm 3, and 'simply report inner products with canonical vectors' in Thm 4. That is not enough. In Thm 3, the first phase commits to a single normal s_i e_i for all future queries in the surviving orthant. Once you shrink to a subcube Q inside that orthant, points outside Q but still in the orthant (e.g., closer to the origin than Q) are not separated by s_i e_i. You'd need a different normal, but then the earlier commitment and any 0-answers at that same point constrain your choices. The paper never states the consistency invariant that would let the adversary answer new queries without contradicting earlier ones. Without it, you only get the single-scale d² bound, not the R/ρ dependence.\n\nSame issue in Thm 4: if a point outside Q was previously answered with inner product 0 along some direction v, then a later canonical-vector normal must be orthogonal to v; that is not guaranteed by the separation-from-Q argument. The stress-test note's example is real.\n\nAlso, the abstract and intro claim tightness 'up to a logarithmic term' for mixed-integer convex optimization. That only holds for n=0 or fixed n; the upper bound for general n has an (n+d)² factor, so the lower bound in d and upper in (n+d)² are not tight when n is comparable to d. They should state the continuous case as tight and describe the n>0 setting as a gap.\n\nWho is this for? People working on oracle complexity and communication complexity of convex optimization. The fixed-scale d² lower bound is a true advance. The paper deserves peer review — a serious referee might help repair the recursion or find a different way to get the R/ρ factor. But as it stands, the main theorems overclaim. My recommendation: send to review, flag the recursive consistency invariant as the key issue, and ask the authors to either prove it or soften the theorems.","headline":"A real Ω(d²) fixed-scale lower bound for bit and inner-product oracles, but the log(R/ρ) amplification is under-proved and the mixed-integer tightness claim overreaches.","tokens_in":11698,"tokens_out":7462,"would_cite":true,"duration_ms":76637,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C11","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that solving convex feasibility with bit-wise first-order oracles requires a number of queries quadratic in the number of continuous variables, establishing that the standard discretization of cutting-plane methods is esse","keywords":["information complexity","oracle complexity","convex feasibility","mixed-integer convex optimization","separation oracle","bit oracle","inner product oracle","lower bounds"],"falsifier":"For d=4, run the bit-oracle adversary for exactly d²/16 = 1 query in each of two adjacent orthants and then query a point on the boundary between them; check whether the adversary's commitment rule can produce a separating normal that is valid for both orthants' surviving instances. If no such normal exists, the consistency claim for off-orthant queries fails. Alternatively, for the inner-product oracle, verify the claimed ball containment: take a_1,...,a_k from the construction and a point y with ||y-u||_2 < R/(2√d); if any such point violates some split-set condition, the recursion over cube","tokens_in":10838,"feed_emoji":"🧮","tokens_out":5681,"duration_ms":56507,"temperature":0.7,"pith_summary":"The paper asks how many bits of first-order information are needed to solve convex feasibility problems, a special case of mixed-integer convex optimization. It proves that under two 'bit-wise' oracles—one returning individual bits or whole coordinates of a separating hyperplane normal, the other returning only the sign of an inner product with that normal—any algorithm must make Ω(2^n d² log(R/ρ)) queries in the bit model and Ω(2^n d²(1 + log(R/ρ)/log d)) queries in the inner-product model. The quadratic dependence on the number of continuous variables d was previously unknown even for purely continuous convex optimization. These lower bounds match the natural strategy of approximating separating hyperplanes to enough bits and running standard cutting-plane methods, so they settle the bit complexity of first-order convex feasibility up to logarithmic factors. The result matters because it says that any algorithm using only bit-wise first-order information cannot beat the straightforward discretized cutting-plane approach.","feed_headline":"Convex feasibility needs Ω(d²) bit-wise oracle queries","feed_subtitle":"New lower bounds make the natural discretization of cutting-plane methods optimal up to logarithmic factors.","key_machinery":"The key objects are two recursive adversarial-consistency strategies. For the bit oracle, orthant labeling and a 'commit to a standard basis vector' rule: after d/4 zero-answers in an orthant, all further queries there are answered using a fixed coordinate normal; an orthant-counting argument proves one orthant survives d²/16 queries. For the inner-product oracle, the split-set construction: the adversary answers zero for batches of queries, producing unit normals a_1,...,a_k orthogonal to all queried directions and to each other, so that all convex sets inside the intersection of the strips -R/√d < <a_i,y> < 0 are consistent; a geometric lemma shows this intersection contains a cube of side","core_discovery":"The central discovery is an adversarial oracle argument showing that for the class of convex sets in [-R,R]^{n+d} with ρ-fat feasible regions, the bit and inner-product oracles have information complexity quadratic in d. For the bit oracle (even when queries return an entire coordinate of the separating normal), the adversary answers '0' for the first d/4 queries in each orthant, then commits to a standard basis vector as the normal; a counting argument over orthants shows that after d²/16 queries there remains at least one orthant in which every instance is consistent with all replies. Repeating this inside the surviving orthant shrinks the search box by a constant factor each time, yieldin","pith_inferences":["A direct extension target is unconstrained minimization with M-Lipschitz convex objectives; the paper conjectures the analogous Ω(2^n d² log(MR/(ερ))) bound is attainable via its transfer result, but the feasibility argument alone does not prove it.","The unformalized consistency invariant for off-orthant and off-cube queries is the most natural spot to probe: a reader who can construct a query sequence where the 'repeat the argument' step produces contradictory separating normals would reduce the bound to a single-scale d² statement.","The results suggest that in oracle models where each query inherently reveals one real number or one bit, adaptive coordinate-wise exploration cannot outperform block-coordinate cutting-plane methods; this may inform the design of practical solvers.","The structure of the inner-product adversary—building orthogonal directions—mirrors lower-bound techniques for linear systems, indicating a possible transfer to linear programming feasibility with bit-wise oracles."],"forward_implications":["Any algorithm using bit-wise first-order oracles for constrained convex optimization must make at least quadratically many queries in the number of continuous variables, matching the d² bits used by standard discretized cutting-plane methods.","The lower bound holds even for the stronger oracles that return a full coordinate or a full inner product, so it is not an artifact of restricting to single bits.","For mixed-integer problems, the 2^n factor in the bound shows that the exponential dependence on the number of integer variables is inherent for bit-wise oracle models.","The recursive structure shows the log(R/ρ) scaling cannot be avoided by any query strategy that hopes to exploit partial bit information adaptively.","For the inner-product oracle, the amplification factor is only log(R/ρ)/log d, leaving a small log gap to the upper bound, but the quadratic d² baseline is tight."],"fun_headline_variants":["Bit oracles force Ω(d²) queries in convex optimization","Convex sets: Ω(d²) bit oracle queries necessary and tight","Quadratic bit complexity for first-order convex oracles","Tight lower bound: bitwise oracles need d² queries","Even continuous convex optimization needs Ω(d²) bits"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The recursive amplification assumes that whenever the algorithm queries a point outside the currently surviving orthant or cube, the oracle can answer with a separating hyperplane that remains consistent with all previous answers and all instances in the surviving region; the proof asserts this is possible but does not write down the formal consistency invariant.","fun_headline_variants_meta":{"raw":{"variants":["Bit oracles force Ω(d²) queries in convex optimization","Convex sets: Ω(d²) bit oracle queries necessary and tight","Quadratic bit complexity for first-order convex oracles","Tight lower bound: bitwise oracles need d² queries","Even continuous convex optimization needs Ω(d²) bits"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000709,"raw_usage":{"total_tokens":3014,"prompt_tokens":714,"completion_tokens":2300,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":458,"completion_tokens_details":{"reasoning_tokens":2215}},"tokens_in":458,"tokens_out":2300,"duration_ms":13677,"temperature":1.0,"reasoning_tokens":2215,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T00:16:54.880441+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For d=4, run the bit-oracle adversary for exactly d²/16 = 1 query in each of two adjacent orthants and then query a point on the boundary between them; check whether the adversary's commitment rule can produce a separating normal that is valid for both orthants' surviving instances. If no such normal exists, the consistency claim for off-orthant queries fails. Alternatively, for the inner-product oracle, verify the claimed ball containment: take a_1,...,a_k from the construction and a point y with ||y-u||_2 < R/(2√d); if any such point violates some split-set condition, the recursion over cube","supporting_citations":[],"review_version":1}