{"id":"c966b10c-9afb-4437-8c2b-960fa3245ebd","arxiv_id":"2501.11307","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"SIG-SDP exploits sparse interference graphs and matrix multiplicative weights to speed up SDP-based slot assignment for large wireless time-sensitive networks.","lead":"This paper proposes SIG-SDP, a sparse-graph-aided semidefinite programming method that assigns wireless users to time slots while trying to minimize the number of slots. Simulations report faster computation and lower packet loss than existing SDP and heuristic schedulers, but the central optimality and reliability claims are not fully supported.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Binary search relies on an unproven randomized-rounding feasibility oracle; rounding failure is not proof of infeasibility, so the claimed exact slot minimum is not established.","rationale":"The reader identified the same weakest assumption: the unproven completeness of the randomized rounding feasibility oracle in Algorithm 1. This is indeed the most load-bearing element for the paper's headline claim of minimizing the number of slots. The other components have some support: Theorem 1 gives valid bounds (modulo the trivial zero-edge edge case), Theorem 2's strong duality for the SDP CSP is standard, Theorem 3 is a standard MMW regret bound, and the empirical complexity scaling is plausible and partially backed by Figure 12. However, none of these establish that the binary search converges to Z*. The failure mode is one-sided: a rounded assignment that covers all users is a certificate of feasibility, but a failed rounding is not a certificate of infeasibility. Because the algorithm raises the lower bound on failed rounding, it can only overestimate the optimum. The proposed concrete test—comparing returned Z to exhaustive Z* on small instances—directly settles whether this failure mode occurs in practice. If it does, the central claim should be softened to 'provides an upper bound with good empirical performance' rather than 'minimizes the number of slots'.","tokens_in":25938,"tokens_out":6381,"duration_ms":64907,"concrete_test":"Generate small random instances (K ≤ 20) where the true minimum Z* can be computed by exhaustive enumeration over all Z-coloring assignments. For each instance, run Algorithm 1 with an exact SDP solver (or the MMW solver with a very small η) and the specified rounding, repeating the random rounding many times (e.g., 1000 trials). If the returned Z is greater than Z* for any instance in which the SDP at Z* is feasible but no rounding trial yields a full assignment, the overestimate is attributable to the rounding oracle and the central claim fails. If no such instance occurs over a large test set, the practical concern is weakened, though not theoretically closed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim that SIG-SDP 'minimizes the number of slots' depends on Algorithm 1 using the randomized rounding in (25)-(26) as a decision oracle. In each binary-search step, success (|∪z Vz| = K) certifies Z-feasibility, but failure only triggers Z_a ← Z+1 (Algorithm 1, lines 8-9). This step is valid only if rounding failure implies integer infeasibility. The paper proves no such implication: the SDP relaxation (23) is a necessary condition for integer feasibility, but there is no theorem (e.g., an integrality-gap and rounding-success guarantee analogous to Goemans-Williamson) showing that whenever an integer assignment with Z slots exists, the random-vector rounding of an optimal or near-optimal SDP solution will find one. If the rounding misses a feasible Z, the binary search raises the lower bound and returns a slot count strictly larger than Z*; the algorithm is then an upper-bound heuristic, not a minimizer. This is structurally independent of Theorem 3's duality-gap convergence, which only concerns the SDP solution quality, and is not rescued by the simulations showing good performance, since those report returned slot counts without comparison to true optima.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the NP-hard problem of minimizing the number of time slots in a wireless time-sensitive network under association and interference constraints. It proposes SIG-SDP, a framework that relaxes the integer slot-assignment problem to an SDP constraint satisfaction problem, bounds the optimal slot count using chromatic numbers of sparse interference graphs, and performs a binary search in which each candidate slot count is tested by solving the relaxed SDP with a matrix multiplicative weights (MMW) algorithm and then rounding the solution to integer assignments. The authors also present an online architecture for dynamic networks and report simulations showing near-linear scaling, faster computation than ADMM, and lower packet error rates than heuristics and linear relaxation.","tokens_in":26253,"tokens_out":3669,"duration_ms":38785,"significance":"If the claims hold, the paper would make SDP-based interference management practical for networks with hundreds of users, a useful step for WTSN. The paper has clear strengths: a well-specified system model, a thoughtful exploitation of interference graph sparsity, a complete MMW formulation with a duality-gap convergence theorem, extensive simulations across network sizes, and a promised open-source implementation. The main significance hinges on the exact-slot-minimization claim, which currently rests on an unproven randomized-rounding feasibility oracle, and on the reliability claim, which is directly qualified by the paper's own simulation results.","major_comments":[{"comment":"The binary search treats the randomized rounding in (25)-(26) as a feasibility oracle: if rounding succeeds for a tested Z, the upper bound is lowered; if it fails, the lower bound is raised to Z+1. This is valid only if rounding failure implies that no integer assignment with Z slots exists. The paper proves no such implication. The SDP relaxation (23) is a necessary condition for integer feasibility, but there is no theorem, analogous to the Goemans-Williamson rounding guarantee, showing that whenever an integer assignment with Z slots exists, the random-vector rounding of an optimal or near-optimal SDP solution will find one. Consequently, the algorithm can return a slot count strictly larger than the true optimum, and the abstract's claim that the framework \"minimizes the number of slots\" is not established. This is structurally independent of Theorem 3, which only bounds the duality gap of the SDP solution. The authors should either prove a rounding-success guarantee (with high probability) or explicitly reframe the method as a heuristic that returns an upper bound on the minimum number of slots.","section":"Section IV-B, Algorithm 1 (lines 8-9)"},{"comment":"The paper's own simulation results show that approximately 5-10% of users have packet error rates exceeding the required threshold of 10^-5, and the text attributes this to unmeasurable interference that is not included in the constraints. This directly weakens the abstract's claim of \"ensuring reliability subject to interference constraints\": the constraints in (10) are based only on measured interference, so the method does not guarantee the actual packet error rate requirement. The authors should qualify the reliability claim throughout the paper to refer to constraints on measured interference, and should prominently state that the end-to-end reliability target is not guaranteed when unmeasurable interference is present.","section":"Section VII-E, Fig. 10a"},{"comment":"Theorem 3 is proved under the explicit assumption that the randomized sketching in (39)-(42) is exact. The paper then states, without proof, that sketching error only scales the gap by a constant factor, citing [33]. This is a load-bearing step for the convergence claim in the practical algorithm, and the conditions under which the constant-factor argument applies to this specific SDP CSP (with the constraint structure and the fixed sketch dimension D) should be spelled out. Additionally, the near-linear complexity claim O(K) depends on treating both the MMW iteration count N and the maximum degree Omega as constants; Theorem 3 gives N = O((ln K + ln C)/eta^2), which grows logarithmically, and the constancy of Omega is an empirical observation, not a proven bound. The paper should clearly separate the proven asymptotic statement from the simulation-supported constant-N and constant-Omega assumptions.","section":"Section V-D, Theorem 3"}],"minor_comments":[{"comment":"The notation for the sketching approximation is confusing: in (39), v_k are rows of the sketched product, but in (40)-(42) they are used both as row vectors and as factors in an outer product; the sum in (41) should be over the norms of all K rows. Please define the dimensions of V[n] and the resulting matrix consistently.","section":"Equation (39)-(42)"},{"comment":"The for-loop \"for m = 1, . . . , do\" has no explicit termination condition except the break at line 10; this is not a formal loop structure. Please specify a while-loop condition such as \"while Z_a < Z_b\".","section":"Algorithm 1"},{"comment":"The axis labeling in Fig. 9 is unclear: the y-axis appears to list values of eta, but the caption says the x-axis is the number of iterations. Please clarify what the color/height represents and label both axes explicitly.","section":"Figure 9"},{"comment":"The author list of [33] is garbled: \"Y. Carmon, J. C. Duchi, S. Aaron, and T. Kevin\" should be \"Y. Carmon, J. C. Duchi, A. Sidford, and K. Tian.\"","section":"Reference [33]"},{"comment":"In (45), the returned value U(Σ)^{1/2} is a K by D matrix, but it is called a gram form of a K by K matrix. Please clarify the dimensions and how the rounding in (25)-(26) uses this rectangular factor.","section":"Section IV-B, Eq. (24)-(26)"}],"recommendation":"major_revision","confidential_remarks":"The central exact-minimization claim is the main risk. The missing rounding guarantee is a genuine gap, but it is fixable within scope if the authors either add a rigorous rounding analysis for a restricted class of instances or honestly reframe the contribution as an upper-bounding heuristic. The reliability overstatement in the abstract is also fixable by scoping the claims to measured interference. I recommend major revision rather than outright rejection because the sparse-MMW acceleration and the online architecture remain useful contributions even if the exact-minimality claim is downgraded."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The stress-test note is on target. This paper is a plausible engineering heuristic, but the headline claim that it minimizes the number of slots is not established. Algorithm 1's binary search treats the randomized rounding of (25)-(26) as an exact feasibility oracle: if rounding assigns all K users, it declares Z feasible; if not, it raises the lower bound. The second step is the problem. A single rounding failure does not imply integer infeasibility, and there is no theorem (e.g., an integrality gap plus a rounding-success guarantee) that would make it one. So the returned slot count is an upper bound, not the optimum, and the abstract's \"minimizes the number of slots\" is not supported. The paper's own Fig. 10a also shows 5-10% of users above the 1e-5 target error rate, which weakens the \"ensuring reliability\" part of the claim, though the unmeasurable-interference cause is acknowledged.\n\nWhat is genuinely new is the sparse-graph-aware binary search over chromatic-number bounds, plus the sparsity-exploiting MMW solver. The ingredients are prior art (Frieze-Jerrum, Goemans-Williamson, Arora-Kale, Carmon et al.) and are properly cited. The combination for WTSN slot minimization is not in the cited work, and the complexity analysis O(NKOmega^2 log Omega) with empirically constant N and Omega is credible. The speedups over ADMM are plausible because the sparse structure is real. The online deployment study is a useful addition and honestly shows the edge shrinks at higher mobility.\n\nMain soft spots: the unproven rounding oracle, the tuned hyperparameters (eta, N, D) that support empirical convergence but not the feasibility claim, and the mismatch between the problem as formulated (measurable interference only) and the reliability objective as evaluated (all interference). The Hoffman lower-bound formula can also hit lambda_min(Q)=0 in degenerate empty-graph cases; that is minor.\n\nWho is the audience: wireless networking researchers looking for a practical sparse SDP scheduling heuristic, with source code promised. It deserves a serious referee, but the referee should push for either a rounding/feasibility guarantee (unlikely) or an honest reframing as a heuristic with suboptimality measured against the lower bound. I would not desk-reject; I would send for major revision.","headline":"A solid sparse SDP heuristic for WTSN scheduling, but the exact-minimum claim rests on an unproven rounding oracle, and the paper's own reliability numbers miss the stated target.","tokens_in":753,"tokens_out":834,"would_cite":false,"duration_ms":64908,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C22","90C27","05C15"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that sparse interference graphs can make semidefinite-programming-based slot assignment practical for large wireless time-sensitive networks, cutting computation to near-linear in the number of users while preserving or…","keywords":["time-sensitive networking","semidefinite programming","interference graph","slot scheduling","matrix multiplicative weights","graph sparsity","binary search","wireless reliability"],"falsifier":"Take a small network instance where the true minimum slot count is known by exhaustive search, run Algorithm 1, and check whether the binary search ever raises the lower bound because the rounding fails to assign all users even though a feasible $Z$-slot assignment exists. If such an instance is found, the framework returns a slot count above the true minimum.","tokens_in":25754,"feed_emoji":"📡","tokens_out":5485,"duration_ms":50254,"temperature":0.7,"pith_summary":"The paper aims to make semidefinite-programming based slot assignment practical in large wireless time-sensitive networks, where the goal is to minimize the number of time slots while keeping interference below reliability thresholds. Because the problem is NP-hard, the authors relax it to an SDP over a positive semidefinite matrix that encodes, for each pair of users, how likely they share a slot. Their SIG-SDP framework exploits the natural sparsity of interference graphs to bound the search range for the minimum slot count, solves each feasibility check with a matrix multiplicative weights solver that only touches interfering user pairs, and rounds the relaxed solution back to a slot assignment. If correct, this reduces the runtime from high-degree polynomial to near-linear in the number of users, about ten times faster than the classical ADMM solver, and lowers packet loss rates by up to two orders of magnitude relative to linear relaxation and heuristic baselines.","feed_headline":"Sparse interference graphs make slot scheduling nearly linear","feed_subtitle":"A sparse-graph semidefinite framework finds minimum time slots with lower packet loss in large wireless time-sensitive networks.","key_machinery":"The central object is the PSD matrix $X$, whose $(i,j)$-entry represents how likely users $i$ and $j$ are assigned the same slot: slot choices are mapped to unit radial vectors of a regular simplex so that the indicator $\\mathbf{1}\\{z_i = z_j\\}$ becomes $\\frac{1}{Z}(1 + (Z-1)X_{ij})$. The argument is carried by three pieces: sparse interference graphs $G_{\\mathrm{asso}}$ and $G_{\\mathrm{intp}}$ whose edge sets bound the number of constraints and give chromatic-number bounds on $Z^*$; the matrix multiplicative weights algorithm, which plays a two-player game where dual weights follow the hedge rule and primal iterates come from a sketched matrix exponential; and a random-vector rounding step that converts the relaxed PSD matrix into an integer slot assignment. Sparsity is what turns an otherwise high-polynomial SDP into near-linear work, because only non-zero constraint entries are updated.","core_discovery":"On its own terms, the paper establishes that the NP-hard slot-minimization problem can be approached by a binary search whose bounds come from graph coloring: Theorem 1 gives $Z^*$ between $1 - \\lambda_{\\max}(Q)/\\lambda_{\\min}(Q)$ and $\\chi(G_{\\mathrm{intp}}) \\le \\Omega+1$, using the association graph and the interference-power graph. For a fixed candidate $Z$, the integer feasibility problem is relaxed into an SDP constraint satisfaction problem over positive semidefinite matrices with unit diagonal, and the paper proves strong duality for this formulation and a convergence bound for the matrix multiplicative weights solver: with $N = \\eta^{-2}(\\ln K + \\ln C)$ iterations the duality gap is $O(\\eta K)$. The implementation uses randomized sketching to approximate the matrix exponential, keeps only elements of the PSD matrix corresponding to graph edges, and reports a near-linear overall complexity $O(N K \\Omega^2 \\log \\Omega)$. Simulations show convergence in roughly 100 iterations across network sizes and a slot-count minimum that matches or beats the ADMM-based framework while running up to ten times faster.","pith_inferences":["The paper does not prove that the random rounding in (25)-(26) certifies feasibility, so the returned $Z$ may overestimate the true minimum; a testable extension is to replace rounding with an exact feasibility check for small instances and compare the binary-search verdicts.","Because Theorem 3 assumes exact matrix-exponential sketching, the finite-rank approximation error enters as an unquantified constant factor; one testable design question is how $D$ must scale with $K$ or $\\Omega$ to preserve the $O(\\eta K)$ gap in practice.","The sparsity assumption itself is geometric: with finite receiver sensitivity $\\gamma$, each user's interfering neighborhood is bounded in area, so $\\Omega$ saturates. In fading channels the graph edges become stochastic, so an extension would be to build a random graph model and ask whether expected chromatic-number bounds still hold.","The online results suggest a complexity-reliability tradeoff: further acceleration, such as one-shot graph-to-assignment mapping, would directly improve reliability under mobility, a direction the paper names in its conclusion."],"forward_implications":["The minimum number of slots can be located by binary search inside $[1 - \\lambda_{\\max}(Q)/\\lambda_{\\min}(Q),\\, \\Omega+1]$, so the search range shrinks with graph sparsity rather than growing with the number of users.","The MMW solver certifies a duality gap of $O(\\eta K)$ after $O(\\eta^{-2}(\\ln K + \\ln C))$ iterations, giving a practical stopping rule for the relaxed feasibility problem.","Exploiting edge sparsity makes per-iteration cost $O(K\\Omega^2)$, which is near-linear in $K$ whenever the maximum interference-neighbor count $\\Omega$ saturates as the network grows.","On the simulated WTSN scenarios, the framework returns the minimum slot count with about 10 times less computation than the ADMM-based SDP and packet error rates roughly 100 times lower than linear relaxation and 10 times lower than greedy heuristics.","In the online architecture, updating assignments during user mobility beats the low-complexity heuristic for slow-moving users, and the advantage shrinks as mobility increases."],"supporting_citations":[{"why":"Provides the matrix multiplicative weights framework and its regret bound used to prove the convergence of the MMW solver in Theorem 3.","marker":"[31]"},{"why":"Supplies the rank-1 sketch of the matrix exponential used to approximate the primal PSD iterates in (39)-(42).","marker":"[33]"},{"why":"Contributes the SDP rounding idea and vector representation that maps relaxed solutions back to discrete assignments.","marker":"[18]"},{"why":"Provides the regular-simplex vector encoding and the inner-product identity in (16)-(18) that expresses slot-sharing indicators through $X$.","marker":"[40]"},{"why":"Formulates the integer programming problem and the linear relaxation baseline used as a comparison for slot assignment quality.","marker":"[16]"},{"why":"The ADMM solver is the main polynomial-complexity baseline whose runtime the framework must beat.","marker":"[28]"},{"why":"Gives the Hoffman eigenvalue bound on the chromatic number used for the lower bound in Theorem 1.","marker":"[37]"},{"why":"Supplies the hedge rule used for dual variable updates in the MMW algorithm.","marker":"[42]"}],"fun_headline_variants":["Sparse-graph SDP speeds WTSN slot scheduling 10x","Near-linear SDP for large-scale wireless TSN","SIG-SDP: 10x faster scheduling, 100x lower loss","Wireless TSN: sparse graphs enable near-linear scheduling"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that when a feasible slot assignment with $Z$ slots exists, the relaxed SDP solution plus the random rounding step will actually find one; the paper does not prove this, so the returned minimum slot count could be larger than the true minimum.","fun_headline_variants_meta":{"raw":{"variants":["Sparse-graph SDP speeds WTSN slot scheduling 10x","Near-linear SDP for large-scale wireless TSN","SIG-SDP: 10x faster scheduling, 100x lower loss","Wireless TSN: sparse graphs enable near-linear scheduling"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000182,"raw_usage":{"total_tokens":1375,"prompt_tokens":1072,"completion_tokens":303,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":688,"completion_tokens_details":{"reasoning_tokens":228}},"tokens_in":688,"tokens_out":303,"duration_ms":3677,"temperature":1.0,"reasoning_tokens":228,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T18:25:52.420268+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a small network instance where the true minimum slot count is known by exhaustive search, run Algorithm 1, and check whether the binary search ever raises the lower bound because the rounding fails to assign all users even though a feasible $Z$-slot assignment exists. If such an instance is found, the framework returns a slot count above the true minimum.","supporting_citations":[{"cited_title":"A combinatorial, primal-dual approach to semidefinite programs,","cited_arxiv_id":null,"evidence_quote":"Provides the matrix multiplicative weights framework and its regret bound used to prove the convergence of the MMW solver in Theorem 3."},{"cited_title":"A rank-1 sketch for matrix multiplicative weights,","cited_arxiv_id":null,"evidence_quote":"Supplies the rank-1 sketch of the matrix exponential used to approximate the primal PSD iterates in (39)-(42)."},{"cited_title":"Improved approximation algo- rithms for maximum cut and satisfiability problems using semidefinite programming,","cited_arxiv_id":null,"evidence_quote":"Contributes the SDP rounding idea and vector representation that maps relaxed solutions back to discrete assignments."},{"cited_title":"Improved approximation algorithms for max k-cut and max bisection,","cited_arxiv_id":null,"evidence_quote":"Provides the regular-simplex vector encoding and the inner-product identity in (16)-(18) that expresses slot-sharing indicators through $X$."},{"cited_title":"Conic optimization via operator splitting and homogeneous self-dual embedding,","cited_arxiv_id":null,"evidence_quote":"The ADMM solver is the main polynomial-complexity baseline whose runtime the framework must beat."},{"cited_title":"On eigenvalues and colorings of graphs,","cited_arxiv_id":null,"evidence_quote":"Gives the Hoffman eigenvalue bound on the chromatic number used for the lower bound in Theorem 1."}],"review_version":1}