15 problems

Is computing a Kemeny-optimal aggregate ranking NP-hard when the input consists of exactly three complete rankings?

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

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

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

Does every $n$-state synchronizing one-cluster automaton admit a reset 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$?

For every fixed $k>6$, can $k$-coloring be solved in worst-case time $(2-\varepsilon_k)^n$, strictly faster than the general $2^n$ chromatic-number algorithm?

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?

Let $\operatorname{Length}(q)$ denote the length, in bits, of a program or theory $q$. Treat the Standard Model plus gravity, abbreviated SM+G, as a theory encoded by a program for…