Georgia Institute of Technology College of Sciences

Data structures are everywhere in computer software.  Classical data structures are specially designed to make each individual operation fast.  A more flexible approach is to design the structure so that it adapts to its use.  This idea has produced data structures that perform well in practice and have surprisingly good performance guarantees.  In this talk I’ll review some recent work on such data structures, specifically on self-adjusting search trees and self-adjusting heaps.

For graphs with maximum degree $\Delta$, a greedy algorithm shows $\chi(G) \leq \Delta + 1$. Brooks improved this to $\chi(G) \leq \Delta$ when $G$ has no cliques of size $\Delta + 1$, provided $\Delta \geq 3$. If is conjectured that if one forbids other graphs, the bound can be pushed further: for instance, Alon, Krivelevich, and Sudakov conjecture that, for any graph $F$, there is a constant $c(F) > 0$ such that $\chi(G) \leq (c(F) + o(1)) \Delta / \log\Delta$ for all $F$-free graphs $G$ of maximum degree $\Delta$. The only graphs $F$ for which this conjecture has been verified so far---by Alon, Krivelevich, and Sudakov themselves---are the so-called almost bipartite graphs, i.e., graphs that can be made bipartite by removing at most one vertex. Equivalently, a graph is almost bipartite if it is a subgraph of the complete tripartite graph $K_{1,t,t}$ for some $t \in \N$. The best heretofore known upper bound on $c(F)$ for almost bipartite $F$ is due to Davies, Kang, Pirot, and Sereni, who showed that $c(K_{1,t,t}) \leq t$. We prove that in fact $c(F) \leq 4$ for any almost bipartite graph $F$, thus making the bound independent of $F$ in all the known cases of the conjecture. We also establish a more general version of this result in the setting of DP-coloring (also known as correspondence coloring), which we give a gentle introduction to. Finally, we consider consequences of this result in the context of sublinear algorithms.

This is joint work with Anton Bernshteyn and Abhishek Dhawan.

Dense kernel matrices resulting from pairwise evaluations of a kernel function arise naturally in machine learning and statistics. Previous work in constructing sparse transport maps or sparse approximate inverse Cholesky factors of such matrices by minimizing Kullback-Leibler divergence recovers the Vecchia approximation for Gaussian processes. However, these methods often rely only on geometry to construct the sparsity pattern, ignoring the conditional effect of adding an entry. In this work, we construct the sparsity pattern by leveraging a greedy selection algorithm that maximizes mutual information with target points, conditional on all points previously selected. For selecting k points out of N, the naive time complexity is O(N k^4), but by maintaining a partial Cholesky factor we reduce this to O(N k^2). Furthermore, for multiple (m) targets we achieve a time complexity of O(N k^2 + N m^2 + m^3) which is maintained in the setting of aggregated Cholesky factorization where a selected point need not condition every target. We directly apply the selection algorithm to image classification and recovery of sparse Cholesky factors. By minimizing Kullback-Leibler divergence, we apply the algorithm to Cholesky factorization, Gaussian process regression, and preconditioning with the conjugate gradient, improving over k-nearest neighbors particularly in high dimensional, unusual, or otherwise messy geometries with non-isotropic kernel functions.

Determinant maximization problem gives a general framework that models problems arising in as diverse fields as statistics, convex geometry, fair allocations, combinatorics, spectral graph theory, network design, and random processes. In an instance of a determinant maximization problem, we are given a collection of vectors $U = {v_1, \ldots, v_n}$ in $d$ dimensions, and a goal is to pick a subset $S$ of given vectors to maximize the determinant of the matrix $\sum_{i \in S} v_i v_i^T$. Often, the set $S$ of picked vectors must satisfy additional combinatorial constraints such as cardinality constraint ($|S| \leq k$) or matroid constraint ($S$ is a basis of a matroid defined on the vectors). In this talk, we give a polynomial-time deterministic algorithm that returns an $r^{O(r)}$-approximation for any matroid of rank $r \leq d$. Our algorithm builds on combinatorial algorithms for matroid intersection, which iteratively improves any solution by finding an alternating negative cycle in the exchange graph defined by the matroids. While the determinant function is not linear, we show that taking appropriate linear approximations at each iteration suffice to give the improved approximation algorithm.

This talk is based on joint work with Adam Brown, Madhusudhan Pittu, Mohit Singh, and Prasad Tetali.