Networks

Training Week 6

On 9 -13 April 2018 NETWORKS organizes the sixth Training Week for PhD Students of NETWORKS. 

The topics of this Training Week are a minicourse on Stochastic Simulation and one on Applications of Grothendieck's inequality. Jan-Pieter Dorsman and Jop Briët are the main lecturers in the morning during this Training Week.

 

In the afternoon various Networks PhD students and other Networks researchers will give talks about their recent results. There will also be time for joint research in small groups (either in existing collaborations or in new collaborations) in so-called working sessions.

 

Minicourse Stochastic Simulation1dorsman

Lecturer: Jan-Pieter Dorsman

 

Stochastic simulation methods have become a fundamental part of the toolset of practitioners and researchers across different applied domains and academic disciplines. This is because they often enable the numerical computation of performance measures of a wide variety of complex stochastic dynamical systems, which typically defy an explicit analysis. In research, stochastic simulation also provides ways to validate conjectures of exact or asymptotic results, or to assess the accuracy of approximations.

 

This course aims to discuss basic ideas and methods associated with stochastic simulation. In particular, I will focus on the following issues which arise when applying simulation methods:

 

1. How does one generate the required input random variables?

2. When simulating, one typically replicates a simulation experiment R times, and based on the output the performance measure under consideration is estimated. How large should R be chosen to obtain an estimate with a given precision?

3. What can we do if the variance of the usual estimator becomes so big, that the required number of replications R gets prohibitively high?

4. When estimating stationary performance measures, one typically starts the process at an initial state, and after a while the process tends to equilibrium.

But how do we know when we `are' in equilibrium? Or are there other (clever) ways to estimate stationary performance measures?

 

The mini-course is loosely based on the book 'Stochastic Simulation: Algorithms and Analysis' by Søren Asmussen and Peter Glynn, which is also an excellent source for background reading.

 

Minicourse Applications of Grothendieck's inequalityBri_t_Jop2

Lecturer: Jop Briët

 

An important feature of an interesting network is that its parts are connected. In these lectures I will discuss how some of the topics of NETWORKS are connected through a relatively simple but profound result known as Grothendieck's inequality. Despite its rather abstract origin (tensor products of Banach spaces), having originally been published in a somewhat obscure journal, and its namesake leaving the field shortly after proving it, this result found an enormous number of applications both within and far beyond its original scope, for instance in quantum computing, quasirandom graphs, approximation algorithms and computational complexity. I will discuss this inequality with the following overall goals in mind:


1. To provide a powerful mathematical tool for the NETWORKS problem-solving toolkit.
2. To expose a common core of some seemingly unrelated NETWORKS problems.
3. To give a single mnemonic for a collection problems and topics you may not think about on a daily basis.
4. To stimulate research on new applications of the inequality and its many variants.

In particular, I will discuss the relevance of Grothendieck's inequality to some (probably not all) of the following topics:

1. Quantum networks, formed by composite physical systems that are connected through arguably the most striking feature of quantum mechanics: entanglement.
2. Quantum query algorithms, such as Shor's factoring algorithm and quantum walk-based algorithms, and their characterization in terms of low-degree polynomials.
3. Combinatorial and spectral notions of quasirandomness for sparse graphs.
4. Algorithms for community detection in sparse random graphs.
5. Algorithmic versions of Szemerédi's regularity lemma (asserting that any dense graph can be partitioned in a certain regular way into a small number of parts).
6. Approximation algorithms for the maximum cut problem in graphs.

Relevant literature:
https://arxiv.org/abs/quant-ph/0404076 (quantum entanglement)
https://arxiv.org/abs/1711.07285 (quantum algorithms)
https://arxiv.org/abs/1108.2464 (quasirandom graphs)
https://arxiv.org/abs/1603.03025 (survey on Grothendieck & optimization)
https://arxiv.org/abs/1411.4686 (community detection)

 

Lecture notes:

 

 

Location

Conferentiecentrum Kaap Doorn , Postweg 9, 3941 KA   Doorn,  http://www.kaapdoorn.com/