按年被提到
20082018 · 1 次2026
数学、逻辑与理论›数学猜想与重大证明·arXiv:0808.0163 · cs.DS

Twice-Ramanujan Sparsifiers

Joshua Batson, Daniel A. Spielman, Nikhil Srivastava · 2008
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 2 人首次 2018-05-11 · 最近 2022-11-28
2不同的人
2活跃月份
2讨论串
6被引(OpenAlex)
arXiv 摘要(候选层不写导读)

We prove that every graph has a spectral sparsifier with a number of edges linear in its number of vertices. As linear-sized spectral sparsifiers of complete graphs are expanders, our sparsifiers of arbitrary graphs can be viewed as generalizations of expander graphs. In particular, we prove that for every $d>1$ and every undirected, weighted graph $G=(V,E,w)$ on $n$ vertices, there exists a weighted graph $H=(V,F,\tilde{w})$ with at most $\lceil d(n-1) \rceil$ edges such that for every $x \in \mathbb{R}^{V}$, \[ x^{T}L_{G}x \leq x^{T}L_{H}x \leq (\frac{d+1+2\sqrt{d}}{d+1-2\sqrt{d}})\cdot x^{T}L_{G}x \] where $L_{G}$ and $L_{H}$ are the Laplacian matrices of $G$ and $H$, respectively. Thus, $H$ approximates $G$ spectrally at least as well as a Ramanujan expander with $dn/2$ edges approximates the complete graph. We give an elementary deterministic polynomial time algorithm for constructing $H$.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论gjm11 · 2018-05

“John Urschel is a mathematician who recently retired from being an NFL American football player, at least in part because of the dangers of brain damage from repeated concussions. There have been several HN posts about him, but the only one I can find with a lot of comments is this one: https://news.ycombinator.com/item?id=14866573 His favourite theorem …”

John Urschel's Favorite Theorem原评论 ↗
被提交为 story · 1 次