論文の概要: Shuffling Cards When You Are of Very Little Brain: Low Memory Generation of Permutations
- arxiv url: http://arxiv.org/abs/2505.01287v1
- Date: Fri, 02 May 2025 14:00:57 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-05 17:21:20.053001
- Title: Shuffling Cards When You Are of Very Little Brain: Low Memory Generation of Permutations
- Title（参考訳）: 非常に小さな脳のときカードをシャッフルする
- Authors: Boaz Menuhin, Moni Naor,
- Abstract要約: 置換のジェネレータはメモリが限られており、"Guesser"はメモリが無制限である。
秘密のメモリを持つDealersにとっても、このバウンダリが最も有効であることを示す。
- 参考スコア（独自算出の注目度）: 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 are tight bounds for the relationship between the guessing probability and the memory required to generate the permutation. We suggest a method for the Dealer that requires~$m$ bits of storage, constant time for each turn and makes any Guesser pick correctly only $O(n/m+\log m)$ cards in expectation. The method does not require any secrecy from the dealer, i.e. it is ``open book" or ``whitebox". On the other hand, we show that this bound is the best possible, even for Dealers with secret memory: For any $m$-bit Dealer there is a (computationally powerful) guesser that makes $\Omega(n/m+\log m)$ correct guesses in expectation. 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$のストレージと各ターンの一定時間を必要とするDealerのメソッドを提案し,Guesserが正しく選択するのは$O(n/m+\logのみとする。
m) 予想で$カード。
この方法はディーラーからの機密を一切必要とせず、すなわち『オープンブック』または『ホワイトボックス』である。
一方、このバウンダリはシークレットメモリを持つディーラーにとっても最良であることを示す:$m$-bitディーラーには$\Omega(n/m+\logを作る(計算的に強力な)推測器があります。
m) 予想の正しい推測。
また、$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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。