It is well-known that the class of sets that can be computed by polynomial size circuits is equal to the class of sets that are polynomial time reducible to a sparse set. It is widely believed, but unfortunately up to now unproven, that there are sets in EXP^{NP}, or even ... more >>>

A recursive enumerator for a function h is an algorithm f which
enumerates for an input x finitely many elements including h(x).
f is an k(n)-enumerator if for every input x of length n, h(x)
is among the first k(n) elements enumerated by f.
If there is a k(n)-enumerator for ... more >>>

Normally, communication Complexity deals with how many bits
Alice and Bob need to exchange to compute f(x,y)
(Alice has x, Bob has y). We look at what happens if
Alice has x_1,x_2,...,x_n and Bob has y_1,...,y_n
and they want to compute f(x_1,y_1)... f(x_n,y_n).
THis seems hard. We look at various ... more >>>