7
$\begingroup$

Conventional coding theory provides a good geometric picture behind linear error correction codes in terms of Hamming distance. What additional geometric requirement one should add to make a code locally decodable?

In other words what channel model does locally decodable code try to solve? Where does it fit in Shannon theory?

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ I am not an expert, but afaik we don't have nearly as nice a picture. Klim Efremenko has some work on connections to representation theory cs.tau.ac.il/~klim/papers/Induced.pdf. Representation theory itself seeks to understand the structure of groups through geometry, by studying actions of the group on a vector space. $\endgroup$
    – Sasho Nikolov
    Aug 28 '13 at 3:45
  • $\begingroup$ @SashoNikolov representation theory also seeks to better understand vector spaces - and other objects - with additional symmetries by leveraging the symmetries. (understanding the groups themselves is just one application, albeit a particularly fruitful one :).) $\endgroup$
    – Joshua Grochow
    May 28 '19 at 17:43
  • $\begingroup$ Is there a clear relationship between the different questions in this post? $\endgroup$
    – usul
    May 30 '19 at 13:09
  • $\begingroup$ Shannon theory tells that there is atleast one geometrization mechanism which assigns a metric that comes with each channel by giving provide capacity results when we use the correct metric. Coding is incarnation that depends on the creativity of the instantiator of those purported geometrization mechanisms and without the full picture the instantiator always fall short of the promise of capacity results unless by good fortune. $\endgroup$
    – Mr.
    May 30 '19 at 13:26
  • $\begingroup$ I'm not sure that locally decodable codes are associated with a different channel model. $\endgroup$
    – Peter Shor
    May 30 '19 at 19:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.