
PreviousNext
Continuing a line of investigation that has studied the
function classes #P, #SAC^1, #L, and #NC^1, we study the
class of functions #AC^0. One way to define #AC^0 is as the
class of functions computed by constant-depth polynomial-size
arithmetic circuits of unbounded fan-in addition ...
more >>>
We introduce a notion of a "real game"
(a generalization of the Karchmer - Wigderson game),
and "real communication complexity",
and relate them to the size of monotone real formulas
and circuits. We give an exponential lower bound
for tree-like monotone protocols of small real
communication complexity ...
more >>>
We show that in the context of nonuniform complexity,
nondeterministic logarithmic space bounded computation can be made
unambiguous. An analogous result holds for the class of problems
reducible to context-free languages. In terms of complexity classes,
this can be stated as:
NL/poly = UL/poly
LogCFL/poly ...
more >>>
PreviousNext