Tag: computer science
All the articles with the tag "computer science".
-
Gaps between random points
Posted on:Drop n points uniformly on a circle. The gaps are exchangeable, the expected largest gap is exactly Hₙ/n, about ln n times the average, and its exact distribution is an alternating sum due to Fisher. The same formula is the ln n load imbalance of consistent hashing.
-
Johnson–Lindenstrauss lemma
Posted on:Any n points embed linearly into about ε⁻² log n dimensions with all pairwise distances preserved within 1 ± ε, whatever the source dimension: a chi-square tail bound plus a union bound.
-
Optimal message passing on sparse graphs
Posted on:Our NeurIPS 2023 paper: the asymptotically Bayes-optimal classifier for node classification on sparse contextual stochastic block models, and what it implies for graph neural networks.
-
Stein's paradox
Posted on:In three or more dimensions the sample mean is dominated everywhere by a shrinkage estimator. The reason is the Gaussian shell, and the idea is a precursor of ridge regression.
-
Effects of graph convolutions in multi-layer networks
Posted on:Our ICLR 2023 paper: graph convolutions provably lower the feature-signal threshold for node classification, and two convolutions help much more than one.
-
Fast and online palindrome counting
Posted on:An efficient algorithm for online palindrome counting using the palindrome tree of Rubinchik and Shur: the problem, the data structure, and the implementation.
-
Lunch with Donald Knuth
Posted on:Reflections on a lunch meeting with Donald Knuth. Covers his thoughts on P vs NP, advice on life and curiosity, and his recent mathematical interests in families of sets.
-
St. Petersburg paradox
Posted on:A coin-toss game whose expected winnings are infinite, and why nobody would pay much to play: expectation against intuition, resolved by practical constraints.