We prove exponential separations between the sizes of
particular refutations in negative, respectively linear, resolution and
general resolution. Only a superpolynomial separation between negative
and general resolution was previously known. Our examples show that there
is no strong relationship between the size and width of refutations in
negative and ... more >>>

Branching programs are a well-established computation model
for Boolean functions, especially read-once branching programs
have been studied intensively. Exponential lower bounds for
deterministic and nondeterministic read-once branching programs
are known for a long time. On the other hand, the problem of
proving superpolynomial lower bounds ... more >>>

We present several new and fairly practical public-key encryption
schemes and prove them secure against
adaptive chosen ciphertext attack. One scheme is based on Paillier's
Decision Composite Residuosity (DCR) assumption,
while another is based in the classical Quadratic Residuosity (QR)
assumption. The analysis is in the standard ... more >>>