Hardness vs randomness
From MaRDI portal
Recommendations
Cites work
- BPP has subexponential time simulations unless EXPTIME has publishable proofs
- A Note on Randomized Polynomial Time
- Alternation
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- scientific article; zbMATH DE number 3980487 (Why is no real title available?)
- scientific article; zbMATH DE number 3724342 (Why is no real title available?)
- Probabilistic encryption
- Pseudorandom bits for constant depth circuits
- Pseudorandom number generation and space complexity
- Turing machines that take advice
Cited in
(only showing first 100 items - show all)- Pseudorandom generators for space-bounded computation
- Synthesizers and their application to the parallel construction of pseudo-random functions
- Index sets and presentations of complexity classes
- Optimal bounds for the approximation of Boolean functions and some applications
- Randomness vs time: Derandomization under a uniform assumption
- Relativized worlds with an infinite hierarchy
- The landscape of communication complexity classes
- \(\mathrm{AC}^{0}\circ \mathrm{MOD}_{2}\) lower bounds for the Boolean inner product
- Lower bound on average-case complexity of inversion of Goldreich's function by drunken backtracking algorithms
- Symmetric random function generator (SRFG): a novel cryptographic primitive for designing fast and robust algorithms
- Some results on derandomization
- On the existence of compact $\varepsilon$-approximated formulations for knapsack in the original space
- Some consequences of the existnce of pseudorandom generators
- New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes.
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Uniformly hard languages.
- Dual weak pigeonhole principle, Boolean complexity, and derandomization
- Towards a tight hardness-randomness connection between permanent and arithmetic circuit identity testing
- How strong is Nisan's pseudo-random generator?
- The complexity of inverting explicit Goldreich's function by DPLL algorithms
- Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs
- Isolation, matching, and counting uniform and nonuniform upper bounds
- Hard sets are hard to find
- Feasibly constructive proofs of succinct weak circuit lower bounds
- Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
- Fourier concentration from shrinkage
- Explicit list-decodable codes with optimal rate for computationally bounded channels
- Lower bounds for arithmetic circuits via the Hankel matrix
- Cryptographic pseudorandom generators can make cryptosystems problematic
- Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization
- On the possibility of basing cryptography on \(\mathsf{EXP}\ne \mathsf{BPP} \)
- Regarding two conjectures on clique and biclique partitions
- On explicit constructions of designs
- Expander-based cryptography meets natural proofs
- A note on perfect correctness by derandomization
- On the volume of unit balls of finite-dimensional Lorentz spaces
- Entropy numbers of finite-dimensional embeddings
- 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
- Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
- Simple extractors via constructions of cryptographic pseudo-random generators
- Depth-4 lower bounds, determinantal complexity: a unified approach
- Improved bounds for quantified derandomization of constant-depth circuits and polynomials
- Proving that \(\mathrm{prBPP}=\mathrm{prP}\) is as hard as proving that ``almost NP is not contained in P/poly
- Mining circuit lower bound proofs for meta-algorithms
- Unifying known lower bounds via geometric complexity theory
- On optimal language compression for sets in PSPACE/poly
- On extracting space-bounded Kolmogorov complexity
- Computational depth: Concept and applications
- NL-printable sets and nondeterministic Kolmogorov complexity
- Reconstructive dispersers and hitting set generators
- Lower bounds for the circuit size of partially homogeneous polynomials
- On the limits of depth reduction at depth 3 over small finite fields
- On approximating the eigenvalues of stochastic matrices in probabilistic logspace
- Tripartite-to-bipartite entanglement transformation by stochastic local operations and classical communication and the structure of matrix spaces
- Pseudorandomness for approximate counting and sampling
- Upward separations and weaker hypotheses in resource-bounded measure
- Quantum certificate complexity
- Pseudorandomness and average-case complexity via uniform reductions
- Extractors from Reed-Muller codes
- On zero error algorithms having oracle access to one query
- On the complexity of constructing pseudorandom functions (especially when they don't exist)
- Resource bounded symmetry of information revisited
- 3SUM, 3XOR, triangles
- Pseudorandom sources for BPP
- Deterministic function computation with chemical reaction networks
- CCA-secure (puncturable) KEMs from encryption with non-negligible decryption errors
- BKW meets Fourier new algorithms for LPN with sparse parities
- Simple and efficient batch verification techniques for verifiable delay functions
- scientific article; zbMATH DE number 1670863 (Why is no real title available?)
- Pseudorandom generators without the XOR lemma (extended abstract)
- Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses
- A Selection of Lower Bounds for Arithmetic Circuits
- On beating the hybrid argument
- Geometric complexity theory. V: Efficient algorithms for Noether normalization
- Advice lower bounds for the dense model theorem
- Fine-Grained Cryptography
- A Survey of Data Structures in the Bitprobe Model
- A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3
- Can every randomized algorithm be derandomized?
- Uniform derandomization from pathetic lower bounds
- Some new consequences of the hypothesis that P has fixed polynomial-size circuits
- Almost k-wise independent sets establish hitting sets for width-3 1-branching programs
- An introduction to randomness extractors
- Incompressible functions, relative-error extractors, and the power of nondeterministic reductions
- ON THE HARDNESS AGAINST CONSTANT-DEPTH LINEAR-SIZE CIRCUITS
- Correlation bounds for poly-size \(\mathrm{AC}^0\) circuits with \(n^{1 - o(1)}\) symmetric gates
- Candidate one-way functions based on expander graphs
- In a world of \(\mathrm{P}=\mathrm{BPP}\)
- On Yao's XOR-lemma
- On the optimal compression of sets in PSPACE
- ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION
- A Pseudorandom Oracle Characterization of ${\text{BPP}}$
- Nisan-Wigderson generators in proof systems with forms of interpolation
- Minimum circuit size, graph isomorphism, and related problems
- Nonuniform ACC circuit lower bounds
- Entropy of weight distributions of small-bias spaces and pseudobinomiality
- On nonadaptive reductions to the set of random strings and its dense subsets
- scientific article; zbMATH DE number 3876586 (Why is no real title available?)
- Characterizing polynomial complexity classes by reducibilities
This page was built for publication: Hardness vs randomness
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1337458)
