{"id":"arxiv/2611.25662","url":"https://arxiv.org/abs/2611.25662","tags":["math.CO","math.PR"],"score":0,"title":"Positive semidefiniteness of random submatrices","domain":"math.CO","source":"arxiv","authors":["Rajko Nenadov","Lander Verlinde"],"reviews":0,"subject":"math.CO","summary":"Given a symmetric matrix $A \\in [-1,1]^{n \\times n}$, we estimate the probability that a random principal submatrix, obtained by taking each index independently with probability $p$, is positive semidefinite. As a corollary, we show that $O(\\varepsilon^{-1})$ indices chosen uniformly at random suffice for testing positive semidefiniteness with squared Frobenius distance threshold $\\varepsilon n^2$, thus nearly matching the lower bound of Bakshi, Chepurko, and Jayaram (``Testing Positive Semi-Definiteness via Random Submatrices'', FOCS 2020). The key ingredient is a dense model lemma for…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-19","reactions":{}}