Nikolai Kriukov (University of Amsterdam)
Functional Central Limit Theorem for the simultaneous subgraph count of dynamic Erd\\H{o}s-R\\\'{e}nyi random graphs abstract
Abstract:
In this talk we consider a dynamic Erd\\H{o}s-R\\\'{e}nyi random graph with independent identically distributed edge processes. Our goal is to describe the joint evolution of count of different subgraphs. Central result of this talk is joint functional convergence of the subgraph counts to a specific multidimensional Gaussian process, which holds under mild assumptions on the edge processes, most notably a Lipschitz-type condition. Seminar organized by Prof. Hashorva
11:00 • EPF Lausanne, Extranef 125
Lars Rohwedder
Recursive randomized rounding over s-t walks abstract
Abstract:
We develop an algorithm for finding s-t walks with non-trivial guarantees. Specifically, we want to approximately maximize a monotone submodular function over vertices vi sited in the walk and bound the repetition of vertices in the walk. We also discuss an application in the problem of maximizing monotone submodular functions over perfect matchings in bipartite graphs.The algorithm is based on a recursive randomized rounding procedure over a Sherali-Adams extended formulation.This is upcoming joint work with Rico Zenklusen.
11:00 • EPF Lausanne, MA B1 524
Anouk Brose (University of California, Davis, US)
Lattice Diameters of Polytopes abstract
Abstract:
The lattice diameter of a polytope measures the maximum number of collinear lattice points in a polytope, equivalently, the maximum number of lattice points in a one-dimensional section of a polytope. We study structural properties of the lattice diameter and show connections to the shortest vector problem and the lattice width of a polytope. Algorithmically, we give a fixed-dimension polynomial time algorithm that computes the lattice diameter of a rational polytope, and show that this problem is NP-hard when the dimension is non-fixed. Furthermore, we study how segments attaining the lattice diameter behave under dilation of the polytope and prove an Ehrhart-theory type result. This is joint work with G. Averkov, J.A. De Loera, G. Lopez-Campos, and A. Torres.
13:15 • ETH Zentrum, Rämistrasse 101, Zürich, Building HG, Room G 19.1
Prof. Dr. Hannah Larson (UC Berkely)
Tautological classes on the strata of differentials
13:30 • ETH Zentrum, Rämistrasse 101, Zürich, Building HG, Room G 43