We prove a central limit theorem for the fluctuations of the size of the giant component in a random graph with small but supercritical edge probability.
This is joint work with D. Barraez and W. Fernandez de la Vega.
The previous talk (Buhrman's) showed that communication via qubits can drastically reduce the communication cost in the setting of communication complexity, compared to classical communication. Here we show that use of pre-established quantum entanglement can be used to solve problems that would otherwise require communication without any exchange of information at all, be it classical or quantum. This is especially interesting in the light of a theorem that says that entanglement cannot be used to communicate information. In the second half of the talk, we turn the table around and investigate the complexity of simulating entanglement with classical communication. It is shown that any observable effect of sharing one bit of entanglement can be simulated exactly by the exchange of a small number of classical bits.
This is joint work with Richard Cleve and Alain Tapp.
The new paradigm of quantum computing makes use of quantum mechanical effects to speed up computation. It has been shown by Shor that factorization of a number M can be done in polynomial time on a quantum computer. In comparison the best known classical algorithms take close to exponential time. Whereas classical computers operate on bits, quantum algorithms make essential use of bits in superposition: qubits. Qubits can--just as classical bits--be used to code information. A fundamental result in quantum information theory by Kholevo (1973) shows that k qubits can not contain more information than k classical bits. Nevertheless it can be shown that communication via qubits can drastically reduce the communication cost in the setting of communication complexity. We will give an overview of results obtained in this area.
We consider the set of all graph homomorphism from a graph G to a fixed graph H, where G is a graph of constant maximum degree. (These are also called H-colourings.) Since exact counting is known to be #P-Complete for most H, we consider approximate counting using the Monte Carlo Markov chain (MCMC) method. We show that, for "most" (in a sense which will be defined) graphs H, and large enough constant maximum degree, all Markov chains in a very large class will have mixing times exponential in the size of G in the worst case. The approach is closely related to previous work of the speaker, Frieze and Jerrum on counting independent sets.
This is joint work with Colin Cooper and Alan Frieze.
This is joint work with Paul Beame.
Digital trees, also known as tries, are a flexible data structure that can implement dictionaries. From the probabilistic standpoint, they lead to the abstract trie process that may be defined as follows: start from a collection of individuals and split them recursively into subgroups by indepdenent coin flips, until all individuals have been separated from each other. Basic analyses involve an interesting combination of generating functions, difference equations, and Mellin transforms. The talk will illustrate the rôle of the trie process in the design and analysis of algorithms. Applications are to be found in such diverse areas as dynamic and extensible hashing, communication protocols, probabilistic estimation algorithms, geometric data retrieval, text processing, data compression, polynomial factorization methods, and even the metric theory of continued fractions.
The problem of counting homomorphisms from a general graph G to a fixed graph H is a natural generalisation of graph colouring, with important applications in statistical physics. Hell and Nesetril showed that the decision corresponding to a graph H is NP-complete unless H has a loop or is bipartite; otherwise it is in P. Martin Dyer and I have found a characterisation of counting problems for graph homomorphisms. We found that counting is #P-complete unless every connected component of H is an isolated vertex without a loop, a complete graph with all loops present, or a complete unlooped bipartite graph; otherwise it is in P. In this talk I sketch the proof of our result and describe some consequences.
This is joint work with Martin Dyer.
Eberly and Giesbrecht proposed a Monte Carlo algorithm
for finding a complete orthogonal system of primitive
idempotents of a subalgebra 
given by
m matrices which generate A as an algebra. The number of
arithmetical operations required by the algorithm is essentially
the cost of performing 
matrix multiplications
in Mn(Fq). We show how to use this result to compute
the main structural invariants of A such as the radical
and a Wedderburn complement in time similar to the cost of
matrix multiplications in Mn(Fq).
We investigate the computational complexity of counting independent
(a.k.a. stable) sets in a graph of maximum degree at most 
.
A range of phenomena may be observed as increases. For 
,the number of independent sets can obviously be computed exactly in
polynomial time. For 
, the exact version is #P-complete,
but approximation--in the sense of fully polynomial randomised
approximation scheme or FPRAS--is possible at least for 
.For 
, a wide class of algorithms is ruled out by
the existence of something akin to a phase transition. Finally, for
, there can be no FPRAS of any kind unless
. This last result sharpens an observation
of Luby and Vigoda relating approximability of optimisation and counting
problems.
This is joint work with Martin Dyer (Leeds) and Alan Frieze (CMU).
We prove that the problem MIN-SBR of sorting a permutation by the minimum number of reversals is hard to approximate (NP-hard by randomized reductions) within any constant factor less than some explicit threshold. This excludes an existence of a PTAS for this problem, thus settling a question which was open for some time. The proof method uses certain new explicit approximation hardness techniques for bounded dependency, and bounded degree optimization problems. The MIN-SBR problem has been motivated and extensively studied in computational molecular biology, but existence of PTASs remained an open issue. This problem connects also to the well known problem of sorting by prefix reversals (or, so called, pancakes sorting). Our nonapproximability result for MIN-SBR is also in sharp contrast to its signed version for which efficient exact algorithms have been designed recently.
This is joint work with P. Berman.
Blum, Shub and Smale pioneered a complexity theory of computation over the real numbers (and other rings), with particular emphasis on P and NP. In this talk I will present analogues of well-known randomized complexity classes such as BPP, MA, AM, over the real and complex numbers. The similarities and differences with the classical (boolean) case will be highlighted, and some applications to the complexity of "concrete" problems of real or complex geometry will be presented.
A function f is self-reducible if it can be computed in polynomial time given an oracle for f. In a random-self-reduction the distribution of each query must be independent of the input. Random-self-reductions have many applications, including cryptographic protocols, PCPs, average-case complexity, and program checking. A simpler model of randomized self-reducibility is coherence, in which the only condition on the queries is that the input may not be among the queries. We show that there is a function which is random-self-reducible with 2 rounds of queries, but which is not coherent, even with polynomial advice, when the queries must be made in a single round.
This is joint work with L. Babai.
In TSP with neighborhoods (TSPN) we are given a collection X of
k polygonal regions, called neighborhoods, with totally n vertices, and we seek th
e shortest
tour that visits each neighborhood. The Euclidean TSP is a special case of the TSPN problem,
so TSPN is also NP-hard. In this paper we present a simple and fast algorithm that, given a
start point, computes a TSPN tour of length 
times the optimum in time 
. When no start point is given we show how to compute a ``good'' start point in time
, hence we obtain a logarithmic approximation algorithm that runs in time .We also present an algorithm which performs at least one of the following two tasks (which o
f these tasks is performed depends on the given input):
(1) It outputs in time 
a TSPN tour of length times the optimum.
(2) It outputs a TSPN tour of length less than 
times the optimum in cubic t
ime, where 
is an arbitrary real constant given as an optional parameter.
The results above are significant improvements, since the best previously
known logarithmic approximation algorithm runs in 
time in
the worst case.
This is joint work with Joachim Gudmundsson.
We will review the relaxational properties (spectral gap, logarithmic Sobolev constant, bottlenecks) for continuos time Metropolis spin flip dynamics and Kawasaki spin exchange dynamics for lattice random Gibbsian fields both in absence of phase transition and in the pahse transition regime. We will point out also some interesting open problems.
Consider a complete graph Kn with random independent edge
lengths, each uniformly distributed on (0,1).
Let Ln denote the random length of a minimum spanning tree.
It is well known that 
as 
, where
.
We are interested in the probability of large deviations, that is, in the probab
ility that 
where 
.There have been several results concerning this: we at last can show that this p
robability dies exponentially with n. We sketch how to do this using
Talagrand's inequality.
We will discuss quantum algorithms for counting the number of
solutions, t, to f(x) = 1 where f maps 
to
. We assume that we have a quantum black-box for
evaluating f.
These algorithms make use of a quantum eigenvalue estimation
algorithm to output estimates 
of t.
With 
applications of f, we get 
with probability at least 2/3.
With 
applications of f, we get 
with probability at least 2/3.
With 
applications of f, we get
with probability at least 2/3.
This is joint work with G. Brassard, P. Hoyer, and A. Tapp.
This is joint work with Omer Reingold.
We determine the expected height Hn of a random bianry search tree to within O(1). We also show that Var(Hn) is O(1).
We develop a general framework for the analysis of algorithms of a broad Euclidean type. The average-case complexity of an algorithm is seen to be related to the analytic behaviour in the complex plane of the set of elementary transformations determined by the algorithms. The methods rely on properties of transfer operators suitably adapted from dynamical systems theory. As a consequence, we obtain precise average-case analyses of four algorithms for evaluating the Jacobi symbol of computational number theory fame, thereby solving conjectures of Bach and Shallit. These methods provide a unifying framework for the analysis of an entire class of gcd-like algorithms together with new results regarding the probable behaviour of their cost functions.
In the black-box model of computation, an N-bit input X is given as a black-box which gives the ith bit of the input when queried on i. Our aim is to compute some function f(X) using as few queries as possible. For classical computers, this query complexity is known as the decision tree complexity of f and has been well studied. We give an overview of recent results for query complexity in the setting of quantum computation. These results include (1) a polynomial relation between quantum and classical complexity for all total f, (2) a tight characterization of the quantum complexity of all symmetric functions, (3) tight bounds for small-error quantum search, (4) some recent quantum-classical gaps in the zero-error (Las Vegas) setting, and (5) some recent gaps for average-case complexity.
This is joint work with R. Beals, H. Buhrman, R. Cleve, M. Mosca, Ch. Zalka.
This document was generated using the LaTeX2HTML translator Version 97.1 (release) (July 13th, 1997)
Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html -split 0 abst.tex.
The translation was initiated by Miklos Santha on 5/14/1999