The following pages link to Dieter van Melkebeek (Q354650):
Displayed 47 items.
- Is Valiant-Vazirani's isolation probability improvable? (Q354652) (← links)
- On derandomization and average-case complexity of monotone functions (Q428873) (← links)
- Pseudorandom generators, typically-correct derandomization, and circuit lower bounds (Q430845) (← links)
- Space hierarchy results for randomized and other semantic models (Q626680) (← links)
- An improved time-space lower bound for tautologies (Q652633) (← links)
- Language compression and pseudorandom generators (Q813317) (← links)
- Deterministic and randomized bounded truth-table reductions of P, NL, and L to sparse sets (Q1276171) (← links)
- (Q1318425) (redirect page) (← links)
- Block orthogonal systems for symmetric \(P\)-forms (Q1318426) (← links)
- (Q1575725) (redirect page) (← links)
- The zero-one law holds for BPP (Q1575726) (← links)
- Randomness and completeness in computational complexity (Q1591868) (← links)
- The quantum black-box complexity of majority (Q1871636) (← links)
- Invariant finite Borel measures for rational functions on the Riemann sphere (Q1900617) (← links)
- Hard sets are hard to find (Q1961379) (← links)
- Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games (Q2012178) (← links)
- Computational depth: Concept and applications (Q2368976) (← links)
- Time-space tradeoff in derandomizing probabilistic logspace (Q2432534) (← links)
- A generic time hierarchy with one bit of advice (Q2472432) (← links)
- A time lower bound for satisfiability (Q2581273) (← links)
- (Q2729236) (← links)
- Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses (Q2819595) (← links)
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses (Q2875151) (← links)
- (Q2913799) (← links)
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses (Q3149879) (← links)
- Minimum Circuit Size, Graph Isomorphism, and Related Problems (Q3176189) (← links)
- Time‐Space Lower Bounds for the Polynomial‐Time Hierarchy on Randomized Machines (Q3446808) (← links)
- Time-space lower bounds for satisfiability (Q3455209) (← links)
- A Survey of Lower Bounds for Satisfiability and Related Problems (Q3587579) (← links)
- Pseudorandom Generators and Typically-Correct Derandomization (Q3638904) (← links)
- (Q4258582) (← links)
- (Q4336273) (← links)
- (Q4501551) (← links)
- (Q4668733) (← links)
- (Q4910739) (← links)
- Separating Complexity Classes Using Autoreducibility (Q4943880) (← links)
- Minimum Circuit Size, Graph Isomorphism, and Related Problems (Q4993283) (← links)
- (Q5111135) (← links)
- Derandomizing Isolation in Space-Bounded Settings (Q5232318) (← links)
- STACS 2004 (Q5309732) (← links)
- An Improved Time-Space Lower Bound for Tautologies (Q5323091) (← links)
- Automata, Languages and Programming (Q5466530) (← links)
- Power from Random Strings (Q5470741) (← links)
- Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses (Q5501928) (← links)
- Holographic Proofs and Derandomization (Q5700569) (← links)
- Automata, Languages and Programming (Q5716845) (← links)
- (Q6126365) (← links)