Pith. sign in

REVIEW 4 minor 300 references

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

T0 review · 0 major / 4 minor · reviewed 2026-08-01 · deepseek-v4-flash

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

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

desk verdict 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. read the letter →

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

Gil Cohen , Dean Doron , Noam Goldgraber This is my paper
classification cs.CCcs.DS MSC 68Q1568Q1705C50
keywords pseudorandomgeneratorpermutationbranchingprogramsread-onceINWexpandergraphsspectralexpansionforward-backwardweightsseedlength
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 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.

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(

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

Extended reading notes

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

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.

Editorial extensions

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.

Reading between the lines

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.
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

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 · score 1.0 of 10

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.

Assumptions & free parameters 0 free parameters · 3 assumptions · 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.

assumptions (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.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Forward-Backward Weight Analysis of INW for Permutation Branching Programs." pith.science (2026). https://pith.science/paper/JVW4LB6R

@misc{pith2026260718168,
  author       = {Pith},
  title        = {Pith review of: A Forward-Backward Weight Analysis of INW for Permutation Branching Programs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JVW4LB6R}},
  note         = {Machine review of arXiv:2607.18168}
}
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 to comment.

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=

Show all 300 references
  1. [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 =

    1983 doi

  2. [10]

    Jung , title =

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

    1981 doi

  3. [11]

    Theoretical Computer Science , FJOURNAL =

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

    1981 doi

  4. [12]

    SIAM Journal on Computing , FJOURNAL =

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

    1977 doi

  5. [13]

    2023 , organization=

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

    2023

  6. [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

  7. [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=

  8. [16]

    2021 , MRCLASS =

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

    2021

  9. [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 =

    2020

  10. [18]

    , author=

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

  11. [19]

    Electronic Colloquium on Computational Complexity (ECCC) , volume=

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

  12. [20]

    Computational Complexity Conference (CCC) , pages=

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

    2011

  13. [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 =

    2017 doi

  14. [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 =

    2013 doi

  15. [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 =

    2022 doi

  16. [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

  17. [25]

    SIAM Journal on Computing , volume=

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

    2011

  18. [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

  19. [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

  20. [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

  21. [29]

    John von Neumann, Collected Works , volume=

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

  22. [30]

    Extreme High-End

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

  23. [31]

    , author=

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

  24. [32]

    ACM Transactions on Algorithms (TALG) , volume=

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

  25. [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

  26. [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

  27. [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

  28. [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

  29. [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

  30. [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

  31. [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

  32. [40]

    Electronic Colloquium on Computational Complexity (ECCC) , year=

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

  33. [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

  34. [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

  35. [43]

    SIAM Journal on Computing , volume=

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

    2011

  36. [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

  37. [45]

    Journal of the ACM (JACM) , volume=

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

    2018

  38. [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 =

    2022 doi

  39. [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

  40. [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

  41. [49]

    SIAM Journal on Computing , volume=

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

    2018

  42. [50]

    Theory of Cryptography Conference , pages=

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

    2012

  43. [51]

    SIAM Journal on Computing , volume=

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

    2006

  44. [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

  45. [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

  46. [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=

  47. [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

  48. [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

  49. [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

  50. [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

  51. [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

  52. [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

  53. [61]

    Journal of Cryptology , volume=

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

    2020

  54. [62]

    SIAM Journal on Computing , volume =

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

  55. [63]

    , author=

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

  56. [64]

    2026 , ISBN =

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

    2026 doi

  57. [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=

  58. [66]

    Approximation, Randomization, and Combinatorial Optimization

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

  59. [67]

    Computational Complexity Conference (CCC) , pages =

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

    2020

  60. [68]

    Approximation, Randomization, and Combinatorial Optimization

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

  61. [69]

    Annual Cryptology Conference , pages=

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

    2013

  62. [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

  63. [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

  64. [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

  65. [73]

    Towards optimal two-source extractors and

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

    2017

  66. [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

  67. [75]

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

    2012 doi

  68. [76]

    Information Processing Letters , volume=

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

    2015

  69. [77]

    , author=

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

  70. [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

  71. [79]

    Mathematika , volume=

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

    2019

  72. [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

  73. [81]

    Pseudorandom generators for group products , BOOKTITLE =

    Kouck\'. Pseudorandom generators for group products , BOOKTITLE =. 2011 , MRCLASS =. doi:10.1145/1993636.1993672 , URL =

    2011

  74. [82]

    An efficient parallel solver for

    Peng, Richard and Spielman, Daniel A.\ , booktitle=. An efficient parallel solver for. 2014 , organization=

    2014

  75. [83]

    IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science , year=

    Randomness extractors--applications and constructions , author=. IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science , year=

  76. [84]

    2008 , publisher=

    Computational Complexity: A Conceptual Perspective , author=. 2008 , publisher=

    2008

  77. [85]

    Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing , pages =

    Armoni, Roy and Ta-Shma, Amnon and Wigderson, Avi and Zhou, Shiyu , title =. Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing , pages =. 1997 , publisher =

    1997

  78. [86]

    SIAM Journal on Computing , pages=

    Targeted pseudorandom generators, simulation advice generators, and derandomizing logspace , author=. SIAM Journal on Computing , pages=. 2021 , publisher=

    2021

  79. [87]

    SIAM Journal on Computing , volume=

    An O( logn log logn) Space Algorithm for Undirected st-Connectivity , author=. SIAM Journal on Computing , volume=. 2008 , publisher=

    2008

  80. [88]

    2011 , publisher=

    Chung, Kai-Min and Reingold, Omer and Vadhan, Salil , journal=. 2011 , publisher=

    2011

  81. [89]

    Proving that

    Tell, Roei , journal=. Proving that. 2019 , publisher=

    2019

  82. [90]

    computational complexity , volume=

    Derandomizing polynomial identity tests means proving circuit lower bounds , author=. computational complexity , volume=. 2004 , publisher=

    2004

  83. [91]

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

    Non-Malleable Extractors and Non-Malleable Codes: Partially Optimal Constructions , author=. 34th Computational Complexity Conference (CCC 2019) , pages =. 2019 , organization=

    2019

  84. [92]

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

    On recycling the randomness of states in space bounded computation , author=. Annual Symposium on Theory of Computing (STOC) , pages=. 1999 , organization=

    1999

  85. [93]

    Proceedings of the forty-fifth annual ACM symposium on Theory of computing , pages=

    List decoding Reed-Solomon, Algebraic-Geometric, and Gabidulin subcodes up to the Singleton bound , author=. Proceedings of the forty-fifth annual ACM symposium on Theory of computing , pages=. 2013 , organization=

    2013

  86. [94]

    Approximation, Randomization, and Combinatorial Optimization

    Better Pseudodistributions and Derandomization for Space-Bounded Computation , author=. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM) , year=

  87. [95]

    36th Computational Complexity Conference (CCC 2021) , pages =

    Pyne, Edward and Vadhan, Salil , title =. 36th Computational Complexity Conference (CCC 2021) , pages =. 2021 , publisher =

    2021

  88. [96]

    Theory of Cryptography Conference , pages=

    Non-malleable codes, extractors and secret sharing for interleaved tampering and composition of tampering , author=. Theory of Cryptography Conference , pages=. 2020 , publisher=

    2020

  89. [97]

    Computational Complexity Conference (CCC , year=

    Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas , author=. Computational Complexity Conference (CCC , year=

  90. [98]

    Theory of Computing , volume =

    Andrej Bogdanov and Zeev Dvir and Elad Verbin and Amir Yehudayoff , title =. Theory of Computing , volume =. 2013 , doi =

    2013

  91. [99]

    and Lv, Zelin , TITLE =

    Hoza, William M. and Lv, Zelin , TITLE =. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM) , pages=

  92. [100]

    35th Computational Complexity Conference (CCC 2020) , pages =

    Log-Seed Pseudorandom Generators via Iterated Restrictions , author=. 35th Computational Complexity Conference (CCC 2020) , pages =. 2020 , organization=

    2020

  93. [101]

    Approximation, Randomization, and Combinatorial Optimization

    Dean Doron and Amnon Ta-Shma and Roei Tell , title =. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) , pages =. 2020 , publisher =

    2020

  94. [102]

    46th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2014) , pages=

    On derandomizing algorithms that err extremely rarely , author=. 46th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2014) , pages=. 2014 , organization=

    2014

  95. [103]

    Random Struct

    Oded Goldreich and Avi Wigderson , title =. Random Struct. Algorithms , volume =

  96. [104]

    2008 49th Annual IEEE Symposium on Foundations of Computer Science , pages=

    Network extractor protocols , author=. 2008 49th Annual IEEE Symposium on Foundations of Computer Science , pages=. 2008 , organization=

    2008

  97. [105]

    Theoretical Computer Science , volume=

    Quantum cryptography: Public key distribution and coin tossing , author=. Theoretical Computer Science , volume=

  98. [106]

    2009 50th Annual IEEE Symposium on Foundations of Computer Science , pages=

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

    2009

  99. [107]

    Theory of Computing , volume=

    Pseudorandomness for width-2 branching programs , author=. Theory of Computing , volume=. 2013 , publisher=

    2013

  100. [108]

    SIAM journal on Computing , volume=

    Privacy amplification by public discussion , author=. SIAM journal on Computing , volume=. 1988 , publisher=

    1988

  101. [109]

    Electronic Colloquium on Computational Complexity (ECCC) , year=

    Seed Protecting Extractors , author=. Electronic Colloquium on Computational Complexity (ECCC) , year=

  102. [110]

    Electronic Colloquium on Computational Complexity (ECCC) , year=

    A Study of Error Reduction Polynomials , author=. Electronic Colloquium on Computational Complexity (ECCC) , year=

  103. [111]

    2017 , month =

    Some of My Favorite Open Problems on Expanders and Extractors , author=. 2017 , month =

    2017

  104. [112]

    Saks, Michael and Zuckerman, David , howpublished=

  105. [113]

    arXiv preprint arXiv:1504.04675 , year=

    Pseudorandomness for read-once, constant-depth circuits , author=. arXiv preprint arXiv:1504.04675 , year=

    arXiv

  106. [114]

    Electronic Colloquium on Computational Complexity (ECCC) , volume=

    An exposition of Bourgain’s 2-source extractor , author=. Electronic Colloquium on Computational Complexity (ECCC) , volume=

  107. [115]

    International Journal of Number Theory , volume=

    More on the sum-product phenomenon in prime fields and its applications , author=. International Journal of Number Theory , volume=. 2005 , publisher=

    2005

  108. [116]

    Approximation, Randomization, and Combinatorial Optimization

    Pseudorandom Generators for Read-Once Monotone Branching Programs , author=. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM) , year=

  109. [117]

    SIAM Journal on Computing , volume=

    Computing with very weak random sources , author=. SIAM Journal on Computing , volume=. 1999 , publisher=

    1999

  110. [118]

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

    Near-optimal pseudorandom generators for constant-depth read-once formulas , author=. 34th Computational Complexity Conference (CCC 2019) , year=

    2019

  111. [119]

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

    Pseudorandom generators for width-3 branching programs , author=. Annual Symposium on Theory of Computing (STOC) , pages=. 2019 , publisher =

    2019

  112. [120]

    Better condensers and new extractors from

    Ta-Shma, Amnon and Umans, Christopher , booktitle=. Better condensers and new extractors from. 2012 , organization=

    2012

  113. [121]

    Approximation, Randomization, and Combinatorial Optimization

    Two-source condensers with low error and small entropy gap via entropy-resilient functions , author=. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019) , pages =. 2019 , organization=

    2019

  114. [122]

    , author=

    Randomness Extraction from Somewhat Dependent Sources. , author=. Electronic Colloquium on Computational Complexity (ECCC) , year=

  115. [123]

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

    Extractors for adversarial sources via extremal hypergraphs , author=. 52nd Annual Symposium on Theory of Computing (STOC 2020) , pages=. 2020 , organization=

    2020

  116. [124]

    Approximation, Randomization, and Combinatorial Optimization

    Evading subspaces over large fields and explicit list-decodable rank-metric codes , author=. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014) , year=

    2014

  117. [125]

    , author=

    Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas. , author=. Electronic Colloquium on Computational Complexity (ECCC) , year=

  118. [126]

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

    Folded codes from function field towers and improved optimal rate list decoding , author=. 44th Annual Symposium on Theory of Computing (STOC 2012) , pages=. 2012 , publisher=

    2012

  119. [127]

    List decoding

    Guruswami, Venkatesan and Xing, Chaoping , booktitle=. List decoding. 2013 , publisher =

    2013

  120. [128]

    Improved decoding of

    Guruswami, Venkatesan and Sudan, Madhu , booktitle=. Improved decoding of. 1998 , organization=

    1998

  121. [129]

    Pseudorandomness and

    Steinke, Thomas and Vadhan, Salil and Wan, Andrew , journal=. Pseudorandomness and. 2017 , publisher=

    2017

  122. [130]

    2019 , pages =

    Lee, Chin Ho , booktitle =. 2019 , pages =

    2019

  123. [131]

    2024 , organization=

    Cheng, Kuan and Wang, Yichuan , booktitle =. 2024 , organization=

    2024

  124. [132]

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

    Improved pseudorandomness for unordered branching programs through local monotonicity , author=. 50th Annual Symposium on Theory of Computing (STOC 2018) , pages=. 2018 , publisher =

    2018

  125. [133]

    Proceedings of 53th Annual Symposium on the Foundations of Computer Science (FOCS 2012) , pages=

    Better pseudorandom generators from milder pseudorandom restrictions , author=. Proceedings of 53th Annual Symposium on the Foundations of Computer Science (FOCS 2012) , pages=. 2012 , organization=

    2012

  126. [134]

    SIAM Journal on Computing , volume=

    Extensions to the method of multiplicities, with applications to Kakeya sets and mergers , author=. SIAM Journal on Computing , volume=. 2013 , publisher=

    2013

  127. [135]

    Simulating

    Zuckerman, David , journal=. Simulating. 1996 , publisher=

    1996

  128. [136]

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

    A Complete Characterization of Unitary Quantum Space , author=. 9th Innovations in Theoretical Computer Science Conference (ITCS 2018) , year=

    2018

  129. [137]

    Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    Average-radius list-recoverability of random linear codes , author=. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2018 , organization=

    2018

  130. [138]

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

    An efficient reduction from two-source to non-malleable extractors: achieving near-logarithmic min-entropy , author=. 49th Annual Symposium on Theory of Computing (STOC 2017) , pages=. 2017 , organization=

    2017

  131. [139]

    arXiv preprint arXiv:1710.00557 , year=

    A Quantum-Proof Non-Malleable Extractor, With Application to Privacy Amplification against Active Quantum Adversaries , author=. arXiv preprint arXiv:1710.00557 , year=

    arXiv

  132. [140]

    A Simple Explicit Construction of an n^

    Barak, Boaz , journal=. A Simple Explicit Construction of an n^

  133. [141]

    SIAM Journal on Computing , volume=

    Trevisan's extractor in the presence of quantum side information , author=. SIAM Journal on Computing , volume=. 2012 , publisher=

    2012

  134. [142]

    Foundations and Trends in Theoretical Computer Science , volume=

    Theory of Unconditional Pseudorandom Generators , author=. Foundations and Trends in Theoretical Computer Science , volume=. 2024 , publisher=

    2024

  135. [143]

    Approximation, Randomization, and Combinatorial Optimization

    Dean Doron and Fran. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017) , pages =. 2017 , volume =. doi:10.4230/LIPIcs.APPROX-RANDOM.2017.41 , annote =

    2017 doi

  136. [144]

    Journal of Computer and System Sciences , volume=

    Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors , author=. Journal of Computer and System Sciences , volume=. 2011 , publisher=

    2011

  137. [145]

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

    A better-than- 3n lower bound for the circuit complexity of an explicit function , author=. Proceedings of 57th Annual IEEE Symposium on the Foundations of Computer Science (FOCS 2016) , pages=. 2016 , organization=

    2016

  138. [146]

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

    Nearly optimal pseudorandomness from hardness , author=. 61st Annual Symposium on Foundations of Computer Science (FOCS 2020) , pages=. 2020 , organization=

    2020

  139. [147]

    SIAM Journal on Computing , volume=

    Privacy amplification and nonmalleable extractors via character sums , author=. SIAM Journal on Computing , volume=. 2014 , publisher=

    2014

  140. [148]

    SIAM Journal on Computing , volume=

    Nonmalleable extractors with short seeds and applications to privacy amplification , author=. SIAM Journal on Computing , volume=. 2014 , publisher=

    2014

  141. [149]

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

    Extractors: Optimal up to constant factors , author=. 35th Annual Symposium on Theory of Computing (STOC 2003) , pages=. 2003 , organization=

    2003

  142. [150]

    Journal of Computer and System Sciences , volume=

    Pseudo-random generators for all hardnesses , author=. Journal of Computer and System Sciences , volume=. 2003 , publisher=

    2003

  143. [151]

    Foundations of Computer Science, 2001

    Simple extractors for all min-entropies and a new pseudo-random generator , author=. Foundations of Computer Science, 2001. Proceedings. 42nd IEEE Symposium on , pages=. 2001 , organization=

    2001

  144. [152]

    Journal of Computer and System Sciences , volume=

    Extracting randomness: A survey and new constructions , author=. Journal of Computer and System Sciences , volume=. 1999 , publisher=

    1999

  145. [153]

    Foundations of Computer Science, 2001

    Extractors from reed-muller codes , author=. Foundations of Computer Science, 2001. Proceedings. 42nd IEEE Symposium on , pages=. 2001 , organization=

    2001

  146. [154]

    Proceedings of 59th Annual Symposium on the Foundations of Computer Science (FOCS) , pages=

    Pseudorandom Generators for Read-Once Branching Programs, in any Order , author=. Proceedings of 59th Annual Symposium on the Foundations of Computer Science (FOCS) , pages=. 2018 , organization=

    2018

  147. [155]

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

    On extracting randomness from weak random sources , author=. 28th Annual Symposium on Theory of Computing (STOC 1996) , pages=. 1996 , organization=

    1996

  148. [156]

    Constructive bounds for a

    Alon, Noga and Krivelevich, Michael , journal=. Constructive bounds for a. 1997 , publisher=

    1997

  149. [157]

    21st Annual Symposium on Theory of computing (STOC 1989) , pages=

    Pseudo-random generation from one-way functions , author=. 21st Annual Symposium on Theory of computing (STOC 1989) , pages=. 1989 , organization=

    1989

  150. [158]

    arXiv preprint arXiv:1312.3717 , year=

    Optimal algorithms for linear algebra by quantum inspiration , author=. arXiv preprint arXiv:1312.3717 , year=

    arXiv

  151. [159]

    arXiv preprint arXiv:0811.3648 , year=

    Revisiting norm estimation in data streams , author=. arXiv preprint arXiv:0811.3648 , year=

    arXiv

  152. [160]

    Combinatorica , volume=

    Affine extractors over prime fields , author=. Combinatorica , volume=. 2011 , publisher=

    2011

  153. [161]

    42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015) , pages=

    On the problem of approximating the eigenvalues of undirected graphs in probabilistic logspace , author=. 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015) , pages=. 2015 , organization=

    2015

  154. [162]

    arXiv preprint arXiv:2006.03530 , year=

    Eliminating Intermediate Measurements in Space-Bounded Quantum Computation , author=. arXiv preprint arXiv:2006.03530 , year=

    2006 arXiv

  155. [163]

    SIAM Journal on Computing , volume=

    On threshold circuits and polynomial computation , author=. SIAM Journal on Computing , volume=. 1992 , publisher=

    1992

  156. [164]

    Information processing letters , volume=

    On computing the determinant in small parallel time using a small number of processors , author=. Information processing letters , volume=. 1984 , publisher=

    1984

  157. [165]

    computational complexity , volume=

    On approximating the eigenvalues of stochastic matrices in probabilistic logspace , author=. computational complexity , volume=. 2017 , publisher=

    2017

  158. [166]

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

    Simple and fast derandomization from very hard functions: Eliminating randomness at almost no cost , author=. 53rd Annual Symposium on Theory of Computing (STOC 2021) , pages=. 2021 , organization=

    2021

  159. [167]

    Electronic Colloquium on Computational Complexity (ECCC) , volume=

    Extractors for affine sources with polylogarithmic entropy , author=. Electronic Colloquium on Computational Complexity (ECCC) , volume=

  160. [168]

    Electronic Colloquium on Computational Complexity (ECCC) , year=

    Hardness vs.\ Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise , author=. Electronic Colloquium on Computational Complexity (ECCC) , year=

  161. [169]

    33th Computational Complexity Conference (CCC 2018) , pages =

    A New Approach for Constructing Low-Error, Two-Source Extractors , author=. 33th Computational Complexity Conference (CCC 2018) , pages =. 2018 , organization=

    2018

  162. [170]

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

    Making the most of advice: New correlation breakers and their applications , author=. Proceedings of 57th Annual Symposium on the Foundations of Computer Science (FOCS 2016) , pages=. 2016 , organization=

    2016

  163. [171]

    Approximation, Randomization, and Combinatorial Optimization

    Space pseudorandom generators by communication complexity lower bounds , author=. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014) , year=

    2014

  164. [172]

    Simplifying

    Chen, Ben and. Simplifying. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM) , pages =. 2025 , publisher =

    2025

  165. [173]

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

    The coin problem and pseudorandomness for branching programs , author=. 51st Annual Symposium on Foundations of Computer Science (FOCS 2010) , pages=. 2010 , organization=

    2010

  166. [174]

    International Colloquium on Automata, Languages, and Programming , pages=

    On the Problem of Approximating the Eigenvalues of Undirected Graphs in Probabilistic Logspace , author=. International Colloquium on Automata, Languages, and Programming , pages=. 2015 , organization=

    2015

  167. [175]

    GAFA Geometric And Functional Analysis , volume=

    On the construction of affine extractors , author=. GAFA Geometric And Functional Analysis , volume=. 2007 , publisher=

    2007

  168. [176]

    1994 , publisher=

    Nisan, Noam , journal=. 1994 , publisher=

    1994

  169. [177]

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

    Random walks, universal traversal sequences, and the complexity of maze problems , author=. Annual Symposium on Foundations of Computer (FOCS) , pages=. 1979 , organization=

    1979

  170. [178]

    SIAM Journal on Computing , volume=

    Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses , author=. SIAM Journal on Computing , volume=. 2002 , publisher=

    2002

  171. [179]

    SIAM Journal on Computing , volume=

    A sublinear space, polynomial time algorithm for directed st connectivity , author=. SIAM Journal on Computing , volume=. 1998 , publisher=

    1998

  172. [180]

    International Conference on Foundations of Software Technology and Theoretical Computer Science , pages=

    Randomized time-space tradeoffs for directed graph connectivity , author=. International Conference on Foundations of Software Technology and Theoretical Computer Science , pages=. 2003 , organization=

    2003

  173. [181]

    , author=

    Two-Source Extractors for Quasi-Logarithmic Min-Entropy and Improved Privacy Amplification Protocols. , author=. Electronic Colloquium on Computational Complexity (ECCC) , year=

  174. [182]

    Electronic Colloquium on Computational Complexity (ECCC) , year =

    Xin Li , title =. Electronic Colloquium on Computational Complexity (ECCC) , year =

  175. [183]

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

    Derandomization beyond connectivity: Undirected laplacian systems in nearly logarithmic space , author=. Annual Symposium on the Foundations of Computer Science (FOCS) , pages=. 2017 , organization=

    2017

  176. [184]

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

    Li, Xin , title =. 49th Annual Symposium on Theory of Computing (STOC 2017) , year =

    2017

  177. [185]

    Pseudorandom Generators for Read-Once ACC\^

    Gavinsky, Dmitry and Lovett, Shachar and Srinivasan, Srikanth , booktitle=. Pseudorandom Generators for Read-Once ACC\^. 2012 , organization=

    2012

  178. [186]

    Theory of Computing , volume=

    Pseudorandom generators from polarizing random walks , author=. Theory of Computing , volume=. 2019 , publisher=

    2019

  179. [187]

    Pseudorandomness via the discrete

    Gopalan, Parikshit and Kane, Daniek and Meka, Raghu , booktitle=. Pseudorandomness via the discrete. 2015 , organization=

    2015

  180. [188]

    Annals of Mathematics , pages=

    Entropy waves, the zig-zag graph product, and new constant-degree expanders , author=. Annals of Mathematics , pages=. 2002 , publisher=

    2002

  181. [189]

    Approximation, Randomization, and Combinatorial Optimization

    Pseudorandom bit generators that fool modular sums , author=. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM) , pages=. 2009 , publisher=

    2009

  182. [190]

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

    Pseudorandom generators for regular branching programs , author=. 51st Annual Symposium on Foundations of Computer Science (FOCS 2010) , pages=. 2010 , organization=

    2010

  183. [191]

    46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05) , pages=

    Correcting errors beyond the Guruswami-Sudan radius in polynomial time , author=. 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05) , pages=. 2005 , organization=

    2005

  184. [192]

    Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on , pages=

    Pseudorandomness for read-once formulas , author=. Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on , pages=. 2011 , organization=

    2011

  185. [193]

    Probabilistic logarithmic-space algorithms for

    Doron, Dean and Le Gall, Fran. Probabilistic logarithmic-space algorithms for. LIPIcs-Leibniz International Proceedings in Informatics , volume=. 2017 , pages =

    2017

  186. [194]

    SIAM Journal on Computing , volume=

    Pseudorandom generators for polynomial threshold functions , author=. SIAM Journal on Computing , volume=. 2013 , publisher=

    2013

  187. [195]

    SIAM Journal on Computing , volume=

    Pseudorandom generators for combinatorial shapes , author=. SIAM Journal on Computing , volume=. 2013 , publisher=

    2013

  188. [196]

    Journal of Computer and System Sciences , volume=

    Randomness is linear in space , author=. Journal of Computer and System Sciences , volume=. 1996 , publisher=

    1996

  189. [197]

    Low rank co-diagonal matrices and

    Grolmusz, Vince , journal=. Low rank co-diagonal matrices and

  190. [198]

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

    Pseudorandomness for network algorithms , author=. Annual Symposium on Theory of Computing (STOC) , pages=. 1994 , organization=

    1994

  191. [199]

    A new proof of Szemer

    Gowers, William Timothy , journal=. A new proof of Szemer. 1998 , publisher=

    1998

  192. [200]

    Combinatorica , volume=

    A statistical theorem of set addition , author=. Combinatorica , volume=. 1994 , publisher=

    1994

  193. [201]

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

    Three-source extractors for polylogarithmic min-entropy , author=. 56th Annual Symposium on Foundations of Computer Science (FOCS 2015) , pages=. 2015 , organization=

    2015

  194. [202]

    Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on , pages=

    Extractors for a constant number of independent sources with polylogarithmic min-entropy , author=. Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on , pages=. 2013 , organization=

    2013

  195. [203]

    IBM Research Report RJ , year =

    Moni Naor , title =. IBM Research Report RJ , year =

  196. [204]

    A note on constructive methods for

    Chung, Fan RK , journal=. A note on constructive methods for. 1981 , publisher=

    1981

  197. [205]

    A constructive lower bound for

    Frankl, Peter , journal=. A constructive lower bound for

  198. [206]

    A constructive estimation of the

    Nagy, Zs , journal=. A constructive estimation of the

  199. [207]

    Lower bounds for some

    Abbott, HL , journal=. Lower bounds for some. 1972 , publisher=

    1972

  200. [208]

    arXiv preprint arXiv:1508.01115 , year=

    Improved constructions of two-source extractors , author=. arXiv preprint arXiv:1508.01115 , year=

    arXiv

  201. [209]

    Advances in Cryptology--EUROCRYPT 2014 , pages=

    Key derivation without entropy waste , author=. Advances in Cryptology--EUROCRYPT 2014 , pages=. 2014 , publisher=

    2014

  202. [210]

    and Fassino, C

    Codenotti, B. and Fassino, C. , pages=. CALCOLO , volume=. 1992 , issn=. doi:10.1007/BF02576760 , title=

    1992 doi

  203. [211]

    Unbalanced expanders and randomness extractors from

    Guruswami, Venkatesan and Umans, Christopher and Vadhan, Salil , journal=. Unbalanced expanders and randomness extractors from. 2009 , publisher=

    2009

  204. [212]

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

    Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets , author=. 34th Annual Symposium on Theory of Computing (STOC 2002) , pages=. 2002 , organization=

    2002

  205. [213]

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

    Better extractors for better codes? , author=. 36th Annual Symposium on Theory of Computing (STOC 2004) , pages=. 2004 , organization=

    2004

  206. [214]

    SIAM Journal on Computing , volume=

    Nonmalleable Extractors and Codes, with Their Many Tampered Extensions , author=. SIAM Journal on Computing , volume=. 2020 , publisher=

    2020

  207. [215]

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

    Randomness conductors and constant-degree lossless expanders , author=. 34th Annual Symposium on Theory of Computing (STOC 2002) , pages=. 2002 , organization=

    2002

  208. [216]

    , author=

    Leakage-Resilient Extractors and Secret-Sharing against Bounded Collusion Protocols. , author=. Electronic Colloquium on Computational Complexity (ECCC) , volume=

  209. [217]

    2001 , school=

    List decoding of error-correcting codes , author=. 2001 , school=

    2001

  210. [218]

    Theory of Computing , volume=

    Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number , author=. Theory of Computing , volume=

  211. [219]

    Computational Complexity (CCC), 2011 IEEE 26th Annual Conference on , pages=

    A new approach to affine extractors and dispersers , author=. Computational Complexity (CCC), 2011 IEEE 26th Annual Conference on , pages=. 2011 , organization=

    2011

  212. [220]

    Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data

    Dodis, Yevgeniy and Reyzin, Leonid and Smith, Adam. Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data. Advances in Cryptology - EUROCRYPT 2004. 2004

    2004

  213. [221]

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

    Extracting correlations , author=. Proceedings of 50th Annual IEEE Symposium on the Foundations of Computer Science (FOCS 2009) , pages=. 2009 , organization=

    2009

  214. [222]

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

    Non-malleable extractors and symmetric key cryptography from weak secrets , author=. 41st Annual Symposium on Theory of Computing (STOC 2009) , pages=. 2009 , organization=

    2009

  215. [223]

    Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on , pages=

    Non-malleable extractors, two-source extractors and privacy amplification , author=. Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on , pages=. 2012 , organization=

    2012

  216. [224]

    Foundations of Computer Science, 2007

    Intrusion-resilient secret sharing , author=. Foundations of Computer Science, 2007. FOCS'07. 48th Annual IEEE Symposium on , pages=. 2007 , organization=

    2007

  217. [225]

    Information Theory, IEEE Transactions on , volume=

    Extractor codes , author=. Information Theory, IEEE Transactions on , volume=. 2004 , publisher=

    2004

  218. [226]

    twenty-eighth annual ACM symposium on Theory of computing , pages=

    The space complexity of approximating the frequency moments , author=. twenty-eighth annual ACM symposium on Theory of computing , pages=. 1996 , organization=

    1996

  219. [227]

    Random Structures & Algorithms , volume=

    Simple Constructions of Almost k -wise Independent Random Variables , author=. Random Structures & Algorithms , volume=. 1992 , publisher=

    1992

  220. [228]

    Journal of Computer and System Sciences , volume=

    Hardness vs.\ randomness , author=. Journal of Computer and System Sciences , volume=. 1994 , publisher=

    1994

  221. [229]

    thirty-first annual ACM symposium on Theory of computing , pages=

    Extracting all the randomness and reducing the error in Trevisan's extractors , author=. thirty-first annual ACM symposium on Theory of computing , pages=. 1999 , organization=

    1999

  222. [230]

    Journal of the ACM (JACM) , volume=

    Extractors and pseudorandom generators , author=. Journal of the ACM (JACM) , volume=

  223. [231]

    Constant depth circuits,

    Linial, Nathan and Mansour, Yishay and Nisan, Noam , journal=. Constant depth circuits,. 1993 , publisher=

    1993

  224. [232]

    IEEE Transactions on Information Theory , volume=

    Linear-time encodable/decodable codes with near-optimal rate , author=. IEEE Transactions on Information Theory , volume=. 2005 , publisher=

    2005

  225. [233]

    1957 , publisher=

    List decoding for noisy channels , author=. 1957 , publisher=

    1957

  226. [234]

    Information Theory, IEEE Transactions on , volume=

    Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs , author=. Information Theory, IEEE Transactions on , volume=. 1992 , publisher=

    1992

  227. [235]

    Foundations of Computer Science, 2009

    Constructing small-bias sets from algebraic-geometric codes , author=. Foundations of Computer Science, 2009. FOCS'09. 50th Annual IEEE Symposium on , pages=. 2009 , organization=

    2009

  228. [236]

    Studies in Complexity and Cryptography

    Three XOR-lemmas—an exposition , author=. Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation , pages=. 2011 , publisher=

    2011

  229. [237]

    2014 , publisher=

    Analysis of boolean functions , author=. 2014 , publisher=

    2014

  230. [238]

    Foundations of Computer Science, 1993

    On representations by low-degree polynomials , author=. Foundations of Computer Science, 1993. Proceedings., 34th Annual Symposium on , pages=. 1993 , organization=

    1993

  231. [239]

    Polylogarithmic independence fools

    Braverman, Mark , journal=. Polylogarithmic independence fools. 2010 , publisher=

    2010

  232. [240]

    Computational limitations of small-depth circuits , author=

  233. [241]

    Information Processing Letters , volume=

    Almost k-wise independence versus k-wise independence , author=. Information Processing Letters , volume=. 2003 , publisher=

    2003

  234. [242]

    SIAM journal on computing , volume=

    Small-bias probability spaces: Efficient constructions and applications , author=. SIAM journal on computing , volume=. 1993 , publisher=

    1993

  235. [243]

    1995 , publisher=

    Pairwise independence and derandomization , author=. 1995 , publisher=

    1995

  236. [244]

    Studies in complexity and cryptography , SERIES =

    Goldreich, Oded , TITLE =. Studies in complexity and cryptography , SERIES =. 2011 , MRCLASS =. doi:10.1007/978-3-642-22670-0\_24 , URL =

    2011 doi

  237. [245]

    Foundations and Trends

    Arithmetic circuits: A survey of recent results and open questions , author=. Foundations and Trends. 2010 , publisher=

    2010

  238. [246]

    Two-Source Dispersers for Polylogarithmic Entropy and Improved

    Cohen, Gil , journal=. Two-Source Dispersers for Polylogarithmic Entropy and Improved

  239. [247]

    Two-source dispersers for polylogarithmic entropy and improved

    Cohen, Gil , journal=. Two-source dispersers for polylogarithmic entropy and improved. 2019 , publisher=

    2019

  240. [248]

    Higham and Charles S

    Sheung Hun Cheng and Nicholas J. Higham and Charles S. Kenney and Alan J. Laub , title =. SIAM J. Matrix Anal. Appl , year =

  241. [249]

    2013 , pages =

    Inverting well conditioned matrices in quantum logspace , booktitle =. 2013 , pages =

    2013

  242. [250]

    computational complexity , volume=

    Non-deterministic exponential time has two-prover interactive protocols , author=. computational complexity , volume=. 1991 , publisher=

    1991

  243. [251]

    probabilistic polynomial time , author=

    In search of an easy witness: Exponential time vs. probabilistic polynomial time , author=. Journal of Computer and System Sciences , volume=. 2002 , publisher=

    2002

  244. [252]

    Foundations of Computer Science, 1999

    Noncryptographic selection protocols , author=. Foundations of Computer Science, 1999. 40th Annual Symposium on , pages=. 1999 , organization=

    1999

  245. [253]

    SIAM Journal on Discrete Mathematics , volume=

    A robust noncryptographic protocol for collective coin flipping , author=. SIAM Journal on Discrete Mathematics , volume=. 1989 , publisher=

    1989

  246. [254]

    SIAM Journal on Computing , volume=

    Lower bounds for leader election and collective coin-flipping in the perfect information model , author=. SIAM Journal on Computing , volume=. 2002 , publisher=

    2002

  247. [255]

    CoRR , volume =

    Raghu Meka , title =. CoRR , volume =. 2015 , url =

    2015

  248. [256]

    Random Structures & Algorithms , volume=

    On the distribution of the number of roots of polynomials and explicit weak designs , author=. Random Structures & Algorithms , volume=. 2003 , publisher=

    2003

  249. [257]

    1976 , publisher=

    Quantum detection and estimation theory , author=. 1976 , publisher=

    1976

  250. [258]

    SIAM Journal on Computing , volume=

    Approximate list-decoding of direct product codes and uniform hardness amplification , author=. SIAM Journal on Computing , volume=. 2009 , publisher=

    2009

  251. [259]

    Saff, E. B. and Totik, V. , title =. 1989 , doi =

    1989

  252. [260]

    , journal=

    Johnson, S. , journal=. A new upper bound for error-correcting codes , year=. doi:10.1109/TIT.1962.1057714 , ISSN=

    1962

  253. [261]

    Combinatorics, Probability

    Noga Alon and Benny Sudakov , title =. Combinatorics, Probability. 2000 , pages =

    2000

  254. [262]

    Simulating independence: New constructions of condensers,

    Barak, Boaz and Kindler, Guy and Shaltiel, Ronen and Sudakov, Benny and Wigderson, Avi , journal=. Simulating independence: New constructions of condensers,. 2010 , publisher=

    2010

  255. [263]

    2-source dispersers for n^

    Barak, Boaz and Rao, Anup and Shaltiel, Ronen and Wigderson, Avi , journal=. 2-source dispersers for n^. 2012 , publisher=

    2012

  256. [264]

    Combinatorica , volume=

    The Shannon capacity of a union , author=. Combinatorica , volume=. 1998 , publisher=

    1998

  257. [265]

    Combinatorica , volume=

    Intersection theorems with geometric consequences , author=. Combinatorica , volume=. 1981 , publisher=

    1981

  258. [266]

    SIAM Journal on Computing , volume=

    Unbiased bits from sources of weak randomness and probabilistic communication complexity , author=. SIAM Journal on Computing , volume=. 1988 , publisher=

    1988

  259. [267]

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

    Extractors with weak random seeds , author=. 37th Annual Symposium on Theory of Computing (STOC 2005) , pages=. 2005 , organization=

    2005

  260. [268]

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

    New independent source extractors with exponential improvement , author=. 45th Annual Symposium on Theory of Computing (STOC 2013) , pages=. 2013 , organization=

    2013

  261. [269]

    26th Conference on Computational Complexity (CCC 2011) , pages=

    Improved constructions of three source extractors , author=. 26th Conference on Computational Complexity (CCC 2011) , pages=. 2011 , organization=

    2011

  262. [270]

    SIAM Journal on Computing , volume=

    Extractors for a constant number of polynomially small min-entropy independent sources , author=. SIAM Journal on Computing , volume=. 2009 , publisher=

    2009

  263. [271]

    SIAM Journal on Computing , volume=

    Extracting randomness using few independent sources , author=. SIAM Journal on Computing , volume=. 2006 , publisher=

    2006

  264. [272]

    2009 , publisher =

    Arora, Sanjeev and Barak, Boaz , title =. 2009 , publisher =

    2009

  265. [273]

    twelfth annual ACM symposium on Theory of computing , pages=

    Some connections between nonuniform and uniform complexity classes , author=. twelfth annual ACM symposium on Theory of computing , pages=. 1980 , organization=

    1980

  266. [274]

    2012 , publisher=

    Boolean function complexity: advances and frontiers , author=. 2012 , publisher=

    2012

  267. [275]

    Shlomo Hoory and Nathan Linial and Avi Wigderson and An Overview , title =. Bull. Amer. Math. Soc. (N.S , year =

  268. [276]

    , year =

    Noga Alon and Oded Goldreich and Johan Håstad and René Peralta , title =. , year =

  269. [277]

    Journal of the ACM (JACM) , volume=

    Algebraic methods for interactive proof systems , author=. Journal of the ACM (JACM) , volume=. 1992 , publisher=

    1992

  270. [278]

    Journal of the ACM (JACM) , volume=

    Ip= pspace , author=. Journal of the ACM (JACM) , volume=. 1992 , publisher=

    1992

  271. [279]

    Joseph Naor and Moni Naor , title =. SIAM J. Comput , year =

  272. [280]

    2007 , publisher=

    An Introduction to Quantum Computing , author=. 2007 , publisher=

    2007

  273. [281]

    2000 , publisher=

    Quantum Computation and Quantum Information , author=. 2000 , publisher=

    2000

  274. [282]

    , year =

    Gilles Brassard and Peter Høyer and Michele Mosca , title =. , year =

  275. [283]

    Improved decoding of folded

    Kopparty, Swastik and Ron-Zewi, Noga and Saraf, Shubhangi and Wootters, Mary , booktitle=. Improved decoding of folded. 2018 , organization=

    2018

  276. [284]

    Information and Computation , volume=

    Linear-time list recovery of high-rate expander codes , author=. Information and Computation , volume=. 2018 , publisher=

    2018

  277. [285]

    arXiv preprint arXiv:2002.08579 , year=

    Linear-time Erasure List-decoding of Expander Codes , author=. arXiv preprint arXiv:2002.08579 , year=

    2002 arXiv

  278. [286]

    Theory of Computing , volume=

    List-decoding multiplicity codes , author=. Theory of Computing , volume=. 2015 , publisher=

    2015

  279. [287]

    Combinatorica , volume=

    Deterministic extractors for affine sources over large fields , author=. Combinatorica , volume=. 2008 , publisher=

    2008

  280. [288]

    IEEE Transactions on Information Theory , volume=

    Explicit codes achieving list decoding capacity: Error-correction with optimal redundancy , author=. IEEE Transactions on Information Theory , volume=. 2008 , publisher=

    2008

  281. [289]

    31st International Colloquium on Automata, Languages, and Programming (ICALP 2004) , pages=

    Linear-time list decoding in error-free settings , author=. 31st International Colloquium on Automata, Languages, and Programming (ICALP 2004) , pages=. 2004 , organization=

    2004

  282. [290]

    Linear-algebraic list decoding for variants of

    Guruswami, Venkatesan and Wang, Carol , journal=. Linear-algebraic list decoding for variants of. 2013 , publisher=

    2013

  283. [291]

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

    Multi-collision resistance: a paradigm for keyless hash functions , author=. 50th Annual Symposium on Theory of Computing (STOC 2018) , pages=

    2018

  284. [292]

    Annual International Cryptology Conference , pages=

    Domain extension of public random functions: Beyond the birthday barrier , author=. Annual International Cryptology Conference , pages=. 2007 , organization=

    2007

  285. [293]

    SIAM Journal on Computing , number=

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

    2019

  286. [294]

    Holmgren, Justin and Lombardi, Alex and Rothblum, Ron , booktitle=. Fiat--. 2021 , organization=

    2021

  287. [295]

    35th Annual Cryptology Conference (CRYPTO 2015) , pages=

    Parallel hashing via list recoverability , author=. 35th Annual Cryptology Conference (CRYPTO 2015) , pages=. 2015 , organization=

    2015

  288. [296]

    SIAM Journal on Computing , volume=

    Short seed extractors against quantum storage , author=. SIAM Journal on Computing , volume=. 2011 , publisher=

    2011

  289. [297]

    Theory of Computing , volume =

    Scott Aaronson and Andris Ambainis , title =. Theory of Computing , volume =. 2005 , pages =

    2005

  290. [298]

    and Johnson, Charles R

    Horn, Roger A. and Johnson, Charles R. , howpublished =

  291. [299]

    IEEE Transactions on Information Theory , volume=

    The bounded-storage model in the presence of a quantum adversary , author=. IEEE Transactions on Information Theory , volume=. 2008 , publisher=

    2008

  292. [300]

    and Van Loan, Charles F

    Golub, Gene H. and Van Loan, Charles F. , title =. 1996 , isbn =

    1996

Pith tools

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