Pith. sign in

REVIEW 2 major objections 3 minor 59 references

How to Verify Consistency of Probabilistic Claims

T0 review · 2 major / 3 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read This paper constructs an interactive PCP in which a polynomial-time verifier certifies approximate consistency of a circuit-specified probabilistic model by evaluating the model at a few points and reading a few locations of an…

desk verdict Good NP result, but the main IPCP theorem has a real soundness gap that looks fixable only with self-correction. read the letter →

arxiv 2608.11181 v1 pith:KLC72B3B submitted 2026-08-11 cs.CC cs.AIcs.LG

Orr Paradise , Oliver Richardson , Yoshua Bengio , Shafi Goldwasser This is my paper · ORCID
classification cs.CCcs.AIcs.LG MSC 68Q1568Q1703B48
keywords probabilisticconsistencyinteractivePCPReed–Mullerencodingsum-checkprotocolCarathéodorytheoremNPcertificatepredictivemodelverificationclaims
topics P versus NP
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

This paper asks whether a probabilistic predictor that implicitly makes exponentially many conditional-probability claims can be certified as self-consistent in polynomial time. The central result is an interactive PCP: given circuits $(P,Q)$ describing the predictor, a polynomial-time verifier evaluates the circuits at a few points, reads a few locations of an exponentially long proof oracle, and interacts with a single untrusted prover to certify approximate consistency up to a tunable additive gap. En route, the paper shows that approximate $\ell^2$-consistency of $m$ explicit claims lies in NP with $O(mn + \log B)$-bit certificates, and that a small completeness-soundness gap reduces the certificate to low-precision weights of length $O(m(n + \log(m/\varepsilon_{\mathrm{gap}})))$. If correct, the result turns consistency of a predictive model into a property that can be checked efficiently rather than only estimated by sampling, which matters for AI systems whose safety rests on honest probabilistic claims.

What carries the argument

The construction is carried by four mechanisms. The Carathéodory witness replaces any distribution by one supported on $m+1$ points with identical $\ell^2$ constraint residuals, and the squared $\ell^2$ norm makes the optimal weights on a fixed support the solution of the linear system (5), whose coefficients are bounded via Hadamard's inequality so that the weights have polynomial bit-length. The proof oracle is the Reed–µller encoding, a Reed–Muller (multilinear-extension) code of the support vectors and the binary bits of the weights, which is locally testable and lets the verifier compute marginals through the gadgets $agree$ and $vec2int$. The encoding check (VerEnc) combines a multilinearity test with sum-checks certifying Booleanity and unit measure; the marginal check (VerMarginoid) verifies a field-valued marginal by reducing it to a random point via the SumCheck protocol. Finally, the SumCheck protocol reduces the two exponential sums defining $\mathrm{Inc}^2$ and $\|Q\|_1$ to single point evaluations of the arithmetic circuits $\hat P, \hat Q$ and of the oracle.

What would settle it

Take a small explicit model $(P,Q)$ whose consistency is witnessed by a known distribution $\mu$, write its exact Reed–µller codeword, then corrupt the oracle on a $\delta$-fraction of coordinates chosen so that every point the verifier's specific random coins select falls in the corrupted set; run Algorithm 6 with a prover claiming a marginal different from $\mu$'s. If the verifier accepts with probability greater than $\varepsilon_{\mathrm{sound}}$ (or if VerMarginoid accepts a false marginal beyond the bound of Claim 26), the closeness-to-codeword substitution in the proof of Theorem 32 is false.

Watch

Extended reading notes

Core claim

On the paper's own terms, the main theorem is that Model-Consistency---given circuits $P$ and $Q$ over a query universe of size $2^{\ell(d+1)+d}$, is there a distribution $\mu$ over $n = 2^d$ Boolean variables with $\mathrm{Inc}_{P,Q}(\mu) \le \tau$---admits a polynomial-time interactive PCP. The verifier's protocol (Algorithm 6) runs one encoding-proximity test, two sum-checks, two marginal checks, and three direct circuit evaluations; it reads only $\mathrm{poly}(\ell, d, B, \log(1/\varepsilon_{\mathrm{gap}}), 1/\varepsilon_{\mathrm{sound}})$ symbols of an oracle of length $|F|^{O(\ell d + B)}$ and exchanges polynomially many field elements with a single untrusted prover. The oracle encodes a sparse witnessing distribution, whose existence comes from a Carathéodory argument: any consistent collection of $m$ claims has a witness supported on $m+1$ points, and the paper proves the weights can be taken rational with polynomially many bits (Proposition 8 gives logarithmic-precision weights at the cost of an additive gap; Proposition 9 places the exact version in NP with certificate length $O(mn + \log B)$, the verifier solving for the weights itself). The completeness guarantee requires the model to be $(\tau - \varepsilon_{\mathrm{gap}})$-consistent, and soundness rejects every model with inconsistency above $\tau$ except with probability $\varepsilon_{\mathrm{sound}}$.

Load-bearing premise

The soundness proof of the main theorem assumes that a proof oracle which differs from a valid encoding on only a $\delta$-fraction of points can be treated as that exact encoding whenever the verifier's random reads avoid the differing points; the cited soundness lemmas do not prove this, because they assume the oracle is already the exact polynomial that is linear in each coordinate.

Editorial extensions

If this is right

  • Consistency of a circuit-specified predictor becomes verifiable in polynomial time up to an additive gap, with the verifier evaluating the model circuits at only a few points.
  • The NP certificate for $m$ explicit claims is of length $O(mn + \log B)$; introducing a small completeness-soundness gap shortens the stored weights to $O(\log(m/\varepsilon_{\mathrm{gap}}))$ bits each, which is what allows the witness to be written into the proof oracle.
  • If sound, the protocol guarantees that no untrusted prover can make an inconsistent model appear consistent except with probability $\varepsilon_{\mathrm{sound}}$, despite the verifier reading only a few oracle locations.
  • The Reed–µller library (validity check and marginal verification) is presented as a self-contained primitive that can verify marginals of distributions for purposes beyond consistency checking.
  • Delegating the circuit evaluations (Theorem 38) replaces the degree dependence with a depth dependence, so the verifier's runtime becomes polynomial in the model size; for uniformly presented circuits it becomes polylogarithmic in the circuit size.

Reading between the lines

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

  • The soundness proof's step from 'δ-close to a codeword' to 'behave as the exact codeword' is the spot to test: if it fails, the protocol may still be sound with the self-corrected marginal verifier VerMarginal substituted for VerMarginoid, at a modest cost in queries.
  • The $\ell^2$ norm is doing double duty: squaring makes the witness's stationarity conditions linear, so switching to an $\ell^p$ or entropy-based inconsistency measure would require a new witness bit-complexity analysis.
  • Because the honest prover must commit to the exact inconsistency value, a learned prover that only estimates would have no accepting strategy; the paper's own suggestion of an approximate sum-check is a concrete place to look for a version that tolerates estimated provers.
  • A natural experiment is to instantiate Algorithm 6 on a toy model with the explicit honest-prover strategies and check empirically whether a trained circuit can play both oracle and prover roles through context resets.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 3 minor

Summary. The paper studies whether a circuit-specified probabilistic predictor's conditional-probability claims can be jointly consistent and whether that consistency can be verified efficiently. For explicitly given collections of m probabilistic claims, it proves that ℓ2-approximate consistency has witnesses supported on O(m) points with polynomial-bit rational weights (Prop. 9) and a gapped low-precision variant (Prop. 8), giving NP membership and near-linear certificates. It also proves hardness of approximation for explicit consistency and NEXP-completeness for the succinct model-consistency problem. The main contribution is an interactive PCP (Thm 32) in which a polynomial-time verifier uses a Reed–Muller-like encoding of a sparse witness distribution, sumcheck sub-protocols, and a proximity test to certify model consistency; Theorem 38 delegates circuit evaluations to obtain depth-efficient verifier bounds.

Significance. The explicit-consistency results are carefully argued and appear technically sound: the Carathéodory sparsification, the exact rational solve, the determinant bounds, and the prime-certificate trick are convincing and give a meaningful improvement in certificate length. The paper is also commendably explicit about the Reed–µller encoding library and about its limitations, e.g., Remark 36 and Remark 40. If the IPCP soundness were established, Theorem 32 would be a significant first probabilistically checkable proof system for model consistency. However, as detailed below, the soundness proof of the main theorem has a load-bearing gap, so the headline result is not currently proven.

major comments (2)
  1. [§8.2, proof of Theorem 32 (soundness case)] The paragraph beginning "Otherwise π is δ-close to a codeword" assumes that once the Verifier's oracle reads land in the agreement region, "every subprotocol now behaves as if run" on the nearby codeword. This is not established. Claim 26 and Fact 22 require the oracles to be multilinear, or the summand to have bounded individual degree; a function that agrees with a multilinear function on finitely many queried points can be arbitrary elsewhere, and the degree bound is a global property of the oracle. Algorithm 6 Step 5 calls VerMarginoid, not the self-correcting VerMarginal of Algorithm 5, so conditioning on point queries cannot restore the missing degree bound. Consequently the soundness of Theorem 32, and of Theorem 38 which inherits the same Step 5 and the same analysis, is unproven. Since Theorem 32 is the headline contribution, this is a load-bearing gap.
  2. [§7.2, Claim 24 (non-multilinear case)] The same issue appears in the proof of Claim 24. In situation (ii), the proof transfers the multilinear-case bound to a δ-close oracle by adding the probability that the SumCheck's final query lands where Z differs from its closest multilinear polynomial Z̃. But SumCheck soundness for the polynomial Z̃ does not apply to an interactive transcript produced by a Prover who sees the actual non-multilinear Z. Relative Hamming closeness does not control the value or degree of Z²−Z off the agreement set, and the final query being an agreement point does not constrain the earlier Prover messages. Thus the soundness bound for VerEnc is not established as written.
minor comments (3)
  1. [§8.2, proof of Theorem 32] The phrase "every subprotocol now behaves as if run oneπ" appears garbled; it should read "as if run on the nearby codeword eπ" or similar.
  2. [§5.3] The illustrative statement that at m=10^6 and B=32 "a 32-bit number suffices" for the auxiliary prime is not derived; since the prime length is O(log B_M)=O(log m + log B), a short explanation of the constant would help the reader check the example.
  3. [§6.2, Claim 17] The statement of Claim 17 says the promise problem is NP-hard for all δ∈(0,2^{-k}) and k≥3, but the proof uses the inapproximability results of Håstad, which are typically stated for Exact-kSAT with k≥3 and a specific gap; please clarify that the reduction inherits the exact parameter range of the cited theorems.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the IPCP construction is self-contained, and the central claims do not reduce to their inputs; the flagged soundness gap in Theorem 32 is an unproven step, not a circular derivation.

full rationale

The paper's central derivation chain is not circular. The inconsistency measure Inc is defined directly (Eq. 1 and Definitions 3 and 5), and the goal is to verify this definition; that is not self-referential. The sparse-witness results rest on Carathéodory's theorem, Cramer's rule, Hadamard's inequality, and explicit rounding lemmas, none of which presuppose the target result. The low-precision witness (Claim 12) is derived from an explicit perturbation bound (Lemma 10) and a density claim (Lemma 11), not from the consistency statement being proved. The IPCP of Algorithm 6 reduces the consistency inequality to SumCheck, VerEnc, and VerMarginoid, whose soundness is inherited from standard polynomial-identity and proximity-testing facts (Fact 22, Claim 24, Claim 26). The cited prior work by the authors ([RH21, Ric22], [AGPR25]) is used for motivation and framing, not as a load-bearing theorem; the paper explicitly departs from [RH21, Ric22] by switching from relative entropy to an l2 norm, and the new protocol is specified and analyzed directly. The main genuine concern is that the soundness proof of Theorem 32 asserts without proof that, conditionally on oracle reads landing in the agreement region of a delta-close Reed-Muller codeword, sub-protocols that require global multilinearity and degree bounds behave as on the exact codeword. That is a soundness gap and a correctness risk, not circularity: it does not make the theorem's conclusion an input to its derivation. No equation equates a prediction with its fitted input, no parameter is fitted to a subset of data and then renamed a prediction, and no uniqueness claim is imported from the authors' prior work to force a choice. Accordingly, the circularity score is 0.

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

The central claims rest on standard mathematical theorems and a specific modeling choice for inconsistency. No parameters are fitted to data, and no new physical or mathematical entities are postulated beyond the proof-oracle encoding, which is a standard construction.

assumptions (6)
  • standard math Carathéodory's theorem
    Used in Section 5.1 to sparsify the witnessing distribution to m+1 support points.
  • standard math Cramer's rule and Hadamard's inequality
    Used in Lemma 13 to bound the bit-length of exact optimal weights.
  • standard math SumCheck protocol soundness (LFKN92)
    Used throughout Sections 7 and 8 to reduce sums over exponentials to point evaluations; soundness assumes the summed polynomial has bounded individual degree.
  • standard math Schwartz-Zippel lemma
    Used in soundness proofs of VerEnc and VerMarginoid.
  • standard math BLR self-correction (Fact 27)
    Defined but not used in the main protocol; relevant to VerMarginal.
  • domain assumption Model (P,Q) is given as Boolean circuits with B-bit outputs; consistency is defined via the ℓ2-weighted inconsistency measure
    The formal problem statement in Section 4.2; the choice of measure follows Potyka (2014) and Richardson and Halpern (2021).

how reviews work

0 comments
Cite this review

Pith. "Pith review of How to Verify Consistency of Probabilistic Claims." pith.science (2026). https://pith.science/paper/KLC72B3B

@misc{pith2026260811181,
  author       = {Pith},
  title        = {Pith review of: How to Verify Consistency of Probabilistic Claims},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KLC72B3B}},
  note         = {Machine review of arXiv:2608.11181}
}
read the original abstract

When a probabilistic predictor answers many conditional-probability queries, are its answers self-consistent, and can this be verified in polynomial time? This problem is of interest for AI safety, where safety is derived from honesty about probabilistic predictions of unwanted outcomes potentially caused by an AI action. We construct an interactive PCP as follows. Let a predictive model be specified by a probability circuit P and a circuit Q which outputs confidence in predictions. Together, P and Q implicitly specify exponentially many probabilistic claims. We show a protocol in which a polynomial-time verifier can verify the approximate consistency of (P,Q). The verifier is given the pair of circuits (P,Q), which it evaluates at only a few points; alongside them it is given a proof oracle, an encoding of a witnessing probability distribution allegedly consistent with the predictions of (P,Q), which it reads at a few locations while interacting with a single untrusted prover. En route, we must ensure the existence of a sparse witnessing distribution consistent with the model's predictions. To do so, we first consider witness distributions for the consistency of explicit probabilistic claims, rather than claims specified by a predictor: say m claims, each of the form Pr[Y = 1 | X = x] = p, over n Boolean variables. Building on work initiated by Nilsson (Artif. Intell., 1986), we place l_2-approximate probabilistic consistency of explicit claims in NP, with certificates of length O(mn + log B) in the input bit-precision B; we further show how a small additive completeness-soundness gap removes the dependence on B. Together these results provide a complexity-theoretic foundation for certifying the self-consistency of probabilistic predictors. We view our interactive PCP as a first step toward training predictive models to prove their own consistency.

Figures

Figures reproduced from arXiv: 2608.11181 by the authors.

Figure 1
Figure 1. Left: m probabilistic claims, collected, e.g., as the outputs of a predictive model, are verified against a short proof certificate that the Verifier reads in full (Explicit-Consistency; Proposition 9). Right: the entire model is verified in one go via an Interactive PCP; the Verifier evaluates the model at two points, reads polynomially many positions of an exponentially long proof oracle, and interacts with a sing… view at source ↗
Figure 2
Figure 2. The protocol as a chain of reductions: an arrow E → E′ means that verifying E reduces to verifying E′ , interacting with the Prover via the sub-protocol labeling the arrow. The root is the statement the Verifier sets out to check; rounded boxes are intermediate expressions that get reduced further; and the bottom row holds the only objects accessed directly: the input circuits P, Q (gray), which the Verifier evaluat… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

59 extracted references · 50 canonical work pages

  1. [7]

    Interactive oracle proofs

    [BCS16] Eli Ben-Sasson, Alessandro Chiesa, and Nicholas Spooner. Interactive oracle proofs. In Martin Hirt and Adam D. Smith, editors,Theory of Cryptography - 14th Inter- national Conference, TCC 2016-B, Beijing, China, October 31 - November 3, 2016, Proceedings, Part II, Lecture Notes in Computer Science, pages 31–60,

    work page 2016

  2. [10]

    Smith, and Patrick White

    [BFR+00] Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, and Patrick White. Testing that distributions are close. In41st Annual Symposium on Foundations of Computer Science, FOCS 2000, Redondo Beach, California, USA, November 12-14, 2000, pages 259–269. IEEE Computer Society,

    work page 2000

  3. [13]

    Avoiding obfuscation with prover-estimator debate.CoRR, abs/2506.13609,

    [BIP25] Jonah Brown-Cohen, Geoffrey Irving, and Georgios Piliouras. Avoiding obfuscation with prover-estimator debate.CoRR, abs/2506.13609,

    arXiv

  4. [15]

    Sum-of-squares proofs and the quest toward optimal algorithms.CoRR, abs/1404.5236,

    [BS14] Boaz Barak and David Steurer. Sum-of-squares proofs and the quest toward optimal algorithms.CoRR, abs/1404.5236,

    arXiv

  5. [17]

    Seshadhri, and Erik Waingarten

    [CCR+25] Deeparnab Chakrabarty, Xi Chen, Simeon Ristic, C. Seshadhri, and Erik Waingarten. Monotonicity testing of high-dimensional distributions with subcube conditioning. In Michal Kouck´ y and Nikhil Bansal, editors,Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025, pages 1019–1030. ACM,

    work page 2025

  6. [18]

    [CFLS93] Anne Condon, Joan Feigenbaum, Carsten Lund, and Peter W. Shor. Probabilistically checkable debate systems and approximation algorithms for pspace-hard functions. In S. Rao Kosaraju, David S. Johnson, and Alok Aggarwal, editors,Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 16-18, 1993, San Diego, CA, USA, pages 3...

    work page 1993

  7. [21]

    [Coo71] Stephen A. Cook. The complexity of theorem-proving procedures. In Michael A. Harrison, Ranan B. Banerji, and Jeffrey D. Ullman, editors,Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, May 3-5, 1971, Shaker Heights, Ohio, USA, pages 151–158. ACM,

    work page 1971

  8. [23]

    Making games short (extended abstract)

    [FK97] Uriel Feige and Joe Kilian. Making games short (extended abstract). In Frank Thom- son Leighton and Peter W. Shor, editors,Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, Texas, USA, May 4-6, 1997, pages 506–516. ACM,

    work page 1997

Show all 59 references
  1. [25]

    Adversarial re- silience in sequential prediction via abstention

    [GHMS23] Surbhi Goel, Steve Hanneke, Shay Moran, and Abhishek Shetty. Adversarial re- silience in sequential prediction via abstention. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors,Advances in Neu- ral Information Processi...

    2023

  2. [26]

    On the power of interactive proofs for learning

    [GJK+24] Tom Gur, Mohammad Mahdi Jahanara, Mohammad Mahdi Khodabandeh, Ninad Rajgopal, Bahar Salamatian, and Igor Shinkar. On the power of interactive proofs for learning. In Bojan Mohar, Igor Shinkar, and Ryan O’Donnell, editors,Proceedings of 58 the 56th Annual ACM Symposium...

    2024

  3. [27]

    Beyond perturbations: Learning guarantees with arbitrary adversarial test examples

    [GKKM20a] Shafi Goldwasser, Adam Tauman Kalai, Yael Kalai, and Omar Montasser. Beyond perturbations: Learning guarantees with arbitrary adversarial test examples. In Hugo Larochelle, Marc’Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan- Tien Lin, editors,Advance...

    2020

  4. [30]

    Neural interactive proofs

    [HA25] Lewis Hammond and Sam Adam-Day. Neural interactive proofs. InThe Thirteenth International Conference on Learning Representations, ICLR 2025, Singapore, April 24-28,

    2025

  5. [32]

    Rothblum

    59 [HR22] Tal Herman and Guy N. Rothblum. Verifying the unseen: interactive proofs for label- invariant distribution properties. In Stefano Leonardi and Anupam Gupta, editors, STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, p...

    2022

  6. [34]

    Rothblum

    [HR25a] Tal Herman and Guy N. Rothblum. How to verify any (reasonable) distribution prop- erty: Computationally sound argument systems for distributions. InThe Thirteenth International Conference on Learning Representations, ICLR 2025, Singapore, April 24-28,

    2025

  7. [35]

    Rothblum

    [HR25b] Tal Herman and Guy N. Rothblum. Proving natural distribution properties is harder than testing them. In66th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2025, Sydney, Australia, December 14-17, 2025, pages 2003–2016. IEEE,

    2025

  8. [36]

    Ai safety via debate.arXiv preprint arXiv:1805.00899,

    [ICA18] Geoffrey Irving, Paul Christiano, and Dario Amodei. Ai safety via debate.arXiv preprint arXiv:1805.00899,

    arXiv

  9. [40]

    Towards optimally abstaining from prediction with OOD test examples

    [KK21a] Adam Kalai and Varun Kanade. Towards optimally abstaining from prediction with OOD test examples. In Marc’Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors,Advances in Neural Infor- mation Processing Systems 34: Ann...

    2021

  10. [41]

    Efficient learning with arbitrary covariate shift

    [KK21b] Adam Tauman Kalai and Varun Kanade. Efficient learning with arbitrary covariate shift. In Vitaly Feldman, Katrina Ligett, and Sivan Sabato, editors,Algorithmic Learning Theory, 16-19 March 2021, Virtual Conference, Worldwide, Proceedings of Machine Learning Research, p...

    2021

  11. [44]

    Mirrokni, Renato Paes Leme, Adrian Vladu, and Sam Chiu-wai Wong

    [ML VW17] Vahab S. Mirrokni, Renato Paes Leme, Adrian Vladu, and Sam Chiu-wai Wong. Tight bounds for approximate carath´ eodory and beyond. In Doina Precup and Yee Whye Teh, editors,Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, A...

    2017

  12. [45]

    PAC verification of statistical algorithms

    [MS23] Saachi Mutreja and Jonathan Shafer. PAC verification of statistical algorithms. In Gergely Neu and Lorenzo Rosasco, editors,The Thirty Sixth Annual Conference on Learning Theory, COLT 2023, 12-15 July 2023, Bangalore, India, Proceedings of Machine Learning Research, pag...

    2023

  13. [46]

    O’Brien, Carrie Jun Cai, Meredith Ringel Morris, Percy Liang, and Michael S

    [POC+23] Joon Sung Park, Joseph C. O’Brien, Carrie Jun Cai, Meredith Ringel Morris, Percy Liang, and Michael S. Bernstein. Generative agents: Interactive simulacra of human behavior. In Sean Follmer, Jeff Han, J¨ urgen Steimle, and Nathalie Henry Riche, editors,Proceedings of ...

    2023

  14. [47]

    Linear programs for measuring inconsistency in probabilistic logics

    [Pot14] Nico Potyka. Linear programs for measuring inconsistency in probabilistic logics. In Proceedings of the 14th International Conference on Principles of Knowledge Repre- sentation and Reasoning (KR 2014), pages 568–577,

    2014

  15. [49]

    Consolidation of probabilistic knowledge bases by inconsistency minimization

    [PT14] Nico Potyka and Matthias Thimm. Consolidation of probabilistic knowledge bases by inconsistency minimization. InProceedings of the 21st European Conference on Artificial Intelligence (ECAI 2014), pages 729–734. IOS Press,

    2014

  16. [51]

    Richardson, Joseph Y

    [RHS23] Oliver E. Richardson, Joseph Y. Halpern, and Christopher De Sa. Inference for prob- abilistic dependency graphs. In Robin J. Evans and Ilya Shpitser, editors,Uncertainty in Artificial Intelligence, UAI 2023, July 31 - 4 August 2023, Pittsburgh, PA, USA, volume 216 ofPr...

    2023

  17. [52]

    Richardson

    [Ric22] Oliver E. Richardson. Loss as the inconsistency of a probabilistic dependency graph: Choose your model, not your loss function. In Gustau Camps-Valls, Francisco J. R. Ruiz, and Isabel Valera, editors,International Conference on Artificial Intelligence and Statistics, A...

    2022

  18. [55]

    Time-optimal interactive proofs for circuit evaluation

    [Tha13] Justin Thaler. Time-optimal interactive proofs for circuit evaluation. In Ran Canetti and Juan A. Garay, editors,Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22,

    2013

  19. [58]

    Probabilistic algorithms for sparse polynomials

    [Zip79] Richard Zippel. Probabilistic algorithms for sparse polynomials. In Edward W. Ng, editor,Symbolic and Algebraic Computation, EUROSAM ’79, An International Sym- posiumon Symbolic and Algebraic Computation, Marseille, France, June 1979, Pro- ceedings, volume 72 ofLecture...

    1979

  20. [145]

    Uniformity testing over hypergrids with subcube conditioning

    [CM24] Xi Chen and Cassandra Marcussen. Uniformity testing over hypergrids with subcube conditioning. In David P. Woodruff, editor,Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, V A, USA, January 7- 10, 2024, pages 4338–4370. SIAM,

    2024

  21. [1907]

    Canonne, Xi Chen, Gautam Kamath, Amit Levi, and Erik Waingarten

    56 [CCK+21] Cl´ ement L. Canonne, Xi Chen, Gautam Kamath, Amit Levi, and Erik Waingarten. Random restrictions of high dimensional distributions and uniformity testing with subcube conditioning. In D´ aniel Marx, editor,Proceedings of the 2021 ACM-SIAM Symposium on Discrete Alg...

    2021

  22. [1921]

    A note on efficient zero-knowledge proofs and arguments (extended ab- stract)

    [Kil92] Joe Kilian. A note on efficient zero-knowledge proofs and arguments (extended ab- stract). In S. Rao Kosaraju, Mike Fellows, Avi Wigderson, and John A. Ellis, editors, Proceedings of the 24th Annual ACM Symposium on Theory of Computing, May 4-6, 1992, Victoria, British...

    1992

  23. [1931]

    [RH21] Oliver Richardson and Joseph Y. Halpern. Probabilistic dependency graphs. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Education...

    2021

  24. [1950]

    Interactive PCP

    [KR08] Yael Tauman Kalai and Ran Raz. Interactive PCP. In Luca Aceto, Ivan Damg ˚ ard, Leslie Ann Goldberg, Magn´ us M. Halld´ orsson, Anna Ing´ olfsd´ ottir, and Igor Walukiewicz, editors,Automata, Languages and Programming, 35th Interna- tional Colloquium, ICALP 2008, Reykja...

    2008

  25. [1979]

    63 [ZPIE17] Jun-Yan Zhu, Taesung Park, Phillip Isola, and Alexei A. Efros. Unpaired image-to- image translation using cycle-consistent adversarial networks. InIEEE International Conference on Computer Vision, ICCV 2017, Venice, Italy, October 22-29, 2017, pages 2242–2251. IEEE...

    2017

  26. [1980]

    Hilbert bases, caratheodory’s theorem and combinatorial optimization

    [Seb90] Andr´ as Seb¨ o. Hilbert bases, caratheodory’s theorem and combinatorial optimization. In Ravi Kannan and William R. Pulleyblank, editors,Proceedings of the 1st Inte- ger Programming and Combinatorial Optimization Conference, Waterloo, Ontorio, Canada, May 28-30 1990, ...

    1990

  27. [1982]

    Tenenbaum, and Igor Mordatch

    [DLT+24] Yilun Du, Shuang Li, Antonio Torralba, Joshua B. Tenenbaum, and Igor Mordatch. Improving factuality and reasoning in language models through multiagent debate. In Ruslan Salakhutdinov, Zico Kolter, Katherine A. Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, a...

    2024

  28. [1985]

    E-mail and the unexpected power of interaction

    [Bab90] L´ aszl´ o Babai. E-mail and the unexpected power of interaction. InProceedings: Fifth Annual Structure in Complexity Theory Conference, Universitat Polit` ecnica de Catalunya, Barcelona, Spain, July 8-11, 1990, pages 30–44. IEEE Computer Society,

    1990

  29. [1990]

    Approximating nash equilibria and dense bipartite subgraphs via an approximate version of caratheodory’s theorem

    54 [Bar15] Siddharth Barman. Approximating nash equilibria and dense bipartite subgraphs via an approximate version of caratheodory’s theorem. In Rocco A. Servedio and Ronitt Rubinfeld, editors,Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, ST...

    2015

  30. [1991]

    Levin, and Mario Szegedy

    [BFLS91] L´ aszl´ o Babai, Lance Fortnow, Leonid A. Levin, and Mario Szegedy. Checking com- putations in polylogarithmic time. In Cris Koutsougeras and Jeffrey Scott Vitter, editors,Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, May 5-8, 1991, New Orleans...

    1991

  31. [1992]

    Struc- tured consistency loss for semi-supervised semantic segmentation.arXiv preprint arXiv:2001.04647,

    [KJPJ20] Jongmok Kim, Jooyoung Jang, Hyunwoo Park, and SeongAh Jeong. Struc- tured consistency loss for semi-supervised semantic segmentation.arXiv preprint arXiv:2001.04647,

    2001 arXiv

  32. [1994]

    On the complexity of statistical reasoning (extended ab- tract)

    [KN95] Joe Kilian and Moni Naor. On the complexity of statistical reasoning (extended ab- tract). InThird Israel Symposium on Theory of Computing and Systems, ISTCS 1995, Tel Aviv, Israel, January 4-6, 1995, Proceedings, pages 209–217. IEEE Com- puter Society,

    1995

  33. [1996]

    [RSS+25] Dhruv Rohatgi, Abhishek Shetty, Donya Saless, Yuchen Li, Ankur Moitra, Andrej Risteski, and Dylan J. Foster. Taming imperfect process verifiers: A sampling per- spective on backtracking.CoRR, abs/2510.03149,

  34. [1997]

    Probabilistic machines can use less running time

    [Fre77] Rusins Freivalds. Probabilistic machines can use less running time. In Bruce Gilchrist, editor,Information Processing, Proceedings of the 7th IFIP Congress 1977, Toronto, Canada, August 8-12, 1977, pages 839–842. North-Holland,

    1977

  35. [1998]

    [AZWG21] Cem Anil, Guodong Zhang, Yuhuai Wu, and Roger B. Grosse. Learning to give checkable answers with prover-verifier games.CoRR, abs/2108.12099,

    arXiv

  36. [2000]

    Rothblum, Jonathan Shafer, and Amir Yehudayoff

    [GRSY21] Shafi Goldwasser, Guy N. Rothblum, Jonathan Shafer, and Amir Yehudayoff. Inter- active proofs for verifying machine learning. In James R. Lee, editor,12th Innovations in Theoretical Computer Science Conference, ITCS 2021, Virtual Conference, Jan- uary 6-8, 2021, LIPIc...

    2021

  37. [2001]

    Public coin interactive proofs for label-invariant distribution properties

    [Her24] Tal Herman. Public coin interactive proofs for label-invariant distribution properties. In Amit Kumar and Noga Ron-Zewi, editors,Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2024, London School of Economics, Lon...

    2024

  38. [2013]

    Interpretability guarantees with merlin-arthur classifiers

    [WST+24] Stephan W¨ aldchen, Kartikey Sharma, Berkant Turan, Max Zimmer, and Sebastian Pokutta. Interpretability guarantees with merlin-arthur classifiers. In Sanjoy Das- gupta, Stephan Mandt, and Yingzhen Li, editors,International Conference on Artifi- cial Intelligence and S...

    2024

  39. [2014]

    Generative language modeling for automated the- orem proving.CoRR, abs/2009.03393,

    [PS20] Stanislas Polu and Ilya Sutskever. Generative language modeling for automated the- orem proving.CoRR, abs/2009.03393,

    2009 arXiv

  40. [2015]

    [BBH+12] Boaz Barak, Fernando G. S. L. Brand˜ ao, Aram W. Harrow, Jonathan A. Kelner, David Steurer, and Yuan Zhou. Hypercontractivity, sum-of-squares proofs, and their applications. In Howard J. Karloff and Toniann Pitassi, editors,Proceedings of the 44th Symposium on Theory ...

    2012

  41. [2016]

    Sum-check protocol for approximate computations

    [BDG+26] Dor Bitan, Zachary DeStefano, Shafi Goldwasser, Yuval Ishai, Yael Tauman Kalai, and Justin Thaler. Sum-check protocol for approximate computations. In Joan Dae- men and Emmanuel Thom´ e, editors,Advances in Cryptology - EUROCRYPT 2026 - 45th Annual International Confe...

    2026

  42. [2017]

    Proofs of proximity for distribution testing

    [CG18] Alessandro Chiesa and Tom Gur. Proofs of proximity for distribution testing. In Anna R. Karlin, editor,9th Innovations in Theoretical Computer Science Conference, ITCS 2018, Cambridge, MA, USA, January 11-14, 2018, LIPIcs, pages 53:1–53:14. Schloss Dagstuhl - Leibniz-Ze...

    2018

  43. [2018]

    Incoherent probability judgments in large language models

    [ZG24] Jian-Qiao Zhu and Tom Griffiths. Incoherent probability judgments in large language models. In Larissa K. Samuelson, Stefan Frank, Mariya Toneva, Allyson Mackey, and Eliot Hazeltine, editors,Proceedings of the 46th Annual Meeting of the Cogni- tive Science Society, CogS...

    2024

  44. [2019]

    Prover-verifier games improve legibility of LLM outputs.CoRR, abs/2407.13692,

    [KCE+24] Jan Hendrik Kirchner, Yining Chen, Harri Edwards, Jan Leike, Nat McAleese, and Yuri Burda. Prover-verifier games improve legibility of LLM outputs.CoRR, abs/2407.13692,

    arXiv

  45. [2020]

    Identifying unpredictable test examples with worst-case guarantees

    [GKKM20b] Shafi Goldwasser, Adam Tauman Kalai, Yael Tauman Kalai, and Omar Montasser. Identifying unpredictable test examples with worst-case guarantees. InInformation Theory and Applications Workshop, ITA 2020, San Diego, CA, USA, February 2-7, 2020, pages 1–14. IEEE,

    2020

  46. [2021]

    Trading group theory for randomness

    [Bab85] L´ aszl´ o Babai. Trading group theory for randomness. In Robert Sedgewick, editor, Proceedings of the 17th Annual ACM Symposium on Theory of Computing, May 6-8, 1985, Providence, Rhode Island, USA, pages 421–429. ACM,

    1985

  47. [2022]

    Rothblum

    [HR23] Tal Herman and Guy N. Rothblum. Doubley-efficient interactive proofs for distri- bution properties. In64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, pages 743–751. IEEE,

    2023

  48. [2023]

    Ash, Cyril Zhang, and Andrej Risteski

    [BLM+25] Edoardo Botta, Yuchen Li, Aashay Mehta, Jordan T. Ash, Cyril Zhang, and Andrej Risteski. On the query complexity of verifier-assisted language generation. In Aarti Singh, Maryam Fazel, Daniel Hsu, Simon Lacoste-Julien, Felix Berkenkamp, Tegan Maharaj, Kiri Wagstaff, a...

    2025

  49. [2024]

    Marshall, Ilan Newman, Georgios Pil- iouras, and Mario Szegedy

    [BIM+26] Jonah Brown-Cohen, Geoffrey Irving, Simon C. Marshall, Ilan Newman, Georgios Pil- iouras, and Mario Szegedy. Debate is efficient with your time.CoRR, abs/2602.08630,

  50. [2025]

    International ai safety report 2025: first key update: capabilities and risk implications.arXiv preprint arXiv:2510.13653,

    [BCP+25] Yoshua Bengio, Stephen Clare, Carina Prunkl, Shalaleh Rismani, Maksym An- driushchenko, Ben Bucknall, Philip Fox, Tiancheng Hu, Cameron Jones, Sam Man- ning, et al. International ai safety report 2025: first key update: capabilities and risk implications.arXiv preprin...

    2025

  51. [2026]

    Scalable AI safety via doubly-efficient debate

    [BIP24] Jonah Brown-Cohen, Geoffrey Irving, and Georgios Piliouras. Scalable AI safety via doubly-efficient debate. In Ruslan Salakhutdinov, Zico Kolter, Katherine A. Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors,Forty- first Internation...

    2024

Pith tools

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