Multitasker threshold at average degree log n
Open Problem (multitasker at average degree $\Theta(\log n)$) · arXiv:1611.02400
Status open medium confidence
No paper resolving the open problem has been found. The follow-up work arXiv:1809.02835 (Multitasking Capacity: Hardness Results and Improved Constructions, published in SIAM J. Discrete Math.) proves hardness of approximation results and provides improved constructions achieving $\alpha = 1/2 - \varepsilon$ for matchings of size $n/\mathrm{poly}(d)$, but does not construct multitaskers with $\alpha > 0$ independent of $n$ at average degree $\Theta(\log n)$. The specific threshold question — whether $\Theta(\log n)$ average degree suffices for constant $\alpha$ — remains open as of the search date.
Cited literature (1)
-
Proves computational hardness for approximating multitasking capacity and gives improved constructions achieving $\alpha = 1/2 - \varepsilon$ for matchings of size $n/\mathrm{poly}(d)$, but does not resolve the $\Theta(\log n)$ average-degree threshold question.
Reviewer notes. The main follow-up paper arXiv:1809.02835 was verified via WebFetch; it improves constructions and proves hardness but does not address the specific open problem about $\Theta(\log n)$ average degree. No other paper specifically resolving this threshold question was found in the search.
Context
The paper shows there exist multitaskers of average degree $\Omega(\log\log n)$ with $\alpha > 1/3 - \varepsilon$, and that for the multitasking capacity to decay with average degree $d$ one must assume $d$ grows faster than $\log\log n$. The question is whether the threshold can be pushed up to $\Theta(\log n)$.
Notes. Statement appears in running prose without a labelled environment; PDF source.
Source paper
A Graph-Theoretic Approach to Multitasking
Noga Alon, Jonathan D. Cohen, Biswadip Dey, Tom Griffiths, Sebastian Musslick, Kayhan Ozcimder, Daniel Reichman, Igor Shinkar, Tal Wagner · 2017-06-09
https://arxiv.org/abs/1611.02400
PDF source