4 ms·
This very recent paper shows a matching (conditional) lower bound of \Omega(n\log n): https://arxiv.org/abs/1902.10935 https://arxiv.org/abs/1902.10935 (the har
by moab 8y ago
This very recent paper shows a matching (conditional) lower bound of \Omega(n\log n): https://arxiv.org/abs/1902.10935 https://arxiv.org/abs/1902.10935 (the hardness is from a conjecture in network coding).
- davidivadavid 8y agoVery interesting. I was just wondering what the lower bound could be (beyond O(n) which seems fairly obvious, even though as a hobbyist I'd be hard pressed to even prove that).