We will discuss the MCMC method. We will talk about approximately counting the number of satisfying assignments of a DNF formula, approximately counting the number of independent sets in a graph, and (time permitting) the Metropolis Algorithm.
We address the important question of the extent to which random variables and vectors with truncated power tails retain the characteristic features of random variables and vectors with power tails.
Cryptographic primitives often define controlled access to (learning and influencing) information, permitting some kind of access while denying others.
The notion of communication complexity (CC) was introduced by Yao in 1979, who investigated the following problem involving two separated parties (Alice and Bob).
