3 ms·
https://scholar.harvard.edu/files/ericbalkanski/files/the-adaptive-complexity-of-maximizing-a-submodular-function.pdf https://scholar.harvard.edu/files/ericbalk
by rindalir 8y ago
https://scholar.harvard.edu/files/ericbalkanski/files/the-adaptive-complexity-of-maximizing-a-submodular-function.pdf https://scholar.harvard.edu/files/ericbalkanski/files/the-ad...
- MaxBarraclough 8y agoI don't think that's it. That's one of Singer's earlier works. I'm fairly sure the relevant one is https://arxiv.org/pdf/1804.06355.pdf https://arxiv.org/pdf/1804.06355.pdf (listed as 'under submission' at https://people.seas.harvard.edu/~yaron/papers.html https://people.seas.harvard.edu/~yaron/papers.html , in line with the article's description)
- rindalir 8y agoThe one I posted is the one that was accepted at STOC this year.