The following pages link to (Q4526985):
Displaying 50 items.
- Incompressible functions, relative-error extractors, and the power of nondeterministic reductions (Q301524) (← links)
- Derandomized parallel repetition theorems for free games (Q371195) (← links)
- Pseudorandom generators for combinatorial checkerboards (Q395607) (← 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)
- Complexity of hard-core set proofs (Q451110) (← links)
- Randomness buys depth for approximate counting (Q483707) (← links)
- Small-bias is not enough to hit read-once CNF (Q519906) (← links)
- Metric structures and probabilistic computation (Q541224) (← links)
- The size of SPP (Q596117) (← links)
- The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory (Q619899) (← links)
- Infeasibility of instance compression and succinct PCPs for NP (Q619903) (← links)
- Hardness amplification within NP against deterministic algorithms (Q619904) (← links)
- Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds (Q645124) (← links)
- Arthur and Merlin as oracles (Q649095) (← links)
- Improved direct product theorems for randomized query complexity (Q693002) (← links)
- Collapsing and separating completeness notions under average-case and worst-case hypotheses (Q693053) (← links)
- The complexity of explicit constructions (Q693069) (← links)
- Avoiding simplicity is complex (Q693072) (← links)
- Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification (Q744610) (← links)
- Improved hardness amplification in NP (Q868960) (← links)
- A broader view on the limitations of information processing and communication by nature (Q885681) (← links)
- Query complexity in errorless hardness amplification (Q901934) (← links)
- Relations between average-case and worst-case complexity (Q927398) (← links)
- Chernoff-type direct product theorems (Q1027975) (← links)
- Approximation of boolean functions by combinatorial rectangles (Q1399979) (← links)
- Almost \(k\)-wise independence and hard Boolean functions. (Q1401305) (← links)
- Randomness vs time: Derandomization under a uniform assumption (Q1604214) (← links)
- Random oracles and non-uniformity (Q1648794) (← links)
- Generic hardness of the Boolean satisfiability problem (Q1676251) (← links)
- Catalytic space: non-determinism and hierarchy (Q1702851) (← links)
- Knapsack in graph groups (Q1702854) (← links)
- Evaluation of circuits over nilpotent and polycyclic groups (Q1750355) (← links)
- Tally NP sets and easy census functions. (Q1854340) (← links)
- In search of an easy witness: Exponential time vs. probabilistic polynomial time. (Q1872732) (← links)
- Uniformly hard languages. (Q1874273) (← 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)
- Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games (Q2012178) (← links)
- Fourier concentration from shrinkage (Q2012185) (← links)
- Explicit list-decodable codes with optimal rate for computationally bounded channels (Q2029777) (← links)
- A note on perfect correctness by derandomization (Q2146431) (← links)
- Simple extractors via constructions of cryptographic pseudo-random generators (Q2268098) (← links)
- On derandomized composition of Boolean functions (Q2281253) (← links)
- Improved bounds for quantified derandomization of constant-depth circuits and polynomials (Q2311548) (← links)
- Verification of quantum computation: an overview of existing approaches (Q2311888) (← links)
- Proving that \(\mathrm{prBPP}=\mathrm{prP}\) is as hard as proving that ``almost NP'' is not contained in P/poly (Q2328311) (← links)
- Mining circuit lower bound proofs for meta-algorithms (Q2351392) (← links)
- On optimal language compression for sets in PSPACE/poly (Q2354585) (← links)
