Jennifer T. Chayes
(Microsoft Research), Phase Transitions in Computer Science
Phase transitions are familiar phenomena in physical systems. But they
also occur in many probabilistic and combinatorial models, including
random versions of some classic problems in theoretical computer
science.
In this talk, I will discuss phase transitions in several systems,
including the random graph — a simple probabilistic model which
undergoes a critical transition from a disordered to an ordered phase;
ksatisfiability — a canonical model in theoretical computer science
which undergoes a transition from solvability to insolvability; and
optimum partitioning — a fundamental problem in combinatorial
optimization, which undergoes a transition from existence to
nonexistence of a perfect optimizer.
Technically, phase transitions only occur in infinite
systems. However, real systems and the systems we simulate are large,
but finite. Hence the question of finitesize scaling: Namely, how
does the transition behavior emerge from the behavior of large, finite
systems? Results on the random graph, satisfiability and optimum
partitioning locate the critical windows of these transitions and
establish interesting features within these windows.
No knowledge of phase transitions will be assumed in this talk
Christos H. Papadimitriou
(U. California, Berkeley), The Internet, the Web, and Algorithms
The Internet and the worldwide web, unlike all other computational
artifacts, were not deliberately designed by a single entity, but
emerged from the complex interactions of many. As a result, they must
be approached very much the same way that cells, galaxies or markets
are studied in other sciences: By speculative (and falsifiable)
theories trying to explain how selfish algorithmic actions could have
led to what we observe. I present several instances of recent work on
this theme, with several collaborators
Joel Spencer
(Courant Institute), Erdős Magic
The Probabilistic Method is a lasting legacy of the late Paul Erdős.
We give two examples — both problems first formulated by
Erdős in the 1960s with new results in the last few years and
both with substantial open questions. Further in both examples we take
a Computer Science vantagepoint, creating a probabilistic algorithm to
create the object (coloring, packing respectively) and showing that
with positive probability the created object has the desired
properties.
Given \(m\) sets each of size \(n\) (with an arbitrary intersection pattern)
we want to color the underlying vertices Red and Blue so that no set
is monochromatic. Erdős showed this may always be done
if \(m< 2(n1)\), we give a recent argument of Srinivasan and
Radhukrishnan that extends this to \(m < c 2n\sqrt{n/\ln n}\). One first
colors randomly and then recolors the blemishes with a clever random
sequential algorithm.
In a universe of size \(N\) we have a family of sets, each of size
\(k\), such that each vertex is in \(D\) sets and any two vertices
have only \(o(D)\) common sets. Asymptotics are for fixed \(k\) with
\(N,D\). We want an asymptotic packing, a subfamily of \(N/k\)
disjoint sets. Erdős and Hanani conjectured such a packing exists
(in an important special case of asymptotic designs) and this
conjecture was shown by Rödl. We give a simple proof of the
speaker that analyzes the random greedy algorithm.
Jorge Urrutia
(UNAM), Open Problems in Computational Geometry
In this paper we present a collection of problems which have defied
solution for some time. We hope that this paper will stimulate renewed
interest in these problems, leading to solutions to at least some of
them.
Umesh V. Vazirani
(U. California, Berkeley), Quantum Algorithms
Quantum computers are the only model of computing to credibly violate
the modified ChurchTuring thesis, which states that any reasonable
model of computation can be simulated by a probabilistic Turing
Machine with at most polynomial factor simulation overhead. This is
dramatically demonstrated by Shor’s polynomial time algorithms for
factorization and discrete logarithms [13]. Shor’s algorithm, as well as the earlier
algorithm due to Simon [12] can both be
cast into the general framework of the hidden subgroup problem (see
for example [10]). Two recent
papers [11], [9] study how well this framework extends to
solving the hidden subgroup problem for nonabelian groups (which
includes the graph isomorphism problem).
Grigni, M., Schulman, S., Vazirani, M., Vazirani, U.. Quantum
Mechnical Algorithms for the Non beli n Hidden Subgroup Problem.
In: Proceedings of the Thirtythird Annual ACM Symposium on the Theory
of Computing Crete, Greece, 2001.
L. Hales and S. Hallgren. Quantum Fourier S mpling Simplified. In:
Proceedings of the Thirtyfirst Annual ACM Symposium on the Theory of
Computing pages 330–338,Atlanta,Georgia, 1–4 May 1999.
Hallgren, S., Russell, A., TShma, A.. Normal subgroup reconstruction
and quantum computation using group representations. In: Proceedings
of the 32nd Annual ACM Symposium on Theory of Computing 627–635,
2000.
D. Simon. On the power of quantum computation. In: Proc. 35th
Symposium on Foundations of Computer Science (FOCS), 1994.
Shor P. W.. Polynomialtime algorithms for prime factorization and
discrete alogarithms on a quantum computer. SIAM J. Comp., 26 No.5, pp
1484–1509, October 1997.
Mihalis Yannakakis
(Avaya Laboratories), Testing and Checking of Finite State Systems
Finite state machines have been used to model a wide variety of
systems, including sequential circuits, communication protocols, and
other types of reactive systems, i.e., systems that interact with
their environment. In testing problems we are given a system, which we
may test by providing inputs and observing the outputs produced.
The goal is to design test sequences so that we can deduce desired
information about the given system under test, such as whether it
implements correctly a given specification machine (conformance
testing), or whether it satisfies given requirement properties
(blackbox checking).
In this talk we will review some of the theory and algorithms on basic
testing problems for systems modeled by different types of finite
state machines. Conformance testing of deterministic machines has been
investigated for a long time; we will discuss various efficient
methods. Testing of nondeterministic and probabilistic machines is
related to games with incomplete information and to partially
observable Markov decisions processes.
The verification of properties for finite state systems with a known
structure (i.e., “white box” checking) is known as the
modelchecking problem, and has been thoroughly studied for many
years, yielding a rich theory, algorithms and tools. Blackbox
checking, i.e., the verification of properties for systems with an
unknown structure, combines elements from model checking, conformance
testing and learning.
