Unsolved Problems

Problem Given two codes $R,C$, their Tensor Product $R \otimes C$ is the code that consists of the matrices whose rows are codewords of $R$ and whose ...

Problem Let $a_1,a_2,\ldots,a_n$ be natural numbers with $\sum_{i=1}^n a_i < 2^n - 1$. It follows from the pigeon-hole principle that there exist dist...

If $p$ is prime and $g,h \in {\mathbb Z}_p^*$, we write $\log_g(h) = n$ if $n \in {\mathbb Z}$ satisfies $g^n = h$. The problem of finding such an int...

Problem Prove unconditionally that $\mathcal{AM}$ $\subseteq$ $\Sigma_2$....

Conjecture Can all problems that can be computed by a probabilistic Turing machine (with error probability < 1/3) in polynomial time be solved by a de...

Conjecture For every rational $\epsilon > 0$ and every rational $\Delta$, there is no polynomial-time algorithm for the following problem. Given is a...