Open €

The cash prize is reserved only to the first to solve each question. Notice the expiration date.

OMv and hinted-Mv (€300-500)

€500: Prove or disprove the OMv conjecture

€300: Prove or disprove the v-hinted Mv conjecture (Conj. 5.2 in vdBNS)

(First offered at ADFOCS 2018. Offer expires in 2028.)

Cut Query for Reachability (€100)

Input: Hidden unweighted directed graph G=(V, E)

Query access: For 𝑆 ⊆ 𝑉, cut(S) returns the number of edges going out from S

Output: Exist path from nodes s to t?

€100: Either show that O(n^1.999) queries is possible or rule out O(n^1.001) queries.

(First offered at ICALP 2024. Offer expires in 2034.)

€5 Questions

Prove or disprove the following (informal) statements in either a Turing Machine or a RAM model. There is a decision problem P such that the following holds. (i) On input of size n, P can be solved in 10n time. (ii) There is an algorithm A that can solve P in 100n^2 time. (iii) Any algorithm B that solves P in 10n time has description size strictly larger than the description of A.