Hardness vs randomness
From MaRDI portal
Publication:1337458
DOI10.1016/S0022-0000(05)80043-1zbMath0821.68057WikidataQ56815522 ScholiaQ56815522MaRDI QIDQ1337458
Publication date: 6 November 1994
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Random number generation in numerical analysis (65C10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Immunity and Simplicity for Exact Counting and Other Counting Classes, Efficient constructions of Hitting Sets for systems of linear functions, Nisan-Wigderson generators in proof systems with forms of interpolation, Simple analysis of graph tests for linearity and PCP, The Journey from NP to TFNP Hardness, Minimum Circuit Size, Graph Isomorphism, and Related Problems, Quantified Derandomization: How to Find Water in the Ocean, Fooling Polytopes, Nonuniform ACC Circuit Lower Bounds, Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds, Derandomization from Algebraic Hardness, Entropy of Weight Distributions of Small-Bias Spaces and Pseudobinomiality, Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization, Worst-case hardness suffices for derandomization: A new method for hardness-randomness trade-offs, On closure properties of bounded two-sided error complexity classes, Characterizing polynomial complexity classes by reducibilities, Two Comments on Targeted Canonical Derandomizers, On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions, Unnamed Item, On secret sharing, randomness, and random-less reductions for secret sharing, The power of natural properties as oracles, Black-box separations for non-interactive classical commitments in a quantum world, Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\), Extractors: low entropy requirements colliding with non-malleability, Paradigms for Unconditional Pseudorandom Generators, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, How to get more mileage from randomness extractors, Flavors of Compressive Sensing, Unnamed Item, Unnamed Item, Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma, Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs, Pseudo-deterministic Proofs, On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets, On polynomial approximations to AC, Agnostic Learning from Tolerant Natural Proofs, Almost k-Wise Independent Sets Establish Hitting Sets for Width-3 1-Branching Programs, Pseudo-Derandomizing Learning and Approximation, NONDETERMINISTIC CIRCUIT MINIMIZATION PROBLEM AND DERANDOMIZING ARTHUR-MERLIN GAMES, An Introduction to Randomness Extractors, Approximate counting in bounded arithmetic, NL-printable sets and Nondeterministic Kolmogorov Complexity, Unnamed Item, On pseudorandomness and resource-bounded measure, Pseudorandom generators without the XOR lemma, Arthur and Merlin as Oracles, Minimum Circuit Size, Graph Isomorphism, and Related Problems, Injective trapdoor functions via derandomization: how strong is Rudich's black-box barrier?, Unnamed Item, Unnamed Item, Injective trapdoor functions via derandomization: how strong is Rudich's black-box barrier?, Easiness assumptions and hardness tests: Trading time for zero error, Extracting all the randomness and reducing the error in Trevisan's extractors, Hardness amplification within NP, Cell-probe lower bounds for the partial match problem, Pseudo-random generators for all hardnesses, A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus$ via the Coin Problem], On algorithmic statistics for space-bounded algorithms, ON THE HARDNESS AGAINST CONSTANT-DEPTH LINEAR-SIZE CIRCUITS, Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 − o(1) Symmetric Gates, Candidate One-Way Functions Based on Expander Graphs, In a World of P=BPP, On Yao’s XOR-Lemma, On the Optimal Compression of Sets in PSPACE, Unnamed Item, Unnamed Item, Hardness of approximate two-level logic minimization and PAC learning with membership queries, ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION, On the Symmetries of and Equivalence Test for Design Polynomials., Randomness and Intractability in Kolmogorov Complexity, Typically-correct derandomization for small time and space, Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits, Does Looking Inside a Circuit Help, Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace, A Polynomial-Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3, Efficient Construction of Rigid Matrices Using an NP Oracle, A Note on Perfect Correctness by Derandomization, New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes., In search of an easy witness: Exponential time vs. probabilistic polynomial time., On the possibility of basing cryptography on \(\mathsf{EXP}\ne \mathsf{BPP} \), Deterministic function computation with chemical reaction networks, Uniformly hard languages., Regarding two conjectures on clique and biclique partitions, On explicit constructions of designs, Expander-based cryptography meets natural proofs, A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3, Computational depth: Concept and applications, NL-printable sets and nondeterministic Kolmogorov complexity, Dual weak pigeonhole principle, Boolean complexity, and derandomization, Incompressible functions, relative-error extractors, and the power of nondeterministic reductions, A note on perfect correctness by derandomization, The landscape of communication complexity classes, Reconstructive dispersers and hitting set generators, Index sets and presentations of complexity classes, DNF sparsification and a faster deterministic counting algorithm, A satisfiability algorithm and average-case hardness for formulas over the full binary basis, The size of SPP, Lower bounds for the circuit size of partially homogeneous polynomials, \(\mathrm{AC}^{0}\circ \mathrm{MOD}_{2}\) lower bounds for the Boolean inner product, On the limits of depth reduction at depth 3 over small finite fields, Robust simulations and significant separations, Uniform derandomization from pathetic lower bounds, On approximating the eigenvalues of stochastic matrices in probabilistic logspace, The Gelfand widths of \(\ell_p\)-balls for \(0 < p \leq 1\), Lower bound on average-case complexity of inversion of Goldreich's function by drunken backtracking algorithms, Tripartite-to-bipartite entanglement transformation by stochastic local operations and classical communication and the structure of matrix spaces, On the volume of unit balls of finite-dimensional Lorentz spaces, Optimal bounds for the approximation of Boolean functions and some applications, Pseudorandom generators for \(\mathrm{CC}^0[p\) and the Fourier spectrum of low-degree polynomials over finite fields], Pseudorandom generators for combinatorial checkerboards, The isomorphism conjecture for constant depth reductions, The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory, Symmetric random function generator (SRFG): a novel cryptographic primitive for designing fast and robust algorithms, Pseudorandom generators against advised context-free languages, Towards a tight hardness-randomness connection between permanent and arithmetic circuit identity testing, On derandomization and average-case complexity of monotone functions, The complexity of inverting explicit Goldreich's function by DPLL algorithms, CCA-secure (puncturable) KEMs from encryption with non-negligible decryption errors, Random low-degree polynomials are hard to approximate, Pseudorandom generators, typically-correct derandomization, and circuit lower bounds, BKW meets Fourier new algorithms for LPN with sparse parities, Simple and efficient batch verification techniques for verifiable delay functions, Variations on Muchnik's conditional complexity theorem, Low-depth witnesses are easy to find, Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds, Weak derandomization of weak algorithms: explicit versions of Yao's lemma, Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs, Arthur and Merlin as oracles, Isolation, matching, and counting uniform and nonuniform upper bounds, Hard sets are hard to find, Circuit lower bounds in bounded arithmetics, Entropy numbers of finite-dimensional embeddings, Relations between average-case and worst-case complexity, Random walks on graphs and Monte Carlo methods, Extremal set theory and LWE based access structure hiding verifiable secret sharing with malicious-majority and free verification, Upward separations and weaker hypotheses in resource-bounded measure, Small-bias is not enough to hit read-once CNF, Quantum certificate complexity, Underapproximation for model-checking based on universal circuits, Collapsing and separating completeness notions under average-case and worst-case hypotheses, Improving the space-bounded version of Muchnik's conditional complexity theorem via ``naive derandomization, Pseudo-random graphs and bit probe schemes with one-sided error, The complexity of explicit constructions, Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution, Feasibly constructive proofs of succinct weak circuit lower bounds, Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games, Fourier concentration from shrinkage, Simple extractors via constructions of cryptographic pseudo-random generators, Extractors from Reed-Muller codes, On zero error algorithms having oracle access to one query, On the existence of compact $\varepsilon$-approximated formulations for knapsack in the original space, Explicit list-decodable codes with optimal rate for computationally bounded channels, Depth-4 lower bounds, determinantal complexity: a unified approach, Negation-limited formulas, Comparing notions of computational entropy, On the complexity of constructing pseudorandom functions (especially when they don't exist), Natural Proofs versus Derandomization, Lower bounds for arithmetic circuits via the Hankel matrix, A Selection of Lower Bounds for Arithmetic Circuits, Cryptographic pseudorandom generators can make cryptosystems problematic, Geometric complexity theory V: Efficient algorithms for Noether normalization, Improved bounds for quantified derandomization of constant-depth circuits and polynomials, Advice Lower Bounds for the Dense Model Theorem, Fine-Grained Cryptography, Synthesizers and their application to the parallel construction of pseudo-random functions, Proving that \(\mathrm{prBPP}=\mathrm{prP}\) is as hard as proving that ``almost NP is not contained in P/poly, A Survey of Data Structures in the Bitprobe Model, Resource bounded symmetry of information revisited, An upward measure separation theorem, Randomness vs time: Derandomization under a uniform assumption, Mining circuit lower bound proofs for meta-algorithms, Unifying known lower bounds via geometric complexity theory, Relativized worlds with an infinite hierarchy, On optimal language compression for sets in PSPACE/poly, On extracting space-bounded Kolmogorov complexity, Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization, 3SUM, 3XOR, triangles
Cites Work
- Unnamed Item
- Unnamed Item
- Turing machines that take advice
- Pseudorandom bits for constant depth circuits
- Probabilistic encryption
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- Pseudorandom number generation and space complexity
- A Note on Randomized Polynomial Time
- Alternation
