8
研究人员挫败随机性创建理想代码
source link: https://www.solidot.org/story?sid=69761
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
研究人员挫败随机性创建理想代码
假设你在尝试传输消息。将每个字符转换为比特，再将每个比特转换为信号。然后通过铜线、光纤或空气发送。尽你所能地小心，对方收到的内容也将和你发送的不同。噪声在破坏方面从不失手。在 1940 年代，计算机科学家首先遇到了不可避免的噪声问题。五十年之后，他们想出了一个优雅的方法来回避它：如果你可以对一条消息进行编码，若是它在你的收件人阅读之前被篡改了就会非常明显？不能通过封面判断一本书的好坏，但是信息可以。
他们将此属性称为局部可测试性（local testability），此类消息可以仅在几个部分进行超快速测试，就可以确定其正确性。接下来的 30 年里，研究人员在创建此类测试方面取得了实质性进展，但他们的努力总是棋差一着。许多人认为局部可测试性永远不会实现其理想形式。
现在在 11 月 8 日发布的一篇预印本论文中，魏茨曼科学研究所的计算机科学家 Irit Dinur和耶路撒冷希伯来大学的四位数学家 Shai Evra、Ron Livne、Alex Lubotzky 和 Shahar Mozes 找到了方法。“这是我所知道的数学或计算机科学领域最引人注目的现象之一，”华威大学的 Tom Gur 表示。“这是整个领域的圣杯。”
他们的新技术将消息转换成“超级金丝雀”，这种对象比已知的任何其他消息都更能证明自身的健康状况。在其上层结构任何地方隐藏的重大破坏经过在几个地方进行的简单测试都会变得非常明显。大多数早先的数据编码方法依赖于某种形式的随机性。但对于局部可测试性而言，随机性无能为力。研究人员不得不设计出一种高度非随机的全新图形结构。
他们将此属性称为局部可测试性（local testability），此类消息可以仅在几个部分进行超快速测试，就可以确定其正确性。接下来的 30 年里，研究人员在创建此类测试方面取得了实质性进展，但他们的努力总是棋差一着。许多人认为局部可测试性永远不会实现其理想形式。
现在在 11 月 8 日发布的一篇预印本论文中，魏茨曼科学研究所的计算机科学家 Irit Dinur和耶路撒冷希伯来大学的四位数学家 Shai Evra、Ron Livne、Alex Lubotzky 和 Shahar Mozes 找到了方法。“这是我所知道的数学或计算机科学领域最引人注目的现象之一，”华威大学的 Tom Gur 表示。“这是整个领域的圣杯。”
他们的新技术将消息转换成“超级金丝雀”，这种对象比已知的任何其他消息都更能证明自身的健康状况。在其上层结构任何地方隐藏的重大破坏经过在几个地方进行的简单测试都会变得非常明显。大多数早先的数据编码方法依赖于某种形式的随机性。但对于局部可测试性而言，随机性无能为力。研究人员不得不设计出一种高度非随机的全新图形结构。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK