
PreviousNext
We prove super-linear lower bounds for the number of edges
in constant depth circuits with $n$ inputs and up to $n$ outputs.
Our lower bounds are proved for all types of constant depth
circuits, e.g., constant depth arithmetic circuits, constant depth
threshold circuits ...
more >>>
We show new tradeoffs for satisfiability and nondeterministic
linear time. Satisfiability cannot be solved on general purpose
random-access Turing machines in time $n^{1.618}$ and space
$n^{o(1)}$. This improves recent results of Lipton and Viglas and
Fortnow.
The investigation of the computational power of randomized computations
is one of the central tasks of current complexity and algorithm theory.
In this paper for the first time a "strong" separation between the power
of determinism, Las Vegas randomization, and nondeterminism for a compu-
ting model is proved. The computing ...
more >>>
PreviousNext