Fugu-MT 論文翻訳(概要): A Zero-Knowledge PCP Theorem

論文の概要: A Zero-Knowledge PCP Theorem

arxiv url: http://arxiv.org/abs/2411.07972v1
Date: Tue, 12 Nov 2024 17:54:35 GMT
ステータス: 翻訳完了
システム内更新日: 2024-11-13 13:19:50.445596
Title: A Zero-Knowledge PCP Theorem
Title（参考訳）: ゼロ知識PCP理論
Authors: Tom Gur, Jack O'Connor, Nicholas Spooner,
Abstract要約: すべての q* に対して、NP に対する PCP が存在し、(適応的な) 敵に対する完全ゼロの知識であり、少なくとも NP* のクエリを証明できることが示される。さらに, NEXP に対する指数サイズの定数型 PCP を, 任意の時間的敵に対する完全なゼロ知識で構築する。
参考スコア（独自算出の注目度）: 5.278573457491116
License:
Abstract: We show that for every polynomial q* there exist polynomial-size, constant-query, non-adaptive PCPs for NP which are perfect zero knowledge against (adaptive) adversaries making at most q* queries to the proof. In addition, we construct exponential-size constant-query PCPs for NEXP with perfect zero knowledge against any polynomial-time adversary. This improves upon both a recent construction of perfect zero-knowledge PCPs for #P (STOC 2024) and the seminal work of Kilian, Petrank and Tardos (STOC 1997).
Abstract（参考訳）: 任意の多項式 q* に対して、NP に対して多項式サイズ、定数クエリ、非適応 PCP が存在し、これは証明にほとんどの q* クエリを課す (適応的) 敵に対する完全なゼロ知識である。さらに,任意の多項式時間対向に対する完全ゼロ知識を持つNEXPに対して,指数サイズの定数型PCPを構築する。これは最近、#P (STOC 2024) のための完全ゼロ知識 PCP の構築と、Kilian, Petrank and Tardos (STOC 1997) の独創的な仕事の両方を改善している。

関連論文リスト

Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文参考訳（メタデータ） (2024-08-14T19:04:13Z)
Perfect Zero-Knowledge PCPs for #P [5.278573457491116]
完全ゼロ知識確率的証明(PZK-PCP)を#Pのすべての言語に対して構築する。これは、BPP以外の言語向けのPZK-PCPの最初の構成である。
論文参考訳（メタデータ） (2024-03-18T16:36:09Z)
Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians [0.0]
非適応型量子PCPは、証明クエリ数が一定である場合に適応型量子PCPをシミュレートできることを示す。また、ある量子PCPステートメントが偽であるような(量子)オラクルが存在することも示している。
論文参考訳（メタデータ） (2024-03-07T19:00:06Z)
The Power of Lorentz Quantum Computer [6.9754404995027794]
本稿では,最近提案されたローレンツ量子コンピュータ(LQC)の,従来の量子コンピュータと比較して優れた性能を示す。計算複雑性クラス$text Psharp textP$を導入し、複雑性クラス$text Psharp textP$と等価性を実証する。 Aaronsonが提案したポストセレクションによる量子コンピューティングはLQCで効率的にシミュレートできるが、その逆ではない。
論文参考訳（メタデータ） (2024-03-07T03:00:09Z)
PPFlow: Target-aware Peptide Design with Torsional Flow Matching [52.567714059931646]
ペプチド構造設計のためのねじれ角の内部構造をモデル化するために,textscPPFlowと呼ばれるターゲット認識型ペプチド設計手法を提案する。さらに, PPBench2024というタンパク質-ペプチド結合データセットを構築した。
論文参考訳（メタデータ） (2024-03-05T13:26:42Z)
When is Agnostic Reinforcement Learning Statistically Tractable? [76.1408672715773]
エンフスパンニング容量と呼ばれる新しい複雑性測度は、設定された$Pi$にのみ依存し、MDPダイナミクスとは独立である。我々は、学習するためにスーパーポリノミカルな数のサンプルを必要とする制限付きスパンリング能力を持つポリシークラス$Pi$が存在することを示した。これにより、生成的アクセスとオンラインアクセスモデルの間の学習可能性の驚くほどの分離が明らかになる。
論文参考訳（メタデータ） (2023-10-09T19:40:54Z)
Find a witness or shatter: the landscape of computable PAC learning [63.26015736148707]
本稿では,最近の3つのオープンな質問を解き,CPAC学習可能性の研究に寄与する。まず,全てのCPAC学習可能なクラスが,サンプルの複雑さで適切なCPAC学習が可能なクラスに含まれることを証明した。第二に、適切に学習できるが、計算不能に急速に増加するサンプルの複雑さに限り、決定可能な仮説のクラスが存在することを示す。
論文参考訳（メタデータ） (2023-02-06T02:52:36Z)
Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文参考訳（メタデータ） (2022-09-28T17:53:25Z)
Controlling the Complexity and Lipschitz Constant improves polynomial nets [55.121200972539114]
多項式ネットの結合CP分解(CCP)モデルとNested Coupled CP分解(NCP)モデルに対する新しい複雑性境界を導出する。本研究では、6つのデータセットで実験的に評価し、モデルが逆摂動に対して頑健であるとともに精度も向上することを示す。
論文参考訳（メタデータ） (2022-02-10T14:54:29Z)
PCP Theorems, SETH and More: Towards Proving Sub-linear Time Inapproximability [7.8651861370959955]
分散PCP定理は任意の時間不近似性を証明するために一般化できるが、線形の場合失敗することを示す。線形時間アルゴリズムの研究の進展を考えると、線形時間近似アルゴリズムの研究を導く上では、サブ線形PCP定理が重要である。
論文参考訳（メタデータ） (2020-11-04T14:39:41Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。