The independence number of the Birkhoff polytope graph, and applications to maximally recoverable codes

DOI10.1137/18M1205856zbMATH Open1419.05217arXiv1702.05773MaRDI QIDQ5232331FDOQ5232331

Authors: Daniel M. Kane, Shachar Lovett, Sankeerth Rao 

Publication date: 2 September 2019

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Abstract: Maximally 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 x n grid topologies. Prior to the current work, it was known that d is between $(logn{)}^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.

Full work available at URL: https://arxiv.org/abs/1702.05773

Recommendations

• New bounds on the field size for maximally recoverable codes instantiating grid-like topologies
• Locally recoverable codes from planar graphs
• Tighter bounds on the independence number of the Birkhoff graph
• Low-density MDS codes and factors of complete graphs
• Maximally Recoverable Codes for Grid-like Topologies

zbMATH Keywords

Birkhoff polytoperepresentation theorycoding theorymaximally recoverable codes

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Combinatorial aspects of representation theory (05E10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Representations of finite symmetric groups (20C30) Theory of error-correcting codes and error-detecting codes (94B99)

Cites Work

• Title not available (Why is that?)
• Geometry, complexity, and combinatorics of permutation polytopes
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Family of Optimal Locally Recoverable Codes
• Explicit Maximally Recoverable Codes With Locality
• Bipartite perfect matching is in quasi-NC
• Maximally Recoverable Codes for Grid-like Topologies

Cited In (4)

• New bounds on the field size for maximally recoverable codes instantiating grid-like topologies
• Sparse MDS Matrices over Small Fields: A Proof of the GM-MDS Conjecture
• Tighter bounds on the independence number of the Birkhoff graph
• Improved covering results for conjugacy classes of symmetric groups via hypercontractivity

This page was built for publication: The independence number of the Birkhoff polytope graph, and applications to maximally recoverable codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5232331)