We construct locally decodable codes (LDCs) to correct insertion-deletion errors in the setting where the sender and receiver share a secret key or where the channel is resource-bounded. Our constructions rely on a so-called "Hamming-to-InsDel" compiler (Ostrovsky and Paskin-Cherniavsky, ITS '15 & Block et al., FSTTCS '20), which compiles any locally decodable Hamming code into a locally decodable code resilient to insertion-deletion (InsDel) errors. While the compilers were designed for the classical coding setting, we show that the compilers still work in a secret key or resource-bounded setting. Applying our results to the private key Hamming LDC of Ostrovsky, Pandey, and Sahai (ICALP '07), we obtain a private key InsDel LDC with constant rate and polylogarithmic locality. Applying our results to the construction of Blocki, Kulkarni, and Zhou (ITC '20), we obtain similar results for resource-bounded channels; i.e., a channel where computation is constrained by resources such as space or time.


翻译:我们在发送者和接收者共享秘密密钥或频道受资源约束的设置中建立本地可下载代码(LDC),以纠正在发送者和接收者共享秘密密钥或频道受资源约束的设置中插入删除错误。我们的构造依赖于所谓的“Hamming-InsDel”编译器(Ostrovsky和Paskin-Cherniavsky,ITS '15 & Block等人,FSTTCS '20),该代码将任何本地可下载的含汞代码编译成一个适合插入删除错误的本地可下载代码。虽然编译器是为经典编码设置设计的,但我们显示编译者仍然在一个秘密密钥或受资源约束的设置中工作。将我们的成果应用到Ostrovsky、Pandey和Sahai的私人密钥Hamming最不发达国家(ICCAP '07),我们得到了一个具有恒定速率率和多logy位置的InsDel最不发达国家的私人密钥。将我们的结果应用到布基、Kulkarni和Zhou(IT20)的构建中,但我们获得类似的时间将空间用于这样的频道。

0
下载
关闭预览

相关内容

编译器(Compiler),是一种计算机程序,它会将用某种编程语言写成的源代码(原始语言),转换成另一种编程语言(目标语言)。
专知会员服务
60+阅读 · 2020年3月19日
【阿里巴巴】 AI编译器,AI Compiler @ Alibaba,21页ppt
专知会员服务
44+阅读 · 2019年12月22日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
【数字化】探索制造业数字化转型的新路径
产业智能官
5+阅读 · 2019年10月28日
Hierarchically Structured Meta-learning
CreateAMind
25+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
随波逐流:Similarity-Adaptive and Discrete Optimization
我爱读PAMI
5+阅读 · 2018年2月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Meta-Transfer Learning for Few-Shot Learning
Arxiv
8+阅读 · 2018年12月6日
Arxiv
5+阅读 · 2017年12月14日
Arxiv
3+阅读 · 2017年10月1日
VIP会员
相关资讯
【数字化】探索制造业数字化转型的新路径
产业智能官
5+阅读 · 2019年10月28日
Hierarchically Structured Meta-learning
CreateAMind
25+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
随波逐流:Similarity-Adaptive and Discrete Optimization
我爱读PAMI
5+阅读 · 2018年2月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员