ECCC-Report TR17-033https://eccc.weizmann.ac.il/report/2017/033Comments and Revisions published for TR17-033en-usTue, 28 Mar 2017 02:00:14 +0300
Revision 2
| The independence number of the Birkhoff polytope graph, and applications to maximally recoverable codes |
Daniel Kane,
Shachar Lovett,
Sankeerth Rao
https://eccc.weizmann.ac.il/report/2017/033#revision2Maximally recoverable codes are codes designed for distributed storage which combine quick recovery from single node failure and optimal recovery from catastrophic failure. Gopalan et al [SODA 2017] studied the alphabet size needed for such codes in
grid topologies and gave a combinatorial characterization for it.
Consider a labeling of the edges of the complete bipartite graph $K_{n,n}$ with labels coming from $F_2^d$ , that satisfies the following condition: for any simple cycle, the sum of the labels over its edges is nonzero. The minimal d where this is possible controls the alphabet size needed for maximally recoverable codes in $n×n$ grid topologies.
Prior to the current work, it was known that d is between $(\log n)^2$ and $n\logn$. We improve both bounds and show that d is linear in n. The upper bound is a recursive construction which beats the random construction. The lower bound follows by first relating the problem to the independence number of the Birkhoff polytope graph, and then providing tight bounds for it using the representation theory of the symmetric group.Tue, 28 Mar 2017 02:00:14 +0300https://eccc.weizmann.ac.il/report/2017/033#revision2
Revision 1
| The independence number of the Birkhoff polytope graph, and applications to maximally recoverable codes |
Daniel Kane,
Shachar Lovett,
Sankeerth Rao
https://eccc.weizmann.ac.il/report/2017/033#revision1Maximally recoverable codes are codes designed for distributed storage which combine quick recovery from single node failure and optimal recovery from catastrophic failure. Gopalan et al [SODA 2017] studied the alphabet size needed for such codes in
grid topologies and gave a combinatorial characterization for it.
Consider a labeling of the edges of the complete bipartite graph $K_{n,n}$ with labels
coming from $F_2^d$ , that satisfies the following condition: for any simple cycle, the sum
of the labels over its edges is nonzero. The minimal d where this is possible controls
the alphabet size needed for maximally recoverable codes in $n×n$ grid topologies.
Prior to the current work, it was known that d is between $(log n)^2$ and $nlogn$. We
improve both bounds and show that d is linear in n. The upper bound is a recursive
construction which beats the random construction. The lower bound follows by first
relating the problem to the independence number of the Birkhoff polytope graph, and
then providing tight bounds for it using the representation theory of the symmetric
group.Tue, 28 Mar 2017 01:55:50 +0300https://eccc.weizmann.ac.il/report/2017/033#revision1
Paper TR17-033
| Labeling the complete bipartite graph with no zero cycles |
Daniel Kane,
Shachar Lovett,
Sankeerth Rao
https://eccc.weizmann.ac.il/report/2017/033Assume that the edges of the complete bipartite graph $K_{n,n}$ are labeled with elements of $\mathbb{F}_2^d$, such that the sum over
any simple cycle is nonzero. What is the smallest possible value of $d$? This problem was raised by Gopalan et al. [SODA 2017] as it characterizes the alphabet size needed for maximally recoverable codes in grid topologies.
We show that the answer is that $d$ is linear in $n$. The upper bound is an explicit construction which improves upon the random construction. The lower bound is more technical, and relies on the study of independent sets in certain Cayley graphs of the permutation group.
Sun, 19 Feb 2017 20:38:32 +0200https://eccc.weizmann.ac.il/report/2017/033