Fugu-MT 論文翻訳(概要): A polylogarithmic bound for list replicability

論文の概要: A polylogarithmic bound for list replicability

arxiv url: http://arxiv.org/abs/2610.20657v1
Date: Wed, 14 Oct 2026 00:15:18 GMT
ステータス: 翻訳完了
システム内更新日: 2026-10-16 19:13:15.971385
Title: A polylogarithmic bound for list replicability
Title（参考訳）: リスト複製性のための多対数境界
Abstract要約: Zhang [Zha26]は最近、$Mge 2$ ドメインポイント上の$Nge 2$ のすべてのクラスのリスト-リプリケータビリティ番号が$O(log2 Mlog N)$であることを発表した原稿を投稿した。
参考スコア（独自算出の注目度）: 0.815557531820863
License: http://creativecommons.org/licenses/by-nc-sa/4.0/
Abstract: Zhang [Zha26] recently posted a manuscript announcing that the list-replicability number of every class of $M\ge 2$ binary concepts on $N\ge 2$ domain points is $O(\log^2 M\log N)$, which would be the first polylogarithmic upper bound on this quantity. In this note, we present a short, self-contained proof of this bound, following the high-level approach of the manuscript but with considerably simpler arguments.
Abstract（参考訳）: Zhang [Zha26] は、最近、$M\ge 2$ ドメインポイント上の$N\ge 2$ ドメインポイントのすべてのクラスのリスト-リプリケータビリティ番号が$O(\log^2 M\log N)$である、と発表した原稿を投稿した。本論では,本書の高レベルなアプローチに従えば,比較的単純な議論を伴う,短い自己完結型証明を提示する。

関連論文リスト

A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
論文参考訳（メタデータ） (2026-09-09T10:13:43Z)
Exponentially Fewer-Server PIR from Sparser $S$-Decoding Polynomials [2.5782420501870296]
一定の$s$に対して、$s$サーバのプライベート情報検索プロトコルが存在することを示す。我々の数論予想は既存の予想によって示唆される。
論文参考訳（メタデータ） (2026-07-24T06:59:30Z)
Faster quantum linear system solver beyond the condition number [50.84794327094274]
線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
論文参考訳（メタデータ） (2026-07-08T17:49:40Z)
Sign-Rank, Index, and List Replicability: Connections and Separations [0.815557531820863]
この問題に対する2つのアプローチは、$mathbbZ$-indexとリストの複製可能性数という、分析し易い尺度によって、符号ランクの低い境界を確立する。我々は、$mathbbZ$-index がリストの複製率の線型関数によって上界であることが示している。また、2つの概念クラスの積が2つの概念クラスのリスト複製可能性数の和で束縛されたリスト複製性数を持つことを示す、基本的な構成結果も証明する。
論文参考訳（メタデータ） (2026-06-16T17:57:16Z)
Hardness of High-Dimensional Linear Classification [58.29089693778071]
我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
論文参考訳（メタデータ） (2026-03-19T15:53:41Z)
Basic quantum subroutines: finding multiple marked elements and summing numbers [1.1265248232450553]
量子クエリーの最適数$O(sqrtN k)$を用いて、サイズ$N$のリスト内のすべての$k$マーク要素を見つける方法を示す。
論文参考訳（メタデータ） (2023-02-20T19:11:44Z)
Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文参考訳（メタデータ） (2022-06-07T18:00:01Z)
Low-degree learning and the metric entropy of polynomials [44.99833362998488]
少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
論文参考訳（メタデータ） (2022-03-17T23:52:08Z)
$Q$-learning with Logarithmic Regret [60.24952657636464]
楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
論文参考訳（メタデータ） (2020-06-16T13:01:33Z)

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