35 problems
Determine the computational complexity of the following decision problem: given a planar graph with maximum degree at most and an integer , decide whether…
Given oracle access to an unknown tournament on vertices, where one query reveals the orientation of a selected edge, determine the deterministic query complexity of…
Fix an integer . For each number of items divisible by , let be arbitrary base valuations. Independently choose uniformly rando…
For every finite graph with maximum degree and every integer , the lazy Glauber dynamics on the set of proper -colorings of has mixing tim…
Let be independent random vectors, each uniformly distributed among the vectors with exactly nonzero coordinates. An online algorithm chooses s…
There exists a constant and infinitely many Traveling Salesman Problem instances with cities, together with an initial Hamiltonian cycle , such that every sequence o…
For each , let be the infimum, over randomized algorithms that use vertex-query access to an acyclic unique-sink orientation of the binary hypercube and outpu…
For every fixed integer and every constant , let be a random -uniform hypergraph on vertices in which each -element hyperedge is present independen…
There exists an absolute constant such that, for every nonzero polynomial , the number of distinct real roots of satisfies…
For every fixed arity , every -ary constraint-satisfaction problem having a Mal'tsev extension has linear non-redundancy; equivalently, its non-redundancy is in the re…
Given a sequence of insertions of elements into a ground set, a monotone submodular function accessible through value queries, and a cardinality bound , does there exist a r…
For a matrix , define its binary rank by such that…
Determine asymptotically tight worst-case sample-size bounds for length generalization by transformers whose solutions are expressible in the fragments …
Let an -synchronization string of length over an alphabet be a word such that, for every , the insertion-deletion edit dis…
Can an -decoding polynomial modulo a suitable product of primes attain the lower-bound minimum of nonzero coefficients?
Conjecture 1 (Černý). An -state synchronizing automaton admits a synchronizing word of length at most .
Can a single-pass semi-streaming algorithm beat the naive greedy approximation for maximum matching?
Can the -distinct language be recognized by an acyclic NFA of size for some ?
Can -coloring be solved in time , for some , for every ?
Given a set of alternatives, three linear orders over , and a number , does there exist a linear order over 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?