論文の概要: Improved lower bounds for decomposable randomized encoding

• arxiv url: http://arxiv.org/abs/2609.18020v1
• Date: Wed, 16 Sep 2026 02:17:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-20 08:55:53.599074
• Title: Improved lower bounds for decomposable randomized encoding
• Title（参考訳）: 分解不能なランダム化符号化のための下界の改良
• Abstract要約: 関数 $f$ に対する分解可能なランダム化符号化 (DRE) は、個々の入力をローカルにエンコードする$n$を許容する。 OR に対する最初の超線型下界を証明し、より一般的にはすべての非周期対称函数に対して証明する。
• 参考スコア（独自算出の注目度）: 1.4724626819957034
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: A decomposable randomized encoding (DRE) for a function $f$ allows $n$ parties, using shared randomness, to encode their individual inputs locally so that the collection of encodings reveals $f(x_1,\ldots,x_n)$ and nothing else. DREs are widely used in efficient multiparty computation. Their main complexity measure is size, the total bit length of the local encodings. Yet the optimal DRE size remains poorly understood even for the $n$-bit OR function. We prove the first superlinear lower bound for OR and, more generally, for every non-periodic symmetric function. Under an additional symmetry assumption, we prove a sharp $Ω(n\log n)$ lower bound for OR, matching the classic construction of Feige, Kilian, and Naor (STOC 1994). We also prove the first $Ω(n^2)$ lower bound on DRE size for non-explicit Boolean functions.
• Abstract（参考訳）: 関数 $f$ に対する分解可能なランダム化符号化 (DRE) では、共有ランダムネスを使用して、各入力をローカルにエンコードすることで、エンコーディングのコレクションが $f(x_1,\ldots,x_n)$ とその他何も示さない。 DREは効率的なマルチパーティ計算に広く利用されている。 主な複雑性尺度は、ローカルエンコーディングのビット長であるサイズである。 しかし、$n$-bit OR 関数であっても、最適な DRE サイズはよく分かっていない。 OR に対する最初の超線型下界を証明し、より一般的にはすべての非周期対称函数に対して証明する。 追加の対称性の仮定の下で、我々は鋭く$Ω(n\log n)$ lower bound for OR を証明し、Feige, Kilian, Naor (STOC 1994) の古典的な構成と一致する。 また、非明示的ブール函数に対する DRE サイズ上の最初の $Ω(n^2)$ 下界も証明する。

関連論文リスト

• Fast Bounded-Independence Functions and Their Duals [21.031497777539332]
  暗号アプリケーションによって動機付けされ、この領域で過去の結果を一般化し、改善する。 上記の結果が暗号に有用であることを示す。 これには、完全にセキュアなマルチパーティ計算のための最初の非自明なプロトコルが含まれる。
  論文  参考訳（メタデータ） (2026-06-05T07:53:04Z)
• Fault-Tolerant Resource Comparison of Qudit and Qubit Encodings for Diagonal Quadratic Operators [36.94429692322632]
  有限局所ヒルベルト空間のトランケーションは、格子場の理論の量子シミュレーションにおいて自然に現れ、キュディエンコーディングを動機付ける。 実スカラー場の一様体-振幅の離散化において、実スカラー場を1つの論理的$d$-level qudit または$n_b=eil log drceil$ logical qubitsを用いて、$U=e-it_x2$で例証した対角展開の非クリフォードコストを比較する。
  論文  参考訳（メタデータ） (2026-04-29T15:25:08Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。 まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。 我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2024-06-07T12:07:16Z)
• (1+1) Genetic Programming With Functionally Complete Instruction Sets Can Evolve Boolean Conjunctions and Disjunctions with Arbitrarily Small Error [16.075339182916128]
  GPシステムは、必要最小限のコンポーネントが備わっている場合、$n$変数の結合を進化させることができる。 GPシステムは、$O(ell n log2 n)$, $ell geq が受理木の大きさの極限であるような予想において、正確なターゲット関数を進化させることができることを示す。
  論文  参考訳（メタデータ） (2023-03-13T20:24:21Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。 損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
  論文  参考訳（メタデータ） (2020-09-18T02:18:44Z)
• 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)
• Exact Quantum Query Algorithms Outperforming Parity -- Beyond The Symmetric functions [3.652509571098291]
  まず、$Omega left(2fracsqrtn2 right)$非対称関数の直和に基づくクラスに対して、最適な正確な量子クエリアルゴリズム(Q_algo(f)$)を得る。 Q_algo$のクエリ複雑性は$lceil frac3n4 rceil$であるのに対して、$D_oplus(f)$は$n-1$と$lceil frac3n4 rceの間で異なる。
  論文  参考訳（メタデータ） (2020-08-14T12:17:48Z)

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

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