Events

The number of matrices and a random matrix with prescribed row and column sums and 0-1 entries

QIP = PSPACE

Abstract:

The interactive proof system model of computation is a cornerstone of computational complexity theory, and its quantum computational variant has been studied in quantum complexity theory for the past decade.

On minor-closed classes of matroids

Abstract:

Over the last 10 years I have been working with Bert Gerards and Geoff Whittle on trying to extend the graph minors project of Neil Robertson and Paul Seymour to matroids representable over a given finite fields.

Some new trends and applications of variational analysis

Abstract:

Variational analysis has been well recognized as a rapidly growing and fruitful area in mathematics motivated mainly by the study of constrained optimization and equilibrium problems, while also applying perturbation ideas and v

Semidefinite programming: algorithms and applications

Abstract:

Semidefinite programming (SDP) problems are linear optimization problems over the set of positive semidefinite symmetric matrices.

Fooling Strong LP and SDP Relaxations for Vertex Cover​

Abstract:

A vertex cover of a graph is a subset of the vertices touching all the edges.

Pólya's Theorem with Zeros

Abstract:

Let R[X] := R[X₁,…,X_n].

Split Decomposition

Abstract:

The split decomposition of undirected graphs (also called join decomposition) has a number of nice applications. There are also attractive results on unique decomposition and on the structure of indecomposable graphs, and efficient decomposition algorithms.

The matching structure behind the composition of strips

Abstract:

A strip is a triple (G,a,b), where G is a simple, undirected graph and a,b are vertices of G whose neighborhood is a clique. The composition of strips takes as input a set of strips, and outputs a graph.

Optimization algorithms: worst-case behaviour and related conjectures

Abstract:

The simplex and primal-dual interior point methods are currently the most computationally successful algorithms for linear optimization.