Saugata Basu

Toda \cite{Toda} proved in 1989 that the (discrete) polynomial time hierarchy,

$\mathbf{PH}$,

is contained in the class $\mathbf{P}^{\#\mathbf{P}}$,

namely the class of languages that can be

decided by a Turing machine in polynomial time given access to an

oracle with the power to compute a function in the ...
more >>>

Henning Wunderlich

In an unpublished Russian manuscript Razborov proved that a matrix family with high

rigidity over a finite field would yield a language outside the polynomial hierarchy

in communication complexity.

We present an alternative proof that strengthens the original result in several ways.

In particular, we replace rigidity by the strictly ...
more >>>

Edward Hirsch, Dmitry Sokolov

Unambiguous hierarchies [NR93,LR94,NR98] are defined similarly to the polynomial hierarchy; however, all witnesses must be unique. These hierarchies have subtle differences in the mode of using oracles. We consider a "loose" unambiguous hierarchy $prUH_\bullet$ with relaxed definition of oracle access to promise problems. Namely, we allow to make queries that ... more >>>