Computational complexity: a conceptual perspective

O Goldreich - ACM Sigact News, 2008 - dl.acm.org
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 …

Quantum walk based search algorithms

M Santha - International Conference on Theory and Applications of …, 2008 - Springer
In this survey paper we give an intuitive treatment of the discrete time quantization of
classical Markov chains. Grover search and the quantum walk based search algorithms of …

[图书][B] Random graphs

B Bollobás, B Bollobás - 1998 - Springer
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 …

[图书][B] Computational complexity: a modern approach

S Arora, B Barak - 2009 - books.google.com
This beginning graduate textbook describes both recent achievements and classical results
of computational complexity theory. Requiring essentially no background apart from …

[图书][B] Randomized Algor ithms

R Motwani - 1995 - books.google.com
For many applications a randomized algorithm is either the simplest algorithm available, or
the fastest, or both. This tutorial presents the basic concepts in the design and analysis of …

[PDF][PDF] Random walks on graphs

L Lovász - Combinatorics, Paul erdos is eighty, 1993 - cs.yale.edu
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 …

Lower bounds for covering times for reversible Markov chains and random walks on graphs

DJ Aldous - Journal of Theoretical Probability, 1989 - Springer
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 …

Expander graphs and their applications

S Hoory, N Linial, A Wigderson - Bulletin of the American Mathematical …, 2006 - ams.org
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 …

Theory and application of trapdoor functions

AC Yao - 23rd Annual Symposium on Foundations of …, 1982 - ieeexplore.ieee.org
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 …

Principles and methods of testing finite state machines-a survey

D Lee, M Yannakakis - Proceedings of the IEEE, 1996 - ieeexplore.ieee.org
With advanced computer technology, systems are getting larger to fulfill more complicated
tasks: however, they are also becoming less reliable. Consequently, testing is an …