Georgia Institute of Technology College of Sciences

Everybody are convinced that everything is known about the simplest random process of coin tossing. I will show that it is not the case. Particularly not everything was known for the simplest chaotic dynamical systems like the tent map (which is equivalent to coin tossing). This new area of finite time predictions emerged from a natural new question in the theory of open dynamical systems.

Sampling is a fundamental algorithmic task. Many modern applications require sampling from complicated probability distributions in high-dimensional spaces. While the setting of logconcave target distribution is well-studied, it is important to understand sampling beyond the logconcavity assumption. We study the Unadjusted Langevin Algorithm (ULA) for sampling from a probability distribution on R^n under isoperimetry conditions. We show a convergence guarantee in Kullback-Leibler (KL) divergence assuming the target distribution satisfies log-Sobolev inequality and the log density has bounded Hessian. Notably, we do not assume convexity or bounds on higher derivatives. We also show convergence guarantees in Rényi divergence assuming the limit of ULA satisfies either log-Sobolev or Poincaré inequality. Joint work with Santosh Vempala (arXiv:1903.08568).

In the first part of this talk, I will give an overview of a theory of harmonic analysis on a class of fractals that includes the Sierpinski gasket. The starting point of the theory is the introduction by J. Kigami of a Laplacian operator on these fractals. After reviewing the construction of this fractal Laplacian, I will survey some of the properties of its spectrum. In the second part of the talk, I will discuss the fractal analogs of the Heisenberg uncertainty principle, and the spectral properties a class of  Schr\"odinger operators.  

A central pervasive challenge in genomics is that RNA/DNA must be reconstructed from short, often noisy subsequences. In this talk, we describe a new digraph algorithm which enables this "assembly" when analyzing high-throughput transcriptomic sequencing data. Specifically, the Flow Decomposition problem on a directed ayclic graph asks for the smallest set of weighted paths that “cover” a flow (a weight function on the edges where the amount coming into any vertex is equal to the amount leaving). We describe a new linear-time algorithm solving *k*-Flow Decomposition, the variant where exactly *k* paths are used. Further, we discuss how we implemented and engineered a general Flow Decomposition solver based on this algorithm, and describe its performance on RNA-sequence data.  Crucially, our solver finds exact solutions while achieving runtimes competitive with a state-of-the-art heuristic, and we discuss the implications of our results on the original model selection for transcript assembly in this setting.