• Time: Thursday, April 25, 2019 at 5:30pm
  • Place: WEH 8220

Michael Anastos

Title: k-cores of random graphs

Abstract: Given a graph $G$, the $k$-core of $G$ is the maximum induced subgraph of $G$ that has minimum degree $k$. The random graph process is the graph process $G_0,G_1,…,G_{\binom{n}{2}}$ where $G_0=([n], \emptyset)$ and $G_{i+1}$ is generated by adding an edge to $G_i$ that is chosen uniformly at random from $\binom{[n]}{2}\setminus E(G_i)$. In this talk we will discuss about the existence of large subgraphs of the $k$-cores of $G_0,G_1,…,G_{\binom{n}{2}}$.

Kerrek Stinson

Title: Existence of weak solutions for the Cahn-Hilliard PDE with elasticity and nonlinear boundary terms

Abstract: In this talk, we discuss existence for the Cahn-Hilliard reaction model introduced by Bazant et. al. for Lithium-ion batteries. Prior work analyzes the PDE using a regularizing viscosity term. Our primary contribution is that we no longer use this. Under some conditions on the form of nonlinear boundary conditions, we recover a classical solution.

Xiaofei Shi

Abstract: We show how to solve a number of problems in numerical linear algebra, such as least squares regression, $\ell_p$-regression for any $p \geq 1$, low rank approximation, and kernel regression, in time $T(A) \poly(\log(nd))$, where for a given input matrix $A \in \mathbb{R}^{n \times d}$, $T(A)$ is the time needed to compute $A\cdot y$ for an arbitrary vector $y \in \mathbb{R}^d$. Since $T(A) = O(\nnz(A))$, where $\nnz(A)$ denotes the number of non-zero entries of $A$, the time is no worse, up to polylogarithmic factors, as all of the recent advances for such problems that run in input-sparsity time. However, for many applications, $T(A)$ can be much smaller than $\nnz(A)$, yielding significantly sublinear time algorithms. For example, in the overconstrained $(1+\epsilon)$-approximate polynomial interpolation problem, $A$ is a Vandermonde matrix and $T(A) = O(n \log n)$; in this case our running time is $n \cdot \poly(\log n) + \poly(d/\epsilon)$ and we recover the results of \cite{avron2013sketching} as a special case. For overconstrained autoregression, which is a common problem arising in dynamical systems, $T(A) = O(n \log n)$, and we immediately obtain $n \cdot \poly(\log n) + \poly(d/\epsilon)$ time. For kernel autoregression, we significantly improve the running time of prior algorithms for general kernels. For the important case of autoregression with respect to the polynomial kernel, we obtain even faster algorithms. Our algorithms show that, perhaps surprisingly, most of these optimization problems do not require much more time than that of a polylogarithmic number of matrix-vector multiplications.

Jing Zhang

Title: Independence in Additive Ramsey Theory

Abstract: I will talk about the truth and independence of the following statement: given any coloring of R into finitely many colors, there exists an infinite subset X such that X+X is monochromatic.

Food will be served.