Randomized algorithms, once viewed as a tool in computational number theory, have by
now found widespread application. Growth has been fueled by the two major benefits of …

This book is rooted in the thesis that complexity theory is extremely rich in conceptual
content, and that this contents should be explicitly communicated in expositions and courses …

Although the theory of random graphs is one of the youngest branches of graph theory, in
importance it is second to none. It began with some sporadic papers of Erdős in the 1940s …

This beginning graduate textbook describes both recent achievements and classical results
of computational complexity theory. Requiring essentially no background apart from …

Various aspects of the theory of random walks on graphs are surveyed. In particular,
estimates on the important parameters of access time, commute time, cover time and mixing …

But, perhaps, we should start with a few words about graphs in general. They are, of course,
one of the prime objects of study in Discrete Mathematics. However, graphs are among the …

The purpose of this paper is to introduce a new information theory and explore its
appplications. Using modern computational complexity, we study the notion of information …

For simple random walk on a N-vertex graph, the mean time to cover all vertices is at least
cN log (N), where c> 0 is an absolute constant. This is deduced from a more general result …

With advanced computer technology, systems are getting larger to fulfill more complicated
tasks: however, they are also becoming less reliable. Consequently, testing is an …

A basic issue in computer science is the complexity of problems. Computational complexity
measures how much time or memory is needed as a function of the input problem size …