Pith. sign in

REVIEW 4 minor 300 references

The INW pseudorandom generator ε-fools permutation branching programs with seed length O((log w + log(1/ε))·log n), matching the spectral-analysis lower bound.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · deepseek-v4-flash

2026-08-01 15:47 UTC pith:JVW4LB6R

load-bearing objection This is the real thing: a new INW analysis that gets optimal log n and log w for permutation BPs, matching the spectral lower bound; the forward-backward weight trick is genuinely new and the proof checks out.

arxiv 2607.18168 v2 pith:JVW4LB6R submitted 2026-07-20 cs.CC cs.DS

A Forward-Backward Weight Analysis of INW for Permutation Branching Programs

Gil Cohen , Dean Doron , Noam Goldgraber This is my paper
classification cs.CC cs.DS MSC 68Q1568Q1705C50
keywords pseudorandom generatorpermutation branching programsread-once branching programsINW generatorexpander graphsspectral expansionforward-backward weightsseed length
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The paper proves that the decades-old INW generator, when instantiated with expanders whose expansion is polynomial in width w and 1/ε but independent of length n, fools permutation branching programs with essentially optimal seed length. The key is a new error analysis that tracks both a forward weight and a backward weight of the program, showing that the error from the generator's seed-recycling steps does not accumulate across the recursion. This improves the dependence on width from exponential or quartic in previous analyses to a logarithm, and attains the optimal logarithmic dependence on length that prior regular-branching-program analyses missed. The result is tight for any spectral analysis of INW, matching a known lower bound. If correct, it means one of the simplest pseudorandom generators is optimal for reversible computation, up to constants.

Core claim

The paper establishes that the expander-based INW generator with spectral expansion λ = ε/(32w^3) is an ε-PRG for permutation read-once branching programs of length n and width w, with seed length O((log(1/ε) + log w)·log n). The proof works by defining, for each interval of the program, a forward weight and a backward weight that measure how much the program's layers mix test vectors. The central estimate shows the error of one seed-recycling step is bounded by the product of the forward and backward weights times the expander's spectral expansion, and an induction then shows the total error stays bounded by O(λ) times the product of the total forward and backward weights, each at most 2w t

What carries the argument

The central object is the forward–backward weight pair: for a permutation branching program, the forward weight F_I(p) = Σ_t ‖p_t^T (P_{t,0} − P_{t,1})‖₁ and backward weight B_I(q) = Σ_t ‖(P_{t,0} − P_{t,1}) q_{t+1}‖₁, where p_t and q_t are the propagated test vectors. These are controlled by a weight lemma extended to arbitrary real vectors, bounding each weight by 2Σ_{i<j}|v_i − v_j| ≤ 2w‖v‖₁. The proof then uses the vector-valued expander mixing lemma to bound the seed-recycling error by λ·F_L(p)·B_R(q), and an induction over dyadic intervals shows the error does not accumulate, yielding the final bound. A reformulation in terms of program-dependent seminorms, and a refined potential Φ_I(

Load-bearing premise

The argument hinges on the weight lemma's extension to arbitrary real-valued labels via affine rescaling, which requires the branching program's transition operators to preserve the all-ones vector — a property of permutation programs that does not hold for arbitrary regular programs.

What would settle it

Enumerate all width-2 permutation branching programs of small length (say n=8), implement the INW generator with λ = ε/(32w^3) using an explicit expander family, and measure the maximum deviation in acceptance probability over all programs; if any deviation exceeds ε, the central claim is false.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • For constant width and constant error, the seed length becomes O(log n), which is optimal, and the generator remains explicit and space-efficient.
  • The width dependence in the seed length improves from previous super-polynomial or w^4 penalties to just O(log w), matching the spectral lower bound.
  • The proof's forward–backward weight decomposition shows that the expander degree can be completely independent of the program length, eliminating the log log n term present in prior regular-branching-program analyses.
  • The refined analysis gives an exact convolution identity for the error, Φ_I(p,q) = Σ_{t<u} f_t b_u, identifying exactly which layer pairs contribute to the total error and offering a new tool for future analyses.

Where Pith is reading between the lines

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

  • Extending the forward–backward symmetry to regular (non-permutation) branching programs would require a two-sided weight that works when the reversed program is not regular; the current proof exploits the fact that permutation programs remain permutation-regular when reversed.
  • The convolution form suggests a probabilistic interpretation: the total error is driven by ordered pairs of layers separated by the recursion split, which could lead to testable predictions about which permutation programs are hardest to fool.
  • The binary-alphabet restriction is load-bearing: the proof relies on the two-label structure, so the gap to the d-letter lower bound (Ω(log n·log log min{n,d})) remains open, and a different technique would be needed to close it.
  • Since the seed length matches a lower bound that assumes only spectral expansion, any further improvement would have to exploit non-spectral properties of the expanders, which may inspire new generator designs.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 4 minor

Summary. This paper gives a new analysis of the INW pseudorandom generator for permutation read-once branching programs (ROBPs). The main theorem (Theorem 3.1) states that if the expanders in the INW construction have spectral expansion λ = ε/(32w^3), then the generator ε-fools length-n width-w permutation ROBPs, with seed length O((log w + log(1/ε)) log n). The proof introduces 'forward' and 'backward' weight functions built on the BRRY weight, proves a key expander-product estimate (Proposition 3.4) using a vector-valued expander mixing lemma, and then proves by induction (Proposition 3.5) that the error measured against these weights does not accumulate with recursion depth. The paper also recasts the argument in terms of interval-dependent forward-backward seminorms and gives a refined inductive potential with a convolution interpretation. The appendix supplies missing proofs for the vector-valued mixing lemma and for the extension of the BRRY weight lemma to arbitrary real vectors.

Significance. If correct, the result achieves the natural optimal parameters for spectral analyses of the INW generator against permutation branching programs, matching the HPV24 lower bound up to constants. It improves exponentially over De and Steinke in the width dependence and removes the log log n term from the BRRY bound in the permutation case. The proof is elegant and mostly self-contained: the key imported tool is Lemma 5 of [BRRY14], and the paper supplies the needed extension to arbitrary real labels (Lemma 3.2, Appendix A), which is valid because both a permutation BP and its reversal are regular, so T_t 1 = 1 in both directions. The induction in Proposition 3.5 closes cleanly with constants c = 2, λ = ε/(32w^3), and the restriction to permutation BPs is genuinely load-bearing rather than cosmetic. This is a strong contribution to the derandomization literature.

minor comments (4)
  1. [Section 2.3] In the definition of the INW construction, H_i is described as '2d-regular'. Since the seed for G_i is (x,y) with y in {0,1}^d, the degree must be 2^d. Please correct the notation, or clarify the parameterization.
  2. [Abstract / Theorem 1.1] The phrase 'INW-generator set' is awkward; 'INW generator construction' or 'INW generator instantiation' would be clearer.
  3. [Section 4.1, Eqs. (4.2)-(4.3)] The comparison with the seminorm of [CHL+23] is useful but the transpose conventions are stated quickly. A one-sentence explanation of how D^-_{eT_L}(p)^2 equals their interval seminorm under W_{r←ℓ}=T_{[ℓ,r)}^T would help the reader avoid confusion.
  4. [Appendix A, Lemma 3.2 proof] When applying Lemma 5 of [BRRY14] to the reversed program, the sentence 'the backward propagation in the reversed program is precisely...' assumes the reader re-indexes layers. Explicitly noting that (P_{t,0}^T, P_{t,1}^T) are permutation matrices and hence the reversed program is again regular would remove any residual doubt.

Circularity Check

0 steps flagged

No significant circularity: the main theorem is a self-contained spectral analysis of INW over permutation BPs, relying on the external BRRY weight lemma; the sole self-citation defines weighted PRGs and is not load-bearing.

full rationale

The derivation in Theorem 3.1 is independent of its conclusion. The seed length O((log(1/ε)+log w)log n) follows from instantiating the INW generator with λ=ε/(32w^3), and the proof of error ε-fooling is carried out in Propositions 3.4 and 3.5. The load-bearing external input is Lemma 5 of [BRRY14], whose authors are disjoint from the present paper. Its extension to arbitrary real vectors in Lemma 3.2 and Appendix A is justified by affine rescaling, and the rescaling is valid precisely because permutation BPs satisfy T_t1=1 for both the program and its reversal; no assumption of the target error or seed length is used. The induction in Proposition 3.5 closes with explicit constants, and the final substitution p=e_s, q=1_A, c=2, λ=ε/(32w^3) gives error at most ε/4. The only self-citation is [BCG20], footnote 1, for the definition of weighted PRGs; it is not used in the proof of Theorem 3.1. The cited lower bound [HPV24] is mentioned only to state tightness, not as a premise. There are no fitted parameters relabeled as predictions, no self-citation chain forcing the result, and no uniqueness theorem imported from the authors. The proof is therefore not circular; it receives score 1 only for the presence of a minor, non-load-bearing self-citation.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 0 invented entities

The proof is a self-contained analysis of the standard INW construction. It imports an explicit expander family and the BRRY weight inequality; all other estimates are proved in the paper. There are no fitted constants, no hidden parameters, and no invented entities.

axioms (3)
  • domain assumption BRRY weight bound (Lemma 5 of [BRRY14]): for a regular width-w BP with terminal labels, total layer influence is at most 2Σ_{i<j}|q_i-q_j|.
    Used in Lemma 3.2 to bound forward/backward weights; the paper gives an affine-rescaling proof for arbitrary real vectors, but the underlying inequality is imported.
  • domain assumption Explicit λ-expander family with degree (1/λ)^{Θ(1)} on every vertex set (Theorem 2.5, [MRSV19]).
    Needed to instantiate INW with seed length O(log(1/λ) log n); standard explicit construction, not proved in this paper.
  • standard math Spectral expander mixing lemma for vector-valued zero-mean functions (Lemma 2.6).
    Proved in Appendix A from the spectral definition; used as a black box in Proposition 3.4.

pith-pipeline@v1.3.0-alltime-deepseek · 16304 in / 17762 out tokens · 158685 ms · 2026-08-01T15:47:14.494858+00:00 · methodology

0 comments
read the original abstract

We construct an $\varepsilon$-error PRG for permutation read-once branching programs of length $n$ and width $w$ with seed length \[ O\left((\log w+\log(1/\varepsilon))\cdot \log n\right). \] This gives an exponential improvement in the dependence on $w$ compared with the constructions of De (CCC 2011) and Steinke (ECCC 2012). Compared with the work of Braverman, Rao, Raz, and Yehudayoff (FOCS 2010; SICOMP 2014), which applies more generally to regular branching programs and already achieves the optimal dependence on $w$, our result improves the dependence on the length $n$, attaining the optimal logarithmic dependence. The generator itself is the classical INW PRG of Impagliazzo, Nisan, and Wigderson (STOC 1994). We show that, for permutation branching programs, the INW generator can be instantiated with expanders whose degrees are polynomial in $w$ and $1/\varepsilon$ and, crucially, independent of $n$. To prove this, we analyze error propagation using program-dependent seminorms tailored to the branching program at hand. These seminorms build on the weight function introduced by Braverman et al. The key point is that, when measured in these adapted seminorms, the error does not accumulate throughout the recursion. Since our analysis relies only on the spectral expansion of the underlying expanders, our seed length tightly matches the recent lower bound for spectral analyses of the INW generator due to Hoza, Pyne, and Vadhan (Algorithmica 2024).

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

300 extracted references · 13 canonical work pages

  1. [1]

    SIAM Journal on Computing , volume =

    Braverman, Mark and Rao, Anup and Raz, Ran and Yehudayoff, Amir , title =. SIAM Journal on Computing , volume =. 2014 , doi =. https://doi.org/10.1137/120875673 , abstract =

    work page doi:10.1137/120875673 2014

  2. [2]

    Simplifying the

    Daniel Kozlov , year =. Simplifying the

  3. [3]

    Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    Weighted pseudorandom generators via inverse analysis of random walks and shortcutting , author=. Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2023 , organization=

    2023

  4. [4]

    Opening up the distinguisher: A hardness to randomness approach

    Doron, Dean and Pyne, Edward and Tell, Roei , booktitle=. Opening up the distinguisher: A hardness to randomness approach

  5. [5]

    Computational Complexity Conference (CCC) , year=

    Derandomization with minimal memory footprint , author=. Computational Complexity Conference (CCC) , year=

  6. [6]

    Saks and Shiyu Zhou , title =

    Michael E. Saks and Shiyu Zhou , title =. Journal of Computer and System Sciences , volume =. 1999 , pages =

    1999

  7. [7]

    Annual Symposium on Theory of Computing (STOC) , pages=

    Near-optimal derandomization of medium-width branching programs , author=. Annual Symposium on Theory of Computing (STOC) , pages=

  8. [8]

    Annual Symposium on Theory of Computing (STOC) , pages=

    Approximating iterated multiplication of stochastic matrices in small space , author=. Annual Symposium on Theory of Computing (STOC) , pages=

  9. [9]

    Information and Control , FJOURNAL =

    Borodin, Allan and Cook, Stephen and Pippenger, Nicholas , TITLE =. Information and Control , FJOURNAL =. 1983 , NUMBER =. doi:10.1016/S0019-9958(83)80060-6 , URL =

    work page doi:10.1016/s0019-9958(83)80060-6 1983

  10. [10]

    Jung , title =

    H. Jung , title =. Mathematical Foundations of Computer Science (MFCS) , series =. 1981 , url =. doi:10.1007/3-540-10856-4\_101 , timestamp =

    work page doi:10.1007/3-540-10856-4 1981

  11. [11]

    Theoretical Computer Science , FJOURNAL =

    Simon, Janos , TITLE =. Theoretical Computer Science , FJOURNAL =. 1981 , NUMBER =. doi:10.1016/0304-3975(81)90032-3 , URL =

    work page doi:10.1016/0304-3975(81)90032-3 1981

  12. [12]

    SIAM Journal on Computing , FJOURNAL =

    Gill, John , TITLE =. SIAM Journal on Computing , FJOURNAL =. 1977 , NUMBER =. doi:10.1137/0206049 , URL =

    work page doi:10.1137/0206049 1977

  13. [13]

    2023 , organization=

    Singular value approximation and sparsifying random walks on directed graphs , author=. 2023 , organization=

    2023

  14. [14]

    Approximation, Randomization, and Combinatorial Optimization

    Deterministic Approximation of Random Walks in Small Space , author=. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019) , pages =. 2019 , organization=

    2019

  15. [15]

    Innovations in Theoretical Computer Science Conference (ITCS) , year=

    Pseudorandom generators for unbounded-width permutation branching programs , author=. Innovations in Theoretical Computer Science Conference (ITCS) , year=

  16. [16]

    2021 , MRCLASS =

    Pyne, Edward and Vadhan, Salil , TITLE =. 2021 , MRCLASS =

    2021

  17. [17]

    2020 , MRCLASS =

    Ahmadinejad, AmirMahdi and Kelner, Jonathan and Murtagh, Jack and Peebles, John and Sidford, Aaron and Vadhan, Salil , TITLE =. 2020 , MRCLASS =. doi:10.1109/FOCS46700.2020.00123 , URL =

    arXiv 2020

  18. [18]

    , author=

    Pseudorandomness for Permutation Branching Programs Without the Group Theory. , author=. Electronic Colloquium on Computational Complexity (ECCC) , volume=

  19. [19]

    Electronic Colloquium on Computational Complexity (ECCC) , volume=

    Recent Progress on Derandomizing Space-Bounded Computation , author=. Electronic Colloquium on Computational Complexity (ECCC) , volume=

  20. [20]

    Computational Complexity Conference (CCC) , pages=

    Pseudorandomness for permutation and regular branching programs , author=. Computational Complexity Conference (CCC) , pages=. 2011 , publisher=

    2011

  21. [21]

    Theory of Computing , FJOURNAL =

    Steinke, Thomas and Vadhan, Salil and Wan, Andrew , TITLE =. Theory of Computing , FJOURNAL =. 2017 , MRCLASS =. doi:10.4086/toc.2017.v013a012 , URL =

    work page doi:10.4086/toc.2017.v013a012 2017

  22. [22]

    Approximation, Randomization, and Combinatorial Optimization

    Reingold, Omer and Steinke, Thomas and Vadhan, Salil , TITLE =. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM) , SERIES =. 2013 , MRCLASS =. doi:10.1007/978-3-642-40328-6\_45 , URL =

    work page doi:10.1007/978-3-642-40328-6 2013

  23. [23]

    Proceedings of the 37th

    Bogdanov, Andrej and Hoza, William M.\ and Prakriya, Gautam and Pyne, Edward , TITLE =. Proceedings of the 37th. 2022 , MRCLASS =. doi:10.4230/lipics.ccc.2022.3 , URL =

    work page doi:10.4230/lipics.ccc.2022.3 2022

  24. [24]

    Symposium on Simplicity in Algorithms (SOSA) , pages=

    Deterministic Approximation of Random Walks via Queries in Graphs of Unbounded Size , author=. Symposium on Simplicity in Algorithms (SOSA) , pages=. 2022 , organization=

    2022

  25. [25]

    SIAM Journal on Computing , volume=

    Graph sparsification by effective resistances , author=. SIAM Journal on Computing , volume=. 2011 , publisher=

    2011

  26. [26]

    38th International Colloquium on Automata, Languages, and Programming (ICALP 2011) , pages=

    Efficiently decodable error-correcting list disjunct matrices and applications , author=. 38th International Colloquium on Automata, Languages, and Programming (ICALP 2011) , pages=. 2011 , organization=

    2011

  27. [27]

    21st Annual Symposium on Discrete Algorithms (SODA 2010) , pages=

    Efficiently decodable non-adaptive group testing , author=. 21st Annual Symposium on Discrete Algorithms (SODA 2010) , pages=. 2010 , organization=

    2010

  28. [28]

    57th Annual Symposium on Foundations of Computer Science (FOCS 2016) , pages=

    Heavy hitters via cluster-preserving clustering , author=. 57th Annual Symposium on Foundations of Computer Science (FOCS 2016) , pages=. 2016 , organization=

    2016

  29. [29]

    John von Neumann, Collected Works , volume=

    Various techniques used in connection with random digits , author=. John von Neumann, Collected Works , volume=

  30. [30]

    Extreme High-End

    On Hardness Assumptions Needed for “Extreme High-End” PRGs and Fast Derandomization , author=

  31. [31]

    , author=

    High-Probability List-Recovery, and Applications to Heavy Hitters. , author=. Electronic Colloquium on Computational Complexity (ECCC) , year=

  32. [32]

    ACM Transactions on Algorithms (TALG) , volume=

    For-all sparse recovery in near-optimal time , author=. ACM Transactions on Algorithms (TALG) , volume=

  33. [33]

    40th International Colloquium on Automata, Languages, and Programming (ICALP 2013) , pages=

    _2/ _2 -foreach sparse recovery with low risk , author=. 40th International Colloquium on Automata, Languages, and Programming (ICALP 2013) , pages=. 2013 , organization=

    2013

  34. [34]

    29th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2012) , volume=

    Efficiently decodable compressed sensing by list-recoverable codes and recursion , author=. 29th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2012) , volume=. 2012 , organization=

    2012

  35. [35]

    44th Annual Symposium on Theory of Computing (STOC 2012) , pages=

    Faster approximate multicommodity flow using quadratically coupled flows , author=. 44th Annual Symposium on Theory of Computing (STOC 2012) , pages=. 2012 , organization=

    2012

  36. [36]

    43rd Annual Symposium on Theory of Computing (STOC 2011) , pages=

    Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs , author=. 43rd Annual Symposium on Theory of Computing (STOC 2011) , pages=. 2011 , publisher=

    2011

  37. [37]

    57th Annual Symposium on Foundations of Computer Science (FOCS 2016) , pages=

    Faster algorithms for computing the stationary distribution, simulating random walks, and more , author=. 57th Annual Symposium on Foundations of Computer Science (FOCS 2016) , pages=. 2016 , organization=

    2016

  38. [38]

    Solving directed

    Cohen, Michael B.\ and Kelner, Jonathan and Kyng, Rasmus and Peebles, John and Peng, Richard and Rao, Anup B.\ and Sidford, Aaron , booktitle=. Solving directed. 2018 , organization=

    2018

  39. [39]

    Almost-linear-time algorithms for

    Cohen, Michael B.\ and Kelner, Jonathan and Peebles, John and Peng, Richard and Rao, Anup B.\ and Sidford, Aaron and Vladu, Adrian , booktitle=. Almost-linear-time algorithms for

  40. [40]

    Electronic Colloquium on Computational Complexity (ECCC) , year=

    Eliminating Intermediate Measurements using Pseudorandom Generators , author=. Electronic Colloquium on Computational Complexity (ECCC) , year=

  41. [41]

    IEEE Transactions on Information Theory , volume=

    Sampling of min-entropy relative to quantum knowledge , author=. IEEE Transactions on Information Theory , volume=. 2011 , publisher=

    2011

  42. [42]

    SIAM Journal on Matrix Analysis and Applications , volume=

    Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems , author=. SIAM Journal on Matrix Analysis and Applications , volume=. 2014 , publisher=

    2014

  43. [43]

    SIAM Journal on Computing , volume=

    Spectral sparsification of graphs , author=. SIAM Journal on Computing , volume=. 2011 , publisher=

    2011

  44. [44]

    53rd Annual Symposium on Theory of Computing (STOC 2021) , pages=

    Eliminating intermediate measurements in space-bounded quantum computation , author=. 53rd Annual Symposium on Theory of Computing (STOC 2021) , pages=. 2021 , organization=

    2021

  45. [45]

    Journal of the ACM (JACM) , volume=

    Non-malleable codes , author=. Journal of the ACM (JACM) , volume=. 2018 , publisher=

    2018

  46. [46]

    Theory of Computing , volume =

    Cheng, Kuan and Hoza, William M.\ , title =. Theory of Computing , volume =. 2022 , pages =. doi:10.4086/toc.2022.v018a021 , publisher =

    work page doi:10.4086/toc.2022.v018a021 2022

  47. [47]

    Simple optimal hitting sets for small-success

    Hoza, William M.\ and Zuckerman, David , journal=. Simple optimal hitting sets for small-success. 2020 , publisher=

    2020

  48. [48]

    34th Computational Complexity Conference (CCC 2019) , year=

    Fourier Bounds and Pseudorandom Generators for Product Tests , author=. 34th Computational Complexity Conference (CCC 2019) , year=

    2019

  49. [49]

    SIAM Journal on Computing , volume=

    Bounded independence plus noise fools products , author=. SIAM Journal on Computing , volume=. 2018 , publisher=

    2018

  50. [50]

    Theory of Cryptography Conference , pages=

    Randomness condensers for efficiently samplable, seed-dependent sources , author=. Theory of Cryptography Conference , pages=. 2012 , organization=

    2012

  51. [51]

    SIAM Journal on Computing , volume=

    Extracting randomness via repeated condensing , author=. SIAM Journal on Computing , volume=. 2006 , publisher=

    2006

  52. [52]

    31st Annual Symposium on Foundations of Computer Science (FOCS 1990) , pages=

    General weak random sources , author=. 31st Annual Symposium on Foundations of Computer Science (FOCS 1990) , pages=. 1990 , organization=

    1990

  53. [53]

    Annual Symposium on Theory of Computing (STOC) , pages=

    Pseudorandom generators for group products , author=. Annual Symposium on Theory of Computing (STOC) , pages=. 2011 , organization=

    2011

  54. [54]

    Approximation, Randomization, and Combinatorial Optimization

    Deterministic coupon collection and better strong dispersers , author=. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM) , year=

  55. [55]

    Annual International Conference on the Theory and Applications of Cryptographic Techniques , pages=

    Low Error Efficient Computational Extractors in the CRS Model , author=. Annual International Conference on the Theory and Applications of Cryptographic Techniques , pages=. 2020 , organization=

    2020

  56. [56]

    50th Annual Symposium on Foundations of Computer Science (FOCS 2009) , pages=

    2-source extractors under computational assumptions and cryptography with defective randomness , author=. 50th Annual Symposium on Foundations of Computer Science (FOCS 2009) , pages=. 2009 , organization=

    2009

  57. [57]

    International Conference on Cryptology in India , pages=

    Privacy amplification from non-malleable codes , author=. International Conference on Cryptology in India , pages=. 2019 , organization=

    2019

  58. [58]

    48th Annual Symposium on Theory of Computing (STOC 2016) , pages=

    Textbook non-malleable commitments , author=. 48th Annual Symposium on Theory of Computing (STOC 2016) , pages=. 2016 , organization=

    2016

  59. [59]

    50th Annual Symposium on Theory of Computing (STOC 2018) , pages=

    Non-malleable secret sharing , author=. 50th Annual Symposium on Theory of Computing (STOC 2018) , pages=. 2018 , organization=

    2018

  60. [60]

    Theory of Cryptography Conference , pages=

    From single-bit to multi-bit public-key encryption via non-malleable codes , author=. Theory of Cryptography Conference , pages=. 2015 , organization=

    2015

  61. [61]

    Journal of Cryptology , volume=

    Non-malleable encryption: simpler, shorter, stronger , author=. Journal of Cryptology , volume=. 2020 , publisher=

    2020

  62. [62]

    SIAM Journal on Computing , volume =

    Braverman, Mark and Cohen, Gil and Garg, Sumegha , title =. SIAM Journal on Computing , volume =

  63. [63]

    , author=

    Approximating Large Powers of Stochastic Matrices in Small Space. , author=. Electronic Colloquium on Computational Complexity (ECCC) , volume=

  64. [64]

    2026 , ISBN =

    Cheng, Kuan and Wu, Ruiyang , TITLE =. 2026 , ISBN =. doi:10.1137/1.9781611978971.124 , URL =

    work page doi:10.1137/1.9781611978971.124 2026

  65. [65]

    Error reduction for weighted

    Cohen, Gil and Doron, Dean and Renard, Oren and Sberlo, Ori and. Error reduction for weighted. Computational Complexity Conference (CCC) , year=

  66. [66]

    Approximation, Randomization, and Combinatorial Optimization

    Unbalanced Expanders from Multiplicity Codes , author=. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM) , year=

  67. [67]

    Computational Complexity Conference (CCC) , pages =

    Eshan Chattopadhyay and Jyun-Jie Liao , title =. Computational Complexity Conference (CCC) , pages =. 2020 , publisher =

    2020

  68. [68]

    Approximation, Randomization, and Combinatorial Optimization

    Preserving Randomness for Adaptive Algorithms , author=. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM) , year=

  69. [69]

    Annual Cryptology Conference , pages=

    Non-malleable codes from two-source extractors , author=. Annual Cryptology Conference , pages=. 2013 , organization=

    2013

  70. [70]

    55th Annual Symposium on Foundations of Computer Science (FOCS 2014) , pages=

    Non-malleable codes against constant split-state tampering , author=. 55th Annual Symposium on Foundations of Computer Science (FOCS 2014) , pages=. 2014 , organization=

    2014

  71. [71]

    49th Annual Symposium on Theory of Computing (STOC 2017) , pages=

    Non-malleable codes and extractors for small-depth circuits, and affine functions , author=. 49th Annual Symposium on Theory of Computing (STOC 2017) , pages=. 2017 , organization=

    2017

  72. [72]

    and Zuckerman, David , TITLE =

    Dodis, Yevgeniy and Li, Xin and Wooley, Trevor D. and Zuckerman, David , TITLE =. 52nd Annual Symposium on Foundations of Computer Science (FOCS 2011) , PAGES =

    2011

  73. [73]

    Towards optimal two-source extractors and

    Cohen, Gil , booktitle=. Towards optimal two-source extractors and. 2017 , organization=

    2017

  74. [74]

    SIAM Journal on Computing , pages=

    Local list recovery of high-rate tensor codes and applications , author=. SIAM Journal on Computing , pages=. 2019 , publisher=

    2019

  75. [75]

    Cohen, Gil and Raz, Ran and Segev, Gil , TITLE =. 2012. 2012 , MRCLASS =. doi:10.1109/CCC.2012.21 , URL =

    work page doi:10.1109/ccc.2012.21 2012

  76. [76]

    Information Processing Letters , volume=

    On the de-randomization of space-bounded approximate counting problems , author=. Information Processing Letters , volume=. 2015 , publisher=

    2015

  77. [77]

    , author=

    Randomness Extraction from Somewhat Dependent Sources. , author=. Electron. Colloquium Comput. Complex. , volume=

  78. [78]

    47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) , volume =

    Dean Doron and Jack Murtagh and Salil Vadhan and David Zuckerman , title =. 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) , volume =

    2020

  79. [79]

    Mathematika , volume=

    AN EXPLICIT TWO-SOURCE EXTRACTOR WITH MIN-ENTROPY RATE NEAR 4/9 , author=. Mathematika , volume=. 2019 , publisher=

    2019

  80. [80]

    Proceedings., 33rd Annual Symposium on Foundations of Computer Science , title=

    N. Proceedings., 33rd Annual Symposium on Foundations of Computer Science , title=. 1992 , volume=

    1992

Showing first 80 references.