13
votes
3answers
715 views

Can you cover the Boolean cube {0,1}^n with O(1) Hamming-balls each of radius n/2-c*sqrt(n)?

(where c>0 and the balls need not be disjoint?) This is an embarrassingly simple question, yet somehow I couldn't find an answer (not even, "this is a well-known open problem") after spending some ...