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 50 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)
- A thirty year old conjecture about promise problems (Q347124) (← 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)
- Catalytic space: non-determinism and hierarchy (Q1702851) (← links)
- Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games (Q2012178) (← links)
- Nonuniform reductions and NP-completeness (Q2158296) (← links)
- On optimal language compression for sets in PSPACE/poly (Q2354585) (← links)
- NL-printable sets and nondeterministic Kolmogorov complexity (Q2369009) (← links)
- On approximating the eigenvalues of stochastic matrices in probabilistic logspace (Q2410679) (← links)
- Lower bounds for non-black-box zero knowledge (Q2490264) (← links)
- On zero error algorithms having oracle access to one query (Q2498984) (← links)
- Circuit lower bounds from learning-theoretic approaches (Q2636410) (← links)
- Natural Proofs versus Derandomization (Q2805512) (← links)
- On the Optimal Compression of Sets in PSPACE (Q3088270) (← links)
- Nonuniform ACC Circuit Lower Bounds (Q3189637) (← links)
- (Q3304139) (← links)
- Arthur and Merlin as Oracles (Q3599130) (← links)
- NL-printable sets and Nondeterministic Kolmogorov Complexity (Q4924524) (← links)
- (Q5002644) (← links)
- On Pseudodeterministic Approximation Algorithms. (Q5005164) (← links)
- (Q5009546) (← links)
- Randomized and Symmetric Catalytic Computation (Q5042242) (← links)
- The Untold Story of $$\mathsf {SBP}$$ (Q5042261) (← links)
- Quantified Derandomization: How to Find Water in the Ocean (Q5060673) (← links)
- Randomness and Intractability in Kolmogorov Complexity (Q5091181) (← links)
- Typically-correct derandomization for small time and space (Q5091759) (← links)
- (Q5092470) (← links)
- (Q5092476) (← links)
- Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space (Q5096446) (← links)
- A remark on pseudo proof systems and hard instances of the satisfiability problem (Q5109236) (← links)
- (Q5111269) (← links)
- (Q5121895) (← links)
- Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma (Q5130843) (← links)
- Derandomizing Isolation in Space-Bounded Settings (Q5232318) (← links)
- NONDETERMINISTIC CIRCUIT MINIMIZATION PROBLEM AND DERANDOMIZING ARTHUR-MERLIN GAMES (Q5714674) (← links)
- Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace (Q5856147) (← links)
- Efficient Construction of Rigid Matrices Using an NP Oracle (Q5863325) (← links)
- (Q6054746) (← links)
- Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error (Q6089979) (← links)