Open Problems talk:85

From Open Problems in Sublinear Algorithms
Revision as of 08:55, 12 April 2021 by Jakub Tětek (talk | contribs) (adding a reference)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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;