The following pages link to A. Pavan (Q208054):
Displaying 32 items.
- A thirty year old conjecture about promise problems (Q347124) (← links)
- The fault tolerance of NP-hard problems (Q553311) (← links)
- Collapsing and separating completeness notions under average-case and worst-case hypotheses (Q693053) (← links)
- Extracting Kolmogorov complexity with applications to dimension zero-one laws (Q716318) (← links)
- Comparing reductions to NP-complete sets (Q879596) (← links)
- Autoreducibility, mitoticity, and immunity (Q881593) (← links)
- Relations between average-case and worst-case complexity (Q927398) (← links)
- Hardness hypotheses, derandomization, and circuit complexity (Q937197) (← links)
- Resource-bounded strong dimension versus resource-bounded category (Q1041791) (← links)
- Complete distributional problems, hard languages, and resource-bounded measure (Q1575682) (← links)
- Some results on derandomization (Q1771319) (← links)
- Bi-immunity separates strong NP-completeness notions (Q1887166) (← links)
- On the power of unambiguity in log-space (Q1926109) (← links)
- Perfect zero knowledge: new upperbounds and relativized separations (Q2055744) (← links)
- 2-local random reductions to 3-valued functions (Q2269002) (← links)
- Robustness of PSPACE-complete sets (Q2379952) (← links)
- Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy (Q2456368) (← links)
- Proving SAT does not have small circuits with an application to the two queries problem (Q2475408) (← links)
- Partial bi-immunity, scaled dimension, and NP-completeness (Q2480744) (← links)
- Separation of NP-Completeness Notions (Q2784487) (← links)
- A Thirty Year Old Conjecture about Promise Problems (Q2843273) (← links)
- Length-Increasing Reductions for PSPACE-Completeness (Q2849941) (← links)
- Kolmogorov Complexity in Randomness Extraction. (Q2920128) (← links)
- On Probabilistic Space-Bounded Machines with Multiple Access to Random Tape (Q2946415) (← links)
- Kolmogorov Complexity in Randomness Extraction (Q2947554) (← links)
- Separating Cook Completeness from Karp-Levin Completeness Under a Worst-Case Hardness Hypothesis (Q2978535) (← links)
- New Time-Space Upperbounds for Directed Reachability in High-genus and H-minor-free Graphs. (Q2978548) (← links)
- (Q3113769) (← links)
- Properties of NP‐Complete Sets (Q3434997) (← links)
- A Note on the Advice Complexity of Multipass Randomized Logspace (Q4608590) (← links)
- On Pseudodeterministic Approximation Algorithms. (Q5005164) (← links)
- On the NP-Completeness of the Minimum Circuit Size Problem. (Q5275370) (← links)