scientific article; zbMATH DE number 1335875
From MaRDI portal
Publication:4258566
Recommendations
Cited in
(26)- AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly
- Gate elimination: circuit size lower bounds and \#SAT upper bounds
- The complexity of Bayesian networks specified by propositional and relational languages
- Sparse selfreducible sets and nonuniform lower bounds
- New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes.
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Non-pseudounitary fusion
- Proving that \(\mathrm{prBPP}=\mathrm{prP}\) is as hard as proving that ``almost NP is not contained in P/poly
- Unifying known lower bounds via geometric complexity theory
- Efficient learning algorithms yield circuit lower bounds
- Circuit lower bounds from learning-theoretic approaches
- Algebrization: a new barrier in complexity theory
- Nondeterministic separations
- Two variable vs. linear temporal logic in model checking and games
- Nonuniform ACC circuit lower bounds
- Circuit lower bounds for average-case MA
- Lower bounds against weakly-uniform threshold circuits
- Randomness and intractability in Kolmogorov complexity
- Hardness magnification near state-of-the-art lower bounds
- scientific article; zbMATH DE number 7250147 (Why is no real title available?)
- The power of natural properties as oracles
- Improving \(3N\) circuit complexity lower bounds
- Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds
- On the structure of learnability beyond \textsf{P/poly}
- Symmetric exponential time requires near-maximum circuit size
- Title not available (Why is no real title available?)
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4258566)
