論文の概要: Shuffling Cards When You Are of Very Little Brain: Low Memory Generation of Permutations

• arxiv url: http://arxiv.org/abs/2505.01287v2
• Date: Sat, 07 Jun 2025 16:05:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-10 21:10:46.967974
• Title: Shuffling Cards When You Are of Very Little Brain: Low Memory Generation of Permutations
• Title（参考訳）: 非常に小さな脳のときカードをシャッフルする
• Authors: Boaz Menuhin, Moni Naor,
• Abstract要約: 置換のジェネレータはメモリが限られており、"Guesser"はメモリが無制限である。 任意の$m$-bit Dealerに対して、期待して$Omega(n/m+log m)$正しい推測を達成できる(計算的に強力な)推測器が存在することを示す。
• 参考スコア（独自算出の注目度）: 3.388546694531524
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: How can we generate a permutation of the numbers $1$ through $n$ so that it is hard to guess the next element given the history so far? The twist is that the generator of the permutation (the ``Dealer") has limited memory, while the ``Guesser" has unlimited memory. With unbounded memory (actually $n$ bits suffice), the Dealer can generate a truly random permutation where $\ln n$ is the expected number of correct guesses. Our main results establish tight bounds for the relationship between the guessing probability and the memory $m$ required to generate the permutation. We suggest a method for an $m$-bit Dealer that operates in constant time per turn, and any Guesser can pick correctly only $O(n/m+\log m)$ cards in expectation. The method is fully transparent, requiring no hidden information from the Dealer (i.e., it is "open book" or "whitebox"). We show that this bound is the best possible, even with secret memory. Specifically, for any $m$-bit Dealer, there is a (computationally powerful) guesser that achieves $\Omega(n/m+\log m)$ correct guesses in expectation. We point out that the assumption that the Guesser is computationally powerful is necessary: under cryptographic assumptions, there exists a low-memory Dealer that can fool any computationally bounded guesser. We also give an $O(n)$ bit memory Dealer that generates perfectly random permutations and operates in constant time per turn.
• Abstract（参考訳）: これまでの歴史から次の要素を推測するのが難しいように、どうやって$$$から$n$の数字の置換を生成することができるのか? ツイストは、置換のジェネレータ( ``Dealer)が制限メモリを持ち、 ``Guesser" は無制限メモリである。 非有界メモリ(実際には$n$ bits suffice)を使用すると、Dealerは真にランダムな置換を生成することができる。 我々の主な結果は、推測確率と置換を生成するために必要なメモリ$m$の関係について厳密な境界を定めている。 任意のGuesserが正しく選択できるのは$O(n/m+\log)のみである。 m) 予想で$カード。 この方法は完全透明であり、ディーラーから隠された情報を必要としない(すなわち「オープンブック」または「ホワイトボックス」)。 このバウンダリは、秘密のメモリでさえ、可能な限り最良のものであることを示す。 具体的には、任意の$m$-bit Dealerに対して、$\Omega(n/m+\logを達成する(計算的に強力な)推測器がある。 m) 予想の正しい推測。 我々は、Guesserが計算的に強力であるという仮定が不可欠である:暗号的な仮定の下では、どんな計算的に有界な推測者も騙せる低メモリのDealerが存在する。 また、$Oを与えます。 (n)$bitMemory Dealer 完全にランダムな置換を生成し、ターン毎に一定時間動作させる。

関連論文リスト

• Optimal Computational Secret Sharing [51.599517747577266]
  $(t, n)$-threshold secret sharingでは、秘密の$S$が$n$の参加者に分散される。 共有サイズが $tfrac|S|t + |K|t$ となる構成を示す。
  論文  参考訳（メタデータ） (2025-02-04T23:37:16Z)
• Pseudorandom Permutations from Random Reversible Circuits [1.9567015559455132]
  固定された最寄りのアーキテクチャにおいて,各層が$approx n/3$のランダムゲートからなる深さ$n cdot tildeO(k2)$のランダム回路がほぼ$k$の独立な置換をもたらすことを示す。 また、擬似乱数関数からの擬似乱数置換のLuby-Rack-off構成は可逆回路で実装可能であることを示す。
  論文  参考訳（メタデータ） (2024-04-23T00:50:57Z)
• A Construction of Evolving $k$-threshold Secret Sharing Scheme over A Polynomial Ring [55.17220687298207]
  閾値秘密共有方式により、ディーラーは、秘密が一定量の株式から正しく回収されたことをすべての参加者に分配することができる。 我々は、リング上の$ell$-bitシークレットのための、進化する$k$-thresholdシークレット共有スキームを、正確性と完全なセキュリティで新たに構築することを提案する。
  論文  参考訳（メタデータ） (2024-02-02T05:04:01Z)
• Memory-Query Tradeoffs for Randomized Convex Optimization [16.225462097812766]
  単位球上の$d$-dimensional, $1$-Lipschitz convex関数を最小化するランダム化1次アルゴリズムは、メモリビットの$Omega(d2-delta)か、$Omega(d1+delta/6-o(1))の$クエリを使わなければならない。
  論文  参考訳（メタデータ） (2023-06-21T19:48:58Z)
• On the average-case complexity of learning output distributions of quantum circuits [55.37943886895049]
  統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。 この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
  論文  参考訳（メタデータ） (2023-05-09T20:53:27Z)
• Concurrent Shuffle Differential Privacy Under Continual Observation [60.127179363119936]
  個人的連続和問題(対数問題)について検討する。 並列シャッフルモデルでは,標準シャッフルモデルに比べて誤差が大幅に改善できることが示されている。
  論文  参考訳（メタデータ） (2023-01-29T20:42:54Z)
• A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
  離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。 我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。 次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
  論文  参考訳（メタデータ） (2020-06-02T16:38:36Z)
• Quantum Coupon Collector [62.58209964224025]
  我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。 我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-02-18T16:14:55Z)

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

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