
PreviousNext
In a semantic resolution proof we operate with clauses only
but allow {\em arbitrary} rules of inference:
C_1 C_2 ... C_m
__________________
C
Consistency is the only requirement. We prove a very simple
exponential lower bound for the size ...
more >>>
We consider the framework of Parameterized Complexity, and we
investigate the issue of which problems do admit efficient fixed
parameter parallel algorithms by introducing two different
degrees of efficiently parallelizable parameterized problems, PNC
and FPP. We sketch both some FPP-algorithms solving natural
parameterized problems and ...
more >>>
Luby and Rackoff showed a method for constructing a pseudo-random
permutation from a pseudo-random function. The method is based on
composing four (or three for weakened security) so called Feistel
permutations each of which requires the evaluation of a pseudo-random
function. We reduce somewhat the complexity ...
more >>>
PreviousNext