Open Problems talk:85

From Open Problems in Sublinear Algorithms
Jump to: navigation, search

There came out a paper [1] that considers a very similar question. It does not solve this question explicitly but it would be worth looking at whether their methods imply a solution to this problem. At the very least, it is very relevant.

[1] Sample Amplification:Increasing Dataset Size even when Learning is Impossible; Brian Axelrod, Shivam Garg, Vatsal Sharan, Gregory Valiant;