LOGCFL Venkat Style

H. Venkateswaran, a much loved professor in the School of Computer Science at Georgia Tech and a fellow computational complexity theorist, is retiring at the end of December. In honor of Venkat I'd like talk about my favorite paper of his, relating LOGCFL to semi-unbounded circuits.

Let's start with context-free languages. Even if you never took a theoretical computer science course, you probably saw them in elementary school.

A context-free language is a series of rules like S-> NP VP or N->man. The context-free part comes from the fact that a noun phrase (NP) produces the same sentence fragments wherever it appears. CFLs have a rich theory--there have been whole textbooks devoted to the topics.

LOGCFL are the set of problems that are reducible to context-free languages with a small-space reduction. Formally, A is in LOGCFL if there is a CFL B and a log-space computable function f such that for all x, x is in A if and only if f(x) is in B.

Venkat showed that LOGCFLs are equivalent to semi-unbounded circuits, log-depth circuits with unbounded OR gates but bounded AND gates, the class now called SAC¹ (technically the equivalence holds for log-space uniform SAC¹ but that's not important). His proof goes through various models of alternating Turing machines and push-down automata.

Context-free languages are not closed under complement, for example 0ⁿ1ⁿ0ⁿ is not context-free but its complement is. Somewhat surprisingly Borodin, Cook, Dymond, Ruzzo and Tompa showed that LOGCFL is closed under complement, combining the Immerman-Szelepcsényi inductive counting technique with Venkat's circuit characterization of LOGCFL.

The Borodin result implies that you whether you have bounded ORs and unbounded ANDs, or bounded ANDs and unbounded ORs, you compute the same class.

Enjoy your retirement Venkat. We'll miss you!
Computational Complexity published first on Computational Complexity