Open €
The cash prize is reserved only to the first to solve each question. Notice the expiration date.
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.)
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.