Reversible Computation with Stacks and "Reversible Management of Failures"
この論文は、計算モデルを全単射として解釈可能にするための新しい言語「SCORE」を提案し、証明支援系を用いてスタック操作が全単射であることを検証することで、計算複雑性の研究に寄与する reversible 計算モデルの構築を示しています。
💻 Category
cs.CC
45 件の論文
When Relaxation Does Not Help: RLDCs with Small Soundness Yield LDCs
本論文は、線形符号の要件を排除し、特定の閾値以下の健全性誤差を持つクエリ緩和局所復号可能符号（RLDC）が同様のパラメータを持つクエリ局所復号可能符号（LDC）を構成することを示し、これによりRLDC、RLCC、およびPCPPに対する新たな下限を導出した。
Advances in List Decoding of Polynomial Codes
本書は、情報理論的な限界を超えた誤り訂正を可能にするリスト復号の概念、特に Reed-Solomon コードおよび関連する多項式ベースの符号における、最適なリストサイズと高速アルゴリズムを用いた情報理論容量までの効率的なリスト復号に関する近年の重要な進展を survey するものである。
Learning Read-Once Determinants and the Principal Minor Assignment Problem
この論文は、ランク 1 行列の和で表される行列式多項式（読み取り一回行列式）の学習問題と、主小行列式の割り当て問題（PMAP）の黒箱バージョンを結びつけ、両者をランダム化多項式時間で解くアルゴリズムを提案し、その核心として密行列の「ランク 1 拡張性」という性質を明らかにしたものである。
Quantum Algorithms for Approximate Graph Isomorphism Testing
この論文は、MNRS 量子ウォークを用いた近似グラフ同型性テストの量子アルゴリズムを提案し、のクエリ複雑度で古典的なの下限を超える多項式速度向上を証明するとともに、シミュレーションで近未来の量子デバイスとの互換性を示している。