Quantum random walks - an introductory overview <s> IV. RANDOM WALKS IN COMPUTER SCIENCE <s> We present a randomised polynomial time algorithm for approximating the volume of a convex body K in n -dimensional Euclidean space. The proof of correctness of the algorithm relies on recent theory of rapidly mixing Markov chains and isoperimetric inequalities to show that a certain random walk can be used to sample nearly uniformly from within K . <s> BIB001 </s> Quantum random walks - an introductory overview <s> IV. RANDOM WALKS IN COMPUTER SCIENCE <s> Once we have developed an algorithm (q.v.) for solving a computational problem and analyzed its worst-case time requirements as a function of the size of its input (most usefully, in terms of the O-notation; see ALGORITHMS, ANALYSIS OF), it is inevitable to ask the question: "Can we do better?" In a typical problem, we may be able to devise new algorithms for the problem that are more and more efficient. But eventually, this line of research often seems to hit an invisible barrier, a level beyond whch improvements are very difficult, seemingly impossible, to come by. After many unsuccessful attempts, algorithm designers inevitably start to wonder if there is something inherent in the problem that makes it impossible to devise algorithms that are faster than the current one. They may try to develop mathematical techniques for proving formally that there can be no algorithm for the given problem which runs faster than the current one. Such a proof would be valuable, as it would suggest that it is futile to keep working on improved algorithms for this problem, that further improvements are certainly impossible. The realm of mathematical models and techniques for establishing such impossibility proofs is called computational complexity. <s> BIB002 </s> Quantum random walks - an introductory overview <s> IV. RANDOM WALKS IN COMPUTER SCIENCE <s> For many applications, a randomized algorithm is either the simplest or the fastest algorithm available, and sometimes both. This book introduces the basic concepts in the design and analysis of randomized algorithms. The first part of the text presents basic tools such as probability theory and probabilistic analysis that are frequently used in algorithmic applications. Algorithmic examples are also given to illustrate the use of each tool in a concrete setting. In the second part of the book, each chapter focuses on an important area to which randomized algorithms can be applied, providing a comprehensive and representative selection of the algorithms that might be used in each of these areas. Although written primarily as a text for advanced undergraduates and graduate students, this book should also prove invaluable as a reference for professionals and researchers. <s> BIB003 </s> Quantum random walks - an introductory overview <s> IV. RANDOM WALKS IN COMPUTER SCIENCE <s> We present a simple probabilistic algorithm for solving k-SAT and more generally, for solving constraint satisfaction problems (CSP). The algorithm follows a simple local search paradigm (S. Minton et al., 1992): randomly guess an initial assignment and then, guided by those clauses (constraints) that are not satisfied, by successively choosing a random literal from such a clause and flipping the corresponding bit, try to find a satisfying assignment. If no satisfying assignment is found after O(n) steps, start over again. Our analysis shows that for any satisfiable k-CNF-formula with n variables this process has to be repeated only t times, on the average, to find a satisfying assignment, where t is within a polynomial factor of (2(1-1/k))/sup n/. This is the fastest (and also the simplest) algorithm for 3-SAT known up to date. We consider also the more general case of a CSP with n variables, each variable taking at most d values, and constraints of order l, and analyze the complexity of the corresponding (generalized) algorith m. It turns out that any CSP can be solved with complexity at most (d/spl middot/(1-1/l)+/spl epsiv/)/sup n/. <s> BIB004 </s> Quantum random walks - an introductory overview <s> IV. RANDOM WALKS IN COMPUTER SCIENCE <s> We present a fully-polynomial randomized approximation scheme for computing the permanent of an arbitrary matrix with non-negative entries. <s> BIB005
Classical random walks form one of the cornerstones of theoretical computer science BIB002 BIB003 . As algorithmic tools, they have been applied to a variety of central problems  , such as estimation of the volume of a convex body BIB001 , approximation of the permanent of a matrix BIB005 , and discovery of satisfying assignments for Boolean formulae BIB004 . They provide a general paradigm for sampling and exploring an exponentially large set of combinatorial structures (such as matchings in a graph), by using a sequence of simple, local transitions  . The behavior of many an algorithm that use random walks depends on quantities like its mixing time (the time it takes the walk to approach its stationary distribution; this is important if we wish to sample from a set of combinatorial structures according to some distribution cf. the Markov Chain Monte Carlo Method  ) or its expected hitting times between two vertices of the underlying graph. We will illustrate the latter point with two simple examples before we give the more formal definitions.