pith. sign in

arxiv: 2509.17994 · v3 · submitted 2025-09-22 · 💻 cs.CC · cs.DS· cs.LG

Supersimulators

Cynthia Dwork , Pranay Tankala This is my paper

Pith reviewed 2026-05-18 14:24 UTC · model grok-4.3

classification 💻 cs.CC cs.DScs.LG
keywords supersimulatorregularity lemmamultiaccuracymulticalibrationcomputational indistinguishabilityrandomized Boolean functionscomplexity theory
0
0 comments X

The pith

Every randomized Boolean function admits a supersimulator: a polynomial-size randomized circuit whose outputs cannot be distinguished from the true function with constant advantage even by polynomially larger distinguishers.

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

The paper proves that any randomized Boolean function has a small randomized circuit that behaves indistinguishably from the real function on random inputs. This holds even against distinguishers whose size is polynomial in the circuit size plus the original function's complexity, strengthening earlier simulators that only worked against smaller distinguishers. The proof adapts the Trevisan-Tulsiani-Vadhan regularity lemma using an iteration method from graph theory to let the distinguisher bound depend on the target function while keeping it absolutely bounded. The authors then apply this to show that a known characterization of computational indistinguishability for product distributions needs only multiaccuracy rather than full multicalibration, and that supersimulators give a strictly tighter version of that characterization.

Core claim

We prove that every randomized Boolean function admits a supersimulator: a randomized polynomial-size circuit whose output on random inputs cannot be efficiently distinguished from reality with constant advantage, even by polynomially larger distinguishers. Our result builds on the landmark complexity-theoretic regularity lemma of Trevisan, Tulsiani and Vadhan (2009), which, in contrast, provides a simulator that fools smaller distinguishers. We circumvent lower bounds for the simulator size by letting the distinguisher size bound vary with the target function, while remaining below an absolute upper bound independent of the target function. This dependence on the target function arises from

What carries the argument

The supersimulator, a randomized polynomial-size circuit that fools polynomially larger distinguishers, obtained by iterating the Trevisan-Tulsiani-Vadhan regularity lemma so the distinguisher bound can depend on the target function.

If this is right

  • A multicalibration-based characterization of computational indistinguishability of product distributions actually requires only calibrated multiaccuracy.
  • Supersimulators produce a strictly tighter version of that characterization, closing a prior complexity gap.
  • The same simulators can be substituted into existing applications of the regularity lemma in complexity theory, cryptography, and learning theory.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Supersimulators may simplify proofs that rely on simulating distributions while controlling distinguisher size.
  • The variable-bound technique could extend to other iterative regularity arguments in pseudorandomness.
  • If supersimulators compose well, they might improve reductions between indistinguishability and multiaccuracy in new settings.

Load-bearing premise

The iteration technique from graph regularity allows the distinguisher size bound to vary with the target function while staying below a fixed upper bound independent of that function.

What would settle it

Exhibit one randomized Boolean function together with an explicit polynomial-size circuit family such that every candidate supersimulator of polynomial size can be distinguished from the true function by some circuit whose size is only polynomially larger than the simulator, with advantage bounded away from zero.

read the original abstract

We prove that every randomized Boolean function admits a supersimulator: a randomized polynomial-size circuit whose output on random inputs cannot be efficiently distinguished from reality with constant advantage, even by polynomially larger distinguishers. Our result builds on the landmark complexity-theoretic regularity lemma of Trevisan, Tulsiani and Vadhan (2009), which, in contrast, provides a simulator that fools smaller distinguishers. We circumvent lower bounds for the simulator size by letting the distinguisher size bound vary with the target function, while remaining below an absolute upper bound independent of the target function. This dependence on the target function arises naturally from our use of an iteration technique originating in the graph regularity literature. The simulators provided by the regularity lemma and recent refinements thereof, known as multiaccurate and multicalibrated predictors, respectively, as per Hebert-Johnson et al. (2018), have previously been shown to have myriad applications in complexity theory, cryptography, learning theory, and beyond. We first show that a recent multicalibration-based characterization of the computational indistinguishability of product distributions actually requires only (calibrated) multiaccuracy. We then show that supersimulators yield an even tighter result in this application domain, closing a complexity gap present in prior versions of the characterization.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper proves that every randomized Boolean function admits a supersimulator: a randomized polynomial-size circuit whose output on random inputs cannot be efficiently distinguished from the true function with constant advantage, even by distinguishers that are polynomially larger. The proof adapts the Trevisan-Tulsiani-Vadhan 2009 regularity lemma via an iteration technique from the graph-regularity literature; this allows the distinguisher-size bound to depend on the target function while remaining below a fixed absolute upper bound independent of the function. The paper also shows that a recent multicalibration-based characterization of computational indistinguishability for product distributions requires only calibrated multiaccuracy, and that supersimulators yield a strictly tighter version of this characterization, closing a complexity gap in prior statements.

Significance. If the central existence result holds, the work strengthens the applicability of regularity lemmas in complexity theory by producing simulators that remain polynomial-size yet fool a larger class of distinguishers. This directly improves prior characterizations of product-distribution indistinguishability and has potential downstream uses in cryptography, learning theory, and derandomization. The explicit use of an iteration technique to control size bounds is a technically interesting refinement of the 2009 lemma.

major comments (2)
  1. [Proof of main theorem (around the adaptation of the TTV regularity lemma)] The iteration argument that lets the distinguisher-size bound vary with the target function while staying below an absolute polynomial bound is load-bearing for the supersimulator claim (see the proof sketch following the statement of the main theorem). The manuscript should supply an explicit size calculation showing that the number of iterations and the resulting circuit size remain polynomial in the input length and independent of the particular target function chosen.
  2. [Application to product distributions] The claim that supersimulators close a complexity gap in the product-distribution characterization (final section) rests on the simulator fooling polynomially larger distinguishers. A direct comparison of the new distinguisher-size bound with the bounds appearing in Hebert-Johnson et al. (2018) and the prior multicalibration work would make the improvement quantitative and easier to verify.
minor comments (2)
  1. [Preliminaries] Notation for the randomized circuit and the distinguisher class should be introduced once in a dedicated preliminary section rather than inline in the proof.
  2. [Introduction] The abstract states that the result 'builds on' the 2009 lemma; a short paragraph contrasting the new simulator size with the original TTV bound would help readers immediately see the technical advance.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive suggestions. We address each major comment below and will incorporate the requested clarifications in the revised manuscript.

read point-by-point responses

  1. Referee: [Proof of main theorem (around the adaptation of the TTV regularity lemma)] The iteration argument that lets the distinguisher-size bound vary with the target function while staying below an absolute polynomial bound is load-bearing for the supersimulator claim (see the proof sketch following the statement of the main theorem). The manuscript should supply an explicit size calculation showing that the number of iterations and the resulting circuit size remain polynomial in the input length and independent of the particular target function chosen.

    Authors: We agree that an explicit size calculation will improve the transparency of the argument. In the revision we will expand the proof sketch to include a detailed accounting of the iteration count and circuit-size growth. The analysis will confirm that the process terminates after polynomially many iterations in the input length n and that the final simulator size remains polynomial in n, with the absolute upper bound on distinguisher size ensuring the bound is independent of the particular target function. revision: yes

  2. Referee: [Application to product distributions] The claim that supersimulators close a complexity gap in the product-distribution characterization (final section) rests on the simulator fooling polynomially larger distinguishers. A direct comparison of the new distinguisher-size bound with the bounds appearing in Hebert-Johnson et al. (2018) and the prior multicalibration work would make the improvement quantitative and easier to verify.

    Authors: We thank the referee for this suggestion. In the revised final section we will insert a direct quantitative comparison of the distinguisher-size bounds. The new text will explicitly contrast the polynomial bound achieved by supersimulators against the bounds stated in Hebert-Johnson et al. (2018) and the earlier multicalibration characterizations, thereby making the tightening of the complexity gap concrete. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper establishes the existence of supersimulators for randomized Boolean functions by adapting the external Trevisan-Tulsiani-Vadhan 2009 regularity lemma via an iteration technique drawn from the graph regularity literature. This adaptation permits the distinguisher-size bound to vary with the target function while remaining below a fixed absolute upper bound independent of the function. The subsequent refinements to multicalibration-based characterizations of product-distribution indistinguishability draw on prior external work (Hebert-Johnson et al. 2018) and demonstrate that only calibrated multiaccuracy is required, without any reduction of the central claims to self-definitional equations, fitted inputs renamed as predictions, or load-bearing self-citations. The derivation chain therefore remains self-contained against these independent external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the Trevisan-Tulsiani-Vadhan regularity lemma and the iteration technique from graph regularity literature; no free parameters or new entities are introduced.

axioms (1)
  • domain assumption The complexity-theoretic regularity lemma of Trevisan, Tulsiani and Vadhan (2009)
    The supersimulator construction builds directly on this lemma and adapts it via iteration.

pith-pipeline@v0.9.0 · 5750 in / 1254 out tokens · 49041 ms · 2026-05-18T14:24:01.139294+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

  • IndisputableMonolith/Foundation/AbsoluteFloorClosure.lean reality_from_one_distinction unclear
    ?
    unclear

    Relation between the paper passage and the cited Recognition theorem.

    We prove that every randomized Boolean function admits a supersimulator: a randomized polynomial-size circuit whose output on random inputs cannot be efficiently distinguished from reality with constant advantage, even by polynomially larger distinguishers. ... by letting the distinguisher size bound vary with the target function, while remaining below an absolute upper bound independent of the target function. This dependence on the target function arises naturally from our use of an iteration technique originating in the graph regularity literature.

  • IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear
    ?
    unclear

    Relation between the paper passage and the cited Recognition theorem.

    Theorem 3.1 (Supersimulators, Expanding). ... h is (F^{G(s)}, ε)-regular ... s ≤ S_{⌊1/(3ε²)⌋} where S_{i+1} = S_i + G(S_i) + (0,(log(1/ε))^{O(1)})

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Instance-Adaptive Online Multicalibration

    cs.LG 2026-05 conditional novelty 8.0

    A single online multicalibration algorithm adaptively refines a dyadic grid and achieves instance-dependent rates: O(T^{2/3}) worst-case, O(sqrt T) for marginal stochastic data, and O(sqrt(JT)) for J-piecewise station...

  2. Instance-Adaptive Online Multicalibration

    cs.LG 2026-05 unverdicted novelty 7.0

    A single algorithm for online multicalibration achieves instance-adaptive rates by dynamically refining a dyadic prediction grid, recovering the worst-case Õ(T^{2/3}) bound and improving to Õ(√T) in marginal stochasti...

  3. The Sample Complexity of Multicalibration

    cs.LG 2026-04 unverdicted novelty 7.0

    Multicalibration has minimax sample complexity Θ̃(ε^{-3}) when the number of groups is at most ε^{-κ} for fixed κ>0, versus Θ̃(ε^{-2}) for marginal calibration, with a sharp threshold at κ=0.

Reference graph

Works this paper leans on

36 extracted references · 36 canonical work pages · cited by 2 Pith papers

  1. [1]

    Loss minimization yields multicalibration for large neural networks

    Jaros aw B asiok, Parikshit Gopalan, Lunjia Hu, Adam Tauman Kalai, and Preetum Nakkiran. Loss minimization yields multicalibration for large neural networks. In Innovations in Theoretical Computer Science Conference ( ITCS ) , 2024

    work page 2024

  2. [2]

    On the complexity of simulating auxiliary input

    Yi - Hsiu Chen, Kai - Min Chung, and Jyun - Jie Liao. On the complexity of simulating auxiliary input. In EUROCRYPT : Annual International Conference on the Theory and Applications of Cryptographic Techniques , 2018

    work page 2018

  3. [3]

    S \' lvia Casacuberta, Cynthia Dwork, and Salil P. Vadhan. Complexity-theoretic implications of multicalibration. In ACM Symposium on Theory of Computing ( STOC ) , 2024

    work page 2024

  4. [4]

    Bounds for graph regularity and removal lemmas

    David Conlon and Jacob Fox. Bounds for graph regularity and removal lemmas. Geometric and Functional Analysis , 22(5):1191--1256, 2012

    work page 2012

  5. [5]

    How global calibration strengthens multiaccuracy

    S\' i lvia Casacuberta, Parikshit Gopalan, Varun Kanade, and Omer Reingold. How global calibration strengthens multiaccuracy. In IEEE Symposium on Foundations of Computer Science (FOCS) , 2025

    work page 2025

  6. [6]

    Servedio

    Anindya De, Ilias Diakonikolas, Vitaly Feldman, and Rocco A. Servedio. Nearly optimal solutions for the chow parameters problem and low-weight approximation of halfspaces. In ACM Symposium on Theory of Computing Conferenc ( STOC ) , 2012

    work page 2012

  7. [7]

    Kim, Omer Reingold, Guy N

    Cynthia Dwork, Michael P. Kim, Omer Reingold, Guy N. Rothblum, and Gal Yona. Outcome indistinguishability. In ACM Symposium on Theory of Computing ( STOC ) , 2021

    work page 2021

  8. [8]

    From pseudorandomness to multi-group fairness and back

    Cynthia Dwork, Daniel Lee, Huijia Lin, and Pranay Tankala. From pseudorandomness to multi-group fairness and back. In Conference on Learning Theory (COLT) , 2023

    work page 2023

  9. [9]

    Learning DNF expressions from fourier spectrum

    Vitaly Feldman. Learning DNF expressions from fourier spectrum. In Conference on Learning Theory ( COLT ) , 2012

    work page 2012

  10. [10]

    Frieze and Ravi Kannan

    Alan M. Frieze and Ravi Kannan. The regularity lemma and approximation schemes for dense problems. In IEEE Symposium on Foundations of Computer Science ( FOCS ) , 1996

    work page 1996

  11. [11]

    Frieze and Ravi Kannan

    Alan M. Frieze and Ravi Kannan. Quick approximation to matrices and applications. Combinatorica , 19(2):175--220, 1999

    work page 1999

  12. [12]

    A new proof of the graph removal lemma

    Jacob Fox. A new proof of the graph removal lemma. Annals of Mathematics , 174(1):561--579, 2011

    work page 2011

  13. [13]

    A tight computational indistinguishability bound for product distributions

    Nathan Geier. A tight computational indistinguishability bound for product distributions. In Theory of Cryptography Conference ( TCC ) , 2022

    work page 2022

  14. [14]

    Kim, Omer Reingold, and Udi Wieder

    Parikshit Gopalan, Lunjia Hu, Michael P. Kim, Omer Reingold, and Udi Wieder. Loss minimization through the lens of outcome indistinguishability. In Innovations in Theoretical Computer Science Conference ( ITCS ) , 2023

    work page 2023

  15. [15]

    Omnipredictors

    Parikshit Gopalan, Adam Tauman Kalai, Omer Reingold, Vatsal Sharan, and Udi Wieder. Omnipredictors. In Innovations in Theoretical Computer Science Conference ( ITCS ) , 2022

    work page 2022

  16. [16]

    Kim, Mihir Singhal, and Shengjia Zhao

    Parikshit Gopalan, Michael P. Kim, Mihir Singhal, and Shengjia Zhao. Low-degree multicalibration. In Conference on Learning Theory ( COLT ) , 2022

    work page 2022

  17. [17]

    The primes contain arbitrarily long arithmetic progressions

    Ben Green and Terence Tao. The primes contain arbitrarily long arithmetic progressions. Annals of Mathematics , 167(2):481--547, 2008

    work page 2008

  18. [18]

    Kim, Omer Reingold, and Guy N

    \' U rsula H \' e bert - Johnson, Michael P. Kim, Omer Reingold, and Guy N. Rothblum. Multicalibration: Calibration for the (computationally-identifiable) masses. In International Conference on Machine Learning ( ICML ) , 2018

    work page 2018

  19. [19]

    Degradation and amplification of computational hardness

    Shai Halevi and Tal Rabin. Degradation and amplification of computational hardness. In Theory of Cryptography Conference ( TCC ) , 2008

    work page 2008

  20. [20]

    Generalized and unified equivalences between hardness and pseudoentropy

    Lunjia Hu and Salil Vadhan. Generalized and unified equivalences between hardness and pseudoentropy. In Theory of Cryptography Conference ( TCC ) , 2025

    work page 2025

  21. [21]

    Hard-core distributions for somewhat hard problems

    Russell Impagliazzo. Hard-core distributions for somewhat hard problems. In IEEE Symposium on Foundations of Computer Science (FOCS) , 1995

    work page 1995

  22. [22]

    How to fake auxiliary input

    Dimitar Jetchev and Krzysztof Pietrzak. How to fake auxiliary input. In Theory of Cryptography Conference ( TCC ) , 2014

    work page 2014

  23. [23]

    Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu

    Michael J. Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu. Preventing fairness gerrymandering: Auditing and learning for subgroup fairness. In International Conference on Machine Learning ( ICML ) , 2018

    work page 2018

  24. [24]

    Szemer\' e di’s lemma for the analyst

    L\' a szl\' o Lov\' a sz and Bal\' a zs Szegedy. Szemer\' e di’s lemma for the analyst. Geometric and Functional Analysis , 17:252–270, 2007

    work page 2007

  25. [25]

    Putterman, and Salil Vadhan

    Cassandra Marcussen, Aaron L. Putterman, and Salil Vadhan. Characterizing the distinguishability of product distributions through multicalibration. In Computational Complexity Conference ( CCC ) , 2025

    work page 2025

  26. [26]

    Regularity lemmas for graphs

    Vojt e ch R \"o dl and Mathias Schacht. Regularity lemmas for graphs. In Fete of Combinatorics and Computer Science , volume 20 of Bolyai Society Mathematical Studies , pages 287--325. Springer, 2010

    work page 2010

  27. [27]

    Omer Reingold, Luca Trevisan, Madhur Tulsiani, and Salil P. Vadhan. Dense subsets of pseudorandom sets. In IEEE Symposium on Foundations of Computer Science (FOCS) , 2008

    work page 2008

  28. [28]

    A cryptographic view of regularity lemmas: Simpler unified proofs and refined bounds

    Maciej Sk \'o rski. A cryptographic view of regularity lemmas: Simpler unified proofs and refined bounds. In Theory and Applications of Models of Computation , pages 586--599, Cham, 2017. Springer International Publishing

    work page 2017

  29. [29]

    Regular partitions of graphs

    Endre Szemer \' e di. Regular partitions of graphs. Technical report, Stanford University, Stanford, CA, USA, 1975

    work page 1975

  30. [30]

    Luca Trevisan, Madhur Tulsiani, and Salil P. Vadhan. Regularity, boosting, and efficiently simulating every high-entropy distribution. In IEEE Conference on Computational Complexity ( CCC ) , 2009

    work page 2009

  31. [31]

    The primes contain arbitrarily long polynomial progressions

    Terence Tao and Tamar Ziegler. The primes contain arbitrarily long polynomial progressions. Acta Mathematica , 201(2):213 -- 305, 2008

    work page 2008

  32. [32]

    Salil P. Vadhan. Pseudorandomness. Foundations and Trends in Theoretical Computer Science , 7(1-3):1--336, 2012

    work page 2012

  33. [33]

    Vadhan and Colin Jia Zheng

    Salil P. Vadhan and Colin Jia Zheng. Characterizing pseudoentropy and simplifying pseudorandom generator constructions. In ACM Symposium on Theory of Computing ( STOC ) , 2012

    work page 2012

  34. [34]

    Vadhan and Colin Jia Zheng

    Salil P. Vadhan and Colin Jia Zheng. A uniform min-max theorem with applications in cryptography. In CRYPTO : Annual International Cryptology Conference , 2013

    work page 2013

  35. [35]

    Graph Theory and Additive Combinatorics

    Yufei Zhao. Graph Theory and Additive Combinatorics . Cambridge University Press, 2023

    work page 2023

  36. [36]

    A Uniform Min-Max Theorem and Characterizations of Computational Randomness

    Colin Jia Zheng. A Uniform Min-Max Theorem and Characterizations of Computational Randomness . PhD thesis, Harvard University, 2014

    work page 2014