Georgia Institute of Technology College of Sciences

TBA

A simple algorithm for computing the diameter of an unweighted $n$-vertex graph is to run a BFS from every vertex of the graph. This leads to quadratic time algorithms for computing diameter in sparse graphs and geometric intersection graphs. There are matching fine-grained lower bounds which show that in many cases, it is not possible to get a truly subquadratic time algorithm for diameter computation.

To contrast, we give the first truly subquadratic time algorithm for computing the diameter of an $n$-vertex unit-disk graph. The algorithm runs in with $O^*(n^{2-1/18})$ time. The result is obtained as an instance of a general framework, applicable for distance problems in any graph with bounded distance VC-dimension. To obtain these results, we exploit bounded VC-dimension of neighborhood balls,  low-diameter decompositions, and geometric data structures.

Based on paper in FOCS 2025, joint work with Timothy M. Chan, Hsien-Chih Chang, Jie Gao, Sándor Kisfaludi-Bak, and Hung Le. Arxiv: https://arxiv.org/abs/2510.16346

TBA

The work is devoted to the investigation of the solvability of an integro-differential equation in the case of the double scale anomalous diffusion with a sum of two negative Laplacians in different fractional powers in $R^{3}$. The proof of the existence of solutions relies on a fixed point technique. Solvability conditions for the elliptic operators without the Fredholm property in unbounded domains are used.

The degeneracy of a graph is a measure of sparseness that appears in many contexts throughout graph theory. In extremal graph theory, it is known that graphs of bounded degeneracy have Ramsey number which is linear in their number of vertices (Lee, 2017). Also, the degeneracy gives good bounds on the Turán exponent of bipartite graphs (Alon--Krivelevich--Sudokav, 2003). Extending these results to hypergraphs presents a challenge, as it is known that the naïve generalization of these results -- using the standard notion of hypergraph degeneracy -- are not true (Kostochka--Rödl 2006). We define a new measure of sparseness for hypergraphs called skeletal degeneracy and show that it gives information on both the Ramsey- and Turán-type properties of hypergraphs.

Based on joint work with Jacob Fox, Maya Sankar, Michael Simkin, and Yunkun Zhou