- Rating
- 3
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
Given a hidden set with , say an adversary has access to only noisy observations of , say 's such that . The authors consider the problem of finding a single subspace such that is covered by a few cosets of . As for every compatible , any union of cosets covering half of hits each in at least points. Ruzsa covering lemma then turns that into a cover of . Thm 1 and 3 follow this protocol to show positive results by using only uniform samples from , and when membership queries are additionally allowed. Thm 2 is a negative result that no polynomial-time learner can achieve constant covering cost.
Critical strengths
S1: The idea of using a persistent BSG core (at retained factor and doubling) is a nice one. It allows the authors to support deterministic membership tests and exact uniform sampling. Perhaps this idea can be used in other problems as well.
Critical weaknesses
W1: I think the paper is missing an important citation
- Srinivasan Arunachalam and Arkopal Dutt. 2026. Learning Stabilizer Structure of Quantum States. STOC 2026. My main concern is that the novelty of the proof pipeline (what is new in this work) is not properly stated. The above work follows the same structure of sampling, BSG Test to get a small doubling set, apply algorithmic PFR and repeat.
Questions for authors
Clarification Requests
- See W1 above.
Suggestions
- I think the authors can take a look at this concurrent work to improve their complexity bounds (around Theorem 23 where they use PFR).
5 comments
Response to 77oD Part 2: Improved complexity using polynomial-time PFR
Your recommendation of the newer PFR algorithm led to a substantive improvement: incorporating Arunachalam, Dutt, Grewal, and Gupte [1] strengthens the moderate-corruption learner from FPT dependence on to polynomial dependence on both and . We also updated the full-range bound and recalculated input-sample usage.
1. Improved learning bounds [Q2 (suggestion of improved complexity)].
For , the submitted bound was . Samples, membership queries, and time now all satisfy
$ \operatorname{poly}(n,K,\log(1/\rho)), $
where is the failure probability. The output retains the simultaneous guarantee for all compatible supports, with polynomial covering cost in .
One core suffices in this regime. Its doubling is and its construction and membership costs are polynomial in . Applying the new PFR theorem therefore makes the full composition polynomial.
For arbitrary , let and . The revised bound is $ \text{queries and time}\le(\kappa\Lambda)^{O(\sqrt\kappa)}, $ with polynomial sample complexity in . The remaining XP dependence comes from recursively evaluating residual predicates over peels.
Revision: Theorem 4 states the improved bounds, with updated resource analyses in Appendices E and G. The matched passive/query separation already holds with the original PFR routine; the replacement improves the parameter dependence of the positive algorithm.
2. The interface needed for the replacement.
Revision: We replaced the previous size-oblivious PFR construction in Appendix C with the imported polynomial-time theorem and the finite sampling interface needed by our learner.
Theorem 1.2 of [1] takes membership queries and independent uniform samples without the input set's cardinality. Section 6 and Algorithm 4 of [1] impose predetermined time, sample, and query budgets. Our Theorem 24 records this fixed-input interface.
Our Proposition 25 establishes the adaptive invocation: conditioning on the past fixes a valid small-doubling core and its deterministic predicate. Conditional on finite rejection success, the samples have the exact product law; fresh PFR randomness then gives the conditional guarantee. The outer analysis charges core-membership evaluations to the observed-set oracle.
3. Input samples are counted separately from time.
For core doubling , failure budget , and , Appendix C derives the predetermined bound $ s_{\mathrm{PFR}}(n,L,\delta)\le\left\lceil C_s(1+L)^{a_s}\bigl[(n+1)\log(n+2)+u\bigr]u\right\rceil $ for absolute constants . At fixed and constant confidence, this is input samples.
The count includes samples consumed by constructed density oracles, with finite extraction caps before repetition. Appendix C gives the stage-by-stage accounting for Algorithm 4 of [1]; Appendices E and G propagate these costs through the full-range and moderate-corruption learners.
Thank you again for your comments.
Reference
[1] Srinivasan Arunachalam, Arkopal Dutt, Sabee Grewal, and Aparna Gupte. Marton's Conjecture in Polynomial Time. arXiv:2609.20771, 2026.
Follow-up to 77oD on our response
Thank you again for your insightful suggestions, which helped us clarify the contribution and improve the complexity bounds. Our responses and revised manuscript are now available. We would be grateful to hear whether these address your concerns about the relation to prior work, and would greatly value any further questions or suggestions.
Response to 77oD Part 1: Persistent cores–contribution and prior work
Thank you very much for identifying the relevant BSG–PFR precedent and for recognizing the potential usefulness of the persistent core. Your comment helped us sharpen the distinction between an established algorithmic route and the quantitative primitive developed here. We should have cited Arunachalam–Dutt [1] in the original submission. We have added the citation and revised the contribution discussion to make both the connection and the additional guarantees explicit. Section and theorem references refer to the revised manuscript.
1. The quantitative contribution [W1 and Q1 (clarification request): what is new in the proof pipeline].
Our compiler operates on a general finite support S⊆F2n through uniform samples and membership queries, without enumerating S. Under the premise E(S)≥α∣S∣3, it constructs, with high probability, a finite record D defining a core with $ |Y_D|\ge c\sqrt\alpha\,|S|,\ |Y_D+Y_D|\le C\alpha^{-4}|Y_D|. $
The same record supports deterministic membership evaluation and independent uniform samples from YD, conditional on the finite sampling blocks succeeding. The theorem includes separate soundness and completeness guarantees and worst-case resource bounds, allowing the core to be used repeatedly after an adaptive history.
We turn the sharp retained-mass guarantee of Reiher–Schoen [3] into an algorithm for an implicitly accessed support. It constructs a reusable core with the membership, sampling, and error guarantees required by the learner.
These bounds determine the peeling depth. Writing ε=1−η, the shared corruption budget gives a residual-energy threshold α⋆=Θ(ε/K). On the joint success event, each extracted core retains an Ω(ε/K) fraction of its residual. Peeling continues only while that residual has constant density in B, giving at most O(K/ε) rounds. PFR processes the same core that is subsequently removed.
The accompanying Lean 4 package machine-checks the compiler’s soundness and completeness, exact sampling from its fixed output core, and explicit finite resource bounds, with a map to the corresponding statements in the paper.
2. Relation to the earlier algorithms [W1: attribution and technical distinction].
Arunachalam–Dutt [1] develop implicit BSG access from Bell-difference sampling and combine it with PFR and algebraic recovery. Their analysis adapts the structured-sandwich approach of Tulsiani–Wolf [2] to the nonuniform distribution arising in quantum learning. This is a direct precedent for the overall BSG–PFR route.
Our theorem applies to any finite support satisfying the energy premise, given uniform samples and membership queries. Structured sandwiches provide precedents for fixed-set access; our theorem supplies the stated mass, doubling, and resource bounds for the general energy inputs arising in residual peeling.
Revision: The revised introduction and Section 6 now make this comparison where the construction is introduced. Appendix M.4 gives the fuller account of the access models and guarantees.
3. What the construction enables beyond a core cover [W1: significance of the contribution].
The final learning objective concerns every latent support compatible with one corrupted observation. Peeling and lifting first produce a list that serves each compatible support, possibly through different entries. A fresh-sample coverage rule then selects one entry whose covering guarantee holds simultaneously for all of them.
This common-output construction also supports the matched access comparison: at the same constant quotient-covering budget, samples suffice statistically, polynomial-time passive learning is hard under the specified search-LPN assumption, and membership queries permit polynomial-time recovery at fixed structural parameters. The comparison holds even when the latent support is unique.
References
[1] Srinivasan Arunachalam and Arkopal Dutt. Learning Stabilizer Structure of Quantum States. STOC, 2026.
[2] Madhur Tulsiani and Julia Wolf. Quadratic Goldreich–Levin Theorems. SIAM Journal on Computing, 2014.
[3] Christian Reiher and Tomasz Schoen. Note on the Theorem of Balog, Szemerédi, and Gowers. Combinatorica, 2024.