Martin Dyer, Leslie Ann Goldberg, Mark Jerrum

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 >>>

Oded Goldreich

We highlight a common theme in four relatively recent works

that establish remarkable results by an iterative approach.

Starting from a trivial construct,

each of these works applies an ingeniously designed

sequence of iterations that yields the desired result,

which is highly non-trivial. Furthermore, in each iteration,

more >>>

Ryan O'Donnell, A. C. Cem Say

We consider computation in the presence of closed timelike curves (CTCs), as proposed by Deutsch. We focus on the case in which the CTCs carry classical bits (as opposed to qubits). Previously, Aaronson and Watrous showed that computation with polynomially many CTC bits is equivalent in power to PSPACE. On ... more >>>

Venkatesan Guruswami, Vinayak Kumar

Random walks on expanders are a central and versatile tool in pseudorandomness. If an arbitrary half of the vertices of an expander graph are marked, known Chernoff bounds for expander walks imply that the number $M$ of marked vertices visited in a long $n$-step random walk strongly concentrates around the ... more >>>