Mathematics Problem Archive

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...

Construct deterministic matrices $A\in\mathbb{C}^{M\times N}$ (or $A\in\mathbb{R}^{M\times N}$ ) satisfying the $(s,\frac13)$ -RIP for $s\approx\frac{...

Let $N = 2M$ . For which $s$ is there a polynomial time algorithm that is guaranteed to, with high probability, certify that a gaussian matrix $A$ is ...

Consider a $A\in\mathbb{C}^{M\times N}$ obtained by sampling random rows of a Discrete Fourier Tranform. How large does $M$ need to be in order for, w...

How many mutually unbiased bases are there in 6 dimensions?...

Does the Paley Equiangular tight frame satisfy the Restricted Isometry Property pass the square root bottleneck? (even by logarithmic factors?)....

Give a (polynomial time) construction of the tight frame partition satisfying the properties required in the Kadison-Singer problem (or the related We...

Explicit deterministic constructions of codes achieving the GV bound Is the GV bound tight?...

Prove or disprove: $R_A(\alpha n,\beta n,n)=\alpha+(1-\alpha)R_A(1,\beta n,(1-\alpha)n)+o(1)$....

What are the asymptotics of $\mathcal{D}\left(n;\frac12\right)$ ? \item An interesting aspect of the Deletion Channel is that different messages may h...

What is the approximation ratio (or integrality gap) for the Sum-of-Squares (SOS) relaxation of degree 4 for the Max-Cut problem? What about other con...

What is the value of the (real) Grothendieck constant?...

What is the clique number of the Paley graph? Can the the SOS degree 4 analogue of the theta number help upper bound it?...

Given a $d$ -regular graph on $n$ nodes $G$ . Let $MaxBis(G)$ and $MinBis(G)$ denote, respectively, the size of its largest and smallest bisection. Is...

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?...

Does the projected power method converge (with high probability) to the optimal solution of the angular synchronization problem with (small enough) ga...

Is the SDP for angular synchronization tight (with high probability) for noise levels $\sigma$ essentially until the solution of angular synchronizati...

For which levels of noise is the SDP for Multireference Alignment tight?...

Is the Maximum likelihood for Multireference Alignment consistent? (after fixing the power spectrum) What is the sample complexity of the Multireferen...

The Betti poset of a monomial ideal $I$ determines the Stanley projective dimension of $S/I$ and $I$. More precisely, if $I\subseteq S$ and $I'\subset...

Given a graph $G(V,E)$, find a minimum cardinality set $S \subset V$ of nodes such that adding a complete graph on $S$ renders the graph $G+K_S$ globa...

Problem 1. Given an undirected graph $\displaystyle G=(V,E)$ and $\displaystyle s,t\in V,\;\; k\in N$, decide whether the graph has an acyclic orienta...

Problem 1. Find a good characterization for undirected graphs having an acyclic orientation so that the in-degree of every node is even. Problem 2. Fi...

Is it true that every t-perfect graph is strongly t-perfect?...

Are there deletion-contraction formulas for the polymatroid Tutte polynomial?...

Let D be a digraph without loops and k a positive integer. For a partition $\Pi$ of V(D) into directed paths (a path partition) let $|\Pi|_k=\sum_{P \...

Let $B=\{b_1,b_2,\ldots ,b_k\}\subset\{0,1,\ldots ,n-1\}$, and let $B_i=\{b_1+i, b_2+i,\ldots, b_k+i\}$ where addition is modulo n. That is, ${\mathca...

Let M be a matroid on ground set V, let H=(V,E) be a hypergraph with maximum degree $\Delta$, let c(v) be the cost of node v, and let $l(e) \leq u(e)$...

Let D=(V,A) be a digraph with arc-capacities $c : A \to \mathbb{N}$ and a root node $r_0\in V$. A k-arborescence is the arc-disjoint union of k spanni...

Let G=(A,B;E) be a bipartite graph, and $w:E \to \{1,-1\}$ a conservative weighting. Can we determine in polynomial time the maximum number of positiv...

Is every t-perfect graph 4-colourable?...

A hypergraph $H=(V,E)$ has the Kőnig-property if there is a set $\mathcal{D}\subseteq E$ of pairwise disjoint hyperedges such that there is a vertex c...

If G is an undirected graph with even degrees then call two closed Eulerian walks compatible if no pair of incident edges occurs consecutively in both...

Is there a polynomial algorithm for computing a $v_0$-reduced divisor equivalent to a given divisor of an undirected multigraph?...

Let $G$ be an undirected graph. What is the complexity of computing the rotor-router action of the sandpile group of $G$ on the spanning trees of $G$?...

Is the chip-firing reachability problem co-NP-hard for general digraphs?...

Is the chip-firing halting problem in P for Eulerian digraphs with multiple edges?...

Is it true that the chip-firing halting problem for simple digraphs is NP-complete?...

Is it true that a clutter has the MFMC property if and only if it has the packing property?...

Find a constructive characterization of k-dumpy graphs....

Given a crossing supermodular function $p:2^V\to \mathbb{Z}$ satisfying $p(\emptyset)=p(V)=0$, what is the minimum number of edges of an undirected gr...

Given a crossing supermodular function $p:2^V\to \mathbb{Z}$ satisfying $p(\emptyset)=p(V)=0$, what is the minimum number of pairwise non-parallel arc...

Given a symmetric crossing supermodular function $p:2^V\to \mathbb{R}$ and positive integers $n_1,n_2,\dots,n_k$, does there exist a hypergraph H=(V,E...