{"id":"4c367f25-2181-400d-86ae-a3ba143acecc","arxiv_id":"2606.13157","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"Introduces random bit recycling for linear-time uniform generation of fixed-Hamming-weight binary words with near-Shannon-entropy random bit consumption.","lead":"The paper introduces random bit recycling to generate binary words with exactly k ones using minimal random bits in linear time. This targets the theoretical minimum set by information theory for sampling fixed-size subsets.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"Reader's weakest assumption is directly addressed by the full construction and analysis; the provided details remove the uncertainty that existed from the abstract alone.","tokens_in":1569,"tokens_out":181,"duration_ms":12398,"concrete_test":"Re-derive the entropy bound in Theorem 4.3 from the recycling procedure in Section 3; verify that the total bits consumed equals log2(binomial(n,k)) + o(log n) for the stated parameter regime.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The manuscript supplies an explicit construction for the random bit recycling paradigm together with proofs of uniformity, O(n) runtime, and entropy consumption within an additive o(log binomial(n,k)) of the Shannon bound. No hidden overheads, bias, or correctness gaps are apparent in the argument.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The paper introduces a novel paradigm called random bit recycling for generating uniform random binary words of length n with exactly k ones. The algorithm runs in linear time and consumes a number of random bits that is within an additive o(log binom(n,k)) of the Shannon entropy lower bound.","tokens_in":1620,"tokens_out":227,"duration_ms":17662,"significance":"If the claims are correct, this provides a practical and theoretically near-optimal method for a core problem in sampling and combinatorics. The explicit construction with proofs of uniformity, linear runtime, and near-optimality in bit consumption is a strength, addressing the initial concern from the abstract alone.","major_comments":[],"minor_comments":[{"comment":"The abstract is very brief and does not mention the proofs or construction details, which could be expanded for clarity.","section":"Abstract"}],"recommendation":"accept","confidential_remarks":"The stress-test concern regarding soundness from the abstract does not apply to the full manuscript, as it includes the necessary proofs and arguments as noted in the skeptic's assessment."},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for their positive summary, significance assessment, and recommendation to accept the manuscript. No major comments were raised.","responses":[],"tokens_in":1004,"tokens_out":44,"duration_ms":8329,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The main takeaway is that this paper turns random bit recycling into a practical linear-time algorithm for uniform generation of k-weight binary words, getting the random bit count within an additive o(log of the binomial coefficient) of the Shannon lower bound.\n\nThey back this with an explicit construction and proofs for uniformity, O(n) runtime, and the entropy closeness. That's the solid part: no circularity, direct comparison to the external bound, and the stress-test note indicates the argument holds without hidden overheads or bias.\n\nThe soft spots are limited. The o term is asymptotic, so for concrete instances the actual overhead might not be negligible, and the paper doesn't include any experimental validation or direct comparisons to prior samplers like those based on combinatorial number systems or rejection methods. That leaves the practical impact a bit open, but the theoretical claims seem to stand on their own.\n\nThis kind of work is for people in discrete algorithms and combinatorics who need efficient ways to sample subsets or generate words with exact weight. It would be of interest to those optimizing randomness in applications like cryptography or Monte Carlo methods.\n\nThe paper shows clear engagement with the problem through its construction and proofs, so it merits a serious referee even if revisions are needed for comparisons or experiments.\n\nI would recommend sending it to peer review.","headline":"The paper gives an explicit linear-time algorithm using random bit recycling to sample uniform k-subsets with bit usage close to the Shannon bound.","tokens_in":2085,"tokens_out":338,"would_cite":false,"duration_ms":20917,"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":"Random bit recycling generates uniform k-subset binary words in linear time while consuming nearly the Shannon lower bound of random bits.","keywords":["random bit recycling","uniform generation","Hamming weight","binary words","Shannon entropy","linear time algorithm","k-subsets","combinatorial sampling"],"falsifier":"Run the algorithm on large n and k near n/2, measure the exact average number of random bits consumed per generated word, and compare it to log2(binomial(n,k)); if the measured consumption stays bounded away from the entropy value by a constant factor, the near-optimality claim fails.","tokens_in":2495,"feed_emoji":"♻️","tokens_out":608,"duration_ms":14189,"temperature":0.7,"pith_summary":"Generating binary words of length n with exactly k ones is equivalent to uniformly sampling k-subsets and requires random bits whose cost can be high. The paper introduces random bit recycling as a way to reuse bits during generation. This produces the desired words in linear time with bit consumption that approaches the information-theoretic minimum set by the entropy of the binomial coefficient. A sympathetic reader cares because the method directly attacks the practical expense of randomness while preserving exact uniformity.","feed_headline":"Recycling random bits samples k-subsets near entropy limit","feed_subtitle":"Generates fixed-weight binary words in linear time while using almost the minimum random bits required by information theory.","key_machinery":"Random bit recycling, a paradigm that reuses portions of previously consumed random bits to minimize total consumption while enforcing uniformity and linear runtime.","core_discovery":"The authors introduce the random bit recycling paradigm and use it to build an algorithm that generates uniform random binary words of length n with Hamming weight k in linear time, with the number of random bits consumed made arbitrarily close to the Shannon entropy lower bound log2(binomial(n,k)).","pith_inferences":["The technique may reduce the randomness requirement in downstream randomized algorithms that rely on subset sampling.","In hardware or embedded contexts the method could lower the demand on true random number generators.","Extensions to approximate sampling or to weighted subsets appear compatible with the recycling structure."],"forward_implications":["Uniform sampling of k-subsets becomes practical in settings where random bits are expensive or limited.","The generation procedure matches the information-theoretic minimum up to an arbitrarily small additive overhead.","The linear-time guarantee makes the method suitable for large-scale combinatorial sampling tasks.","The same recycling idea can be applied to other uniform generation problems whose entropy is known."],"fun_headline_variants":["Bit recycling samples k-subsets near entropy bound","Generates Hamming weight k words with near-minimal random bits","Linear-time uniform binary word generation via bit recycling","Random bit reuse achieves near-optimal entropic k-subset sampling"],"cache_read_input_tokens":64,"weakest_assumption_plain":"The recycling mechanism can be realized in an algorithm that simultaneously achieves linear runtime, exact uniformity of the output, and random-bit consumption arbitrarily close to the entropy bound without hidden overheads or correctness violations.","fun_headline_variants_meta":{"raw":{"variants":["Bit recycling samples k-subsets near entropy bound","Generates Hamming weight k words with near-minimal random bits","Linear-time uniform binary word generation via bit recycling","Random bit reuse achieves near-optimal entropic k-subset sampling"]},"model":"grok-4.3","cost_usd":0.003914,"raw_usage":{"total_tokens":1916,"prompt_tokens":486,"num_sources_used":0,"completion_tokens":58,"cost_in_usd_ticks":39137000,"prompt_tokens_details":{"text_tokens":486,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1372,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":486,"tokens_out":58,"duration_ms":9914,"temperature":1.0,"reasoning_tokens":1372,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-06-27T05:10:59.172811+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"Run the algorithm on large n and k near n/2, measure the exact average number of random bits consumed per generated word, and compare it to log2(binomial(n,k)); if the measured consumption stays bounded away from the entropy value by a constant factor, the near-optimality claim fails.","supporting_citations":[],"review_version":1}