The following pages link to Hardness vs randomness (Q1337458):
Displaying 50 items.
- 3SUM, 3XOR, triangles (Q261365) (← links)
- Deterministic function computation with chemical reaction networks (Q268444) (← links)
- Incompressible functions, relative-error extractors, and the power of nondeterministic reductions (Q301524) (← links)
- DNF sparsification and a faster deterministic counting algorithm (Q354649) (← links)
- A satisfiability algorithm and average-case hardness for formulas over the full binary basis (Q354655) (← links)
- Pseudorandom generators for \(\mathrm{CC}^0[p]\) and the Fourier spectrum of low-degree polynomials over finite fields (Q395606) (← links)
- Pseudorandom generators for combinatorial checkerboards (Q395607) (← links)
- On derandomization and average-case complexity of monotone functions (Q428873) (← links)
- Random low-degree polynomials are hard to approximate (Q430841) (← links)
- Pseudorandom generators, typically-correct derandomization, and circuit lower bounds (Q430845) (← links)
- Low-depth witnesses are easy to find (Q445240) (← links)
- Weak derandomization of weak algorithms: explicit versions of Yao's lemma (Q451107) (← links)
- Circuit lower bounds in bounded arithmetics (Q466447) (← links)
- Small-bias is not enough to hit read-once CNF (Q519906) (← links)
- The size of SPP (Q596117) (← links)
- The Gelfand widths of \(\ell_p\)-balls for \(0 < p \leq 1\) (Q609740) (← links)
- The isomorphism conjecture for constant depth reductions (Q619896) (← links)
- The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory (Q619899) (← links)
- Variations on Muchnik's conditional complexity theorem (Q639853) (← links)
- Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds (Q645124) (← links)
- Arthur and Merlin as oracles (Q649095) (← links)
- Collapsing and separating completeness notions under average-case and worst-case hypotheses (Q693053) (← links)
- The complexity of explicit constructions (Q693069) (← links)
- Negation-limited formulas (Q729897) (← links)
- Comparing notions of computational entropy (Q733747) (← links)
- An upward measure separation theorem (Q808696) (← links)
- Pseudorandom generators against advised context-free languages (Q899305) (← links)
- Relations between average-case and worst-case complexity (Q927398) (← links)
- Underapproximation for model-checking based on universal circuits (Q963058) (← links)
- Synthesizers and their application to the parallel construction of pseudo-random functions (Q1288205) (← links)
- Index sets and presentations of complexity classes (Q1366536) (← links)
- Optimal bounds for the approximation of Boolean functions and some applications (Q1390872) (← links)
- Randomness vs time: Derandomization under a uniform assumption (Q1604214) (← links)
- Relativized worlds with an infinite hierarchy (Q1606916) (← links)
- The landscape of communication complexity classes (Q1653337) (← links)
- \(\mathrm{AC}^{0}\circ \mathrm{MOD}_{2}\) lower bounds for the Boolean inner product (Q1671999) (← links)
- Lower bound on average-case complexity of inversion of Goldreich's function by drunken backtracking algorithms (Q1678752) (← links)
- Symmetric random function generator (SRFG): a novel cryptographic primitive for designing fast and robust algorithms (Q1694084) (← links)
- On the existence of compact $\varepsilon$-approximated formulations for knapsack in the original space (Q1785373) (← links)
- New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes. (Q1872705) (← links)
- In search of an easy witness: Exponential time vs. probabilistic polynomial time. (Q1872732) (← links)
- Uniformly hard languages. (Q1874273) (← links)
- Dual weak pigeonhole principle, Boolean complexity, and derandomization (Q1887654) (← links)
- Towards a tight hardness-randomness connection between permanent and arithmetic circuit identity testing (Q1941704) (← links)
- The complexity of inverting explicit Goldreich's function by DPLL algorithms (Q1946844) (← links)
- Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs (Q1960516) (← links)
- Isolation, matching, and counting uniform and nonuniform upper bounds (Q1961370) (← links)
- Hard sets are hard to find (Q1961379) (← links)
- Feasibly constructive proofs of succinct weak circuit lower bounds (Q2007873) (← links)
- Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games (Q2012178) (← links)
