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?

  • 3
    $\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$ Commented Aug 28, 2013 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$ Commented May 28, 2019 at 17:43
  • 1
    $\begingroup$ Is there a clear relationship between the different questions in this post? $\endgroup$
    – usul
    Commented May 30, 2019 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$
    – Turbo
    Commented May 30, 2019 at 13:26
  • 1
    $\begingroup$ I'm not sure that locally decodable codes are associated with a different channel model. $\endgroup$ Commented May 30, 2019 at 19:26


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.