BibSonomy publications for /user/a_olympia/theSat Aug 18 13:22:24 CEST 2007OctQuantifier elimination for the reals with a predicate for the powers of two2006elimination for of powers predicate quantifier reals the two In 1985, van den Dries showed that the theory of the reals with a predicate
for the integer powers of two admits quantifier elimination in an expanded
language, and is hence decidable. He gave a model-theoretic argument, which
provides no apparent bounds on the complexity of a decision procedure. We
provide a syntactic argument that yields a procedure that is primitive
recursive, although not elementary. In particular, we show that it is possible
to eliminate a single block of existential quantifiers in time $2^0_{O(n)}$,
where $n$ is the length of the input formula and $2_k^x$ denotes $k$-fold
iterated exponentiation.Sat Aug 18 13:22:24 CEST 2007New York, NY, USACommun. ACMJuly7558--565Time, clocks, and the ordering of events in a distributed system211978and clocks distributed events ordering system the time Sat Aug 18 13:22:24 CEST 2007PaperbackMayNexus: Small Worlds and the Groundbreaking Theory of Networks2003and groundbreaking networks of small the theory worlds {As <I>Chaos</I> explained the science of disorder, <I>Nexus</I> reveals the new science of connection and the odd logic of six degrees of separation. <P> "If you ever wanted to know how many links connect you and the Pope, or why when the U.S. Federal Reserve Bank sneezes the global economy catches cold, read this book," writes John L. Casti (Santa Fe Institute). This "cogent and engaging" (<I>Nature</I>) work presents the fundamental principles of the emerging field of "small-worlds" theory\—the idea that a hidden pattern is the key to how networks interact and exchange information, whether that network is the information highway or the firing of neurons in the brain. Mathematicians, physicists, computer scientists, and social scientists are working to decipher this complex organizational system, for it may yield a blueprint of dynamic interactions within our physical as well as social worlds. <P>Highlighting groundbreaking research behind network theory, "Mark Buchanan's graceful, lucid, nontechnical and entertaining prose" (Mark Granovetter) documents the mounting support among various disciplines for the small-worlds idea and demonstrates its practical applications to diverse problems\—from the volatile global economy or the Human Genome Project to the spread of infectious disease or ecological damage. <I>Nexus</I> is an exciting introduction to the hidden geometry that weaves our lives so inextricably together.}Sat Aug 18 13:22:24 CEST 2007JulQuantum Algorithms and the Fourier Transform1997algorithm and fourier quantum the transform The quantum algorithms of Deutsch, Simon and Shor are described in a way
which highlights their dependence on the Fourier transform. The general
construction of the Fourier transform on an Abelian group is outlined and this
provides a unified way of understanding the efficacy of these algorithms.
Finally we describe an efficient quantum factoring algorithm based on a general
formalism of Kitaev and contrast its structure to the ingredients of Shor's
algorithm.Sat Aug 18 13:22:24 CEST 2007JulQuantum Copying: Beyond the No-Cloning Theorem1996beyond copying no-cloning quantum the theorem We analyze to what extent it is possible to copy arbitrary states of a
two-level quantum system. We show that there exists a "universal quantum
copying machine", which approximately copies quantum mechanical states in such
a way that the quality of its output does not depend on the input. We also
examine a machine which combines a unitary transformation with a selective
measurement to produce good copies of states in a neighborhood of a particular
state. We discuss the problem of measurement of the output states.