The notion of an optimal acceptor for TAUT (the optimality
property is stated only for input strings from TAUT) comes from the line
of research aimed at resolving the question of whether optimal
propositional proof systems exist. In this paper we introduce two new
types of optimal acceptors, a D-N-optimal ... more >>>

We prove a time hierarchy theorem for inverting functions
computable in polynomial time with one bit of advice.
In particular, we prove that if there is a strongly
one-way function, then for any k and for any polynomial p,
there is a function f computable in linear time
with one ... more >>>

We consider Glauber dynamics on finite spin systems.
The mixing time of Glauber dynamics can be bounded
in terms of the influences of sites on each other.
We consider three parameters bounding these influences ---
$\alpha$, the total influence on a site, as studied by Dobrushin;
$\alpha'$, the total influence ... more >>>