Pith. sign in

REVIEW 2 major objections 4 minor 34 references

Generalized and Unified Equivalences between Hardness and Pseudoentropy

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

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

Pith's one-line read A single efficiently computable simulator is simultaneously entropy-optimal and divergence-optimal for every entropy notion in a family with efficiently computable bounded subgradients, unifying hardness–randomness equivalences and…

desk verdict Strong unified pseudoentropy result with a real but fixable gap in the Shannon-entropy case. read the letter →

arxiv 2507.05972 v3 pith:SSNRIROX submitted 2025-07-08 cs.CC cs.CRcs.LG

Lunjia Hu , Salil Vadhan This is my paper · ORCID
classification cs.CCcs.CRcs.LG MSC 68Q1568Q1794A17
keywords pseudoentropyhardness–randomnessequivalencecomputationalindistinguishabilityweight-restrictedcalibrationmultiaccuracyBregmandivergencemultiplicativeweightsexponentiallowerbound
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

The paper sets out to prove that the many known hardness–randomness equivalences — theorems asserting that a distribution which is hard to predict or approximate must have an efficiently indistinguishable copy with higher entropy — are all instances of one statement. The central claim is that for any family $\Phi$ of convex entropy notions whose subgradients are bounded and computable to $\ell^\infty$ accuracy $\varepsilon/4$ in nonuniform time $T_\Phi$, a single simulator $s$ exists that is simultaneously $\varepsilon$-indistinguishable from the true distribution $g^*$, entropy-optimal among indistinguishable simulators, and divergence-optimal among efficient approximators, for every entropy in the family at once. This unifies the characterizations for average min-entropy, Shannon entropy, and collision probability under one theorem and one proof, and it reduces the dependence on the alphabet size from doubly exponential in $\ell$ to polynomial in $L = 2^\ell$. The paper also claims this unification is essentially optimal: without the subgradient-efficiency assumption, even a single trivial distinguisher forces the simulator to have exponential circuit size.

What carries the argument

The load-bearing object is the identity $H_\varphi(s) - H_\varphi(g^*) - D_\varphi(g^*\|s) = \langle g^* - s, \nabla\varphi \circ s\rangle$ (equation (9) of the paper), which converts the desired coincidence of entropy gap and divergence gap into two inner-product conditions: multiaccuracy, meaning $|\langle s - g^*, f\rangle| \leq \varepsilon$ against every low-complexity distinguisher $f$, and weight-restricted calibration, meaning $\langle s - g^*, r_\varphi \circ s\rangle \leq \varepsilon$ for weight functions $r_\varphi$ that approximate the subgradient $\nabla\varphi$ to accuracy $\varepsilon/4$. The paper proves an enhanced regularity lemma — extending the Complexity-Theoretic Regularity Lemma and the Leakage Simulation Lemma from boolean to $L$-ary outputs — by multiplicative weights / mirror descent: starting from the uniform distribution, each violated condition triggers an additive shift $h \leftarrow h - \varepsilon f$ or $h \leftarrow h - \varepsilon (r \circ \hat{g})$, and a Fenchel–Young divergence potential with the softmax map bounds the number of updates by $O((\log L)/\varepsilon^2)$, yielding the stated circuit bound. Unbounded subgradients, as with Shannon entropy, are handled by perturbing distributions away from the simplex boundary before evaluation. The lower-bound half uses a combinatorial design of exponentially many near-disjoint subsets together with a probabilistic counting argument over a random masking function, forcing the simulator to encode $\exp(\Omega(L))$ distinct behaviors.

What would settle it

An explicit counterexample would settle the matter: exhibit a single convex function $\varphi : \Delta_L \to \mathbb{R}$ whose subgradient is computable by a $\operatorname{poly}(L)$-size circuit and a distribution pair $(\mu, g^*)$ such that every function $s$ that is $0.05$-indistinguishable from $g^*$ against the identity distinguisher and satisfies $H_\varphi(s) \geq H_\varphi(g^*) - 0.05$ requires circuit size $\exp(\Omega(L))$; that would refute the claimed polynomial bound of Theorem 1.10. A direct computational check on small instances (for example $L = 2, 4$ with $\varphi(v) = \lVert v \rVert_2^2$) of whether the paper's multiplicative-weights algorithm satisfies $H_\varphi(s) - H_\varphi(g^*) \geq D_\varphi(g^*\|s) - \varepsilon$ at the stated circuit bound would expose any hidden constant or $\varepsilon$-dependence not captured by the theorem.

Watch

Extended reading notes

Core claim

The paper's discovery is that the equivalence between computational hardness and pseudoentropy can be witnessed by one function at once for an entire family of entropy measures. Formally, for every family $\Phi$ of convex functions $\varphi : \Delta_L \to \mathbb{R}$ whose subgradients lie in $[-1,1]^L$ and can be computed to $\ell^\infty$ accuracy $\varepsilon/4$ in nonuniform time $T_\Phi$, and for every target $g^* : \{0,1\}^n \to \Delta_L$, there is a single simulator $s$ that is $(T,\varepsilon)$-indistinguishable from $g^*$, computable in time $T' = O((T+T_\Phi)\log L / \varepsilon^2 + L\cdot\operatorname{poly}(1/\varepsilon, \log L))$, and satisfies $H_\varphi(s) - H_\varphi(g^*) \geq D_\varphi(g^*\|s) - \varepsilon$ for every $\varphi \in \Phi$. Thus the pseudoentropy gap and the Bregman-divergence hardness gap coincide up to $\varepsilon$, achieved by the same function $s$, for every entropy notion in the family simultaneously. The matching converse shows every achievable pseudoentropy gap is at most the best efficient divergence approximation plus $\varepsilon$. The paper further establishes that the efficiency hypothesis is load-bearing: an exponential-in-$L$ lower bound holds even against a single trivial distinguisher when the subgradient of one convex function is not efficiently computable, and this forces the doubly exponential dependence on $\ell$ for multicalibration and calibrated multiaccuracy.

Load-bearing premise

The polynomial-in-$L$ construction rests entirely on assuming that for every entropy $\varphi$ in the family, a subgradient of $\varphi$ bounded in $[-1,1]^L$ can be computed to $\ell^\infty$ accuracy $\varepsilon/4$ by a nonuniform circuit of size $T_\Phi$, and the paper proves that if this assumption fails, even a single trivial distinguisher forces the simulator to exponential circuit size.

Editorial extensions

If this is right

  • Shannon entropy, average min-entropy, and collision probability become corollaries of one theorem, with the very same simulator witnessing the pseudoentropy gap for all of them at once.
  • The single function $s$ is simultaneously the entropy-optimal indistinguishable simulator and the divergence-optimal low-complexity approximator of $g^*$ — the omnipredictor phenomenon — for every $\varphi$ in the family.
  • The alphabet-size dependence improves from doubly exponential in $\ell$ to polynomial in $L = 2^\ell$, and the paper proves that doubly exponential dependence is unavoidable for multicalibration and even for the weaker calibrated multiaccuracy.
  • When the subgradient family is weakly agnostically learnable, the characterization holds in the uniform model of computation with one algorithm for all input lengths, encompassing the uniform min-entropy and Shannon-entropy results.
  • The reverse direction yields a general upper bound: for every $\varphi$, the best efficient approximation of $g^*$ under $D_\varphi$ is within $\varepsilon$ of the largest pseudoentropy gap any indistinguishable simulator can achieve.

Reading between the lines

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

  • A trade-off the paper leaves implicit is the role of the $\varepsilon/4$ subgradient accuracy: treating it as a free parameter $t$ suggests a conjecture that $T'$ grows polynomially in $1/t$, which could be tested numerically for collision probability on small $L$.
  • Equation (9) reads as a design principle: any pair of conditions that controls $\langle s - g^*, f\rangle$ and $\langle s - g^*, r \circ s\rangle$ yields a pseudoentropy characterization, so other fairness-inspired conditions could generate new characterizations with different complexity profiles.
  • The lower bound's convex function is defined through a maximum over a huge design set and depends on a hidden random mask, so it is not explicitly presentable; finding an explicit, small-circuit-presentable $\varphi$ with the same $\exp(\Omega(L))$ effect would pin down exactly what subgradient efficiency buys.
  • Cryptographic extraction steps are currently analyzed against a single entropy measure at a time, such as min-entropy for hardcore bits or Shannon entropy for pseudorandom-generator constructions; the universal simulator suggests one extraction step could satisfy all such analyses simultaneously whenever the relevant subgradients are efficiently computable.
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

2 major / 4 minor

Summary. This paper proposes a unified pseudoentropy characterization for arbitrary families of convex entropy functions, aiming to cover Shannon entropy, min-entropy, and Rényi-type entropies in a single framework. The key identity (9) rewrites the difference between the pseudoentropy gap and the Bregman divergence as an inner product involving the subgradient of the entropy function at the simulator; the authors show that enforcing multiaccuracy together with weight-restricted calibration suffices to control this term. They prove a nonuniform regularity lemma (Theorem 3.1) via multiplicative weights, yielding a single low-complexity simulator satisfying both conditions, and then derive nonuniform (Theorem 1.10) and uniform (Theorem 1.11/4.3) pseudoentropy characterizations. They also prove an exponential lower bound (Theorem 1.12) showing that a computational assumption on the subgradient of the entropy function is necessary. The advertised extension to Shannon entropy is routed through Section 5, where a transformation sigma_phi is introduced; it is in this section that the manuscript has a significant proof gap.

Significance. The paper's core algebraic identity and the multiplicative-weights construction are rigorous and elegant, and the lower-bound proof via probabilistic counting over EFF85 designs is convincing. If the Shannon-entropy workaround is made fully rigorous, the paper would constitute a substantial advance: it would provide a single simulator that simultaneously witnesses pseudoentropy and approximability for a broad family of entropies, with polynomial dependence on the alphabet size instead of the doubly exponential cost of multicalibration, and it would prove the necessity of the gradient-complexity assumption. The conceptual reduction to weight-restricted calibration is also an important contribution. However, because the advertised inclusion of Shannon entropy is not formally derived as written, the central claim of the paper is not yet fully established.

major comments (2)
  1. [Section 5 (Theorem 5.1)] The claim that Theorem 5.1 is proved in the exact same way as Theorem 1.10 is not justified for the Shannon-entropy transformation sigma_phi(v) = (1 - delta)v + delta*u. Applying Theorem 3.1 with R = {r_phi} approximating grad(phi) composed with sigma_phi controls <s - g*, r_phi(s)> and hence, after the l_infinity approximation, <s - g*, grad(phi)(sigma_phi(s))>. But identity (9), applied to sigma_phi composed with s, gives <g* - sigma_phi(s), grad(phi)(sigma_phi(s))> = <g* - s, grad(phi)(sigma_phi(s))> + <s - sigma_phi(s), grad(phi)(sigma_phi(s))>, and the second term is not controlled by the regularity lemma. For the Shannon choice, this uncontrolled term can have magnitude Theta(delta log(L/delta)), so inequality (41) does not follow unless the perturbation delta and the calibration error are chosen with explicit parameter accounting (e.g., epsilon_cal + O(delta log(L/delta)) <= epsilon). The subsequent implications in Section 5 address only indistinguishability and circuit complexity of sigma_phi composed with s, not this term. This is a load-bearing gap because the abstract advertises Shannon entropy as a special case; a fix with explicit constants should be supplied.
  2. [Section 4.2 and Section 5 (Theorem 4.3)] The uniform result Theorem 4.3, which is the formal version of Theorem 1.11, only applies when every phi in Phi has subgradients mapping into [-1,1]^L, because Definition 4.1 and Claim 4.2 concern families R of functions from Delta_L to [-1,1]^L. Shannon entropy does not satisfy this condition, and the final sentence of Section 5 states only that 'similarly, we can prove a generalized version of Theorem 4.3 using Theorem 3.10 to handle unbounded subgradients in the uniform setting' without stating the generalized theorem or giving any proof. Since the paper claims that the uniform characterization encompasses the uniform versions of Theorems 1.2 and 1.3 of Vadhan and Zheng, which include Shannon entropy, this omission is load-bearing and must be filled in, together with the nonuniform parameter accounting described in the previous comment.
minor comments (4)
  1. [Lemma 3.3, item 3] Item 3 states that ||g_hat_k - g_k||_infty <= epsilon/10, but Algorithm 1 (Lines 3, 10, and 15) requires the l1 bound ||g_hat_k - g_k||_1 <= epsilon/10, and the proof of Lemma 3.2 uses the l1 bound. The coordinatewise precision supplied by Lemma 3.4 does give the l1 bound, but the statement of Lemma 3.3 should be corrected.
  2. [Lemma 3.11] The proof of Lemma 3.11 omits the analysis of the running time and evaluation time of the constructed function s, saying only that this follows 'similarly to Lemma 3.3'. In the uniform setting the construction involves sample access and oracle invocations, so the details are not literally identical; a short argument should be included.
  3. [Section 5] The same symbol epsilon is used both for the error parameter in Theorem 5.1 and for the perturbation parameter in sigma_phi(v) = (1 - epsilon)v + epsilon*u. Since the two parameters must be chosen with different scales to close the argument, using distinct names (e.g., delta for the perturbation) is necessary for clarity.
  4. [Throughout] There are several typographical errors, including 'addtionally' in Theorem 3.10, 'strenthening' in Section 1.5, 'diference' in Section 1.5, and 'un-transformeds' in Section 5. These should be corrected.

Circularity Check

1 steps flagged · score 2.0 of 10

No significant circularity: the central identity (9) is an algebraic equality and the regularity lemmas are proved self-contained against explicit assumptions; the flagged Section 5 Shannon-entropy derivation omits a cross-term estimate in identity (9), which is a rigor gap rather than circularity.

  1. other [Section 5, Theorem 5.1 and the claim that it 'can be proved in the exact same way' as Theorem 1.10; Shannon choice sigma_phi(v) = (1 - epsilon)v + epsilon u.]
    "Theorem 5.1 can be proved in the exact same way as Theorem 1.10 using the enhanced regularity lemma Theorem 3.1, and similarly, we can prove a generalized version of Theorem 4.3 using Theorem 3.10 to handle unbounded subgradients in the uniform setting. ... For the (negative) Shannon entropy phi in (25), define sigma_phi(v) = (1 - epsilon)v + epsilon u, where u = (1/L, . . . ,1/L) is the uniform distribution and epsilon in (0, 1/2)."

    Asserting Theorem 5.1 'can be proved in the exact same way as Theorem 1.10' claims that calibration (11) on s, with r_phi approximating grad-phi∘sigma_phi, implies (41). But applying identity (9) to sigma_phi∘s gives H_phi(sigma_phi∘s)-H_phi(g*)-D_phi(g*∥sigma_phi∘s) = ⟨g*-s, grad-phi(sigma_phi(s))⟩ + ⟨s-sigma_phi(s), grad-phi(sigma_phi(s))⟩. The same-way proof controls only the first term; the cross term is uncontrolled. For the paper's Shannon choice, sigma_phi(s)-s = epsilon(u-s) and ∥grad-phi(sigma_phi(s))∥_∞ = ln(L/epsilon), so the cross term can reach ≈2 epsilon ln(L/epsilon), exceeding the epsilon budget of (41).

full rationale

The paper is essentially self-contained and shows no material circularity. The central identity (9) is an algebraic equality derived from Definitions 1.7 and 1.8, converting the target (4) into the calibration condition (10)-(11) without putting the conclusion into the hypotheses. The forward direction of Theorem 1.10 applies the enhanced regularity lemma (Theorem 3.1) with R := {r_phi}_{phi in Phi}, where r_phi approximates grad-phi to ell-infinity accuracy epsilon/4; Theorem 3.1 is proved in full inside the paper by multiplicative weights (Algorithm 1), with the Fenchel-Young potential Gamma(g*,h_k) ≤ ln L giving termination in O((log L)/epsilon^2) updates and the circuit-complexity bookkeeping done in Lemmas 3.3-3.4. The reverse direction (5) follows directly from the identity D_phi(g*∥g) = D_phi(s∥g) + ⟨s-g*, grad-phi∘g⟩ + (H_phi(s)-H_phi(g*)) plus the indistinguishability of s, a plain inequality rather than a fitted equivalence. The lower bound Theorem 1.12 is proved in-reach with a probabilistic counting argument, so the upper bound does not import its own conclusion through a self-citation chain. Citations to [TTV09, JP14, VZ12, VZ13, Zhe14, CDV24] are contextual: the load-bearing regularity lemma is reproved here, no uniqueness theorem or prior ansatz forces the construction, and no parameter is fitted to data, so no 'prediction' reduces to a fit by construction. The one flagged item is Section 5: the assertion that Theorem 5.1 'can be proved in the exact same way' as Theorem 1.10 omits the cross term ⟨s-sigma_phi(s), grad-phi(sigma_phi(s))⟩ that identity (9) produces when applied to the transformed simulator sigma_phi∘s. With the paper's Shannon choice sigma_phi(v) = (1-epsilon)v + epsilon u, this term can be as large as ≈2 epsilon ln(L/epsilon), exceeding the epsilon budget of (41) once grad-phi is scaled by 1/ln(L/epsilon) to satisfy the boundedness assumption, and the paper's mis-alignment discussion bounds only sigma_phi∘s ∈ Ind(g*,T,3epsilon) and D_phi(g*∥sigma_phi∘g) ≤ D_phi(g*∥g) + O(epsilon). Hence the advertised Shannon-entropy special case, and the analogous uniform unbounded-gradient extension, are not formally derived as written; a fix with epsilon_cal + 2 delta ln(L/delta) ≤ epsilon appears plausible but is absent. This affects correctness and rigor, not circularity: the conclusion is not identical to its inputs by definition.

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

All quantitative claims are proven from explicit parameters; no numeric fitting occurs. The main assumptions (efficient subgradients, oracle access) are stated openly and are shown necessary by the lower bound. Background results are standard and cited, so the paper essentially adds the new theorems by its own proofs.

assumptions (6)
  • standard math Standard convex analysis facts: Fenchel-Young divergence nonnegativity, the conjugate-pair characterization (19), and mirror descent potential decrease (Lemma 2.2).
    Used throughout Sections 2 and 3 to analyze the multiplicative-weights algorithms; these are textbook results, with proofs sketched in the paper and appendix.
  • domain assumption The random variable (X, Y) is fully captured by a distribution mu on {0,1}^n and a function g* mapping x to the conditional distribution of Y given x.
    Section 1.3 notation; this is the standard functional representation used in pseudoentropy literature, not an additional restriction.
  • domain assumption Nonuniform circuit model: distinguishers are functions f: {0,1}^n to [-1,1]^L of circuit size at most T, and Time(T') is a well-defined complexity class.
    Definition 1.6 and surrounding text; standard complexity-theoretic framework required by all hardness-randomness equivalences.
  • standard math Erdős-Frankl-Füredi design lemma (Lemma 6.1): there exist m = exp(Omega(n)) subsets of [n] with size at least alpha*n, pairwise intersections at most 2*alpha^2*n, and even sizes.
    Cited as [EFF85] and used in Theorem 1.12 to build the lower-bound gadgets; verified via the probabilistic method.
  • domain assumption Efficiency of subgradients: for every phi in Phi, some subgradient grad-phi(v) is bounded in [-1,1]^L and computable to L-infinity error epsilon/4 in nonuniform time T_Phi.
    Assumption paragraph of Theorem 1.10; this is the load-bearing premise that yields the poly(L) bound and is shown necessary by Theorem 1.12. In the uniform setting it is replaced by weak agnostic learnability (Definition 4.1).
  • domain assumption In the uniform setting, existence of an (m,T)-distinguishing oracle A and an (m,T)-calibration oracle B, and for Theorem 4.3 an ({grad-phi}, epsilon1, epsilon, delta)-weak agnostic calibration oracle.
    Definitions 3.6, 3.7, 4.1; these oracles model access to efficient distinguishers and learners. For finite families, ERM gives such an oracle (Section 4.2).

how reviews work

0 comments
Cite this review

Pith. "Pith review of Generalized and Unified Equivalences between Hardness and Pseudoentropy." pith.science (2026). https://pith.science/paper/SSNRIROX

@misc{pith2026250705972,
  author       = {Pith},
  title        = {Pith review of: Generalized and Unified Equivalences between Hardness and Pseudoentropy},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SSNRIROX}},
  note         = {Machine review of arXiv:2507.05972}
}
read the original abstract

Pseudoentropy characterizations give quantitatively precise formulations of the relationship between computational hardness and computational randomness. We prove a unified pseudoentropy characterization that generalizes and strengthens previous results in both uniform and nonuniform models of computation. Our characterization applies to a general family of entropy notions, including Shannon entropy and min-entropy as special cases. Moreover, the characterizations for these different entropy notions can be witnessed simultaneously by a single universal function, which captures both computational hardness and computational randomness. A key technical insight is that weight-restricted calibration, from the recent literature on algorithmic fairness, together with standard computational indistinguishability (known as multiaccuracy in the fairness literature), suffices for proving pseudoentropy characterizations for general entropy notions. To obtain this combination of properties, we prove an enhanced version of the Leakage Simulation Lemma (Jetchev and Pietrzak, 2014), which in turn extends the Complexity Theoretic-Regularity Lemma (Trevisan, Tulsiani, and Vadhan, 2009) from boolean functions to ones over a larger alphabet. Our Enhanced Regularity/Leakage-Simulation Lemma enables us to obtain an exponential improvement in the dependence on the alphabet size compared with the pseudoentropy characterizations of Casacuberta, Dwork, and Vadhan (2024), which are based on the stronger notion of multicalibration. We also show that this exponential dependence on the alphabet size is inevitable for multicalibration and even for the weaker notion of calibrated multiaccuracy.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

34 extracted references · 15 canonical work pages

  1. [1]

    Complexity-theoretic implications of multicalibration

    S\' lvia Casacuberta, Cynthia Dwork, and Salil Vadhan. Complexity-theoretic implications of multicalibration. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , STOC 2024, page 1071–1082, New York, NY, USA, 2024. Association for Computing Machinery. https://doi.org/10.1145/3618260.3649748 doi:10.1145/3618260.3649748

    arXiv 2024

  2. [2]

    How global calibration strengthens multiaccuracy

    S \' lvia Casacuberta, Parikshit Gopalan, Varun Kanade, and Omer Reingold. How global calibration strengthens multiaccuracy. arXiv preprint arXiv:2504.15206 , 2025

    arXiv 2025

  3. [3]

    Why simple hash functions work: Exploiting the entropy in a data stream

    Kai-Min Chung, Michael Mitzenmacher, and Salil Vadhan. Why simple hash functions work: Exploiting the entropy in a data stream. Theory of Computing , 9(30):897--945, 2013. URL: https://theoryofcomputing.org/articles/v009a030, https://doi.org/10.4086/toc.2013.v009a030 doi:10.4086/toc.2013.v009a030

    work page doi:10.4086/toc.2013.v009a030 2013

  4. [4]

    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 Gergely Neu and Lorenzo Rosasco, editors, Proceedings of Thirty Sixth Conference on Learning Theory , volume 195 of Proceedings of Machine Learning Research , pages 3566--3614. PMLR, 12--15 Jul 2023. URL: https://proceedings.mlr.press/v195...

    work page 2023

  5. [5]

    Fuzzy extractors: How to generate strong keys from biometrics and other noisy data

    Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, and Adam Smith. Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. SIAM Journal on Computing , 38(1):97--139, 2008. https://arxiv.org/abs/https://doi.org/10.1137/060651380 arXiv:https://doi.org/10.1137/060651380 , https://doi.org/10.1137/060651380 doi:10.1137/060651380

    doi:10.1137/060651380 2008

  6. [6]

    Personal communication, 2025

    Cynthia Dwork and Pranay Tankala. Personal communication, 2025. June 2025

    work page 2025

  7. [7]

    Erdös, P

    P. Erdös, P. Frankl, and Z. F \"u redi. Families of finite sets in which no set is covered by the union of others. Israel Journal of Mathematics , 51(1):79--89, 1985. https://doi.org/10.1007/BF02772959 doi:10.1007/BF02772959

    doi:10.1007/bf02772959 1985

  8. [8]

    Distribution-specific agnostic boosting

    Vitaly Feldman. Distribution-specific agnostic boosting. In Andrew Chi - Chih Yao, editor, Innovations in Computer Science - ICS 2010, Tsinghua University, Beijing, China, January 5-7, 2010. Proceedings , pages 241--250. Tsinghua University Press, 2010. URL: http://conference.iiis.tsinghua.edu.cn/ICS2010/content/papers/20.html

    work page 2010

Show all 34 references
  1. [9]

    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 Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) , volume 251 of Leibniz Inter...

    2023 doi

  2. [10]

    Rothblum

    Parikshit Gopalan, Lunjia Hu, and Guy N. Rothblum. On computationally efficient multi-class calibration. In Shipra Agrawal and Aaron Roth, editors, Proceedings of Thirty Seventh Conference on Learning Theory , volume 247 of Proceedings of Machine Learning Research , pages 1983...

    1983

  3. [11]

    Omnipredictors

    Parikshit Gopalan, Adam Tauman Kalai, Omer Reingold, Vatsal Sharan, and Udi Wieder. Omnipredictors . In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) , volume 215 of Leibniz International Proceedings in Informatics (LIPIcs) , p...

    2022 doi

  4. [12]

    Low-degree multicalibration

    Parikshit Gopalan, Michael P Kim, Mihir A Singhal, and Shengjia Zhao. Low-degree multicalibration. In Po-Ling Loh and Maxim Raginsky, editors, Proceedings of Thirty Fifth Conference on Learning Theory , volume 178 of Proceedings of Machine Learning Research , pages 3193--3234....

    2022

  5. [13]

    Goldreich and L

    O. Goldreich and L. A. Levin. A hard-core predicate for all one-way functions. In Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing , STOC '89, page 25–32, New York, NY, USA, 1989. Association for Computing Machinery. https://doi.org/10.1145/73007.730...

    1989

  6. [14]

    Levin, and Michael Luby

    Johan H A stad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby. A pseudorandom generator from any one-way function. SIAM Journal on Computing , 28(4):1364--1396, 1999. https://doi.org/10.1137/S0097539793244708 doi:10.1137/S0097539793244708

    1999 doi

  7. [15]

    Multicalibration: Calibration for the ( C omputationally-identifiable) masses

    Ursula Hebert-Johnson , Michael Kim, Omer Reingold, and Guy Rothblum. Multicalibration: Calibration for the ( C omputationally-identifiable) masses. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning , volume 80 of ...

    1939

  8. [16]

    Generative Models of Huge Objects

    Lunjia Hu, Inbal Rachel Livni Navon, and Omer Reingold. Generative Models of Huge Objects . In Amnon Ta-Shma, editor, 38th Computational Complexity Conference (CCC 2023) , volume 264 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 5:1--5:20, Dagstuhl, Germ...

    2023 doi

  9. [17]

    Conditional computational entropy, or toward separating pseudoentropy from compressibility

    Chun-Yuan Hsiao, Chi-Jen Lu, and Leonid Reyzin. Conditional computational entropy, or toward separating pseudoentropy from compressibility. In Moni Naor, editor, Advances in Cryptology - EUROCRYPT 2007 , pages 169--186, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg

    2007

  10. [18]

    Statistically hiding commitments and statistical zero-knowledge arguments from any one-way function

    Iftach Haitner, Minh-Huyen Nguyen, Shien Jin Ong, Omer Reingold, and Salil Vadhan. Statistically hiding commitments and statistical zero-knowledge arguments from any one-way function. SIAM Journal on Computing , 39(3):1153--1218, 2009. https://arxiv.org/abs/https://doi.org/10....

    2009 doi

  11. [19]

    Key agreement from weak bit agreement

    Thomas Holenstein. Key agreement from weak bit agreement. In Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing , STOC '05, page 664–673, New York, NY, USA, 2005. Association for Computing Machinery. https://doi.org/10.1145/1060590.1060689 doi:10.114...

    2005

  12. [20]

    Omnipredicting single-index models with multi-index models

    Lunjia Hu, Kevin Tian, and Chutong Yang. Omnipredicting single-index models with multi-index models. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing , STOC '25, page 1762–1773, New York, NY, USA, 2025. Association for Computing Machinery. https://doi.org...

    2025

  13. [21]

    Impagliazzo

    R. Impagliazzo. Hard-core distributions for somewhat hard problems. In Proceedings of IEEE 36th Annual Foundations of Computer Science , pages 538--545, 1995. https://doi.org/10.1109/SFCS.1995.492584 doi:10.1109/SFCS.1995.492584

    1995

  14. [22]

    How to fake auxiliary input

    Dimitar Jetchev and Krzysztof Pietrzak. How to fake auxiliary input. In Yehuda Lindell, editor, Theory of Cryptography , pages 566--590, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg

    2014

  15. [23]

    Kim, Amirata Ghorbani, and James Zou

    Michael P. Kim, Amirata Ghorbani, and James Zou. Multiaccuracy: Black-box post-processing for fairness in classification. In Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society , AIES '19, page 247–254, New York, NY, USA, 2019. Association for Computing Mach...

    2019

  16. [24]

    On agnostic boosting and parity learning

    Adam Tauman Kalai, Yishay Mansour, and Elad Verbin. On agnostic boosting and parity learning. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing , STOC '08, page 629–638, New York, NY, USA, 2008. Association for Computing Machinery. https://doi.org/10.1...

    2008

  17. [25]

    Characterizing the distinguishability of product distributions through multicalibration

    Cassandra Marcussen, Aaron Putterman, and Salil Vadhan. Characterizing the distinguishability of product distributions through multicalibration. arXiv preprint arXiv:2412.03562 , 2024

    2024

  18. [26]

    Near-optimal algorithms for omniprediction

    Princewill Okoroafor, Robert Kleinberg, and Michael P Kim. Near-optimal algorithms for omniprediction. arXiv preprint arXiv:2501.17205 , 2025

    2025

  19. [27]

    Convex analysis , volume 28

    R Tyrrell Rockafellar. Convex analysis , volume 28. Princeton university press, 1997

    1997

  20. [28]

    Dense subsets of pseudorandom sets

    Omer Reingold, Luca Trevisan, Madhur Tulsiani, and Salil Vadhan. Dense subsets of pseudorandom sets. In Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science , FOCS '08, page 76–85, USA, 2008. IEEE Computer Society. https://doi.org/10.1109/FOCS....

    2008 doi

  21. [29]

    Regularity, boosting, and efficiently simulating every high-entropy distribution

    Luca Trevisan, Madhur Tulsiani, and Salil Vadhan. Regularity, boosting, and efficiently simulating every high-entropy distribution. In Proceedings of the 2009 24th Annual IEEE Conference on Computational Complexity , CCC '09, page 126–136, USA, 2009. IEEE Computer Society. htt...

    2009 doi

  22. [30]

    Salil P. Vadhan. Pseudorandomness. Foundations and Trends® in Theoretical Computer Science , 7(1–3):1--336, 2012. URL: http://dx.doi.org/10.1561/0400000010, https://doi.org/10.1561/0400000010 doi:10.1561/0400000010

    2012 doi

  23. [31]

    Characterizing pseudoentropy and simplifying pseudorandom generator constructions

    Salil Vadhan and Colin Jia Zheng. Characterizing pseudoentropy and simplifying pseudorandom generator constructions. In Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing , STOC '12, page 817–836, New York, NY, USA, 2012. Association for Computing Mach...

    2012

  24. [32]

    A uniform min-max theorem with applications in cryptography

    Salil Vadhan and Colin Jia Zheng. A uniform min-max theorem with applications in cryptography. In Ran Canetti and Juan A. Garay, editors, Advances in Cryptology -- CRYPTO 2013 , pages 93--110, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg

    2013

  25. [33]

    Andrew C. Yao. Theory and application of trapdoor functions. In 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982) , pages 80--91, 1982. https://doi.org/10.1109/SFCS.1982.45 doi:10.1109/SFCS.1982.45

    1982 doi

  26. [34]

    A Uniform Min-Max Theorem and Characterizations of Computational Randomness

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

    2014

Pith tools

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