Mathematics Problem Archive

Given a symmetric matrix ${M}$ with small condition number, is there a quasi-linear time (on ${n}$ and the number of non-zero entries of ${M}$ ) proce...

Let ${G=(V,E,W)}$ be a graph and ${k}$ a positive integer, is the following true? $\rho_G(k) \leq \mathrm{polylog}(k) \sqrt{\lambda_k}. \ \ \ \ \ (2)$...

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

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

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

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

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

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

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

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

In a soccer tournament of n teams, every pair of teams plays one match. The winner gets 3 points, the loser gets 0, while both teams receive 1 point i...

Give an algorithm and/or a good characterization to decide if a red-blue edge-coloured bipartite graph contains a perfect matching with exactly k red ...

Decide whether a graph is globally rigid in three-dimensional space....

Can we decide in polynomial time whether a given graph is rigid in 3-dimensional space?...

A spanning tree of a graph G is called $\epsilon$-thin if it contains at most an $\epsilon$ fraction of the edges of each cut. Is there a function $f:...

In a graph G=(V,E) with a root node r, two spanning trees $T_1$ and $T_2$ are called r-independent if for any node x in V-r, the unique paths between ...

Is it true that every smooth polytope has the integer decomposition property?...

Given an undirected graph G=(V,E), find a maximum cardinality 2-matching containing no cycles of length 4 in polynomial time....

Given a graph G=(V,E), and weight and capacity functions $w,u: E \to {\mathbb R_+}$ defined on the edge set, is there a combinatorial, strongly polyno...

Given a bipartite graph G with edge weights, can we find in polynomial time a maximum weight k-element matching in G that can be extended to a perfect...

Let G=(V,E) be an undirected graph and let $(s_1,t_1), (s_2,t_2)$ be two node pairs. Give a combinatorial, polynomial-time algorithm to find edge-disj...

Can we find a minimum k-way cut in a capacitated hypergraph in polynomial time, if k is fixed?...

For a plane graph $G$, let $g(G)$ denote the length of the shortest face in $G$. For a (not necessarily proper) $k$-coloring of $V(G)$ we say that a f...

Any $2k$-edge-connected (possibly infinite) multigraph admits a $k$-edge-connected orientation....

Find a good characterization for undirected graphs having a strongly connected (more generally k-edge-connected) orientation so that the in-degree of ...

Given a directed graph whose arcs are coloured red and blue and integers r and b, can we decide in polynomial time whether the digraph has a cut with ...

Let $M$ be a matroid of rank n whose ground set S can be partitioned into n disjoint bases $B_1,\dots,B_n$. Is it true that $B_1,\dots,B_n$ always hav...

The rotor-routing halting problem asks the following: Given an initial chip-and-rotor configuration on a digraph, does the rotor-routing game eventual...

Given a digraph D=(V,A), two (not necessarily disjoint) subsets $S,T\subseteq V$ and a connectivity requirement k, develop a strongly polynomial time ...

Let $M=(S,r)$ be a loopless matroid of rank k whose ground set can be partitioned into k bases. Is it true that no matter how we partition S into sets...

Is it true that if D=(V,A) is a digraph where every node has positive out-degree, then D has a quasi-kernel of size at most |V|/2?...

Let $G=(V,E)$ be an undirected graph, and $T \subseteq V$ a set of nodes of odd degree. When does an orientation $D$ of $G$ exist which is i) smooth (...

Devise combinatorial polynomial-time algorithms for the following two problems. Given a graph G, find a subgraph H with $O(n)$ edges such that $d_H(X)...

Let the graphs $G=(V,E)$ and $H$ be fixed. An edge set $F\subseteq E$ is called $H$-free if $(V,F)$ does not contain $H$ as a subgraph. We say that $F...

Is it true that if all the hyperedges of a hypergraph $H$ have size at most $k$ for some $k\in \mathbb{N}$, then $H$ admits a strongly maximal matchin...

Is it true that if the hypergraph $H$ has no isolated vertices and all of its hyperedges are finite, then $H$ admits a strongly minimal edge cover?...

$\rm{gon}(G) \leq \frac{|E(G)|-|V(G)|}{2} + 2$, where $\rm{gon}(G)$ the denotes the divisorial gonality of graph $G$....

Let G=(S,T;E) be a bipartite graph, with weights $w:E \to [0,1]$. A proper weighted edge colouring is a colouring of the edges such that at each verte...

When can we characterize hypergraphs that have an orientation satisfying a prescribed symmetric local edge-connectivity requirement? Special case: can...

Erdős: How many colors is it necessary to use so that, if you paint every single point of the two-dimensional plane some color, no two points which ar...