Events

Computational and Cryptanalytic consequences of time travel

Abstract:

We focus on two particular models of closed time like curves.

Faster resource Sharing and VLSI Routing

Abstract:

We present a faster algorithm for the min-max resource sharing problem, generalizing the Garg-Könemann algorithm, and improving previous results by Grigoriadis and Khachiyan, Khandekar, and Jansen and Zhang.

Flexible network design

Topics include

• Theoretical computer science
• Graph algorithms
• Discrete optimization

Local organizers

• Joseph Cheriyan (Waterloo)
• Anupam Gupta (Carnegie Mellon)
• Jochen Könemann (Waterloo)
• Stefano Leonardi (Sapienza U. of Rome)
• R.

Frozen vertices in colourings of a random graph

Abstract:

Over the past decade, much of the work on  random graph colouring,random k-SAT, and other random constraint satisfaction problems has focussed on some foundational unproven hypotheses that have arisen from statistical physics.

Connectivity and matching properties of distance-regular graphs

Abstract:

A strongly regular graph is a regular graph such that the size of the common neighborhood of two distinct vertices depends only on whether the vertices are adjacent or not.

3-Coloring and 3-List-Coloring Graphs of Girth at least Five on Surfaces

Abstract:

Grotzsch proved that every triangle-free planar graph is 3-colorable. This theorem follows easily once one proves that every planar graph of girth at least five is 3-colorable.

Matching Polynomials, Real Stable Polynomials and Ramanujan Graphs

Abstract:

In important recent work Marcus, Spielman and Srivastava have proved that for if k > 2, there is a family of bipartite Ramanujan graphs of valency k.

Line arrangements and intersection theory on algebraic surfaces

Abstract:

Line arrangements in the plane are an object of combinatorial and algebraic geometric interest. Their combinatorial analogues are rank 3 matroids. A line arrangement determines a particular algebraic surface.

The Rim Hook Rule: Relating Quantum Cohomology of the Grassmannian to Ordinary Cohomology of the Grassmannian

Abstract:

I will present the cohomology ring of the Grassmannian of k planes in $\mathbb{C}^n$, roughly a ring with generators related to subspaces of the Grassmannian and product related to overlap

Stable Polynomials and Ramanujan Graphs

Abstract:

We show how Marcus, Spielman and Srivastava use stable polynomials to
construct bipartite Ramunujan graphs of degree $k$ whenever $k\ge3$. (This will be the first of two lectures.)