Before revision:  The best known algorithm in the average-case total setting is due to Wagner (following the approach of Blum-Kalai-Wasserman), and achieves a run-time of u^{O(1/\log k)} , which beats the known (conditional) lower bounds for worst-case k-SUM . One could wonder whether this can be improved even further.
After revision:  The best known algorithm in the average-case total setting is due to Wagner (following the approach of Blum-Kalai-Wasserman), and achieves a run-time of u^{O(1/\log k)} . This beats the known (conditional) lower bounds for worst-case k-SUM . One could wonder whether this can be improved even further.