Mathematics

Efficient computational methods for the shallow water equations and their applications

Yulong Xing (Ohio State University)

Abstract: Nonlinear shallow water equations (SWEs) with a non-flat bottom topography have been widely used to model flows in rivers and coastal areas, with applications arising from ocean, hydraulic engineering, and atmospheric modeling. Development of efficient and accurate numerical algorithms for SWEs has been an active research area in the past few decades. In this presentation, we will talk about efficient finite element methods developed for the SWEs and their applications in computational hydrology.

Presburger Arithmetic and its computational complexity

Danny Nguyen (UCLA)

Abstract: Presburger Arithmetic (PA) is a classical topic in logic, with numerous connection to computer science and combinatorics. Formally, is the first order structure on the integers with only additions and inequalities. Despite its long history, many problems in PA have remained unsolved until recently. We study the complexity of decision problems in PA, and classify them according to hierarchy levels. Along the way, connections to Integer Programming and Optimization will be explained. The talk will be self contained and assumes no prior knowledge of the subject. Joint work with Igor Pak.

Gaussian and bootstrap approximations of high-dimensional U-statistics and their applications

Xiaohui Chen (UIUC (Stat. Dept.))

Abstract: We shall first discuss the Gaussian approximation of high-dimensional and non-degenerate U-statistics of order two under the supremum norm. A two-step Gaussian approximation procedure that does not impose structural assumptions on the data distribution is proposed. Subject to mild moment conditions on the kernel, we establish the explicit rate of convergence that decays polynomially in sample size for a high-dimensional scaling limit, where the dimension can be much larger than the sample size. We also provide computable approximation methods for the quantiles of the maxima of centered U-statistics. Specifically, we provide a unified perspective for the empirical, the randomly reweighted, and the multiplier bootstraps as randomly reweighted quadratic forms, all asymptotically valid and inferentially first-order equivalent in high-dimensions. The bootstrap methods are applied on statistical applications for high-dimensional non-Gaussian data including: (i) principled and data-dependent tuning parameter selection for regularized estimation of the covariance matrix and its related functionals; (ii) simultaneous inference for the covariance and rank correlation matrices. In particular, for the thresholded covariance matrix estimator with the bootstrap selected tuning parameter, we show that the Gaussian-like convergence rates can be achieved for heavy-tailed data, which are less conservative than those obtained by the Bonferroni technique that ignores the dependency in the underlying data distribution. In addition, we also show that even for subgaussian distributions, error bounds of the bootstrapped thresholded covariance matrix estimator can be much tighter than those of the minimax estimator with a universal threshold.

Network creation and distance uniformity

Misha Lavrov (Illinois Math)

Abstract: In a network creation game, several players try to build an efficient network together. Each player, however, is greedy and selfish, and only cares to minimize their own costs. Tragically, some outcomes of this game may result in an equilibrium in which players are much worse off than if a single network creator just told them what to do. How much worse off? Alon, Demaine, Hajiaghayi, and Leighton answer the question for one version of the game, proving that any equilibrium graph has diameter at most 2^O(sqrt(log n)). Moreover, taking a sufficiently power of an equilibrium graph produces a distance-uniform graph. This is a very strong graph property that seems certain to produce a much better diameter bound. Alas, this is not to be. We show that distance-uniform graphs with diameter 2^O(sqrt(log n)) exist, and that this bound is tight. This is joint work with Po-Shen Loh and Arnau Messegué.