論文の概要: An Exposition of GPT Astra's Proof of Lower Bound on DP Continual Counting

• arxiv url: http://arxiv.org/abs/2609.28528v1
• Date: Tue, 22 Sep 2026 17:21:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-25 21:10:09.382164
• Title: An Exposition of GPT Astra's Proof of Lower Bound on DP Continual Counting
• Title（参考訳）: DP連続計数におけるGPTアストラの下界証明
• Abstract要約: ハリソンとリーマンは純粋かつ近似DPの連続数え上げの両方に対して$(log3/2(n))$の低い境界を示すエレガントな証明を与えた。 その後、彼らは$(log2(n))$boundを公表し、これは現在、Bairaktari、Dahl、Larsenの共著である。 両者は技術的に異なるが、アストラの議論はベラクタリとラーセンで導入された関係木幾何学を用いている。
• 参考スコア（独自算出の注目度）: 9.120632918495595
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The goal of this note is to give a detailed proof, to the best of our understanding, of the recent presentation by Harrison and Leeman (arXiv:2609.17650v01 and arXiv:2609.17650v02) of the proof by Astra on the lower bound for differentially private continual counting. We believe a more natural and easy proof is possible and hope that this note will help in that effort. Prior to the initial preprint by Harrison and Leeman (arXiv:2609.17650v01), Bairaktari and Larsen (arXiv:2607.00876) gave an elegant proof to show a lower bound of $Ω(\log^{3/2}(n))$ for both pure and approximate-DP continual counting, and in personal communication had informed us that they have a proof of optimal $Ω(\log^{2}(n))$ for pure-differential private continual counting as well. They have subsequently published their $Ω(\log^{2}(n))$ bound, which is now a joint work of Bairaktari, Dahl, and Larsen (arXiv:2607.00876v3). Their new result is an elegant extension of their technique for approximate-differential privacy. Although the two proofs are technically different, the Astra argument uses related tree geometry introduced in Bairaktari and Larsen.
• Abstract（参考訳）: このノートの目的は、ハリソンとリーマンによる最近のプレゼンテーション (arXiv:2609.17650v01 と arXiv:2609.17650v02) の、Astra による証明の、微分的にプライベートな連続的な数え上げの下位境界における詳細な証明を提供することである。 私たちは、より自然で簡単な証明が可能であると信じており、このメモがその努力に役立つことを期待しています。 Harrison and Leeman (arXiv:2609.17650v01) による最初のプレプリントに先立って、Bairaktari と Larsen (arXiv:2607.00876) は、純DP連続数と近似DP連続数の両方に対して Ω(\log^{3/2}(n))$ の低い境界を示すエレガントな証明を行った。 その後、彼らは$Ω(\log^{2}(n))$boundを公表し、これは現在は Bairaktari, Dahl, and Larsen (arXiv:2607.00876v3) の共著である。 彼らの新しい結果は、近似微分プライバシーのためのテクニックのエレガントな拡張である。 2つの証明は技術的に異なるが、アストラの議論はベラクタリとラーセンで導入された関係木幾何学を用いている。

関連論文リスト

• Comments on the recent improvements of the MRRW bounds [59.04174294928297]
  本稿では,コードワードに付随する単一ベクトルを部分空間に置き換えるスペクトル法の拡張として,OpenAI証明を符号化理論の言語と文脈に提示する。 また、符号化理論の言語と文脈におけるOpenAI証明を、コードワードに付随する1つのベクトルを部分空間に置き換えるスペクトル法の拡張として提示する。
  論文  参考訳（メタデータ） (2026-09-01T20:43:23Z)
• AI-Assisted Discovery of Convex Relaxations via Dual Agents [56.60366723277675]
  すべての許容関数に対して下界が成り立ち、より強い境界を与える凸緩和から従うことを示す。 理論は各エージェントを検証し、反例を検索し、報告されたすべての境界はインターバルにおける明示的な二重実現可能な点によって認証される。
  論文  参考訳（メタデータ） (2026-06-30T06:10:25Z)
• Geometric Measurements of the Axiom of Choice in Neural Proof Embeddings [0.2538209532048866]
  我々はLean 4のカーネルレベルの公理依存性の追跡を用いて、選択の公理が証明空間に測定可能な幾何学的相関を持つことを示す。 このシグネチャは長さ,ファイル,著者,トピックコントロールに留まり,正規化証明源で訓練されたフルソースエンコーダの下で複製されることを示す。
  論文  参考訳（メタデータ） (2026-06-26T19:57:00Z)
• Towards a Doubly Efficient IP=PSPACE [7.597718642680558]
  PSPACEのすべての言語がチューリングマシンによって決定可能な時間$T(n)=nO(log n)$で決定可能であることを示す。 これは、そのような証明システムにおいて最もよく知られた体系を拡張している。
  論文  参考訳（メタデータ） (2026-06-19T23:32:02Z)
• Burau representation, Squier's form, and non-Abelian anyons [53.92822954974537]
  ブレイド群 $B_3$ のブラウ表現から構築した周波数可変2次元非アベリア的演算順序制御を導入する。 Squier 陽性ウィンドウの向こう側にある$Delta(omega)$の符号変更は、因果順序の交互に構成的かつ破壊的干渉を示す。 数値シミュレーションにより、拡張と抑制の両方が確認され、最小の$B_3$ブレイド制御が確立される。
  論文  参考訳（メタデータ） (2025-10-21T00:25:21Z)
• Simple Convergence Proof of Adam From a Sign-like Descent Perspective [58.89890024903816]
  我々は、Adamが以前の$cal O(fracln TTs14)$よりも$cal O(frac1Ts14)$の最適なレートを達成することを示す。 我々の理論分析は、収束を保証する重要な要因として運動量の役割に関する新たな洞察を提供する。
  論文  参考訳（メタデータ） (2025-07-08T13:19:26Z)
• Generating Natural Language Proofs with Verifier-Guided Search [74.9614610172561]
  NLProofS (Natural Language Proof Search) を提案する。 NLProofSは仮説に基づいて関連するステップを生成することを学習する。 EntailmentBank と RuleTaker の最先端のパフォーマンスを実現している。
  論文  参考訳（メタデータ） (2022-05-25T02:22:30Z)
• New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemma [10.176795938619417]
  統計的推定タスクの新たな下限を$(varepsilon, delta)$-differential privacyの制約の下で証明する。 フロベニウスノルムの推定には$Omega(d2)$サンプルが必要であり、スペクトルノルムでは$Omega(d3/2)$サンプルが必要である。
  論文  参考訳（メタデータ） (2022-05-17T17:55:10Z)
• Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling [49.43288037509783]
  ランダムシャッフルは、局所的ランダム化データの差分プライバシー保証を増幅する。 私たちの結果は、以前の作業よりも単純で、ほぼ同じ保証で差分プライバシーに拡張された新しいアプローチに基づいています。
  論文  参考訳（メタデータ） (2020-12-23T17:07:26Z)
• Parallel repetition with a threshold in quantum interactive proofs [0.0]
  O(log (1/epsilon)$ rounds of parallel repetition with a threshold suffice to reduce completeness and soundness error to $epsilon$ for single-proer quantum interactive proof systems。
  論文  参考訳（メタデータ） (2020-08-17T16:06:48Z)

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

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