Georgia Institute of Technology College of Sciences

Discrepancy theory, also referred to as the theory of irregularities of distribution, has been developed into a diverse and fascinating field, with numerous closely related areas, including, numerical integration, Ramsey theory, graph theory, geometry, and theoretical computer science, to name a few. Informally, given a set system S defined over an n-item set X, the combinatorial discrepancy is the minimum, over all two-colorings of X, of the largest deviation from an even split, over all sets in S. Since the celebrated ``six standard deviations suffice'' paper of Spencer in 1985, several long standing open problems in the theory of combinatorial discrepancy have been resolved, including tight discrepancy bounds for halfspaces in d-dimensions [Matousek 1995] and arithmetic progressions [Matousek and Spencer 1996]. In this talk, I will present new discrepancy bounds for set systems of bounded ``primal shatter dimension'', with the property that these bounds are sensitive to the actual set sizes. These bounds are nearly-optimal. Such set systems are abstract, but they can be realized by simply-shaped regions, as halfspaces, balls, and octants in d-dimensions, to name a few. Our analysis exploits the so-called "entropy method" and the technique of "partial coloring", combined with the existence of small "packings".

Kronecker coefficients lie at the intersection of representation theory, algebraic combinatorics and, most recently, complexity theory. They count the multiplicities of irreducible representations in the tensor product of two other irreducible representations of the symmetric group. While their study was initiated almost 75 years, remarkably little is known about them. One of the major problems of algebraic combinatorics is to find an explicit positive combinatorial formula for these coefficients. Recently, this problem found a new meaning in the field of Geometric Complexity Theory, initiated by Mulmuley and Sohoni, where certain conjectures on the complexity of computing and deciding positivity of Kronecker coefficients are part of a program to prove the "P vs NP" problem. In this talk we will give an overview of this topic and we will describe several problems with some results on different aspects of the Kronecker coefficients. We will explore Saxl conjecture stating that the tensor square of certain irreducible representation of S_n contains every irreducible representation, and present a criterion for determining when a Kronecker coefficient is nonzero. In a more combinatorial direction, we will show how to prove certain unimodality results using Kronecker coefficients, including the classical Sylvester's theorem on the unimodality of q-binomial coefficients (as polynomials in q). We will also present some results on complexity in light of Mulmuley's conjectures. The presented results are based on joint work with Igor Pak and Ernesto Vallejo.

In synthetic aperture radar (SAR) imaging, two important applications are formation of high resolution images and motion estimation of moving targets on the ground. In scenes with both stationary targets and moving targets, two problems arise. Moving targets appear in the computed image as a blurred extended target in the wrong location. Also, the presence of many stationary targets in the vicinity of the moving targets prevents existing algorithms for monostatic SAR from estimating the motion of the moving targets. In this talk I will discuss a data pre-processing strategy I developed to address the challenge of motion estimation in complex scenes. The approach involves decomposing the SAR data into components that correspond to the stationary targets and the moving targets, respectively. Once the decomposition is computed, existing algorithms can be applied to compute images of the stationary targets alone. Similarly, the velocity estimation and imaging of the moving targets can then be carried out separately.The approach for data decomposition adapts a recent development from compressed sensing and convex optimization ideas, namely robust principle component analysis (robust PCA), to the SAR problem. Classicalresults of Szego on the distribution of eigenvalues for Toeplitz matrices and more recent results on g-Toeplitz and g-Hankel matrices are key for the analysis. Numerical simulations will be presented.

We will discuss amenability of the topological full group of a minimal Cantor system. Together with the results of H. Matui this provides examples of finitely generated simple amenable groups. Joint with N. Monod.