Pages that link to "Item:Q3323851"
From MaRDI portal
The following pages link to Circuit-size lower bounds and non-reducibility to sparse sets (Q3323851):
Displayed 38 items.
- Amplifying circuit lower bounds against polynomial time, with applications (Q354644) (← links)
- Pseudorandom generators, typically-correct derandomization, and circuit lower bounds (Q430845) (← links)
- Lower bounds against weakly-uniform threshold circuits (Q486977) (← links)
- On uniformity and circuit lower bounds (Q488049) (← links)
- The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory (Q619899) (← links)
- Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds (Q645124) (← links)
- Optimal advice (Q672755) (← links)
- AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly (Q1029043) (← links)
- On proving time constructibility of functions (Q1059393) (← links)
- On solving hard problems by polynomial-size circuits (Q1095663) (← links)
- Almost everywhere high nonuniform complexity (Q1190985) (← links)
- On randomized versus deterministic computation (Q1365675) (← links)
- Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games (Q2012178) (← links)
- Fourier concentration from shrinkage (Q2012185) (← links)
- PAC-learning gains of Turing machines over circuits and neural networks (Q2111729) (← links)
- Mining circuit lower bound proofs for meta-algorithms (Q2351392) (← links)
- Unifying known lower bounds via geometric complexity theory (Q2351393) (← links)
- Circuit principles and weak pigeonhole variants (Q2383589) (← links)
- Polynomial time quantum computation with advice (Q2390250) (← links)
- Robust simulations and significant separations (Q2407096) (← links)
- A note on dimensions of polynomial size circuits (Q2503295) (← links)
- On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant (Q2514144) (← links)
- Efficient learning algorithms yield circuit lower bounds (Q2517822) (← links)
- A note on the circuit complexity of PP (Q2576885) (← links)
- Circuit lower bounds from learning-theoretic approaches (Q2636410) (← links)
- On the Limit of Some Algorithmic Approach to Circuit Lower Bounds (Q2944904) (← links)
- Nonuniform ACC Circuit Lower Bounds (Q3189637) (← links)
- Circuit Lower Bounds for Average-Case MA (Q3194723) (← links)
- Sublogarithmic-space turing machines, nonuniform space complexity, and closure properties (Q3811712) (← links)
- On problems for which no oracle can help (Q3829070) (← links)
- On randomized versus deterministic computation (Q4630263) (← links)
- New collapse consequences of NP having small circuits (Q4645178) (← links)
- Complete sets and closeness to complexity classes (Q4727430) (← links)
- On Pseudodeterministic Approximation Algorithms. (Q5005164) (← links)
- (Q5028364) (← links)
- Relations and equivalences between circuit lower bounds and karp-lipton theorems (Q5091782) (← links)
- (Q5121895) (← links)
- Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma (Q5130843) (← links)