本サイトは 12 時間以上更新されていません（通常は 3 時間ごと）。以下の内容は最新でない可能性があります。
このページに条件に合う項目はありません（絞り込みはこのページ内のみ）。
説明量子優位性が計算複雑性に与える影響は限定的であることを示す論文
要約本論文は、量子性の証明（proofs of quantumness）と（量子検証者による）オブリビアス状態準備の計算複雑性上の意味を検討しています。著者らは、非決定的計算が容易である場合（P = NP）や、BQP = QCMA が成り立つ場合でも、これらが存在しうることを示す証拠を与えています。さらに、古典オラクルと単位オラクルを用いた分離結果を示し、その帰結として相対化証明に基づく暗号構成の限界に関する結論を導いています。
説明情報損失こそ必要：最悪ケース格子からの TC⁰ 擬似ランダム性
要約本論文は、秘密に依存する線形測定値のブロックに決定的な整数丸めを施し、その結果を格子の商に符号化する「代数的丸め学習（LAR）」を提案しています。多項式で有界なモジュラスと次元の下で、秘密に依存しない一様な公開行列上の決定的ラベルは、多項式個の古典的ランダム例に対して独立な一様ラベルと計算的に区別できないことを示しています。安全性は、一般の格子上で近似因子 Õ(q) の GapSVP および SIVP の量子最悪ケース困難性に基づいています。これにより、TC⁰ で鍵と入力を共同評価できる初の耐量子弱擬似ランダム関数が得られ、また雑音のない一様ランダム例から多項式サイズの二隠れ層 ReLU ネットワークを学習することの困難性も示されています。
注目点決定論的丸めによる学習型丸め（LAR）を提案し、最悪ケース格問題に基づくTC0擬似乱数関数と、二層ReLUネットワークの困難性を示したと作者は報告している。
説明局所エッジ秘匿下の部分グラフ計数における対話の効果：一回の追加ラウンドで精度を大きく改善
要約本論文は、対話型の局所エッジ差分プライバシー（LEDP）の下で、任意の無向グラフに対する（非誘導）部分グラフ計数を研究する。二ラウンドのアルゴリズム Linear Noise Cancellation（LNC）は、すべてのグラフで O(n^{k-3/2}/ε^ℓ) の誤差を達成し、対話が最悪ケースの精度を多項式的に改善しうることを示す。さらに、最大次数が既知の上限 d 以下のグラフに対する Predict and Correct（PC）枠組みと、それに対応する下界も示している。
注目点線形ノイズ除去法を提案し、2ラウンドの対話により三角形の加法誤差を√n倍改善、タイトな下界も示す。