Probabilistic Methods in Computer Science (MCS)

Prof. Eli Upfal
Brown University (USA)

Summary:
Probability, randomness and statistics play a key role in modern computer science. From the highly theoretical notion of probabilistic theorem proving, to the very practical applications of cryptography and web search ranking, sophisticated probabilistic techniques have been developed in the last two decades for a broad range of challenging computing applications. This course introduces the basic probabilistic techniques used in the design of randomized algorithms and in probabilistic analysis of algorithms. The course covers the basic probability theory required for working with these techniques, and demonstrates their use in various computing applications. Topics to be covered in course include:

  • Randomized fingerprinting - verifying polynomial identities
  • Randomized algorithms vs. probabilistic analysis of algorithms
  • Moments and deviations - randomized selection algorithm
  • Chernoff and Hoeffding's tail bounds - parallel packet routing
  • Balls bins and random graphs
  • The coupon collector paradigm: hashing, Bloom filter, Hamiltonian cycles in random graphs
  • The probabilistic method - from existential proofs to explicit constructions
  • Markov chains - randomized 2-sat and connectivity algorithms
  • Continuous distribution and the Poisson process - basic queuing processes
  • Algorithmic applications of information theory

Methods for Image Reconstructions with Applications in Medicine and Astronomy (MIR)

Prof. Michele Piana
University of Verona (Italy)

Summary:
The goal of this course is to provide the basic computational tools for image reconstruction. In particular, in the first part the modeling of the image reconstruction problem will be addressed within the framework of the linear inverse problems theory. The core of the course is in the second part, which will discuss the main methodological approaches to image reconstruction from both a deterministic and a probabilistic viewpoint. The final part will offer two applications, one in functional medical imaging and one in solar imaging from on-orbit satellites. The outline of the course is as follows:

Part I: The image reconstruction problem

  1. Image processing and image reconstruction
  2. Models for blurring
  3. Inverse problems: general theory

Part II: Reconstruction methods

  1. Regularization theory for linear problems
  2. Tikhonov method
  3. Iterative methods
  4. A priori information and constraints
  5. The optimal choice of the regularization parameter
  6. Bayesian approaches

Part III: Applications

  1. An application in medical imaging: magnetoencephalography (MEG)
  2. An application in astronomy: solar imaging with visibilities
Slides of lectures:
  1. Part 1
  2. Part 2
  3. Part 3
  4. Part 4

Probabilistic Model Checking (PMC)

Prof. Marta Kwiatkowska
University of Birmingham (UK)

Summary:
Probabilistic model checking is a formal technique for the analysis of systems which exhibit stochastic behaviour. Randomisation is frequently used as a symmetry breaker in distributed coordination, security and communication protocols. Stochastic modelling is also important in perfromability, dependability and fault-tolerance, and more recently in the analysis of biological processes. Probabilistic model checking enables a range of quantitative analyses of probabilistic models against specifications such as "the worst-case probability of intrusion within 10 seconds", "the minimum expected power consumption over all possible schedulings", or "the expected time until a protein degrades".

This course will give an overview of the area of probabilistic model checking, covering both the theoretical foundations as well as the practical aspects of probabilistic model checking. The lectures will include four types of models, all variants of Markov chains, specification notations, and techniques available for their automatic verification. The course will be based on the state-of-the-art probabilistic model checker PRISM and will be amply illustrated by case studies that have been modelled and analysed in PRISM, such as the Bluetooth device discovery, Zeroconf link-local addressing, power management, probabilistic contract signing, and biological signalling pathways. Participants may find it useful to refer to:

  1. PRISM website for software to download, manual, publications, case studies and PRISM bibliography
  2. Online PRISM tutorial
  3. J. Rutten, M. Kwiatkowska, G. Norman and D. Parker. Mathematical Techniques for Analyzing Concurrent and Probabilistic Systems. Volume 23 of CRM Monograph Series. American Mathematical Society. P. Panangaden and F. van Breugel (eds.) 2004.
  4. Lecture handouts and slides.

Foundations of XML Data Manipulation (XML)

Prof. Giorgio Ghelli
University of Pisa (Italy)

Summary:
In this course we present the state of the art of XML Data manipulation, presenting both technology and foundations. The course is structured as follows:

  1. models for XML and semistructured data
  2. languages for XML manipulation
  3. structural description of XML data: types, logics, tree automata
  4. storing XML data
Slides of lectures:
  1. Part 1
  2. Part 2