Pith. sign in

REVIEW 4 minor 50 references

On Computational Hardness of Mistake-Bounded Language Generation: A Random-Oracle Query Separation

T0 review · 0 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A single random-oracle graph family makes unbounded generation perfect while forcing every fixed polynomial-query generator into exponentially many expected mistakes on some target.

desk verdict A sound, clean random-oracle separation with an explicitly scoped uniformity caveat; it deserves a serious referee. read the letter →

arxiv 2608.05029 v1 pith:G7ZI3B4L submitted 2026-08-05 cs.CC

Xiaoyu Li , Andi Han , Dai Shi , Jiaojiao Jiang , Junbin Gao This is my paper · ORCID
classification cs.CC MSC 68Q1568Q32
keywords randomoraclemistake-boundedgenerationclosuredimensionquerycomplexitylanguageinthelimitcumulativemistakesfresh-pointpredictionrandom-functiongraph
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper asks whether a countable family of infinite languages can be simultaneously trivial for an informationally unlimited generator and hard for every computationally bounded one. It answers yes, relative to a random oracle, by constructing languages $L_b=\{E(b,i):i\in\mathbb N\}$ whose elements are tagged oracle values $E(b,i)=\langle\lambda,i,H(b,i)\rangle$ indexed by a hidden seed $b$. On the same oracle, almost surely, an unbounded generator makes zero mistakes on every target under every complete enumeration, while every uniform generator with polynomially many oracle queries per output has some constant $c_G>0$ forcing more than $2^{c_G\lambda}$ expected mistakes on some length-$\lambda$ target within its first $2(\lceil 2^{c_G\lambda}\rceil+1)$ outputs. Infinite accidental agreement among consistent seeds makes the first fact possible; the hidden-seed coupling makes the second. The paper thus separates information-theoretic ease from bounded-access computational hardness in a single construction.

What carries the argument

The central object is the random-function graph collection $\mathcal C^*$: each seed $b$ indexes one infinite row language $L_b$ whose $i$-th element is the tagged oracle value $\langle\lambda,i,H(b,i)\rangle$, so every row has a unique index-$i$ element and membership costs one oracle query. Two mechanisms carry the argument. First, infinite accidental agreement: for any fixed set of consistent seeds, the independent oracle coordinates give, almost surely, infinitely many indices at which all those rows share a value, which yields infinite closures, closure dimension zero, and the cold-start common point used by the unbounded zero-mistake generator. Second, the planted-coupling predictability bound: if an algorithm is given finitely many samples from a hidden row, any $T$-query adaptive run can be shadowed on an independently planted oracle, so it tests at most $T$ seeds independently of the hidden seed and has success probability at most $(T+2)2^{-\lambda}$ at producing a fresh target value; a dense-band predictor reduction then converts any low-mistake generator into such a fresh-point predictor.

What would settle it

A concrete disproof would be a uniform polynomial-query oracle machine $G$ for which, for every $c>0$, all sufficiently large $\lambda$, and all seeds $b\in\{0,1\}^\lambda$, the expected mistakes within $W=2(\lceil 2^{c\lambda}\rceil+1)$ canonical outputs are at most $2^{c\lambda}$. The sharpest place to test the mechanism is Lemma 3.2: an adaptive algorithm that, for some $T=2^{\alpha\lambda}$ with $\alpha>0$, recovers a fresh target value from the canonical samples with probability $2^{-o(\lambda)}$ — or finds the hidden seed with probability better than $T2^{-\lambda}$ — would falsify the planted-coupling bound on which the predictor reduction rests.

Watch

Extended reading notes

Core claim

Relative to a random oracle $H$, the countable collection $\mathcal C^*$ of graph languages $L_b=\{\langle\lambda,i,H(b,i)\rangle:i\in\mathbb N\}$, with $b\in\{0,1\}^\lambda$, has closure dimension zero almost surely. On that same oracle an unbounded generator makes zero mistakes on every target $L_b$ under every complete distinct enumeration, the empty-history output being secured by an infinite all-row agreement among the $2^\lambda$ seeds of a length. Yet every uniform polynomial-query oracle generator $G$ has a constant $c_G>0$ such that at all sufficiently large $\lambda$ some seed $b$ incurs $\mathbb E_G[\mathrm{mist}_{<W_G(\lambda)}(G,L_b,\sigma_b)]>2^{c_G\lambda}$ expected mistakes within $W_G(\lambda)=2(\lceil 2^{c_G\lambda}\rceil+1)$ outputs under the canonical enumeration; Section 4 extends this to every precommitted index schedule. The exponential floor is not eventual failure: it is the cumulative cost of searching for fresh target values before an efficient generator can find them.

Load-bearing premise

The load-bearing premise is that every efficient generator is one fixed uniform oracle machine with no per-length advice and no access to the target seed; the proof's final countable-intersection step over all uniform machines depends on this, and the paper notes that a generator given the seed can enumerate $L_b$ with zero mistakes.

Editorial extensions

If this is right

  • Every fixed polynomial-query generator, including every polynomial-time generator, has a worst-case exponential mistake floor: some target at each large length forces $2^{\Omega(\lambda)}$ expected mistakes within an explicit exponential horizon.
  • The same realized oracle supports both sides, so the separation is not an averaging artefact: the zero-mistake unbounded generator and the hard seeds coexist with probability one.
  • Given the seed $b$, membership in $L_b$ is decidable in polynomial time with one oracle query, so hardness does not come from hiding the target once its index is known.
  • The lower bound survives arbitrary precommitted enumeration schedules, so it is not an artefact of the canonical ascending order; only target-dependent or oracle-dependent orders can trivialize it.
  • The exponent $c_G$ must depend on the generator: for every constant $c_0>0$ there is a deterministic uniform polynomial-query generator whose total mistakes stay below $2^{c_0\lambda}$ almost surely eventually.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the random-oracle separation reflects a general principle, then any closure-search procedure that is computationally bounded must pay a mistake cost roughly exponential in the seed length whenever the family hides its index; this suggests defining an effective closure dimension that charges per-output queries.
  • The sharp boundary between schedule robustness and target-dependent triviality hints that the right notion of a hard enumeration is one precommitted independently of the hidden seed; target-dependent orders encode the seed and should be excluded in future standard-model definitions.
  • The five-property checklist (R1)-(R5) is a testable design target: building a public deterministic family with the stated exponential fresh-point unpredictability and infinite common points would lift the separation out of the random-oracle model; finite-block pseudorandom error-correcting codes already have the hidden-codeword flavor but lack the required infinite-index common-point property.
  • A natural next experiment is to measure the same zero-versus-exponential gap on partial or feedback-augmented variants: the present model is feedback-free, and existing feedback models change the information the generator receives, so the query cost of locating fresh points may behave differently.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 4 minor

Summary. The paper introduces a security-parameterized model of mistake-bounded language generation in which computational cost is measured by per-output oracle queries. Its main result (Theorem 3.9) is a random-oracle separation: for the collection C* of graph languages L_b = {<lambda,i,H(b,i)>}, almost surely C* has closure dimension 0, an unbounded generator makes zero mistakes on every target under every complete distinct enumeration, and every uniform polynomial-query generator G has a constant c_G > 0 such that, on all sufficiently large lengths, some seed forces more than 2^{c_G lambda} expected mistakes within an explicit exponential horizon. The proof has three stages: infinite common-index events from Borel-Cantelli (Lemma 3.1), a planted-coupling fresh-point unpredictability bound (Lemma 3.2), and a reduction from low mistake counts to a fresh-point predictor (Lemma 3.6), followed by a Tonelli-Markov-Borel-Cantelli conversion to a single oracle (Theorem 3.8). Section 4 extends the lower bound to target-independent precommitted schedules, and Section 5 gives a checklist for standard-model attempts.

Significance. The result is a clean and nontrivial query-complexity separation: it shows that information-theoretic ease (closure dimension zero plus zero-mistake generation) can coexist with exponential worst-case expected mistakes under bounded-query access, relative to a random oracle. The planted-coupling argument handles adaptive queries cleanly, the countable-intersection step makes one oracle simultaneously hard for all uniform machines, and the paper is explicit about its scope: hardness is proved for uniform, advice-free generators, while per-length advice and standard-model instantiations are left open. These limitations are stated in the manuscript rather than hidden, so they do not undermine the theorem as formulated. The construction is simple enough to serve as a test case for future structural theories of efficient closure generation. I find no load-bearing flaw in the central derivation.

minor comments (4)
  1. [Appendix B, Proposition B.2] The displayed bound uses (T_W + 1)2^{-lambda}, but Lemma 3.2 supplies (T + 2)2^{-lambda} with T the number of predictor queries, which is T_W in this setting; the constant should be T_W + 2 (or Lemma 3.2 should be tightened). The exponential conclusion of Theorem 4.2 is unaffected by this additive change.
  2. [Definition 2.3] The phrase 'while computing its i-th output' does not state whether i is 0-indexed; since Definition 2.1 names outputs a_0, a_1, ... and the later query sums run from i = 0, please make the indexing convention explicit to avoid off-by-one ambiguity.
  3. [Lemma 3.2 proof, part (ii)] The sentence that H(beta_0, j) is 'queried by neither run' is correct but relies on the coupling fact that on the event not-Q_T the shadow run also never queries seed beta_0; adding a one-sentence justification would improve readability.
  4. [Abstract] The abstract says 'polynomially many oracle queries in lambda and the output index i'; the model charges queries per output, so I suggest rewording to 'per output' to match Definition 2.3.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the random-oracle construction is self-contained and both sides of the separation are proved directly.

full rationale

The paper's central construction is self-contained: the collection C* is defined directly from the random oracle H via E(b,i)=<lambda,i,H(b,i)>, and the two sides of the separation are proved independently against the same oracle. The information-theoretic easiness side (Lemma 3.1(S2), Lemma 3.4) is a direct Borel-Cantelli argument over independent oracle coordinates, and the paper explicitly states that it uses only the definition of closure dimension from [RLT25], proving Cdim(C*)=0 directly instead of importing a characterization. The computational hardness side (Lemmas 3.2, 3.6; Propositions 3.7; Theorem 3.8) reduces a low-mistake generator to a fresh-point predictor whose success probability is bounded by the planted-coupling unpredictability of the random oracle; the predictor's query count is computed from the generator's own per-output cap. No parameter is fitted to the target and then renamed a prediction: the constant c_G is fixed from the generator's query degree, and the hard seed is shown to exist by a Tonelli-Markov-Borel-Cantelli argument over the fraction of easy seeds. The self-citations that appear ([LHJG26a], [LHJG26b], [LHS+26]) are limited to the Discussion as open-problem motivation and are not load-bearing. The paper also explicitly acknowledges its scope limitations in Remark 3.12 (hardness is for uniform machines without target-dependent or per-length advice) and Section 5.1 (no standard-model family is asserted); these are honest model boundaries, not circularities. No equation in the derivation reduces by construction to an input, so the appropriate finding is no significant circularity.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper constructs C* explicitly from a random oracle; it introduces no speculative entities. All primitives (random oracle, generation game, mistake score, closure dimension) come from prior literature or are defined as part of the model. There are no fitted constants: the per-generator exponent c_G is a theorem parameter, not a number fitted to data.

assumptions (5)
  • domain assumption Random oracle H is sampled uniformly and independently on each input (b,i); all parties access H only through queries.
    Definition 2.6 and Appendix A define the probability space; the separation is relative to this oracle model.
  • standard math Standard probability tools (Markov, Tonelli, first and second Borel-Cantelli, countable full-measure intersection) are valid.
    Section 2.4; repeatedly used in Lemmas 3.1, 3.6, 3.7, Theorems 3.8, 4.2.
  • standard math Uniform polynomial-query generators and uniform precommitted schedulers form countable families.
    Finite descriptions of Turing machines; used to intersect probability-one events in Theorems 3.8 and 4.2.
  • domain assumption Each generator's output computation halts on every valid history for every oracle.
    Definition 2.2; ensures the mistake count is measurable and predictors are well defined.
  • ad hoc to paper The tuple encoding is self-delimiting, so languages of different seed lengths never collide.
    Definition 2.6; used in (S1) to guarantee one oracle query determines membership.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On Computational Hardness of Mistake-Bounded Language Generation: A Random-Oracle Query Separation." pith.science (2026). https://pith.science/paper/G7ZI3B4L

@misc{pith2026260805029,
  author       = {Pith},
  title        = {Pith review of: On Computational Hardness of Mistake-Bounded Language Generation: A Random-Oracle Query Separation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/G7ZI3B4L}},
  note         = {Machine review of arXiv:2608.05029}
}
abstract

Generation in the limit guarantees eventual generation for every countable collection of infinite languages in the model of Kleinberg and Mullainathan [KM24], while closure dimension characterizes stronger information-theoretic guarantees [RLT25]. Neither restricts per-output computation. The cumulative-mistake objective in mistake-bounded generation makes finite failure prefixes quantitative [KPR26], and a per-output query budget exposes their computational source. Polynomial-time algorithms are known for parities, conjunctions, and monotone functions with polynomially many maxterms [JKO26]. We ask whether information-theoretic ease can coexist with bounded-access computational hardness. Relative to a random oracle $H$, we answer yes by constructing a countable collection $C^\star$ of infinite languages with closure dimension zero. Almost surely on the same $H$, an unbounded generator makes zero mistakes on every target and every complete distinct enumeration. Yet, writing $\lambda$ for the target-seed length, every fixed uniform generator $G$ with polynomially many oracle queries in $\lambda$ and the output index $i$ has a constant $c_G>0$ such that, for every sufficiently large $\lambda$, some target incurs more than $2^{c_G\lambda}$ expected mistakes within its first $2(\lceil 2^{c_G\lambda}\rceil+1)$ canonical outputs. Infinite accidental agreement enables exhaustive search; sparse queries hide fresh target values. Thus, in the random-oracle model, zero-mistake information-theoretic generation coexists with a generator-dependent exponential lower bound on worst-case expected mistakes under polynomial-query access.

Figures

Figures reproduced from arXiv: 2608.05029 by the authors.

Figure 1
Figure 1. One oracle graph, two access regimes. Unbounded search finds recurring all-row agreement; polynomial-query access can miss fresh target values. The resulting zero-versus-exponential mistake separation is formalized in Theorem 3.9. 1 arXiv:2608.05029v1 [cs.CC] 5 Aug 2026 [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. summarizes the coupling that makes the bound robust to adaptive queries. Independent sources 𝑄 fixed; 𝑏, 𝑔, (𝑦𝑖 )𝑖∈𝑄 , 𝜌𝐴 independent 𝑆 = {(𝑖, 𝑦𝑖 ) : 𝑖 ∈ 𝑄} Plant at the hidden row 𝐻(𝑏, 𝑖) = 𝑦𝑖 for 𝑖 ∈ 𝑄 𝐻(𝛽, 𝑖) = 𝑔(𝛽, 𝑖) otherwise Shadow execution run 𝐴 𝑔 (𝑆) with coins 𝜌𝐴 transcript independent of 𝑏 Tested rows Seeds ⊥ 𝑏 |Seeds| ≤ 𝑇 True row tested P[𝑏 ∈ Seeds] ≤ 𝑇2 −𝜆 No true-row query fresh-value guess ≤ 2 −𝜆 co… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

50 extracted references · 38 canonical work pages

  1. [1]

    Advances in Neural Information Processing Systems 37 (NeurIPS 2024) , pages =

    Jon Kleinberg and Sendhil Mullainathan , title =. Advances in Neural Information Processing Systems 37 (NeurIPS 2024) , pages =. 2024 , doi =. 2404.06757 , archivePrefix =

    arXiv 2024

  2. [2]

    Proceedings of the 38th Conference on Learning Theory (COLT 2025) , series =

    Vinod Raman and Jiaxun Li and Ambuj Tewari , title =. Proceedings of the 38th Conference on Learning Theory (COLT 2025) , series =. 2025 , eprint =

    work page 2025

  3. [3]

    Proceedings of the 38th Conference on Learning Theory (COLT 2025) , series =

    Moses Charikar and Chirag Pabbaraju , title =. Proceedings of the 38th Conference on Learning Theory (COLT 2025) , series =. 2025 , eprint =

    work page 2025

  4. [4]

    Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC 2025) , pages =

    Alkis Kalavasis and Anay Mehrotra and Grigoris Velegkas , title =. Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC 2025) , pages =. 2025 , doi =. 2411.09642 , archivePrefix =

    arXiv 2025

  5. [5]

    Proceedings of the 37th International Conference on Algorithmic Learning Theory (ALT 2026), to appear , year =

    Alkis Kalavasis and Anay Mehrotra and Grigoris Velegkas , title =. Proceedings of the 37th International Conference on Algorithmic Learning Theory (ALT 2026), to appear , year =. 2412.18530 , archivePrefix =

    arXiv 2026

  6. [6]

    Proceedings of the 42nd International Conference on Machine Learning (ICML 2025) , volume =

    Ananth Raman and Vinod Raman , title =. Proceedings of the 42nd International Conference on Machine Learning (ICML 2025) , volume =. 2025 , eprint =

    work page 2025

  7. [7]

    Proceedings of the 66th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2025) , pages =

    Jon Kleinberg and Fan Wei , title =. Proceedings of the 66th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2025) , pages =. 2025 , doi =. 2504.14370 , archivePrefix =

    arXiv 2025

  8. [8]

    2026 , eprint =

    Ziyi Cai and Shuangping Li and Yiheng Shen and Kangning Wang and Peng Zhang , title =. 2026 , eprint =

    work page 2026

Show all 50 references
  1. [9]

    Proceedings of the 38th Conference on Learning Theory (COLT 2025) , series =

    Hristo Papazov and Nicolas Flammarion , title =. Proceedings of the 38th Conference on Learning Theory (COLT 2025) , series =. 2025 , eprint =

    2025

  2. [10]

    Proceedings of the 39th Conference on Learning Theory (COLT 2026) , series =

    Moses Charikar and Jon Kleinberg and Chirag Pabbaraju , title =. Proceedings of the 39th Conference on Learning Theory (COLT 2026) , series =. 2026 , eprint =

    2026

  3. [11]

    2026 , eprint =

    Irene Strauss and Alexandra Butoi and Ryan Cotterell , title =. 2026 , eprint =

    2026

  4. [12]

    2025 , eprint =

    Amin Karbasi and Omar Montasser and John Sous and Grigoris Velegkas , title =. 2025 , eprint =

    2025

  5. [13]

    Proceedings of the 42nd International Conference on Machine Learning (ICML 2025) , series =

    Charlotte Peale and Vinod Raman and Omer Reingold , title =. Proceedings of the 42nd International Conference on Machine Learning (ICML 2025) , series =. 2025 , eprint =

    2025

  6. [14]

    Ash and Cyril Zhang and Andrej Risteski , title =

    Edoardo Botta and Yuchen Li and Aashay Mehta and Jordan T. Ash and Cyril Zhang and Andrej Risteski , title =. Proceedings of the 42nd International Conference on Machine Learning (ICML 2025) , series =. 2025 , eprint =

    2025

  7. [15]

    Advances in Neural Information Processing Systems 38 (NeurIPS 2025, Spotlight) , year =

    Steve Hanneke and Amin Karbasi and Anay Mehrotra and Grigoris Velegkas , title =. Advances in Neural Information Processing Systems 38 (NeurIPS 2025, Spotlight) , year =. 2506.18642 , archivePrefix =

    2025 arXiv

  8. [16]

    Proceedings of the 2026 ACM-SIAM Symposium on Discrete Algorithms (SODA 2026) , pages =

    Yannan Bai and Debmalya Panigrahi and Ian Zhang , title =. Proceedings of the 2026 ACM-SIAM Symposium on Discrete Algorithms (SODA 2026) , pages =. 2026 , doi =. 2507.15319 , archivePrefix =

    2026

  9. [17]

    Proceedings of the 37th International Conference on Algorithmic Learning Theory (ALT 2026) , series =

    Moses Charikar and Chirag Pabbaraju , title =. Proceedings of the 37th International Conference on Algorithmic Learning Theory (ALT 2026) , series =. 2026 , eprint =

    2026

  10. [18]

    2025 , eprint =

    Moses Charikar and Chirag Pabbaraju and Ambuj Tewari , title =. 2025 , eprint =

    2025

  11. [19]

    Language Generation in the Limit: Complexity Barriers and Implications for Learning , booktitle =

    Marcelo Arenas and Pablo Barcel\'. Language Generation in the Limit: Complexity Barriers and Implications for Learning , booktitle =. 2026 , eprint =

    2026

  12. [20]

    Proceedings of the 58th Annual ACM Symposium on Theory of Computing (STOC 2026) , pages =

    Jon Kleinberg and Fan Wei , title =. Proceedings of the 58th Annual ACM Symposium on Theory of Computing (STOC 2026) , pages =. 2026 , doi =. 2511.05295 , archivePrefix =

    2026

  13. [21]

    Proceedings of the 39th Conference on Learning Theory (COLT 2026) , pages =

    Anay Mehrotra and Grigoris Velegkas and Xifan Yu and Felix Zhou , title =. Proceedings of the 39th Conference on Learning Theory (COLT 2026) , pages =. 2026 , volume =. 2511.07417 , archivePrefix =

    2026

  14. [22]

    Kornaropoulos , title =

    Antonios Anastasopoulos and Giuseppe Ateniese and Evgenios M. Kornaropoulos , title =. 2026 , eprint =

    2026

  15. [23]

    Proceedings of the 43rd International Conference on Machine Learning (ICML 2026) , year =

    Aaron Li and Ian Zhang , title =. Proceedings of the 43rd International Conference on Machine Learning (ICML 2026) , year =. 2601.21237 , archivePrefix =

    2026 arXiv

  16. [24]

    Agnostic Language Identification and Generation , year =

    Mikael M. Agnostic Language Identification and Generation , year =. 2601.23258 , archivePrefix =

    arXiv

  17. [25]

    2026 , eprint =

    Jiaxun Li and Vinod Raman and Ambuj Tewari , title =. 2026 , eprint =

    2026

  18. [26]

    Proceedings of the 43rd International Conference on Machine Learning (ICML 2026) , year =

    Giorgio Racca and Michal Valko and Amartya Sanyal , title =. Proceedings of the 43rd International Conference on Machine Learning (ICML 2026) , year =. 2603.11784 , archivePrefix =

    2026 arXiv

  19. [27]

    2026 , eprint =

    Jon Kleinberg and Fan Wei , title =. 2026 , eprint =

    2026

  20. [28]

    2026 , eprint =

    Xiaoyu Li and Andi Han and Jiaojiao Jiang and Junbin Gao , title =. 2026 , eprint =

    2026

  21. [29]

    Proceedings of the 39th Conference on Learning Theory (COLT 2026) , pages =

    Anay Mehrotra and Grigoris Velegkas and Xifan Yu and Felix Zhou , title =. Proceedings of the 39th Conference on Learning Theory (COLT 2026) , pages =. 2026 , volume =. 2604.08504 , archivePrefix =

    2026 arXiv

  22. [30]

    2026 , eprint =

    Jon Kleinberg and Charlotte Peale and Omer Reingold , title =. 2026 , eprint =

    2026

  23. [31]

    2026 , eprint =

    Atul Ganju and Travis McVoy and Shaddin Dughmi and Shang-Hua Teng , title =. 2026 , eprint =

    2026

  24. [32]

    2026 , eprint =

    Jon Kleinberg and Anay Mehrotra and Amin Saberi and Grigoris Velegkas , title =. 2026 , eprint =

    2026

  25. [33]

    2026 , eprint =

    Xiaoyu Li and Andi Han and Dai Shi and Zheng Gao and Jiaojiao Jiang and Junbin Gao , title =. 2026 , eprint =

    2026

  26. [34]

    Polynomial-Time Mistake-Bounded Language Generation , year =

    H\'. Polynomial-Time Mistake-Bounded Language Generation , year =. 2606.16077 , archivePrefix =

  27. [35]

    Proceedings of the 39th Conference on Learning Theory (COLT 2026) , series =

    Nicolas Flammarion and Chirag Pabbaraju and Hristo Papazov and Miltiadis Stouras and Ola Svensson , title =. Proceedings of the 39th Conference on Learning Theory (COLT 2026) , series =. 2026 , eprint =

    2026

  28. [36]

    2026 , eprint =

    Debmalya Panigrahi and Fan Wei and Ian Zhang , title =. 2026 , eprint =

    2026

  29. [37]

    2026 , month = may, url =

    Anay Mehrotra , title =. 2026 , month = may, url =

    2026

  30. [38]

    Mark Gold , title =

    E. Mark Gold , title =. Information and Control , volume =. 1967 , doi =

    1967

  31. [39]

    Information and Control , volume =

    Dana Angluin , title =. Information and Control , volume =. 1980 , doi =

    1980

  32. [40]

    Kearns and Leslie G

    Michael J. Kearns and Leslie G. Valiant , title =. Journal of the ACM , volume =. 1994 , doi =

    1994

  33. [41]

    2025 , eprint =

    Satwik Bhattamishra and Phil Blunsom and Varun Kanade , title =. 2025 , eprint =

    2025

  34. [42]

    Journal of the ACM , volume =

    Leonard Pitt , title =. Journal of the ACM , volume =. 1989 , doi =

    1989

  35. [43]

    Smith , title =

    Carl H. Smith , title =. Journal of the ACM , volume =. 1982 , doi =

    1982

  36. [44]

    Conference on Learning Theory (COLT 2020) , pages =

    Noga Alon and Amos Beimel and Shay Moran and Uri Stemmer , title =. Conference on Learning Theory (COLT 2020) , pages =. 2020 , eprint =

    2020

  37. [45]

    Algorithmic Learning Theory (ALT 2021) , pages =

    Badih Ghazi and Noah Golowich and Ravi Kumar and Pasin Manurangsi , title =. Algorithmic Learning Theory (ALT 2021) , pages =. 2021 , eprint =

    2021

  38. [46]

    Advances in Cryptology --- CRYPTO 2024, Part VI , series =

    Miranda Christ and Sam Gunn , title =. Advances in Cryptology --- CRYPTO 2024, Part VI , series =. 2024 , doi =. 2402.09370 , archivePrefix =

    2024 arXiv

  39. [47]

    Proceedings of the 1st ACM Conference on Computer and Communications Security (CCS) , pages =

    Mihir Bellare and Phillip Rogaway , title =. Proceedings of the 1st ACM Conference on Computer and Communications Security (CCS) , pages =. 1993 , doi =

    1993

  40. [48]

    Journal of the ACM , volume =

    Ran Canetti and Oded Goldreich and Shai Halevi , title =. Journal of the ACM , volume =. 2004 , doi =. cs/0010019 , archivePrefix =

    2004 arXiv

  41. [49]

    Proceedings of the 43rd International Conference on Machine Learning (ICML 2026) , year =

    Steve Hanneke and Amin Karbasi and Anay Mehrotra and Grigoris Velegkas , title =. Proceedings of the 43rd International Conference on Machine Learning (ICML 2026) , year =

    2026

  42. [50]

    2023 , eprint =

    Niki Hasrati and Shai Ben-David , title =. 2023 , eprint =

    2023

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.