Reversible Computation with Stacks and "Reversible Management of Failures"
本文介绍了名为 SCORE 的语言，并通过证明辅助工具在特定状态空间中验证了栈操作为全双射函数，从而实现了将计算模型中的项解释为全双射函数，而非传统的部分双射函数。
💻 Category
cs.CC
45 篇论文
When Relaxation Does Not Help: RLDCs with Small Soundness Yield LDCs
本文通过移除线性码限制并推广至非自适应解码器及局部可纠错码场景，证明了具有小声错率的-查询松弛局部可解码码（RLDC）必然可转化为具有相当参数的标准-查询局部可解码码（LDC），从而改进了相关下界并深化了对两者关系的理解。
Advances in List Decoding of Polynomial Codes
本书综述了近年来在多项式码（特别是 Reed-Solomon 码）列表解码领域的重大进展，包括实现信息论容量下的最优列表大小以及高效、近乎线性甚至次线性时间的解码算法。
Learning Read-Once Determinants and the Principal Minor Assignment Problem
本文提出了一种随机多项式时间算法，通过研究稠密矩阵的“秩一扩展性质”解决了黑盒主元分配问题，并证明了该问题与学习读一次行列式（RODs）在随机多项式时间内是等价的。
Quantum Algorithms for Approximate Graph Isomorphism Testing
该论文提出了一种基于 MNRS 量子行走的近似图同构测试量子算法，在 Erdős–Rényi 随机图模型下实现了 的查询复杂度，并通过证明经典下界为 确立了多项式量子加速。