Georgia Institute of Technology College of Sciences

A low-diameter decomposition (LDD) of an undirected graph G is a partitioning of G into components of bounded diameter, such that only a small fraction of original edges are between the components. This decomposition has played instrumental role in the design of low-stretch spanning tree, spanners, distributed algorithms etc. A natural question is whether such a decomposition can be efficiently maintained/updated as G undergoes insertions/deletions of edges. We make the first step towards answering this question by designing a fully-dynamic graph algorithm that maintains an LDD in sub-linear update time. It is known that any undirected graph G admits a spanning tree T with nearly logarithmic average stretch, which can be computed in nearly linear-time. This tree decomposition underlies many recent progress in static algorithms for combinatorial and scientific flows. Using our dynamic LDD algorithm, we present the first non-trivial algorithm that dynamically maintains a low-stretch spanning tree in \tilde{O}(t^2) amortized update time, while achieving (t + \sqrt{n^{1+o(1)}/t}) stretch, for every 1 \leq t \leq n. Joint work with Sebastian Krinninger.

I will discuss two topics in Dynamical Systems. A uniformly hyperbolic dynamical system preserving Borel probability measure μ is called fair dice like or FDL if there exists a finite Markov partition ξ of its phase space M such that for any integers m and j(i), 1 ≤ j(i) ≤ q one has μ ( C(ξ, j(0)) ∩ T^(-1) C(ξ, j(1)) ∩ ... ∩ T^(-m+1)C(ξ, j(m-1)) ) = q^(-m) where q is the number of elements in the partition ξ and C(ξ, j) is element number j of ξ. I discuss several results about such systems concerning finite time prediction regarding the first hitting probabilities of the members of ξ. Then I will discuss a natural modification to all billiard models which is called the Physical Billiard. For some classes of billiard, this modification completely changes their dynamics. I will discuss a particular example derived from the Ehrenfests' Wind-Tree model. The Physical Wind-Tree model displays interesting new dynamical behavior that is at least as rich as some of the most well studied examples that have come before.

We consider totally irregular measures $\mu$ in $\mathbb{R}^{n+1}$, that is, $$\limsup_{r\to0}\frac{\mu(B(x,r))}{(2r)^n} >0 \;\; \& \;\; \liminf_{r\to0}\frac{\mu(B(x,r))}{(2r)^n}=0$$for $\mu$ almost every $x$. We will show that if $T_\mu f(x)=\int K(x,y)\,f(y)\,d\mu(y)$ is an operator whose kernel $K(\cdot,\cdot)$ is the gradient of the fundamental solution for a uniformly elliptic operator in divergence form associated with a matrix with H\"older continuous coefficients, then $T_\mu$ is not bounded in $L^2(\mu)$.This extends a celebrated result proved previously by Eiderman, Nazarov and Volberg for the $n$-dimensional Riesz transform and is part of the program to clarify the connection between rectifiability of sets/measures on $\mathbb{R}^{n+1}$ and boundedness of singular integrals there. Based on joint work with Mihalis Mourgoglou and Xavier Tolsa.

The structure of non-archimedean curves X and their tame covers f:Y-->X is well understoodand can be adequately described in terms of a (simultaneous) semistable model. In particular, asindicated by the lifting theorem of Amini-Baker-Brugalle-Rabinoff, it encodes all combinatorialand residual algebra-geometric information about f. My talk will be mainly concerned with the morecomplicated case of wild covers, where new discrete invariants appear, with the different function being the most basic one. I will recall its basic properties following my joint work with Cohen and Trushin,and will then pass to the latest results proved jointly with U. Brezner: the different functioncan be refined to an invariant of a residual type, which is a (sort of) meromorphic differential form on the reduction, so that a lifting theorem in the style of ABBR holds for simplest wild covers.