Georgia Institute of Technology College of Sciences

We consider the algorithmic problem of finding large balanced independent sets in sparse random bipartite graphs, and more generally the problem of finding independent sets with specified proportions of vertices on each side of the bipartition. In a bipartite graph it is trivial to find an independent set of density at least half (take one of the partition classes). In contrast, in a random bipartite graph of average degree d, the largest balanced independent sets (containing equal number of vertices from each class) are typically of density (2 + od(1)) log d/d . Can we find such large balanced independent sets in these graphs efficiently? By utilizing the overlap gap property and the low-degree algorithmic framework, we prove that local and low-degree algorithms (even those that know the bipartition) cannot find balanced independent sets of density greater than (1 + ε) log d/d for any ε > 0 fixed and d large but constant.

Inverse problems involve the reconstruction of hidden objects from possibly noisy indirect measurements and are ubiquitous in a variety of scientific and engineering applications. This kind of problems have two main features that make them interesting yet challenging to solve. First, they tend to be ill-posed: the reconstruction is very sensitive to perturbations in the measurements. Second, real-world applications are often large-scale: resulting in computationally demanding tasks. In this talk I will focus on discrete linear problems: giving a general overview of the well-established class of solvers called Krylov subspace methods and its regularizing properties; as well as flexible variants that make them suitable to solve more challenging optimization tasks. I will show results and examples in different imaging applications.

This talk will delve into a method specifically designed for
constructing high-order normal forms in Poincaré maps with high-order
precision and without any major assumption or structure of the
dynamical system itself. We will use the result to generate explicit
twist maps, calculating invariant tori, and determining the flying
time expansions around an elliptic fixed point of a Poincaré map. In
particular, this approach is able to check some non-degenerate
conditions in perturbation theory.

Let ${\mathcal F}L^q_s ({\mathbf R}^2)$ denote the set of all tempered distributions $f \in {\mathcal S}^\prime ({\mathbf R}^2)$ such that the norm $ \| f \|_{{\mathcal F}L^q_s} = (\int_{{\mathbf R}^2}\, ( |{\mathcal F}[f](\xi)| \,( 1+ |\xi| )^s )^q\, d \xi )^{ \frac{1}{q} }$ is finite, where ${\mathcal F}[f]$ denotes the Fourier transform of $f$. We investigate the spectral synthesis for the unit circle $S^1 \subset {\mathbf R}^2$ in ${\mathcal F}L^q_s ({\mathbf R}^2)$ with $1\frac{2}{q^\prime}$, where $q^\prime$ denotes the conjugate exponent of $q$. This is joint work with Prof. Sato (Yamagata University).