← All problems

3SUM Hard Problems

Let AA, BB, and CC be finite sets of integers whose total cardinality is nNn\in\mathbb{N}. The 3SUM decision problem asks whether there exist aAa\in A, bBb\in B, and cCc\in C such that

a+b=c. a+b=c.

A problem is 3SUM-hard in the sense used by the source when this decision problem reduces to it. Determine whether 3SUM-hard problems can be solved in O(n2ϵ)O(n^{2-\epsilon}) time for some fixed ϵ>0\epsilon>0, including in expectation.

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li