{"id":"43ee9473-d6f2-4d03-9b8c-641ea23e0fa9","arxiv_id":"2607.01427","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Black-box reduction turns any T(n, m_in, m_out)-time sparse matrix multiplication algorithm into a robust version approximating the k largest outputs in Õ(T(n, m_in, k)) time.","lead":"The paper gives a black-box reduction that converts any fast algorithm for multiplying two sparse matrices into one that approximates only the k largest entries in the output, with error depending only on the smaller entries, at polylog extra cost. A smart generalist might read it because sparse matrix operations underpin large-scale data analysis, graph algorithms, and machine learning, and making them robust to focus on top results could improve practicality for noisy or ma","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.3","headline":"Black-box reduction's Õ overhead hinges on knapsack-type subroutine adding only polylog factors in word-RAM for arbitrary parameters","rationale":"The reader's weakest assumption is precisely the load-bearing step; the full manuscript would need to exhibit an explicit polylog-time knapsack procedure whose cost is independent of T. Because the claim is a black-box reduction, any super-polylog cost in the auxiliary problem directly invalidates the headline statement. This is an internal modeling question rather than an external-consensus issue.","tokens_in":1865,"tokens_out":376,"duration_ms":15150,"concrete_test":"From the reduction section, extract the exact knapsack instance (item counts, weight/value ranges, capacity) and its claimed solver; re-derive its running time via standard DP or other method and check whether it is O(polylog(n, m_in, k)) in all regimes; if any parameter setting yields super-polylog cost, the Õ(T) bound does not hold.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central claim is that any T(n, m_in, m_out) sparse MM algorithm yields a robust version in Õ(T(n, m_in, k)) time via sparse recovery plus one knapsack-type problem. This requires the knapsack instance (arising from the reduction) to be solvable in polylog(n, m_in, k) time under standard word-RAM assumptions, with no hidden dependence on bit lengths, weights, or capacities that would produce super-polylog cost or break the black-box property. If the knapsack formulation admits instances where exact/approximate solution requires Ω(n^ε) or worse time for some ε>0, the claimed overhead fails and the transformation does not hold for arbitrary T.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The paper claims a black-box reduction showing that any sparse matrix multiplication algorithm running in time T(n, m_in, m_out) can be transformed into a robust algorithm (approximately computing the k largest output entries, with error depending only on smaller entries) running in Õ(T(n, m_in, k)) time. The reduction uses sparse recovery primitives and solves one knapsack-type problem; plugging in the SODA'24 algorithm yields O((m_in + k)^1.346) time, and k^{1+o(1)} time when k ≥ m_in^1.762.","tokens_in":2013,"tokens_out":407,"duration_ms":22563,"significance":"If the reduction holds with the claimed polylog overhead, the result is significant: it makes essentially all existing sparse MM algorithms robust (closing the gap left by Pagh's Õ(m_in + nk) algorithm), and produces improved concrete bounds for the robust variant. The black-box nature and use of an external toolkit plus one auxiliary problem are strengths if the overhead analysis is tight.","major_comments":[{"comment":"The central reduction claim (abstract and reduction section) asserts Õ overhead via sparse recovery plus one knapsack-type problem. The manuscript must explicitly verify that the specific knapsack instance arising in the reduction admits an exact or approximate solution in polylog(n, m_in, k) time in the standard word-RAM model, with no hidden dependence on bit lengths, weights, or capacities that would produce super-polylog cost and invalidate the black-box transformation for arbitrary T.","section":"Reduction / knapsack subroutine"}],"minor_comments":[{"comment":"The abstract states the running-time claim cleanly but does not name the precise sparse-recovery primitives or the knapsack formulation; adding a short high-level overview paragraph would improve readability.","section":null}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for the careful reading and for highlighting the need for an explicit verification of the knapsack subroutine's complexity. We address the single major comment below and will incorporate the requested details in the revision.","responses":[{"response":"We agree that the manuscript should contain an explicit, self-contained argument establishing the polylogarithmic cost of the knapsack step in the word-RAM model. In the reduction the knapsack instance is a special case with polynomially bounded integer weights and capacities whose bit length is O(log(n + k)); it can therefore be solved exactly by a standard O(k · polylog(n + k)) dynamic-programming routine (or approximated to (1+ε) via standard FPTAS techniques) with no hidden dependence on input bit lengths beyond the word size. We will add a dedicated subsection (or appendix lemma) that spells out the precise instance, the DP recurrence, the word-RAM implementation, and the resulting Õ overhead, thereby confirming that the black-box claim holds for arbitrary T.","revision_made":"yes","referee_comment":"[Reduction / knapsack subroutine] The central reduction claim (abstract and reduction section) asserts Õ overhead via sparse recovery plus one knapsack-type problem. The manuscript must explicitly verify that the specific knapsack instance arising in the reduction admits an exact or approximate solution in polylog(n, m_in, k) time in the standard word-RAM model, with no hidden dependence on bit lengths, weights, or capacities that would produce super-polylog cost and invalidate the black-box transformation for arbitrary T."}],"tokens_in":1489,"tokens_out":349,"duration_ms":14122,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The paper gives a black-box reduction that turns any sparse matrix multiplication algorithm into a robust one for computing the k largest output entries approximately. The robust version runs in Õ(T(n, m_in, k)) time if the original is T(n, m_in, m_out).\n\nThis is the main new thing. It was open whether anything besides Pagh's algorithm could be made robust, and the method here uses sparse recovery plus a knapsack problem to achieve the transformation. Plugging in the recent SODA'24 algorithm produces improved concrete bounds like O((m_in + k)^1.346) and almost linear in k when k is sufficiently large.\n\nThe paper does well by supplying a general technique that applies broadly rather than case by case. The connection to sparse recovery is a nice angle.\n\nThe soft spot is the knapsack subroutine. The reduction's polylog overhead depends on solving that knapsack instance quickly in the word-RAM model. If the instances that come up from the reduction require more than polylog time in some cases, or if there are hidden dependencies on bit lengths, the black-box claim would not go through cleanly for every T. The abstract asserts it works, but this part needs careful checking in the full text.\n\nThis is for researchers focused on sparse algorithms and fine-grained complexity. A reader working on matrix multiplication or recovery problems would find the reduction useful.\n\nIt deserves a serious referee to verify the details.\n\nI recommend engaging with the work through peer review.","headline":"The black-box reduction is new and general, but the polylog overhead claim needs verification on the knapsack solver.","tokens_in":2530,"tokens_out":381,"would_cite":true,"duration_ms":25826,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"Any sparse matrix multiplication algorithm can be transformed into a robust version computing the k largest output entries with only polylogarithmic overhead.","keywords":["sparse matrix multiplication","robust algorithms","sparse recovery","black-box reduction","knapsack problem","approximate matrix multiplication","word-RAM model"],"falsifier":"An algorithm T for sparse matrix multiplication where the overhead to make it robust exceeds polylog factors, or a concrete input matrix pair where the reduction outputs entries whose approximation error depends on large missed entries rather than only smaller ones.","tokens_in":2744,"feed_emoji":"","tokens_out":725,"duration_ms":21855,"temperature":0.7,"pith_summary":"The paper establishes a black-box reduction that converts any algorithm for multiplying two sparse n by n matrices, running in time T(n, m_in, m_out), into a robust algorithm that approximately outputs the k largest entries of the product. The new algorithm runs in Õ(T(n, m_in, k)) time by combining sparse recovery primitives with a knapsack-type solver. A sympathetic reader would care because prior sparse matrix multiplication algorithms were generally not robust, except for one special case, and the reduction lets the fastest known algorithms be reused directly for the robust variant, yielding concrete improvements such as O((m_in + k)^1.346) time.","feed_headline":"Sparse matrix multiplication made robust with polylog overhead","feed_subtitle":"Any T(n, m_in, m_out) algorithm converts to one that outputs the k largest entries in Õ(T(n, m_in, k)) time.","key_machinery":"The black-box reduction that invokes sparse recovery primitives and solves a knapsack-type problem to transform any T(n, m_in, m_out)-time sparse matrix multiplication algorithm into a robust Õ(T(n, m_in, k))-time algorithm.","core_discovery":"The paper shows that robust sparse matrix multiplication reduces to standard sparse matrix multiplication. Any algorithm with running time T(n, m_in, m_out) can be turned into a robust algorithm running in Õ(T(n, m_in, k)) time. The reduction works in the word-RAM model and relies on sparse recovery tools together with a knapsack solver to handle the selection of the k largest entries while bounding the approximation error by the smaller entries.","pith_inferences":["The same reduction technique may extend to other sparse linear-algebra tasks that require only the largest entries.","Applications that already use sparse matrix multiplication can switch to the robust version without redesigning the underlying algorithm."],"forward_implications":["Plugging in the SODA'24 sparse matrix multiplication algorithm yields O((m_in + k)^1.346) time for the robust problem.","In the regime k >= m_in^1.762 the reduction produces an almost-optimal k^{1+o(1)}-time algorithm.","Every existing sparse matrix multiplication algorithm can now be converted into a robust version using the same transformation.","The reduction preserves the original running time up to polylog factors while guaranteeing that the approximation error depends solely on the smaller output entries."],"fun_headline_variants":["Black-box reduction robustifies sparse matrix multiplication","Sparse matmul turned robust with polylog overhead reduction","Any sparse matrix algorithm robustified in polylog time","Robust sparse multiplication via reduction to standard"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"Sparse recovery primitives and the knapsack solver can be executed with only polylogarithmic overhead in the standard word-RAM model, without hidden costs that would break the black-box property for arbitrary T.","fun_headline_variants_meta":{"raw":{"variants":["Black-box reduction robustifies sparse matrix multiplication","Sparse matmul turned robust with polylog overhead reduction","Any sparse matrix algorithm robustified in polylog time","Robust sparse multiplication via reduction to standard"]},"model":"grok-4.3","cost_usd":0.005002,"raw_usage":{"total_tokens":2516,"prompt_tokens":815,"num_sources_used":0,"completion_tokens":58,"cost_in_usd_ticks":50024500,"prompt_tokens_details":{"text_tokens":815,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1643,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":815,"tokens_out":58,"duration_ms":13532,"temperature":1.0,"reasoning_tokens":1643,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-03T17:49:31.929732+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"An algorithm T for sparse matrix multiplication where the overhead to make it robust exceeds polylog factors, or a concrete input matrix pair where the reduction outputs entries whose approximation error depends on large missed entries rather than only smaller ones.","supporting_citations":[],"review_version":1}