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; k-satisfiability -- 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 non-existence 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 finite-size 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

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

The Probabilistic Method is a lasting legacy of the late Paul Erdos. We give two examples - both problems first formulated by Erdos 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. Erdos showed this may always be done if m< 2(n-1), 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. Erdos and Hanani conjectured such a packing exists (in an important special case of asymptotic designs) and this conjecture was shown by Rodl. We give a simple proof of the speaker that analyzes the random greedy algorithm.

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.

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 (black-box 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 model-checking problem, and has been thoroughly studied for many years, yielding a rich theory, algorithms and tools. Black-box checking, i.e., the verification of properties for systems with an unknown structure, combines elements from model checking, conformance testing and learning.

Conference Site

Cancun is located off the northeast point of Mexico's Yucatan peninsula directly south of New Orleans, Louisiana, with unparalleled natural attractions: powdery white sand and coral beaches, and turquoise Caribbean waters. The average temperature in April is 26.7 C (80.06 F). There are over two hundred restaurants offering Yucatan specialties, Mexican and international food. It is easy to arrange excursions to important archeological Maya sites such as Chichen-Itza, Tulum, and Coba. There are direct flights and good air connections to many cities in Mexico and abroad.

Statistics by Country of Author's Affiliation
Authors*			Papers**
31.0	(29.2%)		14.18	(31.5%)		USA
14.5	(13.7%)		6.73	(15.0%)		France
13.0	(12.3%)		4.33	(9.6%)		Canada
10.0	(9.4%)		3.50	(7.8%)		Brazil
6.0	(5.7%)		2.67	(5.9%)		Germany
5.0	(4.7%)		2.50	(5.6%)		Italy
4.5	(4.2%)		1.92	(4.3%)		Chile
3.5	(3.3%)		2.25	(5.0%)		UK
3.0	(2.8%)		0.75	(1.7%)		Netherlands
3.0	(2.8%)		0.75	(1.7%)		Japan
2.0	(1.9%)		1.00	(2.2%)		Switzerland
2.0	(1.9%)		0.67	(1.5%)		Denmark
1.0	(0.9%)		0.33	(0.7%)		Australia
1.0	(0.9%)		0.33	(0.7%)		Sweden
1.0	(0.9%)		0.25	(0.6%)		Iceland
1.0	(0.9%)		0.50	(1.1%)		Mexico
1.0	(0.9%)		0.50	(1.1%)		Israel
1.0	(0.9%)		0.50	(1.1%)		Austria
1.0	(0.9%)		0.33	(0.7%)		Spain
1.0	(0.9%)		0.50	(1.1%)		Latvia
0.5	(0.5%)		0.50	(1.1%)		Poland

^*  Authors with n affiliations contributes 1/n to each affiliation.
^** Papers with n authors contribute 1/n to each affiliation.

Statistics by Region of Author's Affiliation
Authors*			Papers**
44.0	(41.5%)		18.5	(41.1%)		USA & Canada
41.5	(39.2%)		19.0	(42.2%)		Europe
15.5	(14.6%)		5.9	(13.1%)		Latin-America
4.0	(3.8%)		1.1	(2.4%)		Australia & Asia
1.0	(0.9%)		0.5	(1.1%)		Middle East

^*  Authors with n affiliations contributes 1/n to each affiliation.
^** Papers with n authors contribute 1/n to each affiliation.

Africa

Australia & Asia

Australia	Shparlinski, Igor;
Japan	Iwama, Kazuo; Miyazaki, Shuichi; Morita, Yasufumi;

Europe

UK	Garefalakis, Theodoulos; Kamareddine, Fairouz; Rytter, Wojciech; van Bakel, Steffen;
Italy	Boldi, Paolo; Calamoneri, Tiziana; Dezani-Ciancaglini, Mariangiola; Petreschi, Rossella; Vigna, Sebastiano;
Sweden	Näslund, Mats;
Germany	Alber, Jochen; Köhler, Ekkehard; Lefmann, Hanno; Niedermeier, Rolf; Prisner, Erich; Schmitt, Niels;
Iceland	Halldórsson, Magnús M.;
Switzerland	Anand, R. Sai; Erlebach, Thomas;
Netherlands	Bloo, Roel; Laan, Twan; Nederpelt, Rob;
France	Bassino, Frédérique; Cassez, Franck; Corteel, Sylvie; Dubacq, Jean-Christophe; Finkel, Alain; Frougny, Christiane; Genest, Blaise; Goubault, Eric; Herbreteau, Frédéric; Lombardy, Sylvain; Muscholl, Anca; Roux, Olivier; Sakarovitch, Jacques; Sutre, Grégoire; Terrier, Véronique;
Poland	Rytter, Wojciech;
Austria	Drmota, Michael;
Denmark	Katajainen, Jyrki; Raussen, Martin;
Spain	Gonzalez Vasco, Maria Isabel;
Latvia	Freivalds, Rusins;

Latin-America

Mexico	Chávez, Edgar;
Chile	Hevia, Alejandro; Kiwi, Marcos; Matamala, Martín; Navarro, Gonzalo; Rapaport, Ivan;
Brazil	Bornstein, Claudson F.; Braga, Marília D. V.; Carmo, Renato; Donadelli, Jair; Kohayakawa, Yoshiharu; Laber, Eduardo Sany; Meidanis, Joao; Milidiú, Ruy Luiz; Pessoa, Artur Alves;

Middle East

Israel

Tamir, Tami;

USA & Canada

Canada

Bose, Prosenjit; Corneil, Derek G.; Devroye, Luc; Evans, William S.; Kirkpatrick, David G.; Mendelsohn, Eric; Morin, Pat; Morrison, Jason; Stevens, Brett; Thérien, Denis; Toussaint, Godfried T.; Wang, Qingda;

USA

Abello, James; Arslan, Abdullah N.; Bender, Michael A.; Brönnimann, Hervé; Canfield, Rod; Chen, Xiaomin; Egecioglu, Ömer; F. Dragan, Feodor; Farach-Colton, Martin; Hevia, Alejandro; Hitczenko, Pawel; Iacono, John; Kanj, Iyad; Konjevod, Goran; Muthukrishnan, S.; Oh, Soohyun; Pontelli, Enrico; Ranjan, Desh; Resende, Mauricio G. C.; Richa, Andréa W.; Sahinalp, Cenk; Shachnai, Hadas; Smith, Carl H.; Straubing, Howard; Sudarsky, Sandra; Sutre, Grégoire; Szegedy, Mario; Szpankowski, Wojciech; Tornaría, Gonzalo; Vempala, Santosh;