Mathematics Problem Archive

Let $X$ be a centered Gaussian random vector in $\mathbb{R}^n$ with known covariance matrix, and for an orthonormal basis $B=(b_1,\ldots,b_n)$ let $N_...

For a $d\times d$ real Gaussian matrix $G_{\mathbb{R}}$ and complex Gaussian matrix $G_{\mathbb{C}}$, both normalized to entry variance $1/d$, define ...

Let ${W}$ denote a symmetric Wigner matrix with i.i.d. entries ${W_{ij}\sim \mathcal{N}(0,1)}$ . Also, given ${B\in\mathbb{R}^{n\times n}}$ symmetric,...

Let $A_1,\dots,A_n\in \mathbb{R}^{d\times d}$ be symmetric matrices and $g_1,\dots,g_n\sim\mathcal{N}(0,1)$ i.i.d.. Does the following hold? $\mathbb{...

Let $X\in\mathbb{R}^{d\times d}$ be a symmetric matrix with (otherwise) independent gaussian entries. Prove (or disprove): $\mathbb{E} \|X\| \lesssim\...

Prove or disprove: there exists a universal constant $C$ such that, for any choice of $n$ symmetric matrices $H_1,\dots,H_n\in\mathbb{R}^{n\times n}$ ...

Part (3) of the problem: Let $s\leq d\leq m$ and $z_1,\dots,z_m\in \mathbb{R}^d$ i.i.d. random vectors with i.i.d. entries $\left( z_k\right)_j = \lef...

Give a tight upperbound to $\mathbb{E}\left\| A^{\otimes k} -\mathbb{E} A^{\otimes k} \right\|.$...

Prove or disprove the following conjecture by Feige : Given $n$ independent random variables $X_1,\dots,X_n$ s.t., for all $i$ , $X_i \geq 0$ and $\ma...

What is the partial recovery threshold for the Stochastic Block Model on $k\geq 3$ communities....

What is the exact recovery threshold for the Stochastic Block Model with a logarithm number of communities? Both computational and information theoret...

Is the k-medians Linear Programming relaxation tight even for point clouds coming from generative models that do not have a community structure?...

Can one give conditions for integrality of the k-medians LP or the k-means SDP based on stability type properties (on the fact that the data is “well-...

Is the Semidefinite programming relaxation for the positive Principal Component Analysis problem tight with high probability for Wigner matrices?...

Let $X_t$ be $d$-dimensional Brownian motion starting at the origin, let $D$ be an open subset of $\mathbb{R}^d$ containing the origin, and let $\tau=...

Let $X_t$ be two-dimensional Brownian motion. (i) For every pair $x,y \notin X[0,1]$, is there a Jordan arc $\Gamma$ containing $x$ and $y$ such that ...

For a set $B$, define its percolation dimension as the infimum of the Hausdorff dimensions of Jordan arcs $A\subset B$ containing at least two distinc...

Let $D$ be a triangle whose angles are all strictly less than $\pi/2$, and let $\mu_2>0$ be the second eigenvalue of the Laplacian on $D$ with Neumann...

Let $D\subset\mathbb{R}^2$ be a connected open set with smooth boundary, and let $X,Y$ be synchronously coupled reflected Brownian motions in $D$ driv...

Let $N$ particles move as independent Brownian motions in a bounded connected open set $D\subset\mathbb{R}^d$. Whenever a particle hits the complement...

Let $D\subset\mathbb{R}^d$, $d\ge2$, be bounded, connected, and open. Suppose there are coupled reflected Brownian motions $X_t,Y_t$ in $D$ and $\vare...

For each $k\in\mathbb{Z}$, let $B^k$ be Brownian motion and $T_k$ a stopping time, with the stopped pieces independent, $0\le T_k<\infty$, and with th...

Choose uniformly a bijective labeling of the vertices of the $n\times n$ discrete square by $1,2,\ldots,n^2$, and call a vertex a peak when all adjace...

For the exclusion process on $\mathbb{Z}$ with $p(x,y)=p(y-x)$, assume $\sum_x|x|p(x)<\infty$, $\sum_xxp(x)>0$, and $\sum_{x<0}x^2p(x)=\infty$. Does t...

On $\mathbb{Z}^2$, take nearest-neighbor jump probabilities $p_1,q_1,p_2,q_2$ in directions $\pm e_1,\pm e_2$, with $p_1>q_1$ and $p_2>q_2$. If the an...

For the exclusion process on $\mathbb{Z}^d$ with translation-invariant kernel $p(x,y)=p(y-x)$ and zero mean $\sum_xxp(x)=0$, prove that every stationa...

For nearest-neighbor asymmetric exclusion on $\mathbb{Z}$ with $p(1)=p>q=p(-1)$, start from the deterministic configuration $\cdots11110000\cdots$. Is...

Give a mathematically useful definition of a process being a 'martingale for practical purposes', so that failure means it is practical to find a stop...

Find a simple network-and-demand toy model in which the marginal satisfiability proportion $r(t)$ can be calculated analytically and exhibits the prop...

For sparse $n$-vertex graphs of average degree $O(1)$ whose vertices have distinct $O(\log n)$-length labels over a finite alphabet, construct univers...

Obtain relaxation- and mixing-time bounds for reversible coagulation-fragmentation Markov chains on finite sets in terms of their model parameters....

For the two stationary branching-coalescing models on $\mathbb{Z}^3$ described by Aldous, prove that as particle intensity tends to zero the suitably ...

Study the constrained Ising storage model described on the page when the underlying graph itself changes in time....

Tasks arrive as a rate-one Poisson process and have types in $[0,1]$; batch processing time $S$ is monotone and strictly subadditive and type $a$ incu...

For the Metropolis chain on a finite Cayley graph with stationary law $\mu(p)$ obtained by stopping random walk at a geometric time, analyze its relax...

For the posterior random weighted graphs $G(t)$ defined from independent Poisson edge counts and flat priors, study the process $\operatorname{gap}(G(...

For sequences of finite weighted networks with vertex recovery rates and stationary SIS infection counts $X^{(n)}_{\theta,\varepsilon}$ satisfying the...

For random proximity graphs on a planar Poisson point process, determine rigorous orders of magnitude for the transversal deviation $T_r$ of a shortes...

For both the diagonal-flip chain on triangulations of the regular $n$-gon and the branch-rotation chain on $n$-cladograms, prove that the relaxation t...

On the bidirected torus $\mathbb{Z}_N^d$ with fixed $d\ge3$, let $b^{(N)},t^{(N)},m^{(N)}$ count excursions of a uniform Eulerian circuit longer than ...

For a uniform Eulerian circuit on the bidirected two-dimensional torus, does $\log L_2^{(N)}/\log N$ converge in distribution to a random variable wit...

On the bidirected complete $n$-vertex graph, is the expected number of length-$i$ excursions in a uniform Eulerian circuit asymptotic to $e^{-i/n}$?...

For a uniform Eulerian circuit on the bidirected Hamming cube $\{0,1\}^d$, determine the asymptotic behavior or distribution of the shortest excursion...

Is there a relation between space-filling $\operatorname{SLE}_\kappa$ for $\kappa>8$ and the conjectural continuum limit of uniform Eulerian circuits ...

Improve the explicit upper and lower bounds for the minimum network length functions $\Psi^{ave}(s)$ and $\Psi^{worst}(s)$, and prove whether there is...

For two independent random $n$-cladograms, under both the uniform and coalescent distributions, prove $\mathbb{E}C_n=n^{\gamma+o(1)}$ for respective c...

For two independent coordinatewise partial orders generated by uniform points in the unit square, prove $\mathbb{E}C_n\sim c n^{1/3}$ and establish th...

For continuous-time processes that merge adjacent polygonal planar regions $A,B$ at a geometry-dependent rate $r(A,B)$, give sufficient conditions on ...

When every adjacent pair of planar empires merges at rate $r(A,B)=1$, does percolation occur?...

For the city-growth model, prove: (a) if $\alpha>1$, the eventual number of cities $M(\infty)$ is finite almost surely; (b) if $\beta<2\alpha$, the la...