Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

Etessami, Kousha ; Feige, Uriel ; Puppis, Gabriele (Ed.)In [Saunderson, 2011; Saunderson et al., 2013], Saunderson, Parrilo, and Willsky asked the following elegant geometric question: what is the largest m = m(d) such that there is an ellipsoid in ℝ^d that passes through v_1, v_2, …, v_m with high probability when the v_is are chosen independently from the standard Gaussian distribution N(0,I_d)? The existence of such an ellipsoid is equivalent to the existence of a positive semidefinite matrix X such that v_i^⊤ X v_i = 1 for every 1 ⩽ i ⩽ m  a natural example of a random semidefinite program. SPW conjectured that m = (1o(1)) d²/4 with high probability. Very recently, Potechin, Turner, Venkat and Wein [Potechin et al., 2022] and Kane and Diakonikolas [Kane and Diakonikolas, 2022] proved that m ≳ d²/polylog(d) via a certain natural, explicit construction. In this work, we give a substantially tighter analysis of their construction to prove that m ≳ d²/C for an absolute constant C > 0. This resolves one direction of the SPW conjecture up to a constant. Our analysis proceeds via the method of Graphical Matrix Decomposition that has recently been used to analyze correlated random matrices arising in various areas [Barak et al., 2019; Bafna et al., 2022]. Our key new technical tool is a refined method to prove singular value upper bounds on certain correlated random matrices that are tight up to absolute dimensionindependent constants. In contrast, all previous methods that analyze such matrices lose logarithmic factors in the dimension.more » « lessFree, publiclyaccessible full text available July 5, 2024

Given a graph and an integer k, Densest kSubgraph is the algorithmic task of finding the subgraph on k vertices with the maximum number of edges. This is a fundamental problem that has been subject to intense study for decades, with applications spanning a wide variety of fields. The stateoftheart algorithm is an O(n^{1/4+ϵ})factor approximation (for any ϵ>0) due to Bhaskara et al. [STOC '10]. Moreover, the socalled logdensity framework predicts that this is optimal, i.e. it is impossible for an efficient algorithm to achieve an O(n^{1/4−ϵ})factor approximation. In the average case, Densest kSubgraph is a prototypical noisy inference task which is conjectured to exhibit a statisticalcomputational gap. In this work, we provide the strongest evidence yet of hardness for Densest kSubgraph by showing matching lower bounds against the powerful SumofSquares (SoS) algorithm, a metaalgorithm based on convex programming that achieves stateofart algorithmic guarantees for many optimization and inference problems. For k ≤ n^1/2, we obtain a degree n^δ SoS lower bound for the hard regime as predicted by the logdensity framework. To show this, we utilize the modern framework for proving SoS lower bounds on averagecase problems pioneered by Barak et al. [FOCS '16]. A key issue is that small denserthanaverage subgraphs in the input will greatly affect the value of the candidate pseudoexpectation operator around the subgraph. To handle this challenge, we devise a novel matrix factorization scheme based on the positive minimum vertex separator. We then prove an intersection tradeoff lemma to show that the error terms when using this separator are indeed small.more » « lessFree, publiclyaccessible full text available June 2, 2024

We give efficient algorithms for finding powersum decomposition of an input polynomial with component s. The case of linear s is equivalent to the wellstudied tensor decomposition problem while the quadratic case occurs naturally in studying identifiability of nonspherical Gaussian mixtures from loworder moments. Unlike tensor decomposition, both the unique identifiability and algorithms for this problem are not wellunderstood. For the simplest setting of quadratic s and , prior work of [GHK15] yields an algorithm only when . On the other hand, the more general recent result of [GKS20] builds an algebraic approach to handle any components but only when is large enough (while yielding no bounds for or even ) and only handles an inverse exponential noise. Our results obtain a substantial quantitative improvement on both the prior works above even in the base case of and quadratic s. Specifically, our algorithm succeeds in decomposing a sum of generic quadratic s for and more generally the th powersum of generic degree polynomials for any . Our algorithm relies only on basic numerical linear algebraic primitives, is exact (i.e., obtain arbitrarily tiny error up to numerical precision), and handles an inverse polynomial noise when the s have random Gaussian coefficients.more » « less