Français

Theme Year 2002-2003

Math in Computer Science

Index Summer School International Annual Conferences Courses Aisenstadt Chairs Workshops Student Support Concentration Periods Seminars ORGANIZING COMMITTE

 

 

 

 

 

 

 

 

 

 

Introduction

The field of computation, formally born only last century but with roots that stretch back to Euclid, is now a mathematical discipline in its own right, with solid theoretical foundations on which are based its spectacular development. The CRM special year in the mathematics of computer science proposes to explore in depth a significant spectrum of the many sub-areas that are core foundational material for modern computer science, that exhibit significant and new mathematical content, and that have indeed influenced the development of mathematics.

Mathematically, the areas with the earliest influence on computer science were logic and discrete mathematics. Since then, the theoretical foundations of computer science have blossomed, and ideas from the area (like effectiveness, complexity and tractability) have grown to occupy an ever more important role in mathematics. More recently, a recurrent theme in many of the domains examined are probabilistic methods; these have permeated the whole of computer science, and so particular emphasis will be placed on the utilisation of these techniques, both in theoretical areas and in more applied ones such as simulation and machine learning.

SUMMER SCHOOL

•Organizer: Gilles Brassard (Montréal)

Classical information theory is firmly rooted in the classical physics of Newton and Einstein. But the world is quantum mechanical. This has prevented us from tapping the full potential of physical reality for information processing purposes. For instance, quantum mechanics allows for unbreakable cryptographic codes and such a high level of parallelism in computation that a classical computer the size of the universe would be left behind. The goal of this school is to make the field of quantum information processing accessible to a general audience of mathematicians and computer scientists who have little or no familiarity with quantum mechanics.

•Lecturers: Andris Ambainis, Charles Bennett, Gilles Brassard, Harry Buhrman, Richard Cleve, Claude Crépeau, Daniel Gottesman, Nicolas Gisin, Peter Høyer, Raymond Laflamme, Alain Tapp et John Watrous.

For more information

AISENSTADT CHAIR LECTURE SERIES

The holders of the Aisenstadt chair for the year will be László Lovász (Microsoft Research) and Endre Szemerédi (Rutgers).

CONCENTRATION PERIODS

Complexity theory, analysis of algorithms
May-June 2002

•Organizers: Pierre McKenzie (Montréal), Denis Thérien (McGill)

In May 2002, the CRM will host two of the most important international conferences in theoretical Computer Science, namely the ACM Symposium on Theory of Computing and the IEEE Conference on Computational Complexity. In addition, there will be several 1-week workshops on topics that lie at the core of the theory of computing. Each workshop will bring together a number of leading scientists who will present both expository lectures and state-of-the-art research.

May 13-17, 2002: Lecture series on branching programs, by Ingo Wegener
(Dortmund)

May 19-21, 2002: ACM Symposium on Theory of Computing (STOC)

May 21-24, 2002: IEEE Conference on Computational Complexity

May 27-31, 2002: Randomness in Branching program

Random techniques play an important role in computer science, through algorithms which give an efficient solution to problems for which no good deterministic solution is known, or through the probabilistic study of complexity. A week will be devoted to this theme, starting with the links between probabilistic methods and branching programs.

June 3-7, 2002: Verification and model-checking

In the past ten years, theoretical work in the area of verification has started to bear fruit. The workshop will cover the major areas of this development, in particular those linked to model- checking.

June 10-14, 2002: Descriptive complexity

An area that has come to the fore in recent years, descriptive complexity gives a tool which complements more classical approaches to complexity theory. After a survey of the area, the workshop will concentrate on links between branching programs and algebraic structures.

Invited speakers for the one-week workshops include: D. Barrington, P. Beame, P.L.
Crescenzi, R. Gavalda, N. Immerman, K.J. Lange, P. Pudlak, A. Razborov, M. Sachs, R. Raz, P. Schnoebelen.

Quantum Foundations in the Light of Quantum Information
October 13 - November 2, 2002

•Organizers: Gilles Brassard (Montréal), Christopher A. Fuchs (Bells Labs, Lucent Technologies)

Rolf Landauer's best-known aphorism is "information is physical". This workshop is centred around the belief that "physics is informational"! Our long-term purpose is to reformulate the foundations of quantum mechanics in the light of quantum information theory. Rather than being counterintuitive, could it be that quantum mechanics was inevitable for information to behave as we understand it now?

For instance, what can we derive from the fact that unconditionally secure cryptographic key distribution is possible but bit commitment is not?

Upon invitation only.

Guests: H. Barnum, G. Brassard, H. Briegel, J. Bub, A. Cabello, C. Caves, R. Cleve, C. Fuchs, N. Gisin, D. Greenberger, L. Hardy, P. Hayden, A. Holevo, R. Jozsa, A. Kent, D. Mayers, D. Mermin, T. Mor, M. Nielsen, A. Peres, I. Pitowsky, R. Schack, B. Schumacher, J. Smolin, R. Spekkens, A. Steane), D. Wallace, W. Wootters, A. Zajonc.

Combinatorics, probability and algorithms
May 2003

•Organizers: David Avis (McGill), Luc Devroye (McGill), Bruce A. Reed (McGill)

Leave nothing to chance. This cliché embodies the common belief that randomness has no place in well-planned methodologies, every i should be dotted and every t should be crossed. In discrete mathematics, at least, nothing could be further from the truth. Introducing random choices into algorithms can improve their performance. The application of probabilistic tools has led to the resolution of combinatorial problems which have resisted attack for decades.

A month-long concentration period will take place around this general theme. Lecturers at the school will introduce participants to a number of weapons, mostly from the probabilistic arsenal, and their applications in combinatorics and in the study of algorithms. We anticipate a significant amount of collaboration between participants at the school during the month.

There will be 5 hour mini-courses given by: V. Chvatal (Rutgers), A. Frieze (Carnegie-Mellon), C. McDiarmid (Oxford), M. Molloy (Toronto), J. Pach (City College New York and Hungarian Academy of Sciences), as well as some lectures by N. Alon (Technion). The session will be combined with the Aisenstadt lectures of L. Lov‡sz (Microsoft Research) and E. Szemeredi (Rutgers).

For more information

INTERNATIONAL ANNUAL MEETINGS

ACM Symposium on Theory of Computing (STOC)
May 19-21, 2002

IEEE Conference on Computational Complexity
May 21-24, 2002

•Organizers: Pierre McKenzie (Montréal), Denis Thérien (McGill)

These two conferences are part of the concentration period on Complexity theory, analysis of algorithms.

•Organizer: Prakash Panangaden (McGill)

Conferences and workshops in this series, held annually since 1985, aim to provide a forum for researchers in all areas surrounding semantics to present their latest research results, and to improve communication and interactions between mathematicians and computer scientists who work in these areas. The areas of relevance include category theory, domain theory, logic and topology on the mathematics side, and type theory, semantics, and the design and implementation of programming languages on the computer science side.

For further information

IEEE Symposium on Logic in Computer Science (LICS)
June 20-26, 2003

•Organizers: Amy P. Felty (Ottawa), Philip Scott (Ottawa)

To be held at the University of Ottawa in 2003, the IEEE Symposium on Logic in Computer Science (LICS) is an annual international forum on theoretical and practical topics in computer science that relate to logic in a broad sense. The CRM will be sponsoring four satellite workshops for this conference.

For more information

WORKSHOPS

Random number generation and highly uniform point sets
June 17-28, 2002

•Organizer: Pierre L'Ecuyer (Montréal)

This workshop will bring together the world leaders in the theoretical and practical aspects of random number generation by computer and the design of highly-uniform point sets for quasi- Monte Carlo integration. The general theme is the development of practical random number generation software for various classes of applications, such as simulation, statistics, numerical analysis, computer games, lotteries, cryptology, etc. In simulation, highly-uniform (or low- discrepancy) point sets can often advantageously replace the traditional random numbers. Their construction and analysis can be based on ideas and tools that are very similar to those used for random number generators and we want to strengthen this connection.

Invited speakers include: C. Crépeau, L. Devroye, M. Evans, B.L. Fox, M. Fushimi, J. Gentle, P. Hellekalek, S. Heinrich, W. Hormann, A. Keller, G. Larcher, P. L'Ecuyer, J. Leydold, C. Lemieux, M. Mascagni, M. Matsumoto, S. Ninomiya, T.Nishimura, A.B. Owen, G. Pirsic, W. Schmid, I. Sloan, S. Tezuka, H. Wozniakowsski, C. Xing.

Information and registration

Mathematical Models and Techniques for Analysing
Systems
September 30 - October 4, 2002

•Organizer: Prakash Panangaden (McGill)

The analysis of systems has both diversified and deepened tremendously in the last few years. In terms of diversification, systems of interest now include stochastic systems, real-time systems and hybrid systems, that is, systems where the state space is partly discrete and partly continuous. Applications include flight management systems for aircraft, process control systems, telecommunication systems and battle management systems. In all of these one has to deal with continuous time evolution and usually with probabilistic aspects as well. Perhaps the most successful mathematical technique for dealing with these problems - now almost 20 years old - is model checking. This is now being extended to probabilistic systems and the theory has advanced to the point where tools have been designed and built. In terms of the general mathematical theory co-inductive techniques, like bisimulation, have proved their value repeatedly.

The workshop would have two main speakers, who will each give five lectures: Prof. Marta Kwiatkowska, U. Birmingham "Probabilistic Model Checking" and Dr. Jan Rutten, CWI Amsterdam "Coinductive Calculus".

Other invited speakers include: R. Alur, P. Caines, R. Jagadeesan, D.Precup.

For further information and registration

Finite Model Theory
March 2-9, 2003

•Organizer: Denis Thérien (McGill)

This workshop will focus on the expressive power of logics and on the deep relationship between logic and computational complexity. The principal speaker will be Phokion Kolaitis (U.C. Santa Cruz). The workshop will be held at the Bellairs Research Institute of McGill University.

For more information

Semigroups and Automata
March 17-21, 2003

•Organizer: Denis Thérien (McGill)

This workshop will discuss recent developments in the theory of automata and semigroups, in particular some dealing with long-standing open problems such as decidability of the dot-depth hierarchy and decidability of Rhodes complexity.

For further information

Cryptographic reduction of quantum and classical protocols
May 20-23, 2003

•Organizer: Claude Crépeau (McGill)

Cryptographic protocols have been studied for two decades in the classical scenario under various computational assumptions. Such protocols as Bit Commitment, Oblivious Transfer and Multiparty Computations have been implemented and reduced to each other. Over the last few years, similar results are now achieved in the context of adversaries equipped with quantum computers. This workshop will bring together specialists of both classical and quantum cryptographic protocols who will present the state of the art in this fascinating area of research.

Invited speakers include: D. Beaver, C. Cachin (*), R. Cramer, C. Crépeau, I. Damgaard, P. Dumais, D. Gottesman, J. van de Graaf, R. Impagliazzo (*), J. Kilian, D. Mayers, M. Naor (*), S. Rudich (*), L. Salvail, A. Smith, A. Tapp, S. Wolf, M. Yung.

(*) to be confirmed

For more information

Advances in Machine Learning
June 8-11, 2003

•Organizers: Yoshua Bengio (Montréal), Bal‡zs Kégl (Montréal), Doina Precup (McGill)

Probabilities are at the core of recent advances in the theory and practice of machine learning algorithms. The workshop will focus on three broad areas where these advances are crucial: statistical learning theory, learning algorithms, and reinforcement learning. The workshop will therefore bring together experts from each of these three important domains. Among the sub -topics that will be covered, we note: variational methods, graphical models, the curse of dimensionality, empirical methods to take advantage of theories of generalization error, and some of the applications of these new methods.

Invited speakers include: P. Bartlett, A. Barto, N.de Freitas, P. Frasconi, G. Hinton, M. Jordan, V. Koltchinskii, Y. Le Cun, M. Littman, G. Lugosi, S. Mahadevan, S. Roweis, B. Scholkopf, D. Schuurmans, S Singh, R. Sutton.

For more information

SEMINARS

There will be a year-long seminar on the mathematics of computing.

COURSES

The Montreal universities offer a variety of courses in the area of the year. The list can be consulted at :
www.iro.umontreal.ca/cours/
www.cs.mcgill.ca/acadpages/grad/course-grad.html
www.cs.concordia.ca/programs/grad/courses.
www.info.uqam.ca/dinfo/coursdepframe.html

STUDENT SUPPORT

Support is available for graduate students and post-doctoral fellows attending the various events. A request for funds must be accompanied by a reference letter from the student's research director and a C.V. Please send your application for financial aid to:

Scientific Activities
Centre de recherches mathématiques
Universite de Montréal
C.P. 6128, Succursale Centre-ville,
Montréal (Québec)
CANADA H3C 3J7

Fax: (514) 343-2254

E-mail: activites@CRM.UMontreal.CA

David Avis (McGill), Yoshua Bengio (Montréal), Gilles Brassard (Montréal), Luc Devroye (McGill), Pierre L'Ecuyer (Montréal), Pierre McKenzie (Montréal), Prakash Panangaden (McGill), Bruce Reed (McGill), Denis Thérien (McGill).

Those wishing to participate in the above activities are invited to write to:

Louis Pelletier
Centre de recherches mathématiques (CRM)
Université de Montréal
C.P. 6128, Succ. Centre-ville
Montréal (Québec)
CANADA H3C3J7

E-mail: ACTIVITES@CRM.UMontreal.CA

Last modifications: May 23, 2002
Webmaster