Computational Complexity
Covers models of computation, complexity classes, structural complexity, complexity tradeoffs, upper and lower bounds. Roughly includes material in ACM Subject Classes F.1 (computation by abstract devices), F.2.3 (tradeoffs among complexity measures), and F.4.3 (formal languages), although some material in formal languages may be more appropriate for Logic in Computer Science. Some material in F.2.1 and F.2.2, may also be appropriate here, but is more likely to have Data Structures and Algorithms as the primary subject area.
Amplifying a hard Tarski family by dimension and width yields a (k/log k)^{Ω(log k)} lower bound, ruling out black-box Tarski solvers for…
· “Bootstrapping Classical and Quantum Query Lower Bounds for Finding Tarski Fixed Points”
An equivalence ties this hardness to symmetry of information, explicit constructions, and circuit lower bounds.
· “Asymmetry and Complexity of Nondeterministic Computations”
A bijection between gates and commutative Frobenius algebras yields polynomial-time Holant algorithms for any domain size.
· “Generalized Fibonacci gates are Frobenius algebras: a proof of Liu's conjecture”