{"id":"0d634751-083d-4e72-a648-092a6b9c73c8","arxiv_id":"2411.15696","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For RIS with coupled phase-amplitude reflection coefficients, the authors give an optimal linear-complexity phase selection algorithm and a fast near-optimal configuration set selection method based on maximizing an integral.","lead":"This paper finds the best discrete reflection settings for a reconfigurable intelligent surface when a real circuit constraint couples each element's phase shift and amplitude. It also picks the best short menu of settings to maximize average capacity, using a fast integral calculation instead of slow Monte Carlo simulation.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The claimed O(NK) complexity is unsupported: the active-interval construction in Sec. III-C is Θ(K^2) per reference element, and sweeping the resulting O(NK) breakpoints needs sorting, so the central linear-complexity claim fails.","rationale":"Most load-bearing concern: the central claim is 'globally optimal RIS reflection coefficients ... complexity linear with the number of RIS elements and linear with the size of the configuration set' (Abstract and Section I). The correctness part is well argued: Theorem 1 justifies per-element projection maximization, Theorem 2 limits each curve to one active interval, and the shifting argument in Section III-D correctly extends a reference element's active intersections to all elements. The weak point is complexity. The construction in Section III-C explicitly computes I_{n,i} for all K curves by intersecting K−1 pairwise intervals per curve, which is Θ(K^2) for the reference element. The paper's step from 'at most NK regions' to 'linear complexity' omits both this preprocessing cost and the cost of sorting the O(NK) breakpoints. This is not a matter of disagreement with community consensus; it is an internal inconsistency between the stated algorithm and the claimed asymptotic complexity. The reader's weakest_assumption focused on the integral approximation in Eq. (25), which is indeed unquantified, but the IMB configuration-selection method is introduced as 'approximately equivalent' and validated numerically, so the damage is more limited. In contrast, the linear-complexity statement is a crisp, central, advertised contribution that the manuscript's own procedure contradicts. A conditional accept is appropriate: require the authors to either prove an O(NK) implementation (e.g., via convex-hull/support-function computation of the upper envelope after sorting by angle) or explicitly restate the complexity as O(K^2+NK) and remove the linear-in-K claim. The reader's verdict already says CONDITIONAL; our concern strengthens the condition but does not change the verdict.","tokens_in":18499,"tokens_out":12356,"duration_ms":114922,"concrete_test":"Implement the reference-element procedure exactly as in Section III-C: for K=8,16,32,64,128, count the number of pairwise intersection solutions (via (15)) and CRC calls needed to form I_{n,1},...,I_{n,K}. If the count for one element is K(K−1) (i.e., scales quadratically), the stated O(NK) complexity is false. Additionally, measure wall-clock time for the full Section III algorithm on N=1 with increasing K; quadratic growth in K would confirm the concern.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's headline contribution—global capacity maximization in O(NK) time—is not supported by the algorithm it actually describes. Section III-C constructs, for a single reference RIS element, the active interval I_{n,i} = ⋂_{l≠i} I_{n,i,l} for every curve i. Each I_{n,i,l} requires solving the pairwise intersection equation (15), and each intersection operation in (16) (the CRC of Table I) takes O(1). Since there are K curves and for each i we must intersect with K−1 other curves, computing the active intervals for the reference element costs Θ(K^2) time. Section III-D avoids repeating this for every element by shifting the reference active intersections, but the Θ(K^2) preprocessing remains. Section III-E then claims that because there are at most NK active intersections/regions, the method is linear in N and K. This confuses the number of swept regions with the cost of finding and sorting them. The O(NK) regions are the union of shifted copies of K reference breakpoints; producing their sorted order for a sweep generally requires Ω(NK log(NK)) comparisons unless additional structure (e.g., pre-sorted shifts) is assumed, which the paper does not state. Consequently, the central 'linear complexity' claim fails even if the enumeration itself is correct. The capacity-maximization result may still be valid as an exact algorithm with higher complexity, but the advertised efficiency guarantee is not.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper considers a single-user RIS-aided channel in which each RIS element's reflection coefficient is chosen from a finite configuration set, with the amplitude and phase coupled through a practical model (Eq. (8)). The first contribution is an algorithm that, for a given configuration set, finds the globally optimal reflection coefficients maximizing capacity by sweeping over the finitely many active intervals of the upper envelope of per-element curves (Sections III-A to III-E); the paper claims this runs in time linear in the number of elements N and the number of choices K. The second contribution is a configuration-set-selection method (IMB) that replaces Monte Carlo averaging by the integral of a one-dimensional function S(x), together with a search-space compression (SSC) that halves the number of candidate sets (Section IV). Numerical results compare the capacity maximization algorithm with exhaustive search and heuristic projection methods, and compare IMB with Monte Carlo based selection.","tokens_in":18743,"tokens_out":10630,"duration_ms":105655,"significance":"If the linear-complexity and global-optimality claims held as stated, the capacity maximization part would be a useful contribution to discrete RIS reflection optimization under the practical coupled phase-amplitude model, extending prior work on arbitrary discrete phase shifts. The IMB idea of replacing channel-average capacity maximization by maximizing a one-dimensional integral is attractive computationally, and the SSC symmetry argument is clean. The paper contains mathematical proofs of the upper-envelope properties and of Theorem 1, and the simulation study is relevant. However, the advertised complexity guarantee is not supported by the described algorithm, and the configuration-set-selection method is an unquantified approximation while being described as optimal. These two issues affect the paper's central claims.","major_comments":[{"comment":"The central complexity claim, repeated in the abstract, Section I, Section III-E, and the conclusion, is not supported by the algorithm actually described. In Section III-C, computing the K active intervals for one reference RIS element requires, for each curve i, intersecting it with the other K-1 curves through Eq. (15) and the CRC operations of Table I; this is Theta(K^2) work, not O(K). Section III-D shifts the resulting reference active intervals to the other N-1 elements, but it does not eliminate this Theta(K^2) preprocessing cost. Section III-E argues that because there are at most NK active intersections, the method is linear in N and K; this confuses the number of swept regions with the cost of finding and sorting them. Producing the sorted list of up to NK breakpoints for the sweep requires Omega(NK log NK) comparisons in general, and even a k-way merge of the shifted copies would require Omega(NK log N). Thus the advertised 'linear with N and K' guarantee fails for the presented algorithm, even though the enumeration itself may still be exact.","section":"Sec. III-C to III-E"},{"comment":"The IMB configuration-set-selection claim is not proven to the strength stated. The reduction of average capacity to the integral of S relies on three assumptions introduced around Eq. (25): |v_n| approximately equal to c, |h0| approximately zero, and replacement of the sum over n of S(angle h*_r - angle v_n) by the integral (N/2pi) integral S(x) dx. None of these assumptions is quantified with an error bound, and the Riemann-sum-to-integral step also requires a uniformity or large-N condition that is not stated. Moreover, Eq. (26) replaces each realization |h*_r| by the same constant and then effectively equates E[log(1 + gamma |h*|^2)] with log(1 + gamma (E|h*|)^2), which is not valid in general. Consequently, the statement that maximizing the average capacity is approximately equivalent to maximizing the integral of S is a heuristic, and the abstract's wording that IMB 'optimally selects the configuration set' overstates the result. The authors should either provide a formal approximation guarantee (e.g., a large-N or asymptotic error bound) or explicitly label IMB as an approximate heuristic and soften the optimality claims throughout.","section":"Sec. IV-A, Eqs. (24)-(26)"},{"comment":"The numerical validation of IMB is performed only in the regime consistent with the assumptions of Eq. (25): the simulations set |h0| = |v_n| = -140 dB, which satisfies |h0| approximately 0 and equal cascaded magnitudes. Since the derivation explicitly assumes a weak direct path, the claim that IMB is the optimal configuration set selection method for the considered system is not tested for stronger direct paths. Figure 9 shows that direct-channel strength qualitatively changes the capacity-maximization problem, so the paper should either characterize the regime in which the IMB approximation is intended to hold or report results for varying |h0|.","section":"Sec. V-B and Fig. 10"}],"minor_comments":[{"comment":"The arctangent-based formula for the intersection points requires care when the denominator is zero and for choosing the correct quadrant; a formulation using atan2 or a short discussion of degenerate cases would improve clarity.","section":"Sec. III-C, Eq. (15)"},{"comment":"The active-interval construction assumes that no two curves coincide on an interval and that intersections are generic; the treatment of ties, where two curves are exactly equal at a boundary or over an interval, is not specified and should be addressed.","section":"Sec. III-C and Table I"},{"comment":"Reference [20] contains a typo: 'adn M.-S. Alouini' should be 'and M.-S. Alouini'.","section":"References"},{"comment":"In the SSC derivation, the symbol psi_k is used both for a reflection coefficient choice and for its phase via angle psi_k; the notation should be made explicit to avoid confusion.","section":"Sec. IV-B, Eq. (28)"},{"comment":"The observation that improved CPP approaches the optimal method as |h0| grows is interesting; a brief remark connecting this to the validity regime of the IMB method in Section IV would help the reader.","section":"Sec. V-A, Fig. 9"}],"recommendation":"major_revision","confidential_remarks":"The capacity maximization proof appears self-contained and the extension from the authors' prior work [34] is not circular. The main editorial risk is that the paper's headline claims ('linear complexity' and 'optimal configuration set selection') are stronger than what the presented algorithm and analysis support. If the authors can either provide a genuinely linear implementation or restate the complexity accurately (e.g., Theta(K^2 + NK log N)) and reposition IMB as an approximate method with validated regimes, the paper could be suitable for publication. No concerns about novelty disclosure beyond the usual expectation to cite related work."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take. The active-interval method is a real extension of the arbitrary-discrete-phase result [34] to the coupled amplitude-phase model, and the global optimality proof for capacity maximization is mathematically solid as far as I can tell. The shifting trick — getting all elements' active intervals from one reference element by phase offsets — is elegant and correct. The numerical agreement with exhaustive search confirms the algorithm's correctness on tested cases. That part of the paper deserves credit.\n\nThe advertised complexity claim does not hold up. The paper says that because there are at most NK active intersections/regions, the method is linear in N and K. But constructing the active intervals for the reference element requires pairwise intersection of K curves, which is Θ(K^2) per element (or per reference element), and the sweep over O(NK) breakpoints needs sorting, which is Ω(NK log NK) in general. The paper doesn't state an assumption that K is constant or that the breakpoints come pre-sorted. So the 'linear complexity' statement in the abstract and Section I is unsupported. This is the central advertised contribution, so it's a real flaw, not a typo.\n\nThe configuration set selection (IMB) is a reasonable heuristic, but the paper labels it 'optimal.' The derivation in Eq. (25) assumes |v_n| ≈ c, |h0| ≈ 0, and ∠v_n uniform over [0,2π) so the sum becomes an integral. No error bound is given, and the equivalence between average capacity and the S(x) integral is only approximate. The SSC symmetry reduction is neat and correctly halves the candidate set, but it doesn't change the combinatorial nature of the search. The M evenly spaced candidate phases also mean the method selects the best among C(M,K) discrete options, not the true continuous optimum.\n\nSo: the capacity maximization core is a solid contribution, but the paper overstates its complexity and calls a heuristic 'optimal.' A serious referee should engage with this; I'd send it to review with the expectation of major revision. The authors can likely fix the complexity claim by providing the actual Θ(K^2) preprocessing cost and stating the sort, or by showing that K is small enough to be treated as a constant. The IMB needs an honest error analysis or at least a clear statement that it is a heuristic.","headline":"Solid capacity-maximization core with an unsupported linear-complexity claim and an overhyped configuration-set heuristic; worth refereeing but needs major revision.","tokens_in":19267,"tokens_out":2208,"would_cite":true,"duration_ms":21499,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A linear-complexity algorithm provably finds capacity-maximizing RIS reflection coefficients under a practical coupled phase-amplitude model, and a one-dimensional integral selects the near-optimal discrete configuration set.","keywords":["reconfigurable intelligent surface","reflection optimization","coupled phase shift and amplitude","capacity maximization","configuration set selection","discrete phase shifts","linear-time algorithm","integral maximization"],"falsifier":"Take a single-user RIS link with a strong direct path (e.g., $|h_0|$ comparable to the RIS-aided path) and uneven element channel magnitudes, and compare the configuration set chosen by maximizing $\\int_0^{2\\pi} S(x)\\,dx$ with the set chosen by exhaustive Monte Carlo selection over all $\\binom{M}{K}$ menus; if the integral-based set does not achieve the largest average capacity, the approximation in Eq. (25) is the point of failure.","tokens_in":18270,"feed_emoji":"📡","tokens_out":12005,"duration_ms":96864,"temperature":0.7,"pith_summary":"Reconfigurable intelligent surfaces (RIS) are usually optimized under the idealization that each element's reflection amplitude and phase shift can be set independently. This paper works with the practical model in which amplitude is a fixed function of phase shift, and each element must pick one of $K$ discrete reflection coefficients. Its first result is an exact, linear-complexity algorithm: for each channel realization, the globally capacity-maximizing assignment of coefficients is found by checking at most $NK$ candidate phases of the optimal end-to-end channel, instead of exhaustive search over $K^N$ combinations. Its second result is a fast configuration-set selector: the average capacity over channel realizations is approximately maximized by maximizing the integral $\\int_0^{2\\pi} S(x)\\,dx$ of a one-dimensional function $S(x)$, so the best discrete menu of $K$ reflection coefficients can be chosen without Monte Carlo simulation. A symmetry argument halves the search over candidate menus. If correct, these results let practical RIS hardware be configured optimally at low cost, and let designers choose the built-in reflection menu by a simple calculation.","feed_headline":"Exact RIS tuning is linear-time even with coupled phase and amplitude","feed_subtitle":"Real RIS hardware couples phase and amplitude; this method keeps global optimality without exhaustive search.","key_machinery":"The load-bearing object is the upper envelope of the per-element projection curves, $F_n(\\angle h^*) = \\max_i \\hat{\\beta}_i \\cos(\\angle h^* - \\angle g_{n,i})$, together with the phase-shifted, element-independent version $S(x) = \\max_i \\hat{\\beta}_i \\cos(x - \\hat{\\alpha}_i)$. The machinery has three parts. First, Theorem 1 turns the combinatorial choice per element into a largest-projection rule once $\\angle h^*$ is fixed, so the only unknown left is that single phase. Second, Theorem 2 shows each cosine curve can dominate on at most one interval, so the active boundaries of the optimal phase are the pairwise intersections of the $K$ curves, and shifting by $\\angle v_n - \\angle v_m$ transfers one element's boundaries to all others. Third, Eqs. (25)-(26) replace the stochastic average over channel realizations by the deterministic integral of $S(x)$, turning configuration-set selection from a Monte Carlo problem into evaluation of one one-dimensional integral per candidate menu, with a final symmetry reduction cutting candidates in half.","core_discovery":"The paper's central claim is that, for a single-user RIS link whose elements obey the practical coupled amplitude-phase relation in (8), the capacity-maximizing reflection coefficients can be found exactly for any finite configuration set in time linear in the number of elements $N$ and the menu size $K$. The argument fixes the phase $\\angle h^*$ of the optimal end-to-end channel; for a fixed $\\angle h^*$, element $n$'s best choice is the menu entry maximizing $\\hat{\\beta}_i \\cos(\\angle h^* - \\angle v_n - \\hat{\\alpha}_i)$, i.e., the largest projection of the element's cascaded channel onto $\\angle h^*$ (Theorem 1). Because each element's projection curves are cosine waves and each curve can be the maximum on at most one interval of $\\angle h^*$ (Theorem 2), the optimal assignment changes only at finitely many phase boundaries; shifting one element's boundaries by $\\angle v_n - \\angle v_m$ gives every other element's boundaries, so the whole axis splits into at most $NK$ regions. For configuration-set selection, the paper shows that under a weak-direct-path, equal-magnitude, uniform-phase approximation, the average capacity is a monotone function of the integral $\\int_0^{2\\pi} S(x)\\,dx$ with $S(x) = \\max_i \\hat{\\beta}_i \\cos(x - \\hat{\\alpha}_i)$, so the best menu is the one with the largest such integral.","pith_inferences":["Editorial inference: the exact linear-complexity capacity-maximization procedure does not actually depend on the specific functional form (8); it only needs a finite menu of amplitude-phase pairs, so measured phase-amplitude tables from a specific RIS prototype could be plugged in directly.","Editorial inference: because the integral criterion discards the direct path, a hybrid objective that adds a direct-path-alignment term to the integral would likely outperform it in strong-line-of-sight settings, a regime the paper's approximation excludes.","Editorial inference: the near-independence of the optimal menu from the cascaded channel phases suggests that an integral-selected configuration set chosen for one scattering environment should remain near-optimal in another environment with similar element-strength statistics; this is a testable prediction the paper does not run.","Editorial inference: the same integral proxy could be extended to multi-user or frequency-selective links by summing $S(x)$ over users or subcarriers, though the paper's proof is for a single narrowband user."],"forward_implications":["For any finite reflection-coefficient menu generated by the coupled model, the capacity-maximizing assignment for a channel realization is computed in time linear in $N$ and $K$, replacing exhaustive search over $K^N$ combinations.","The per-element optimal choice is exactly the menu entry with the largest projection onto the optimal channel phase, so capacity maximization needs no heuristic alignment with the direct channel.","The best configuration set can be selected by maximizing the single integral $\\int_0^{2\\pi} S(x)\\,dx$, avoiding Monte Carlo simulation over channel realizations.","Mirror-symmetric menu pairs give identical integrals, so the number of candidate sets to evaluate is cut approximately in half with no loss in selected capacity.","In the lossless limit ($\\beta_{\\min}=1$ or $\\kappa=0$), the coupled model degenerates to independent amplitude and phase and the evenly spaced phase set is recovered as optimal."],"supporting_citations":[{"why":"Supplies the practical coupled amplitude-phase model (8) that all reflection coefficients in the configuration set must satisfy.","marker":"[36]"},{"why":"Supplies the end-to-end channel expression and the closest-point projection heuristic used as a benchmark and refined via Theorem 1.","marker":"[26]"},{"why":"Establishes the prior linear-time globally optimal method for evenly spaced independent discrete phase shifts that this paper extends to coupled amplitude and phase.","marker":"[32]"},{"why":"Gives the earlier arbitrary-discrete-phase-shift optimal method with linear complexity that the present coupled-model algorithm generalizes.","marker":"[34]"},{"why":"Defines the standard discrete-phase-shift beamforming problem and evenly spaced configuration-set assumption that the paper replaces with arbitrary subsets.","marker":"[31]"},{"why":"Documents that independent phase and amplitude control is infeasible in real RIS hardware, motivating the coupled model.","marker":"[35]"}],"fun_headline_variants":["Linear-Time Optimal RIS Tuning Despite Coupled Phase-Amplitude","Exact RIS Capacity Max in Linear Time, No Exhaustive Search","Coupled RIS Reflections? Optimal Tuning Still Linear-Time","Realistic RIS Coupling Handled: Linear-Time Capacity Max","Optimal RIS Configuration Set Selection with Coupled Amplitudes"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The configuration-set-selection shortcut rests on the assumption that all cascaded channel magnitudes are approximately equal, the direct transmitter-to-receiver path is weak, and the cascaded phases are spread uniformly over $[0,2\\pi)$, so that the average capacity can be replaced by the integral of $S(x)$; when the direct path is strong or the element channels are not similar, the integral-based menu choice can be suboptimal.","fun_headline_variants_meta":{"raw":{"variants":["Linear-Time Optimal RIS Tuning Despite Coupled Phase-Amplitude","Exact RIS Capacity Max in Linear Time, No Exhaustive Search","Coupled RIS Reflections? Optimal Tuning Still Linear-Time","Realistic RIS Coupling Handled: Linear-Time Capacity Max","Optimal RIS Configuration Set Selection with Coupled Amplitudes"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000545,"raw_usage":{"total_tokens":2644,"prompt_tokens":1021,"completion_tokens":1623,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":637,"completion_tokens_details":{"reasoning_tokens":1535}},"tokens_in":637,"tokens_out":1623,"duration_ms":11632,"temperature":1.0,"reasoning_tokens":1535,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T14:00:38.540398+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a single-user RIS link with a strong direct path (e.g., $|h_0|$ comparable to the RIS-aided path) and uneven element channel magnitudes, and compare the configuration set chosen by maximizing $\\int_0^{2\\pi} S(x)\\,dx$ with the set chosen by exhaustive Monte Carlo selection over all $\\binom{M}{K}$ menus; if the integral-based set does not achieve the largest average capacity, the approximation in Eq. (25) is the point of failure.","supporting_citations":[{"cited_title":"Intelligent reflecting surface: practical phase shift model and beamforming optimization,","cited_arxiv_id":null,"evidence_quote":"Supplies the practical coupled amplitude-phase model (8) that all reflection coefficients in the configuration set must satisfy."},{"cited_title":"Reconfigurable intelligent surfaces: A signal pro- cessing perspective with wireless applications,","cited_arxiv_id":null,"evidence_quote":"Supplies the end-to-end channel expression and the closest-point projection heuristic used as a benchmark and refined via Theorem 1."},{"cited_title":"A linear time algorithm for the optimal discrete IRS beamforming,","cited_arxiv_id":null,"evidence_quote":"Establishes the prior linear-time globally optimal method for evenly spaced independent discrete phase shifts that this paper extends to coupled amplitude and phase."},{"cited_title":"Optimal configura- tion of reconfigurable intelligent surfaces with arbitrary discrete phase shifts,","cited_arxiv_id":null,"evidence_quote":"Gives the earlier arbitrary-discrete-phase-shift optimal method with linear complexity that the present coupled-model algorithm generalizes."},{"cited_title":"Intelligent omni-surfaces for full-dimensional wire- less communications: Principles, technology, and implementation,","cited_arxiv_id":null,"evidence_quote":"Documents that independent phase and amplitude control is infeasible in real RIS hardware, motivating the coupled model."}],"review_version":1}