文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > Parity check matrices and product representations of squares
侵权投诉

Parity check matrices and product representations of squares

Let NF(n, k, r) denote the maximum number of columns in an n-row matrix with entries in a finite field F in which each column has at most r nonzero entries and every k columns are linearly independent over F. We obtain near-optimal upper bounds for NF(n, k

Paritycheckmatricesandproductrepresentationsofsquares

AssafNaor

MicrosoftResearch

anaor@microsoft.comJacquesVerstra¨eteUniversityofWaterloojverstra@math.uwaterloo.ca

Abstract

LetNF(n,k,r)denotethemaximumnumberofcolumnsinann-rowmatrixwithentriesina nite eldFinwhicheachcolumnhasatmostrnonzeroentriesandeverykcolumnsarelinearlyindependentoverF.Weobtainnear-optimalupperboundsforNF(n,k,r)inthecasercrk>r.Namely,weshowthatNF(n,k,r) n+wherec≈4

forlargek.Ourmethodis

basedonanovelreductionoftheproblemtotheextremalproblemforcyclesingraphs,andyieldsafastalgorithmfor ndingshortlineardependences.Wepresentadditionalapplicationsofthismethodtoproblemsinextremalhypergraphtheoryandcombinatorialnumbertheory.“Itiscertainlyoddtohaveaninstructioninanalgorithmaskingyoutoplaywithsomenumbersto ndasubsetwithproductasquare...Whyshouldweexpectto ndsuchasubsequence,and,ifitexists,howcanwe ndite ciently?”

CarlPomerance[32].1IntroductionSincethemid-1930sithasbeenwellestablishedthatthereisatightconnectionbetweencombi-natorialnumbertheoryandextremalcombinatorics(see[33,12]andthereferencestherein).Thebasicparadigmisthatforcertainnumbertheoreticalproblemsonecanconstructacombinatorialobject(e.g.agraphorahypergraph),andprovethatitcannotcontaincertaincon gurations(e.g.cycles).Thus,inmanycasesonecanusetheoremsonexcludedcon gurationsinextremalcombi-natoricstoboundthesizeofthecombinatorialstructurethatwasconstructed,andthistranslatesbacktogivenumbertheoreticalconsequences.Thepresentpaperdevelopsanovelreductionofthistype,andappliesittotwoproblemsinalgebraiccombinatorics,namelytocodingtheoryandcombinatorialnumbertheory.Additionally,ourproofsareconstructive,andthusyieldthebestknownalgorithmsforseveralnaturalcomputationalproblems.

Ouroriginalmotivationcomesfromaproblemincodingtheory.LowdensityparitycheckcodeswereintroducedbyGallagerinthe1960s,andhavesincefoundnumeroustheoreticalandpracticalapplicationsinengineeringandcomputerscience(see[22,29,30]foranaccountofthistheory.Wealsoreferto[11]foraniceintroductiontothegeometryofcodes).GivenalinearcodeC Fm2ofdimension andminimumHammingweightt,an(m )×mmatrixHiscalledaparitycheckmatrixofthecodeCifC={v∈Fm2:Hv=0}.WeshallsaythatHisr-sparseifeverycolumnofHhasatmostrnon-zeroentries.TheSyndromeDecodingAlgorithmforsuchcodesworksasfollows:givenacorruptedsignalzonecomputesthevectorxofminimalweight

1

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email