論文の概要: A Survey of Interactive Verifiable Computing: Utilizing Low-degree Polynomials

• arxiv url: http://arxiv.org/abs/2501.05500v1
• Date: Thu, 09 Jan 2025 18:42:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-13 15:25:50.968596
• Title: A Survey of Interactive Verifiable Computing: Utilizing Low-degree Polynomials
• Title（参考訳）: 低次多項式を用いた対話型検証コンピューティングのサーベイ
• Authors: Angold Wang,
• Abstract要約: この調査は、その進化を複雑性理論から現代のゼロ知識の知識の非対話的議論へと遡る。 我々は,対話型証明システム,知識,低次誤り検出・検証プロトコルの適用における重要な発展について検討する。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: This survey provides a comprehensive examination of verifiable computing, tracing its evolution from foundational complexity theory to modern zero-knowledge succinct non-interactive arguments of knowledge (ZK-SNARKs). We explore key developments in interactive proof systems, knowledge complexity, and the application of low-degree polynomials in error detection and verification protocols. The survey delves into essential mathematical frameworks such as the Cook-Levin Theorem, the sum-check protocol, and the GKR protocol, highlighting their roles in enhancing verification efficiency and soundness. By systematically addressing the limitations of traditional NP-based proof systems and then introducing advanced interactive proof mechanisms to overcome them, this work offers an accessible step-by-step introduction for newcomers while providing detailed mathematical analyses for researchers. Ultimately, we synthesize these concepts to elucidate the GKR protocol, which serves as a foundation for contemporary verifiable computing models. This survey not only reviews the historical and theoretical advancements in verifiable computing over the past three decades but also lays the groundwork for understanding recent innovations in the field.
• Abstract（参考訳）: このサーベイは、基礎複雑性理論から現代のゼロ知識簡潔な知識の非対話的議論(ZK-SNARKs)への進化を追究し、検証可能な計算の包括的な検証を提供する。 本稿では,対話型証明システム,知識複雑性,および誤り検出・検証プロトコルにおける低次多項式の適用について検討する。 この調査は、Cook-Levin Theorem、sum-checkプロトコル、GKRプロトコルといった重要な数学的フレームワークを掘り下げ、検証効率と音質の向上における彼らの役割を強調した。 従来のNPベースの証明システムの限界を体系的に解決し、それらを克服するための高度な対話的証明機構を導入することで、この研究は、研究者に詳細な数学的解析を提供しながら、新参者に対してアクセス可能なステップバイステップの導入を提供する。 最終的に、これらの概念を合成し、現代の検証可能なコンピューティングモデルの基礎となるGKRプロトコルを解明する。 この調査は、過去30年間に検証可能なコンピューティングの歴史的および理論的進歩をレビューするだけでなく、この分野における最近のイノベーションを理解するための基礎を築き上げている。

関連論文リスト

• Networks of Networks: Complexity Class Principles Applied to Compound AI Systems Design [63.24275274981911]
  多くの言語モデル推論コールからなる複合AIシステムは、ますます採用されている。 本研究では,提案した回答の生成と正当性検証の区別を中心に,ネットワークネットワーク(NoN)と呼ばれるシステムを構築した。 我々は,Kジェネレータを備えた検証器ベースの判定器NoNを導入し,"Best-of-K"あるいは"judge-based"複合AIシステムのインスタンス化を行う。
  論文  参考訳（メタデータ） (2024-07-23T20:40:37Z)
• Riemannian Geometry-Based EEG Approaches: A Literature Review [1.9411911000346784]
  我々は、BCIにおける脳波信号デコーディングを強化するために、ディープラーニングとリーマン幾何学の統合の最近の進歩を概観する。 これらの手法は、従来のノイズ感度、非定常性、長大な校正時間といった課題にどのように対処するかについて議論する。 本稿では,多様体学習とリーマン分類における今後の研究方向を提案する。
  論文  参考訳（メタデータ） (2024-07-19T13:28:29Z)
• Computational Entanglement Theory [11.694169299062597]
  計算エンタングルメント理論は、計算複雑性における量子情報理論のアイデアの有用性に着想を得たものである。 本研究では,それらの間隙を提示することにより,計算量と情報理論的尺度とが根本的に異なることを示す。 本稿では、量子暗号や擬エントロピーの概念など、計算エンタングルメント理論と他のトピックとの関係について論じる。
  論文  参考訳（メタデータ） (2023-10-04T12:53:04Z)
• Multivariate Time Series Anomaly Detection: Fancy Algorithms and Flawed Evaluation Methodology [2.043517674271996]
  本稿では、MVTS異常検出の文脈において、正常によいプロトコルが弱点を持つ可能性について論じる。 本稿では,PCA(Principal Components Analysis)に基づくシンプルな,かつ難しいベースラインを提案する。このベースラインは,最近のDeep Learning(DL)ベースのアプローチにおいて,一般的なベンチマークデータセットよりも驚くほど優れています。
  論文  参考訳（メタデータ） (2023-08-24T20:24:12Z)
• A Parameterized Theory of PAC Learning [19.686465068713467]
  おそらく略正(PAC)学習は、サンプル複雑性理論の中核的な概念である。 我々は、パラメータ化複雑性の要素を組み込んだ最近のPAC学習結果に新たな光を当てることができるパラメータ化PAC学習の理論を開発した。
  論文  参考訳（メタデータ） (2023-04-27T09:39:30Z)
• Rethinking Complex Queries on Knowledge Graphs with Neural Link Predictors [58.340159346749964]
  本稿では,証明可能な推論能力を備えた複雑なクエリを用いたエンドツーエンド学習を支援するニューラルシンボリック手法を提案する。 これまでに検討されていない10種類の新しいクエリを含む新しいデータセットを開発する。 提案手法は,新しいデータセットにおいて先行手法を著しく上回り,既存データセットにおける先行手法を同時に上回っている。
  論文  参考訳（メタデータ） (2023-04-14T11:35:35Z)
• Validation Diagnostics for SBI algorithms based on Normalizing Flows [55.41644538483948]
  本研究は,NFに基づく多次元条件(後)密度推定器の検証診断を容易にすることを提案する。 また、局所的な一貫性の結果に基づいた理論的保証も提供する。 この作業は、より良い特定モデルの設計を支援したり、新しいSBIアルゴリズムの開発を促進するのに役立つだろう。
  論文  参考訳（メタデータ） (2022-11-17T15:48:06Z)
• Credit Assignment in Neural Networks through Deep Feedback Control [59.14935871979047]
  ディープフィードバックコントロール(Deep Feedback Control, DFC)は、フィードバックコントローラを使用して、望ましい出力ターゲットにマッチするディープニューラルネットワークを駆動し、クレジット割り当てに制御信号を使用する新しい学習方法である。 学習規則は空間と時間において完全に局所的であり、幅広い接続パターンに対するガウス・ニュートンの最適化を近似する。 さらに,DFCと皮質錐体ニューロンのマルチコンパートメントモデルと,局所的な電圧依存性のシナプス可塑性規則を関連づける。
  論文  参考訳（メタデータ） (2021-06-15T05:30:17Z)
• Towards Interaction Detection Using Topological Analysis on Neural Networks [55.74562391439507]
  ニューラルネットワークでは、あらゆる相互作用する特徴は共通の隠蔽ユニットとの強い重み付けの接続に従う必要がある。 本稿では, 永続的ホモロジーの理論に基づいて, 相互作用強度を定量化するための新しい尺度を提案する。 PID(Persistence Interaction Detection)アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2020-10-25T02:15:24Z)
• Provably Efficient Exploration for Reinforcement Learning Using Unsupervised Learning [96.78504087416654]
  強化学習(RL)問題における効率的な探索に教師なし学習を用い,本パラダイムが有効であるかどうかを考察する。 本稿では,教師なし学習アルゴリズムと非線形表RLアルゴリズムという,2つのコンポーネント上に構築された汎用的なアルゴリズムフレームワークを提案する。
  論文  参考訳（メタデータ） (2020-03-15T19:23:59Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。