17 problems

Let $G$ be any finite two-player, one-round entangled game with entangled value $\omega^*(G)=1-\varepsilon<1$. The conjecture asserts that there exists a constant $c=c(G)>0$ such t…

Does there exist a family of data structures which, for every binary text $T\in\{0,1\}^n$, uses $O(n)$ bits of space and answers suffix-array access queries…

For random Boolean $k$-ary constraint satisfaction problems, particularly for odd $k$, does the Sherali–Adams hierarchy achieve refutation guarantees comparable to those obtained b…

Can an $S$-decoding polynomial modulo a suitable product of $k$ primes attain the lower-bound minimum of $k+1$ nonzero coefficients?

Conjecture 1 (Černý). An $n$-state synchronizing automaton admits a synchronizing word of length at most $(n-1)^2$.

Can a single-pass semi-streaming algorithm beat the naive greedy $1/2$ approximation for maximum matching?

Can the $k$-distinct language be recognized by an acyclic NFA of size $c^kn^{O(1)}$ for some $c<4$?

Can $k$-coloring be solved in time $O^{*}((2-\varepsilon_k)^n)$, for some $\varepsilon_k>0$, for every $k$?

Given a set $A$ of alternatives, three linear orders $\succ_{1},\succ_{2},\succ_{3}$ over $A$, and a number $b$, does there exist a linear order $\succ$ over $A$ such that…

Is KINDI CCA secure without a re-encryption check, as claimed by its published uniqueness lemma?

Is there a practical full-strength key-recovery attack on the unmodified SpoC-128 authenticated-encryption scheme?

Can the best known attack on seven-round AES-128 be improved at the standard chosen-plaintext data budget?

Can the best known key-recovery attack against the HAWK signature scheme be made substantially faster?

Does failure of every low-degree polynomial test imply computational indistinguishability for broad permutation-invariant average-case problems?

Does there exist a computably represented countable structure $A$ that is computably AUT-countable on a cone, but for every finite parameter tuple $\bar a$ has an automorphism…

Is Euclidean closest vector NP-hard to approximate within $n^c$ for some fixed constant $c>0$ under a deterministic reduction?

Can one prove a superlinear-in-the-input-size lower bound for unrestricted arithmetic circuits computing the permanent exactly?