Pages that link to "Item:Q3149879"
From MaRDI portal
The following pages link to Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses (Q3149879):
Displayed 23 items.
- Quantum commitments from complexity assumptions (Q260394) (← links)
- The complexity of estimating min-entropy (Q260395) (← links)
- Incompressible functions, relative-error extractors, and the power of nondeterministic reductions (Q301524) (← links)
- Is Valiant-Vazirani's isolation probability improvable? (Q354652) (← links)
- Pseudorandom generators, typically-correct derandomization, and circuit lower bounds (Q430845) (← links)
- Low-depth witnesses are easy to find (Q445240) (← 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)
- Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds (Q645124) (← links)
- Arthur and Merlin as oracles (Q649095) (← links)
- The complexity of explicit constructions (Q693069) (← links)
- Relations between average-case and worst-case complexity (Q927398) (← links)
- On optimal language compression for sets in PSPACE/poly (Q2354585) (← links)
- NL-printable sets and nondeterministic Kolmogorov complexity (Q2369009) (← links)
- Lower bounds for non-black-box zero knowledge (Q2490264) (← links)
- On zero error algorithms having oracle access to one query (Q2498984) (← links)
- Natural Proofs versus Derandomization (Q2805512) (← links)
- On the Optimal Compression of Sets in PSPACE (Q3088270) (← links)
- Nonuniform ACC Circuit Lower Bounds (Q3189637) (← links)
- Arthur and Merlin as Oracles (Q3599130) (← links)
- NL-printable sets and Nondeterministic Kolmogorov Complexity (Q4924524) (← links)
- NONDETERMINISTIC CIRCUIT MINIMIZATION PROBLEM AND DERANDOMIZING ARTHUR-MERLIN GAMES (Q5714674) (← links)