Recovery Beats Storage: Improved Space for Preprocessed 3SUMResearch Paper
The 3SUM problem asks whether finite integer sets contain values with . When many instances draw from the same large sets, preparing information once can reduce the cost of subsequent instances. Preprocessed 3SUM with unknown permits preparation of and , while every query supplies its own subsets and its own target set. This separates…