pith. sign in

arxiv: 2511.03653 · v2 · submitted 2025-11-05 · 💻 cs.CC · cs.DS· cs.LG

Efficient and Private Property Testing via Indistinguishability

Cynthia Dwork , Pranay Tankala This is my paper

Pith reviewed 2026-05-18 00:53 UTC · model grok-4.3

classification 💻 cs.CC cs.DScs.LG
keywords property testingBoolean functionsstructured symmetryregular partitionssupersimulatordifferential privacyindistinguishabilitycomputational complexity
0
0 comments X

The pith

Properties of Boolean functions efficiently testable from few samples are exactly those with structured symmetry based on averages over an efficiently computable partition of the domain.

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

The paper shows an equivalence: a property of an unknown Boolean function can be tested efficiently using only a small random sample of labeled inputs if and only if the property depends solely on the function's average values across the blocks of some efficiently computable partition of the domain. This structured-symmetry characterization parallels the classic regular-partition description of testable graph properties but is adapted here to functions. The equivalence is proved using a new supersimulator construction, which produces a simple randomized circuit that cannot be efficiently distinguished from the original complex function. The work also supplies a sublinear-time differentially private algorithm that outputs concise summaries of regular partitions for graphs and tightens an existing characterization of when two product distributions are computationally indistinguishable.

Core claim

A Boolean function property admits an efficient tester from few samples precisely when it exhibits structured symmetry, meaning it is completely determined by the function's average values on the blocks of an efficiently computable partition of the domain. The paper establishes this equivalence by constructing, for any randomized Boolean function, a supersimulator: a randomized polynomial-size circuit whose behavior on random inputs is indistinguishable from the original function by any efficient distinguisher. The construction iterates a regularity technique from the graph literature in a way that sidesteps known barriers, and the same machinery yields both the function-testing analogue of

What carries the argument

The supersimulator: a randomized polynomial-size circuit that, on random inputs, produces output statistically and computationally indistinguishable from any given randomized Boolean function, even against larger distinguishers.

If this is right

  • Any efficiently testable property yields an explicit efficiently computable partition that can be used to design the tester.
  • Concise summaries of regular partitions of graphs can be computed in sublinear time while satisfying differential privacy.
  • The computational indistinguishability relation between product distributions is tightened, directly improving tests that decide which of two candidate functions produced the observed samples.
  • The supersimulator exists for every randomized Boolean function, supplying a uniform way to replace complex functions by simple circuits in any setting that only requires efficient indistinguishability.

Where Pith is reading between the lines

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

  • The same partition-based view may supply new testers for properties of distributions or other combinatorial objects beyond Boolean functions.
  • Because the supersimulator was originally observed in an algorithmic-fairness context, the construction may yield new ways to simplify models while preserving efficient indistinguishability guarantees.
  • If the quantifier switch that avoids prior regularity barriers generalizes, similar iterative techniques could improve other complexity-theoretic regularity results.

Load-bearing premise

Any structured symmetry possessed by an efficiently testable property can be realized by a partition that is both efficiently computable and obtainable via the iterative regularity construction without encountering the known barriers to improving regularity lemmas.

What would settle it

An explicit Boolean function property that is testable with a constant number of samples yet whose symmetry cannot be expressed by any polynomial-time computable partition, or an efficient algorithm that distinguishes a claimed supersimulator from the original randomized function with non-negligible advantage.

Figures

Figures reproduced from arXiv: 2511.03653 by Cynthia Dwork, Pranay Tankala.

Figure 1
Figure 1. Figure 1: Illustration of the supersimulator construction of Section [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
read the original abstract

Given a small random sample of $n$-bit strings labeled by an unknown Boolean function, which properties of this function can be tested computationally efficiently? We show an equivalence between properties that are efficiently testable from few samples and properties with structured symmetry, which depend only on the function's average values on an efficiently computable partition of the domain. Without the efficiency constraint, a similar characterization in terms of unstructured symmetry was obtained by Blais and Yoshida (2019). We also give a function testing analogue of the classic characterization of testable graph properties in terms of regular partitions, as well as a sublinear time and differentially private algorithm to compute concise summaries of such partitions of graphs. Finally, we tighten a recent characterization of the computational indistinguishability of product distributions, which encompasses the related task of efficiently testing which of two candidate functions labeled the observed samples. Essential to our proofs is the following observation of independent interest: Every randomized Boolean function, no matter how complex, 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. This surprising fact is implicit in a theorem of Dwork et al. (2021) in the context of algorithmic fairness, but its complexity-theoretic implications were not previously explored. We give a new proof of this lemma using an iteration technique from the graph regularity literature, and we observe that a subtle quantifier switch allows it to powerfully circumvent known barriers to improving the landmark complexity-theoretic regularity lemma of Trevisan, Tulsiani, and Vadhan (2009).

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

0 major / 2 minor

Summary. The paper claims an equivalence between Boolean function properties efficiently testable from few samples and those with structured symmetry depending only on averages over an efficiently computable domain partition. It gives a function-testing analogue of testable graph properties via regular partitions, a sublinear-time differentially private algorithm for partition summaries, and tightens a characterization of computational indistinguishability for product distributions. Central is a supersimulator lemma for randomized Boolean functions, proved via iterated regularity from graph theory with a quantifier switch to circumvent barriers from Trevisan, Tulsiani, and Vadhan (2009).

Significance. If the results hold, this advances property testing and complexity by linking efficient testability to structured symmetry and indistinguishability, with the supersimulator lemma of independent interest and potential applications in fairness. The new proof of the supersimulator lemma via iteration and the sublinear private algorithm are notable strengths. These could influence sublinear algorithms and privacy research.

minor comments (2)
  1. Provide more details on the quantifier switch in the supersimulator lemma proof to clarify how it circumvents the barriers of Trevisan, Tulsiani, and Vadhan (2009).
  2. State the main equivalence theorem explicitly early in the introduction for improved readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript, including the summary of our results on the equivalence between efficient sample-based property testing and structured symmetry, the supersimulator lemma, and the sublinear-time private algorithm. We appreciate the recommendation for minor revision and will incorporate clarifications and improvements in the next version.

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper derives an equivalence between efficiently testable properties (from few samples) and structured symmetry properties depending only on averages over an efficiently computable partition. The central technical step is the supersimulator lemma, supported by a new proof via iterated regularity from the graph regularity literature that explicitly circumvents the Trevisan-Tulsiani-Vadhan barriers through a quantifier switch. This construction is presented as independent, with equivalence directions following from the lemma and the graph-property analogue. Citations to Blais-Yoshida (2019) and Dwork et al. (2021) provide context for the unstructured case and an implicit fact, respectively, but do not serve as load-bearing self-citations that reduce the result to prior unverified claims by the same authors. No steps reduce by definition, fitted parameters renamed as predictions, or ansatz smuggling; the derivation remains self-contained against external benchmarks and literature.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard complexity-theoretic assumptions about efficient computability and polynomial-size circuits; no free parameters or new invented entities are introduced beyond the supersimulator concept derived from prior implicit results.

axioms (1)
  • standard math Standard assumptions in computational complexity: polynomial-time computability of partitions and circuits, and existence of efficient distinguishers.
    Invoked when defining 'efficiently computable partition' and 'polynomially larger distinguishers' in the supersimulator statement.

pith-pipeline@v0.9.0 · 5821 in / 1304 out tokens · 38820 ms · 2026-05-18T00:53:27.663599+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

38 extracted references · 38 canonical work pages

  1. [1]

    A combinatorial characterization of the testable graph properties: it's all about regularity

    Noga Alon, Eldar Fischer, Ilan Newman, and Asaf Shapira. A combinatorial characterization of the testable graph properties: it's all about regularity. In ACM Symposium on Theory of Computing ( STOC ) , 2006

    work page 2006

  2. [2]

    A characterization of the (natural) graph properties testable with one-sided error

    Noga Alon and Asaf Shapira. A characterization of the (natural) graph properties testable with one-sided error. In IEEE Symposium on Foundations of Computer Science, ( FOCS ) , 2005

    work page 2005

  3. [3]

    Every monotone graph property is testable

    Noga Alon and Asaf Shapira. Every monotone graph property is testable. In ACM Symposium on Theory of Computing ( STOC ) , 2005

    work page 2005

  4. [4]

    Convex optimization: Algorithms and complexity

    S\' e bastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning , 8(3–4):231–357, 2015

    work page 2015

  5. [5]

    A characterization of constant-sample testable properties

    Eric Blais and Yuichi Yoshida. A characterization of constant-sample testable properties. Random Structures and Algorithms , 55(1):73--88, 2019

    work page 2019

  6. [6]

    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

  7. [7]

    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

  8. [8]

    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

  9. [9]

    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

  10. [10]

    Supersimulators, 2025

    Cynthia Dwork and Pranay Tankala. Supersimulators, 2025

    work page 2025

  11. [11]

    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

  12. [12]

    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

  13. [13]

    , Diptaksho Palit, and Sofya Raskhodnikova

    Renato Ferreira Pinto Jr. , Diptaksho Palit, and Sofya Raskhodnikova. Computational complexity in property testing. In ACM-SIAM Symposium on Discrete Algorithms ( SODA ) , 2026. To appear

    work page 2026

  14. [14]

    Property testing and its connection to learning and approximation

    Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. In IEEE Symposium on Foundations of Computer Science ( FOCS ) , 1996

    work page 1996

  15. [15]

    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

  16. [16]

    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

  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]

    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

  20. [20]

    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

  21. [21]

    Liu, Shachar Lovett, Anthony Ostuni, and Mehtaab Sawhney

    Michael Jaber, Yang P. Liu, Shachar Lovett, Anthony Ostuni, and Mehtaab Sawhney. Quasipolynomial bounds for the corners theorem. In IEEE Symposium on Foundations of Computer Science ( FOCS ) , 2025

    work page 2025

  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]

    Strong bounds for 3-progressions

    Zander Kelley and Raghu Meka. Strong bounds for 3-progressions. In IEEE Symposium on Foundations of Computer Science ( FOCS ) , 2023

    work page 2023

  24. [24]

    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

  25. [25]

    Algebraic property testing: the role of invariance

    Tali Kaufman and Madhu Sudan. Algebraic property testing: the role of invariance. In ACM Symposium on Theory of Computing ( STOC ) , 2008

    work page 2008

  26. [26]

    Brendan McMahan

    H. Brendan McMahan. A survey of algorithms and analysis for adaptive online learning. Journal of Machine Learning Research , 18(90):1--50, 2017

    work page 2017

  27. [27]

    Characterizing the distinguishability of product distributions through multicalibration

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

    work page 2025

  28. [28]

    Robust characterizations of polynomials with applications to program testing

    Ronitt Rubinfeld and Madhu Sudan. Robust characterizations of polynomials with applications to program testing. SIAM Journal on Computing , 25(2):252--271, 1996

    work page 1996

  29. [29]

    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

  30. [30]

    Invariance in Property Testing , pages 211--227

    Madhu Sudan. Invariance in Property Testing , pages 211--227. Springer Berlin Heidelberg, 2010

    work page 2010

  31. [31]

    Regular partitions of graphs

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

    work page 1975

  32. [32]

    Structure and randomness in combinatorics

    Terence Tao. Structure and randomness in combinatorics. In IEEE Symposium on Foundations of Computer Science ( FOCS ) , 2007

    work page 2007

  33. [33]

    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

  34. [34]

    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

  35. [35]

    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

  36. [36]

    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

  37. [37]

    Graph Theory and Additive Combinatorics

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

    work page 2023

  38. [38]

    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