2023/11/20 by Ronen Shaltiel, Emanuele Viola, Shaltiel, Ronen +1
Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cryptography and Data Security #FOS: Computer and information sciences #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2311.11663
openalex publication_date 2023/11/20 · openalex created_date 2023/11/23 · openalex updated_date 2026/07/28
The hardness vs.~randomness paradigm aims to explicitly construct\npseudorandom generators G: 0,1 r \→ 0,1 m that fool circuits\nof size m, assuming the existence of explicit hard functions. A ``high-end\nPRG'' with seed length r=O(\log m) (implying BPP=P) was achieved in a seminal\nwork of Impagliazzo and Wigderson (STOC 1997), assuming the high-end hardness\nassumption: there exist constants 0<\β < 1< B, and functions computable in\ntime 2B \⋅ n that cannot be computed by circuits of size 2\β\n\⋅ n.\n Recently, motivated by fast derandomization of randomized algorithms, Doron\net al.~(FOCS 2020) and Chen and Tell (STOC 2021), construct ``extreme high-end\nPRGs'' with seed length r=(1+o(1))\⋅ \log m, under qualitatively stronger\nassumptions.\n We study whether extreme high-end PRGs can be constructed from the following\nscaled version of the assumption which we call ``the extreme high-end hardness\nassumption'', and in which \β=1-o(1) and B=1+o(1). We give a partial\nnegative answer, showing that certain approaches cannot yield a black-box\nproof. (A longer abstract with more details appears in the PDF file)\n