論文の概要: When Pebbles Are Not Atomic: A Polynomial Separation Between Pure and Entangled Pebbling

• arxiv url: http://arxiv.org/abs/2610.27249v1
• Date: Mon, 19 Oct 2026 20:21:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-21 21:58:47.493146
• Title: When Pebbles Are Not Atomic: A Polynomial Separation Between Pure and Entangled Pebbling
• Title（参考訳）: Pebbleが原子的でないとき:純度と絡み合ったペブリングをポリノミカルに分離する
• Abstract要約: 論文の核心は単純なゲームであり、アロン、モイトラ、スダコフによって発見された特別なクラスグラフと並んでいる。 エンコードされた情報を全値ではなく格納する敵は、より良くできるが、今のところは小さな要因によってのみ可能であることが知られている。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph pebbling is the model in which the memory cost of memory-hard functions and proofs of space is measured, and pebbling lower bounds are the main way to argue that such constructions are secure. It has long seemed that the model is faithful to reality. It is known that it is not exact: an adversary who stores encoded information instead of whole values can do better, but so far only by small factors: a factor of 1.5 in the work that introduced entangled pebbling (Alwen, Chen, Kamath, Kolmogorov, Pietrzak and Tessaro) and, recently, a factor of about log n/log log n (de Rezende, Engström and Reyzin). One could still hope that pebbling is right up to such small factors. In pure pebbling, memory consists of whole labels; entangled pebbling also allows encoded state, such as XORs of labels. We show that the two models can differ polynomially. We study the setting in which proofs of space and data-dependent memory-hard functions are used: a state is prepared in advance, a random challenge has to be answered from it, and memory is paid for as long as it is held. Our graphs are explicit and have indegree two, and on them a pure adversary can do no better, up to a constant factor, than storing every possible answer in advance. Still, an adversary who keeps XORs instead of labels pays polynomially less. This ends the hope that pure pebbling is a faithful model of memory up to small factors. The heart of the paper is a simple combinatorial game, together with a special class of graphs found by Alon, Moitra and Sudakov.
• Abstract（参考訳）: グラフペブブリング(Graph pebbling)は、メモリハード関数のメモリコストと空間の証明を計測するモデルであり、そのような構造が安全であると主張する主要な方法である。 そのモデルは長い間、現実に忠実であるように思われてきた。 エンコードされた情報を全値の代わりに保存する敵は、より良くできるが、今のところは、絡み合った小冊子(Alwen, Chen, Kamath, Kolmogorov, Pietrzak, Tessaro)を導入した仕事における1.5の因子と、最近ではlog n/log log n (de Rezende, Engström, Reyzin) に関する因子がある。 ペブブリングがこのような小さな要因に直結していることを願う人もいるだろう。 純粋なペブブリングでは、メモリはラベル全体で構成され、絡み合ったペブブリングはラベルのXORのようなエンコードされた状態も可能にする。 2つのモデルが多項式的に異なることを示す。 空間とデータに依存したメモリハード関数の証明を事前に用意し、ランダムな課題を解決し、メモリが保持される限り、メモリを支払わなければならないという設定について検討する。 私たちのグラフは明示的で、インディグリーが2つあり、それらの上では、すべての可能な答えを事前に保存するよりも、一定の要素まで、純粋に逆転する方がよい。 それでも、ラベルの代わりにXORを保持する敵は多項式を減らしている。 これにより、純粋なペブブリングがメモリの忠実なモデルである、という希望を、小さな要素にまとめることができます。 論文の心臓は単純な組合せゲームであり、アロン、モイトラ、スダコフによって発見されたグラフの特別なクラスと並んでいる。

関連論文リスト

• Intrinsic Associative Memory on Riemannian Manifolds: Curvature, Capacity, and Emergent Modes [4.879561806094711]
  本稿では,曲率をデータの性質ではなく,連想メモリの設計変数であることを示す。 我々の研究は、曲率が単なるデータの性質ではなく、連想メモリの設計変数であることを示している。
  論文  参考訳（メタデータ） (2026-09-28T17:03:18Z)
• The Memory Trust Gap: Capability-Dependent Failures in Persistent-Memory Agents [0.0]
  永続メモリはパーソナライズされたエージェントをサポートするが、古い保存された事実は警告なしで現在の信頼できる証拠をオーバーライドすることができる。 モデル能力が変化するにつれて、この害がいつ始まるかを研究する。
  論文  参考訳（メタデータ） (2026-09-01T20:35:00Z)
• What to Keep, What to Forget: A Rate--Distortion View of Memory Compaction in LLMs and Agents [1.0742675209112622]
  4つの研究コミュニティがそれぞれ,大規模言語メモリのコンパクト化を学んでいることを示す。 我々は、これらが1つの問題の例であると主張する。 このレンズを1つのコンパクト化目標と層に依存しない下界で正確にし、スタック全体からメソッドを一様に分類する7軸分類法を構築するために使用する。
  論文  参考訳（メタデータ） (2026-07-09T01:15:03Z)
• Sharp Capacity Thresholds in Linear Associative Memory: From Winner-Take-All to Listwise Retrieval [59.859592671274704]
  $dtimes d$ リニアメモリストアはいくつのキー値アソシエーションが可能ですか? この答えは、メモリマトリックスの$d2$自由度だけでなく、検索基準にも依存する。
  論文  参考訳（メタデータ） (2026-05-06T17:53:20Z)
• Simple linear attention language models balance the recall-throughput tradeoff [60.06020449520365]
  線形およびすべり窓の注意を結合したシンプルなアーキテクチャであるBASEDを提案する。 我々は、最大1.3bパラメータの言語モデルをトレーニングし、BASEDがパープレキシティにおいて最強のサブクワッドラティックモデルと一致し、実世界のリコール集約タスクにおいて6.22の精度ポイントでそれらのモデルを上回っていることを示す。
  論文  参考訳（メタデータ） (2024-02-28T19:28:27Z)
• Associative Memories in the Feature Space [68.1903319310263]
  本稿では,低次元のセマンティック埋め込みのみを記憶するメモリモデルを提案する。 MNISTデータセット上の単純なタスクに対して,本手法の概念実証を行う。
  論文  参考訳（メタデータ） (2024-02-16T16:37:48Z)
• Connes implies Tsirelson: a simple proof [91.3755431537592]
  コンヌ埋め込み問題は同期的ツィレルソン予想を意味することを示す。 また、コンネスの代数 $mathcalRomega$ の異なる構成もコンネス埋め込み問題に現れる。
  論文  参考訳（メタデータ） (2022-09-16T13:59:42Z)
• Causal Expectation-Maximisation [70.45873402967297]
  ポリツリーグラフを特徴とするモデルにおいても因果推論はNPハードであることを示す。 我々は因果EMアルゴリズムを導入し、分類的表現変数のデータから潜伏変数の不確かさを再構築する。 我々は、反事実境界が構造方程式の知識なしにしばしば計算できるというトレンドのアイデアには、目立たずの制限があるように思える。
  論文  参考訳（メタデータ） (2020-11-04T10:25:13Z)
• A Weaker Faithfulness Assumption based on Triple Interactions [89.59955143854556]
  より弱い仮定として, 2$-adjacency faithfulness を提案します。 より弱い仮定の下で適用可能な因果発見のための音方向規則を提案する。
  論文  参考訳（メタデータ） (2020-10-27T13:04:08Z)
• Concise Fuzzy Planar Embedding of Graphs: a Dimensionality Reduction Approach [0.2867517731896504]
  グラフ表現を$k$次元空間にマッピングし、主にユークリッド距離を測定することによって近隣ノードの問い合わせに答える。 答えの正確さは低下するが、ファジィ論理によって補償される。
  論文  参考訳（メタデータ） (2018-03-08T14:44:56Z)

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

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