論文の概要: Broadcasting in random recursive dags
- arxiv url: http://arxiv.org/abs/2306.01727v1
- Date: Fri, 2 Jun 2023 17:53:10 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-05 13:42:47.269929
- Title: Broadcasting in random recursive dags
- Title（参考訳）: ランダム再帰的dagにおける放送
- Authors: Simon Briend and Luc Devroye and Gabor Lugosi
- Abstract要約: 均一な$k$-scダグは、既存のノードからランダムに$k$親を選択することでランダムランダムツリーを一般化する。
すべてのノードがビットを受信すると、$k$-sc dagがルートを特定せずに表示される。
以下の関数として$p$のしきい値は、すべてのノードの多数ルールが$c1/2$のエラーを$c+o(1)$とします。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A uniform $k$-{\sc dag} generalizes the uniform random recursive tree by
picking $k$ parents uniformly at random from the existing nodes. It starts with
$k$ ''roots''. Each of the $k$ roots is assigned a bit. These bits are
propagated by a noisy channel. The parents' bits are flipped with probability
$p$, and a majority vote is taken. When all nodes have received their bits, the
$k$-{\sc dag} is shown without identifying the roots. The goal is to estimate
the majority bit among the roots. We identify the threshold for $p$ as a
function of $k$ below which the majority rule among all nodes yields an error
$c+o(1)$ with $c<1/2$. Above the threshold the majority rule errs with
probability $1/2+o(1)$.
- Abstract（参考訳）: 均一$k$-{\sc dag} は、既存のノードからランダムに$k$親を選択することによって、一様ランダム再帰木を一般化する。
最初は$k$ ''roots' から始まります。
それぞれの$k$ルートはビットに割り当てられる。
これらのビットはノイズチャネルによって伝搬される。
両親のビットは確率$p$で反転し、過半数の投票が行われる。
すべてのノードがビットを受信すると、$k$-{\sc dag} がルートを特定せずに表示される。
目標は、ルーツの大多数のビットを見積もることである。
p$ のしきい値は、すべてのノードの多数ルールが $c<1/2$ の誤差 $c+o(1)$ を出力する $k$ 以下の関数として特定する。
しきい値を超えると、多数決ルールは1/2+o(1)$の確率を持つ。
関連論文リスト
- Rényi divergence-based uniformity guarantees for $k$-universal hash functions [59.90381090395222]
普遍ハッシュ関数は、ソースの出力を有限アルファベット上のランダム文字列にマッピングする。
ミンエントロピーによって測定されるように、ほぼ均一なランダムビットを蒸留することが可能であることを示す。
論文 参考訳（メタデータ） (2024-10-21T19:37:35Z) - Pseudorandom and Pseudoentangled States from Subset States [49.74460522523316]
計算基底の部分集合である$S$に対する部分集合状態は [ frac1sqrt|S|sum_iin S |irangle である。
固定された部分集合サイズ $|S|=s$ に対して、$s = 2n/omega(mathrmpoly(n))$ と $s=omega(mathrmpoly(n))$ が与えられたとき、ランダムな部分集合状態は情報理論上はHaarランダム状態と区別できないことを示す。
論文 参考訳（メタデータ） (2023-12-23T15:52:46Z) - On the Trade-off between the Number of Nodes and the Number of Trees in
a Random Forest [8.340919965932443]
我々は、$n$変数の多数関数は、$n-T$が定数であれば、それぞれ大きさで$T$$$(n$)決定ツリーのバッグで表現できることを示した。
k$-out-of-n$関数に関する関連する結果も提示される。
論文 参考訳（メタデータ） (2023-12-16T02:09:34Z) - Dimension-free Remez Inequalities and norm designs [48.5897526636987]
ドメインのクラスが$X$で、テストセットが$Y$で、Emphnormと呼ばれ、次元のないRemez型の見積もりを楽しむ。
ポリトーラスに$f$が拡張されたとき、$f$の上限は$mathcalO(log K)2d$以上増加しないことを示す。
論文 参考訳（メタデータ） (2023-10-11T22:46:09Z) - Minimizing Polarization in Noisy Leader-Follower Opinion Dynamics [17.413930396663833]
本稿では,ノイズの多いソーシャルネットワークにおけるリーダ・フォロワーの意見ダイナミクスに対する偏極最適化の問題について考察する。
私たちは、すべてのリーダの意見が同一であり、変化のない、一般的なリーダフォローのDeGrootモデルを採用しています。
目的関数が単調で超モジュラーであることを示し、その後、近似係数が1-1/e$の単純なグレディアルゴリズムを提案し、O((n-q)3)$時間で問題を解く。
論文 参考訳（メタデータ） (2023-08-14T08:52:24Z) - Fully-Dynamic Approximate Decision Trees With Worst-Case Update Time
Guarantees [3.5509551353363644]
ラベル付き例の挿入と削除の任意の順序に近似的な決定木を保持する最初のアルゴリズムを与える。
我々は$O!left(fracd, f(n)n operatornamenamepolyfrachepsilonright)$ Operations per updateを使って$epsilon$-approximate treeを維持する決定論的アルゴリズムを提供する。
論文 参考訳（メタデータ） (2023-02-08T11:02:58Z) - Repeated Averages on Graphs [2.363388546004777]
我々は$frac(1-epsilon)2log2nlog n-O(n)$が$n$ノード上のすべての連結グラフに対する一般的な下界であることを証明する。
また、星、膨張星、ダンベル、サイクルなど、いくつかの重要なグラフの族に対して、$t_epsilon,1$の急激な等級も得られる。
論文 参考訳（メタデータ） (2022-05-09T20:18:31Z) - Coresets for Decision Trees of Signals [19.537354146654845]
仮にそのような行列に対して$(k,varepsilon)$-coresetを出力する最初のアルゴリズムを提供する。
これは、決定木と -- 機械学習から -- 計算幾何学における分割木の間のリンクをフォージすることで実現している。
論文 参考訳（メタデータ） (2021-10-07T05:49:55Z) - Differentially Private Multi-Armed Bandits in the Shuffle Model [58.22098764071924]
シャッフルモデルにおけるマルチアームバンディット(MAB)問題に対して,$(varepsilon,delta)$-differentially privateアルゴリズムを提案する。
我々の上限は、集中モデルにおいて最もよく知られたアルゴリズムの後悔とほぼ一致し、局所モデルにおいて最もよく知られたアルゴリズムを著しく上回っている。
論文 参考訳（メタデータ） (2021-06-05T14:11:01Z) - Optimal Low-Degree Hardness of Maximum Independent Set [93.59919600451487]
スパースな ErdHos-R'enyi ランダムグラフにおいて,大きな独立集合を求めるアルゴリズム的タスクについて検討する。
低次アルゴリズムのクラスは、半最適サイズの独立した集合を見つけることができるが、それ以上は見つからないことを示す。
論文 参考訳（メタデータ） (2020-10-13T17:26:09Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。