Circuit-size lower bounds and non-reducibility to sparse sets
From MaRDI portal
Publication:3323851
DOI10.1016/S0019-9958(82)90382-5zbMath0537.94027OpenAlexW2092429268WikidataQ61877185 ScholiaQ61877185MaRDI QIDQ3323851
Publication date: 1982
Published in: Information and Control (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0019-9958(82)90382-5
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Complexity of computation (including implicit computational complexity) (03D15)
Related Items
On randomized versus deterministic computation, On solving hard problems by polynomial-size circuits, Circuit lower bounds from learning-theoretic approaches, Circuit principles and weak pigeonhole variants, Nonuniform ACC Circuit Lower Bounds, Polynomial time quantum computation with advice, On randomized versus deterministic computation, Circuit Lower Bounds for Average-Case MA, Amplifying circuit lower bounds against polynomial time, with applications, Robust simulations and significant separations, On the Limit of Some Algorithmic Approach to Circuit Lower Bounds, The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory, Pseudorandom generators, typically-correct derandomization, and circuit lower bounds, Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds, Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma, Unnamed Item, Lower bounds against weakly-uniform threshold circuits, Sublogarithmic-space turing machines, nonuniform space complexity, and closure properties, On uniformity and circuit lower bounds, On Pseudodeterministic Approximation Algorithms., Optimal advice, Almost everywhere high nonuniform complexity, New collapse consequences of NP having small circuits, On problems for which no oracle can help, Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games, Fourier concentration from shrinkage, A note on dimensions of polynomial size circuits, On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant, Efficient learning algorithms yield circuit lower bounds, Unnamed Item, Relations and equivalences between circuit lower bounds and karp-lipton theorems, AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly, Complete sets and closeness to complexity classes, A note on the circuit complexity of PP, On proving time constructibility of functions, PAC-learning gains of Turing machines over circuits and neural networks, Mining circuit lower bound proofs for meta-algorithms, Unifying known lower bounds via geometric complexity theory
