$w$ of wires needed to compute any (asymptotically good) error-correcting code Tight Bounds on Computing Error-Correcting Codes by Bounded-Depth Circuits With Arbitrary Gates
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Information Theory >Tight Bounds on Computing Error-Correcting Codes by Bounded-Depth Circuits With Arbitrary Gates
【24h】

Tight Bounds on Computing Error-Correcting Codes by Bounded-Depth Circuits With Arbitrary Gates

机译：带任意门的有界电路计算纠错码的严格界限

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We bound the minimum number $w$ of wires needed to compute any (asymptotically good) error-correcting code $C:{0,1}^{Omega (n)}to{0,1}^{n}$ with minimum distance $Omega (n)$, using unbounded fan-in circuits of depth $d$ with arbitrary gates. Our main results are: 1) if $d=2$ , then $w=Theta (n ({lg n/lglg n})^{2})$; 2) if $d=3$ , then $w=Theta (nlglg n)$; 3) if $d=2k$ or $d=2k+1$ for some integer $kgeq 2$, then $w=Theta (nlambda_{k}(n))$ , where $lambda_{1}(n)=lceillg nrceil$, $lambda_{i+1}(n)=lambda_{i}^{ast}(n)$ , and the $ast$ operation gives how many times one has to iterate the function $lambda_{i}$ to reach a value at most 1 from the argument $n$; and 4) if $d=lg^{ast}n$ , then $w=O(n)$. For de- th $d=2$ , our $Omega (n ({lg n/lglg n})^{2})$ lower bound gives the largest known lower bound for computing any linear map. The upper bounds imply that a (necessarily dense) generator matrix for our code can be written as the product of two sparse matrices. Using known techniques, we also obtain similar (but not tight) bounds for computing pairwise-independent hash functions. Our lower bounds are based on a superconcentrator-like condition that the graphs of circuits computing good codes must satisfy. This condition is provably intermediate between superconcentrators and their weakenings considered before.
机译：我们绑定了计算任何（渐近良好的）纠错代码所需的最小数量的 $ w $ “ inline”> $ C：{0,1} ^ {Omega（n）}至{0,1} ^ {n} $ $ Omega（n）$ “ TeX”> $ d $ 带有任意门。我们的主要结果是：1）如果 $ d = 2 $ ，则 $ w = Theta（n（{lg n / lglg n}）^ {2}）$ ; 2）如果 $ d = 3 $ ，则 $ w = Theta（nlglg n）$ ; 3）如果 $ d = 2k $ 或 $ d = 2k + 1 $ 表示某些整数 $ kgeq 2 $ ，然后是 $ w = Theta（nlambda_ {k}（n））$ ，其中 $ lambda_ {1}（n）= lceillg nrceil $ ，<公式Formulatype =” inline“> $ lambda_ {i + 1}（n） = lambda_ {i} ^ {ast}（n）$ 和 $ ast $ 操作给出了必须重复多少次函数 $ lambda_ {i} $ 才能从中获得最多1的值参数 $ n $ ;和4）如果 $ d = lg ^ {ast} n $ ，则 $ w = O（n）$ 。对于 $ d = 2 $ ，我们的 $ Omega（n（{lg n / lglg n}）^ {2}）$ 下限给出了用于计算任何线性图的最大已知下限。上限意味着可以将我们的代码的（必要密度）生成器矩阵写为两个稀疏矩阵的乘积。使用已知的技术，我们还可以获得相似（但不严格）的边界来计算成对独立的哈希函数。我们的下限基于类似超级集中器的条件，计算良好代码的电路图必须满足该条件。可证明的是，这种情况介于超级集中器和之前考虑的削弱之间。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号