There was major progress on perfect graphs in the early 2000's: Chudnovsky, Robertson, Thomas and I proved the ``strong perfect graph theorem'' that a graph is perfect if and only if it has no odd hole or odd antihole; and Chudnovsky, Cornuejols, Liu, Vuscovic and I found a polynomial-time algorithm to test whether a graph has an odd hole or odd antihole, and thereby test if it is perfect. (A ``hole'' is an induced cycle of length at least four, and an ``antihole'' is a hole in the complement graph.)

What we couldn't do then was test whether a graph has an odd hole, and this has stayed open for the last fifteen years, despite some intensive effort. I am happy to report that in fact it can be done in poly-time (in time O(|G|^{12}) at the last count), and in this talk we explain how.

Joint work with Maria Chudnovsky, Alex Scott, and Sophie Spirkl.

The Erdos-Hajnal Theorem asserts that non-universal graphs, that is, graphs that do not contain an induced copy of some fixed graph H, have homogeneous sets of size significantly larger than one can generally expect to find in a graph. We obtain two results of this flavor in the setting of r-uniform hypergraphs.

1. A theorem of R\"odl asserts that if an n-vertex graph is non-universal then it contains an almost homogeneous set (i.e one with edge density either very close to 0 or 1) of size \Omega(n). We prove that if a 3-uniform hypergraph is non-universal then it contains an almost homogeneous set of size \Omega(log n). An example of R\"odl from 1986 shows that this bound is tight.

2. Let R_r(t) denote the size of the largest non-universal r-graph G so that neither G nor its complement contain a complete r-partite subgraph with parts of size t. We prove an Erd\H{o}s--Hajnal-type stepping-up lemma, showing how to transform a lower bound for R_r(t) into a lower bound for R_{r+1}(t). As an application of this lemma, we improve a bound of Conlon-Fox-Sudakov by showing that R_3(t) \geq t^{ct).

Joint work with M. Amir and A. Shapira

Get to know the Mathematrix events of this term!

We were a bit too late with ordering food, so the usual sandwich lunch will only start from week 2. However, there may be some small snacks.

In this talk, we show that a range of non-trivial SU(3) structures can be constructed on large classes of Calabi-Yau three-folds. Among the possible SU(3) structures we find Strominger-Hull systems, suitable for heterotic or type II string compactifications. These SU(3) structures of Strominger-Hull type have a non-vanishing and non-closed three-form flux which needs to be supported by source terms in the associated Bianchi identity. We discuss the possibility of finding such source terms and present first steps towards their explicit construction. Provided suitable sources exist, our methods lead to Calabi-Yau compactifications of string theory with a non Ricci-flat, physical metric which can be written down explicitly and in analytic form. The talk is based on the paper 1805.08499.

The zeta-function of a manifold varies with the parameters and may be evaluated in terms of the periods. For a one parameter family of CY manifolds, the periods satisfy a single 4th order differential equation. Thus there is a straight and, it turns out, readily computable path that leads from a differential operator to a zeta-function. Especially interesting are the specialisations to singular manifolds, for which the zeta-function manifests modular behaviour. We are also able to find, from the zeta function, attractor points. These correspond to special values of the parameter for which there exists a 10D spacetime for which the 6D corresponds to a CY manifold and the 4D spacetime corresponds to an extremal supersymmetric black hole. These attractor CY manifolds are believed to have special number theoretic properties. This is joint work with Xenia de la Ossa, Mohamed Elmi and Duco van Straten.

Let k be a characteristic $p>0$ perfect field, V be a complete DVR whose residue field is $k$ and fraction field $K$ is of characteristic $0$. We denote by $\mathcal{E}  _K$ the Amice ring with coefficients in $K$, and by $\mathcal{E} ^\dagger _K$ the bounded Robba ring with coefficients in $K$. Berthelot's classical theory of Rigid Cohomology over varieties $X/k((t))$ gives $\mathcal{E}  _K$-valued objects.  Recently, Lazda and Pal developed a refinement of rigid cohomology,
i.e. a theory of $\mathcal{E} ^\dagger _K$-valued Rigid Cohomology over varieties $X/k((t))$. Using this refinement, they proved a semistable version of the variational Tate conjecture. 

The purpose of this talk is to introduce to a theory of arithmetic D-modules with $\mathcal{E} ^\dagger _K$-valued cohomology which satisfies a formalism of Grothendieck’s six operations. 
 

Landmark-based human action recognition in videos is a challenging task in computer vision. One crucial step is to design discriminative features for spatial structure and temporal dynamics. To this end, we use and refine the path signature as an expressive, robust, nonlinear, and interpretable representation for landmark-based streamed data. Instead of extracting signature features from raw sequences, we propose path disintegrations and transformations as preprocessing to improve the efficiency and effectiveness of signature features. The path disintegrations spatially localize a pose into a collection of m-node paths from which the signatures encode non-local and non-linear geometrical dependencies, while temporally transform the evolutions of spatial features into hierarchical spatio-temporal paths from which the signatures encode long short-term dynamical dependencies. The path transformations allow the signatures to further explore correlations among different informative clues. Finally, all features are concatenated to constitute the input vector of a linear fully-connected network for action recognition. Experimental results on four benchmark datasets demonstrated that the proposed feature sets with only linear network achieves comparable state-of-the-art result to the cutting-edge deep learning methods. 

In the past decade, deep learning methods have achieved unprecedented performance on a broad range of problems in various fields from computer vision to speech recognition. So far research has mainly focused on developing deep learning methods for Euclidean-structured data. However, many important applications have to deal with non-Euclidean structured data, such as graphs and manifolds. Such data are becoming increasingly important in computer graphics and 3D vision, sensor networks, drug design, biomedicine, high energy physics, recommendation systems, and social media analysis. The adoption of deep learning in these fields has been lagging behind until recently, primarily since the non-Euclidean nature of objects dealt with makes the very definition of basic operations used in deep networks rather elusive. In this talk, I will introduce the emerging field of geometric deep learning on graphs and manifolds, overview existing solutions and outline the key difficulties and future research directions. As examples of applications, I will show problems from the domains of computer vision, graphics, high-energy physics, and fake news detection. 

The Ring Learning With Errors problem (RLWE) comes in various forms. Vanilla RLWE is the decision dual-RLWE variant, consisting in distinguishing from uniform a distribution depending on a secret belonging to the dual OK^vee of the ring of integers OK of a specified number field K. In primal-RLWE, the secret instead belongs to OK. Both decision dual-RLWE and primal-RLWE enjoy search counterparts. Also widely used is (search/decision) Polynomial Learning With Errors (PLWE), which is not defined using a ring of integers OK of a number field K but a polynomial ring Z[x]/f for a monic irreducible f in Z[x]. We show that there exist reductions between all of these six problems that incur limited parameter losses. More precisely: we prove that the (decision/search) dual to primal reduction from Lyubashevsky et al. [EUROCRYPT 2010] and Peikert [SCN 2016] can be implemented with a small error rate growth for all rings (the resulting reduction is nonuniform polynomial time); we extend it to polynomial-time reductions between (decision/search) primal RLWE and PLWE that work for a family of polynomials f that is exponentially large as a function of deg f (the resulting reduction is also non-uniform polynomial time); and we exploit the recent technique from Peikert et al. [STOC 2017] to obtain a search to decision reduction for RLWE. The reductions incur error rate increases that depend on intrinsic quantities related to K and f.

Based on joint work with Miruna Roșca and Damien Stehlé.