Hardness vs randomness
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 3980487 (Why is no real title available?)
- scientific article; zbMATH DE number 3724342 (Why is no real title available?)
- 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
- Probabilistic encryption
- Pseudorandom bits for constant depth circuits
- Pseudorandom number generation and space complexity
- Turing machines that take advice
- \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
Cited in
(only showing first 100 items - show all)- Hard sets are hard to find
- Derandomization from Algebraic Hardness
- NONDETERMINISTIC CIRCUIT MINIMIZATION PROBLEM AND DERANDOMIZING ARTHUR-MERLIN GAMES
- Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization
- ON THE HARDNESS AGAINST CONSTANT-DEPTH LINEAR-SIZE CIRCUITS
- Pseudorandom sources for BPP
- Symmetric random function generator (SRFG): a novel cryptographic primitive for designing fast and robust algorithms
- Simple and efficient batch verification techniques for verifiable delay functions
- Two Comments on Targeted Canonical Derandomizers
- scientific article; zbMATH DE number 3876586 (Why is no real title available?)
- A Survey of Data Structures in the Bitprobe Model
- Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses
- On the optimal compression of sets in PSPACE
- Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
- The landscape of communication complexity classes
- Fine-Grained Cryptography
- How to get more mileage from randomness extractors
- The complexity of inverting explicit Goldreich's function by DPLL algorithms
- A Pseudorandom Oracle Characterization of ${\text{BPP}}$
- Flavors of compressive sensing
- Nisan-Wigderson generators in proof systems with forms of interpolation
- Tripartite-to-bipartite entanglement transformation by stochastic local operations and classical communication and the structure of matrix spaces
- FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
- Extractors from Reed-Muller codes
- On explicit constructions of designs
- On the existence of compact $\varepsilon$-approximated formulations for knapsack in the original space
- Upward separations and weaker hypotheses in resource-bounded measure
- On randomized versus deterministic computation
- scientific article; zbMATH DE number 1789922 (Why is no real title available?)
- An upward measure separation theorem
- On closure properties of bounded two-sided error complexity classes
- Characterizing polynomial complexity classes by reducibilities
- NL-printable sets and nondeterministic Kolmogorov complexity
- Negation-limited formulas
- Proving that \(\mathrm{prBPP}=\mathrm{prP}\) is as hard as proving that ``almost NP is not contained in P/poly
- Comparing notions of computational entropy
- \(\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
- scientific article; zbMATH DE number 7528580 (Why is no real title available?)
- scientific article; zbMATH DE number 7650112 (Why is no real title available?)
- On zero error algorithms having oracle access to one query
- Towards a tight hardness-randomness connection between permanent and arithmetic circuit identity testing
- How strong is Nisan's pseudo-random generator?
- Collapsing and separating completeness notions under average-case and worst-case hypotheses
- The complexity of explicit constructions
- On the volume of unit balls of finite-dimensional Lorentz spaces
- Agnostic Learning from Tolerant Natural Proofs
- scientific article; zbMATH DE number 7561765 (Why is no real title available?)
- Entropy numbers of finite-dimensional embeddings
- scientific article; zbMATH DE number 4186980 (Why is no real title available?)
- Nonuniform ACC circuit lower bounds
- Unifying known lower bounds via geometric complexity theory
- Feasibly constructive proofs of succinct weak circuit lower bounds
- On approximating the eigenvalues of stochastic matrices in probabilistic logspace
- Underapproximation for model-checking based on universal circuits
- Index sets and presentations of complexity classes
- Minimum circuit size, graph isomorphism, and related problems
- Randomness and intractability in Kolmogorov complexity
- Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs
- Limitations of Hardness vs. Randomness under Uniform Reductions
- Extracting all the randomness and reducing the error in Trevisan's extractors
- Some results on derandomization
- Pseudorandom bits and lower bounds for randomized Turing machines
- Minimum circuit size, graph isomorphism, and related problems
- On secret sharing, randomness, and random-less reductions for secret sharing
- NL-printable sets and nondeterministic Kolmogorov complexity
- Pseudo-deterministic proofs
- Immunity and Simplicity for Exact Counting and Other Counting Classes
- (Nondeterministic) hardness vs. non-malleability
- Relations between average-case and worst-case complexity
- Random walks on graphs and Monte Carlo methods
- Computational depth: Concept and applications
- Circuit lower bounds in bounded arithmetics
- Arthur and Merlin as oracles
- Mining circuit lower bound proofs for meta-algorithms
- Deterministic function computation with chemical reaction networks
- Cell-probe lower bounds for the partial match problem
- The Gelfand widths of \(\ell_p\)-balls for \(0 < p \leq 1\)
- Pseudorandomness and average-case complexity via uniform reductions
- Hardness of approximate two-level logic minimization and PAC learning with membership queries
- Pseudorandom generators without the XOR lemma
- Some consequences of the existnce of pseudorandom generators
- ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION
- Pseudorandom generators, typically-correct derandomization, and circuit lower bounds
- Random low-degree polynomials are hard to approximate
- Can every randomized algorithm be derandomized?
- A primer on pseudorandom generators
- scientific article; zbMATH DE number 7250153 (Why is no real title available?)
- Language compression and pseudorandom generators
- Advances in Cryptology - CRYPTO 2003
- DNF sparsification and a faster deterministic counting algorithm
- On derandomization and average-case complexity of monotone functions
- Pseudorandomness when the odds are against you
- Isolation, matching, and counting uniform and nonuniform upper bounds
- Relativized worlds with an infinite hierarchy
- Fourier concentration from shrinkage
- An introduction to randomness extractors
- New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes.
- Candidate one-way functions based on expander graphs
- Dual weak pigeonhole principle, Boolean complexity, and derandomization
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)
