We study a generalization of classical combinatorial graph spanners to the spectral setting. Given a set of vectors V ⊆ ℝd, we say a set U ⊆ V is an α-spectral kspanner, for k ≤ d, if for all v ϵ V there is a probability distribution μv supported on U such that where for two matrices A, B ϵ ℝd×d we write iff the sum of the bottom d – k + 1 eigenvalues of B – A is nonnegative. In particular, iff . We show that any set V has an Õ(k)-spectral spanner of size Õ(k) and this bound is almost optimal in the worst case. We use spectral spanners to study composable coresets for spectral problems. We show that for many objective functions one can use a spectral spanner, independent of the underlying function, as a core-set and obtain almost optimal composable core-sets. For example, for the k-determinant maximization problem, we obtain an Õ(k)k-composable core-set, and we show that this is almost optimal in the worst case. Our algorithm is a spectral analogue of the classical greedy algorithm for finding (combinatorial) spanners in graphs. We expect that our spanners find many other applications in distributed or parallel models of computation.

Abstract. We prove that the permanent of nonnegative matrices can be deterministically approximated within a factor of [Formula: see text] in polynomial time, improving upon previous deterministic approximations. We show this by proving that the Bethe approximation of the permanent, a quantity computable in polynomial time, is at least as large as the permanent divided by [Formula: see text]. This resolves a conjecture of [L. Gurvits, Unleashing the Power of Schrijver’s Permanental Inequality with the Help of the Bethe Approximation, preprint, arxiv 1106.2844, 2011]. Our bound is tight and, when combined with previously known inequalities lower bounding the permanent, fully resolves the quality of Bethe approximation for the permanent. As an additional corollary of our methods, we resolve a conjecture of [M. Chertkov and A. B. Yedidia, J. Mach. Learn. Res., 14 (2013), pp. 2029–2066], proving that fractional belief propagation with fractional parameter [Formula: see text] yields an upper bound on the permanent.

“Composable core-sets” are an efficient framework for solving optimization problems in massive data models. In this work, we consider efficient construction of composable core-sets for the determinant maximization problem. This can also be cast as the MAP inference task for “determinantal point processes", that have recently gained a lot of interest for modeling diversity and fairness. The problem was recently studied in \cite{indyk2018composable}, where they designed composable core-sets with the optimal approximation bound of $O(k)^k$. On the other hand, the more practical “Greedy" algorithm has been previously used in similar contexts. In this work, first we provide a theoretical approximation guarantee of $C^{k^2}$ for the Greedy algorithm in the context of composable core-sets; Further, we propose to use a “Local Search" based algorithm that while being still practical, achieves a nearly optimal approximation bound of $O(k)^{2k}$; Finally, we implement all three algorithms and show the effectiveness of our proposed algorithm on standard data sets.

We study the Gibbs sampling algorithm for discrete and continuous $k$-determinantal point processes. We show that in both cases, the spectral gap of the chain is bounded by a polynomial of $k$ and it is independent of the size of the domain. As an immediate corollary, we obtain sublinear time algorithms for sampling from discrete $k$-DPPs given access to polynomially many processors. In the continuous setting, our result leads to the first class of rigorously analyzed efficient algorithms to generate random samples of continuous $k$-DPPs. We achieve this by showing that the Gibbs sampler for a large family of continuous $k$-DPPs can be simulated efficiently when the spectrum is not concentrated on the top $k$ eigenvalues.

We initiate the study of approximating the largest induced expander in a given graph G. Given a Δ-regular graph G with n vertices, the goal is to find the set with the largest induced expansion of size at least δ · n. We design a bi-criteria approximation algorithm for this problem; if the optimum has induced spectral expansion λ our algorithm returns a expander of size at least δn (up to constants). Our proof introduces and employs a novel semidefi- nite programming relaxation for the largest induced expander problem. We expect to see further applications of our SDP relaxation in graph partitioning problems. In particular, because of the close connection to the small set expansion problem, one may be able to obtain new insights into the unique games problem.

Strongly Rayleigh distributions are natural generalizations of product and determinantal probability distributions and satisfy the strongest form of negative dependence properties. We show that the "natural" Monte Carlo Markov Chain (MCMC) algorithm mixes rapidly in the support of a homogeneous strongly Rayleigh distribution. As a byproduct, our proof implies Markov chains can be used to efficiently generate approximate samples of a k-determinantal point process. This answers an open question raised by Deshpande and Rademacher which was studied recently by Kang, Li-Jegelka-Sra, and Rebeschini-Karbasi.