26 problems

There exists an absolute constant $C>0$ such that, for every nonzero polynomial $f\in\mathbb{R}[x]$, the number of distinct real roots of $f$ satisfies…

For every fixed arity $k$, every $k$-ary constraint-satisfaction problem having a Mal'tsev extension has linear non-redundancy; equivalently, its non-redundancy is $O(n)$ in the re…

Given a sequence of insertions of elements into a ground set, a monotone submodular function $f$ accessible through value queries, and a cardinality bound $k$, does there exist a r…

For a matrix $M\in\{0,1\}^{n\times m}$, define its binary rank by…

Determine asymptotically tight worst-case sample-size bounds for length generalization by transformers whose solutions are expressible in the fragments $\mathsf{C\text{-}RASP}_{+}$…

Let an $\varepsilon$-synchronization string of length $n$ over an alphabet $\Sigma$ be a word $S\in\Sigma^n$ such that, for every $0\le i<j<k\le n$, the insertion-deletion edit dis…

Given local random-neighbor access to an unknown unweighted graph $G$ with $n$ vertices, let $N_G$ denote its normalized adjacency matrix and let…

For integers $n$ and $u$ with $u=n^{1+o(1)}$, and a prime $p>u$, define…

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…

For every synchronizing deterministic finite automaton $\mathcal{A}=(Q,\Sigma,\delta)$ with $|Q|=n$, there exists a word $w\in\Sigma^*$ and a state $q_0\in Q$ such that…

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

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?

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

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

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

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

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?