Training Week 7

On 29 October-2 November 2018 NETWORKS organizes the seventh Training Week for PhD Students of NETWORKS.

 

Minicourse Algorithmic techniques for large data and networks

Lecturer: Nikhil Bansal

 

Abstract: I will give an overview of three topics: streaming, sketching and sparsification. Streaming and sketching deal with how to compute all kinds of non-trivial information, even if one has very limited memory and can only make a single pass over the data. In the last few years several very surprising algorithms have been developed for such problems, by using probability in unexpected ways.

Graph sparsification deals with the  following question. Given a graph G, can we replace it by a much sparser graph H with an almost linear number of edges such that H preserves various properties of G. We will consider several classic and recent results, using tools from classic graph theory, spectral methods and probability. Time permitting, we will also see some recent results on sparsification in the streaming model.

The focus will be on explaining the basic algorithmic and probabilistic principles, that can be useful for other problems arising in NETWORKS.

 

Minicourse Random Graphs and Erdos Magic

Lecturer: Joel Spencer (CIMS NYU)

 

Lecture I: The Probabilistic Method.  Basics on the Probabilistic Method or, as we prefer to call it, Erdos Magic. Includes Ramsey Theory bounds, Tournament Ranking, 2-Coloring of Hypergraphs. (Download pdf of the  lecture notes)

 

Lecture II: More Probabilistic Methods. Crossing Numbers.  Asymptotic Calculus. (Download pdf of the  lecture notes)

 

Lecture III: Large Deviations, especially Chernoff Bounds, with applications. Basics on the random graph G(n,p).

 

Lecture IV: The Phase Transition. The change in G(n,p) with pn near one.

 

Location

Conferentiecentrum De Schildkamp, Leerdamseweg 44, 4147 BM Asperen