Abstract We establish dimension-free stability of Webb’s sharp simplex slicing (1996). Incidentally, we show the Lipschitzness of volume of central sections of arbitrary (not necessarily symmetric) convex bodies.

Let $p=\frac{1+\varepsilon}{n}$. It is known that if $N=\varepsilon^3n\to\infty$, then with high probability (w.h.p.) $G_{n,p}$ has a unique giant largest component. We show that if in addition, $\varepsilon=\varepsilon(n)\to 0$, then w.h.p. the cover time of $G_{n,p}$ is asymptotic to $n\log^2N$; previously Barlow, Ding, Nachmias, and Peres had shown this up to constant multiplicative factors.

We consider a constrained version of the shortest path problem on the complete graphs whose edges have independent random lengths and costs. We establish the asymptotic value of the minimum length as a function of the cost-budget within a wide range.

We show that the uniform distribution minimizes entropy among all one-dimensional symmetric log-concave distributions with fixed variance, as well as various generalizations of this fact to Rényi entropies of orders less than 1 and with moment constraints involving p-th absolute moments with p ≤ 2. As consequences, we give new capacity bounds for additive noise channels with symmetric log-concave noises, as well as for timing channels involving positive signal and noise where the noise has a decreasing log-concave density. In particular, we show that the capacity of an additive noise channel with symmetric, log-concave noise under an average power constraint is at most 0.254 bits per channel use greater than the capacity of an additive Gaussian noise channel with the same noise power. Consequences for reverse entropy power inequalities and connections to the slicing problem in convex geometry are also discussed.

We establish a discrete analog of the Rényi entropy comparison due to Bobkov and Madiman. For log-concave variables on the integers, the min entropy is within log e of the usual Shannon entropy. Additionally we investigate the entropic Rogers-Shephard inequality studied by Madiman and Kontoyannis, and establish a sharp Rényi version for certain parameters in both the continuous and discrete cases.

We establish a discrete analog of the Rényi entropy comparison due to Bobkov and Madiman. For log-concave variables on the integers, the min entropy is within log2e of the usual Shannon entropy. With the additional assumption that the variable is monotone we obtain a sharp bound of loge.

We study the minimum spanning tree problem on the complete graph where an edge e has a weight We and a cost Ce, each of which is an independent uniform [0, 1] random variable. There is also a constraint that the spanning tree T must satisfy C(T) ≤ c0. We establish the asymptotic value of the optimum weight via the consideration of a dual problem. The proof is therefore constructive i.e. can be thought of as the analysis of a polynomial time algorithm. We also study the minimum spanning arborescence problem on the complete digraph where an edge e has a weight We and a cost Ce, each of which is an independent uniform [0, 1] random variable. There is also a constraint that the spanning arborescence T must satisfy C(T) ≤ c0. We establish the asymptotic value of the optimum weight via the consideration of a dual problem. The proof is via the analysis of a polynomial time algorithm.

We study the component structure of the random graph $G=G_{n,m,d}$. Here $d=O(1)$ and $G$ is sampled uniformly from ${\mathcal G}_{n,m,d}$, the set of graphs with vertex set $[n]$, $m$ edges, and maximum degree at most $d$. If $m=\mu n/2$, then we establish a threshold value $\mu_\star$ such that if $\mu<\mu_\star$, then with high probability (w.h.p.) the maximum component size is $O(\log n)$. If $\mu>\mu_\star$, then w.h.p. there is a unique giant component of order $n$ and the remaining components have size $O( \log n)$.

In 1948, Shannon showed that the worst additive noise channel for a given noise power is the additive white Gaussian noise channel. We pose the question of the best additive noise within a natural class of noise distributions- namely, symmetric and log-concave distributions on the real line. While we are unable to answer the question, we do completely solve two related optimization problems. In particular, we identify the distribution in this class that minimizes differential entropy when the variance is fixed, and thereby give refined capacity bounds for channels with symmetric log-concave noises. A full version of this paper which also contains more general results and some additional theorems and corollaries is accessible at: https://arxiv.org/abs/1811.00345.