論文の概要: Fourier Sparsity of Delta Functions and Matching Vector PIRs

• arxiv url: http://arxiv.org/abs/2512.09941v1
• Date: Fri, 05 Dec 2025 16:40:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-12 16:15:41.976769
• Title: Fourier Sparsity of Delta Functions and Matching Vector PIRs
• Title（参考訳）: デルタ関数と整合ベクトルPIRのフーリエ空間
• Authors: Fatemeh Ghasemi, Swastik Kopparty,
• Abstract要約: そこで,S-decodings of reduce sparsity is corresponding to find delta function with low Fourier sparsity。 これらの結果は、より優れたSデコードを見つけることで、マッチングベクトルPIRスキームの制限を示唆している。
• 参考スコア（独自算出の注目度）: 0.7734726150561086
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper we study a basic and natural question about Fourier analysis of Boolean functions, which has applications to the study of Matching Vector based Private Information Retrieval (PIR) schemes. For integers m and r, define a delta function on {0,1}^r to be a function f: Z_m^r -> C with f(0) = 1 and f(x) = 0 for all nonzero Boolean x. The basic question we study is how small the Fourier sparsity of a delta function can be; namely how sparse such an f can be in the Fourier basis? In addition to being intrinsically interesting and natural, such questions arise naturally when studying "S-decoding polynomials" for the known matching vector families. Finding S-decoding polynomials of reduced sparsity, which corresponds to finding delta functions with low Fourier sparsity, would improve the current best PIR schemes. We show nontrivial upper and lower bounds on the Fourier sparsity of delta functions. Our proofs are elementary and clean. These results imply limitations on improving Matching Vector PIR schemes simply by finding better S-decoding polynomials. In particular, there are no S-decoding polynomials that can make Matching Vector PIRs based on the known matching vector families achieve polylogarithmic communication with a constant number of servers. Many interesting questions remain open.
• Abstract（参考訳）: 本稿では,ブール関数のフーリエ解析に関する基本的,自然な問題について考察し,マッチングベクトルに基づくプライベート情報検索(PIR)手法の研究に応用する。 整数 m と r に対して {0,1}^r 上のデルタ函数を函数 f と定義する: Z_m^r -> C で f(0) = 1 と f(x) = 0 がすべての 0 でないブール x に対して成立する。 私たちが研究する基本的な問題は、デルタ関数のフーリエ空間がどれほど小さいか、すなわち、そのような f がフーリエ基底でどれだけスパースであるかである。 本質的に興味深く自然であることに加えて、そのような問題は既知の整合ベクトル族に対して「S-復号多項式」を研究するときに自然に生じる。 低いフーリエ空間を持つデルタ関数の発見に対応する空間幅の縮小したS-復号多項式を見つけることは、現在の最良のPIRスキームを改善する。 デルタ関数のフーリエ空間に非自明な上界と下界を示す。 私たちの証明は初等的でクリーンです。 これらの結果は、より優れたS-復号多項式を見つけることで、マッチングベクトルPIRスキームを改善することの制限を示唆している。 特に、既知のマッチングベクトル族に基づくマッチングベクトルPIRを一定数のサーバで多対数通信するS復号多項式は存在しない。 多くの興味深い質問が未解決のままである。

関連論文リスト

• Fourier Fingerprints of Ansatzes in Quantum Machine Learning [0.0]
  本稿では,回路構造に依存するフーリエモード間の相関関係について述べる。 いくつかの一般的なアンサーゼに対して、フーリエ係数相関 (FCC) を計算し、フーリエ指紋を構築する。 本稿では、ランダムなフーリエ級数学習の問題に対して、FCCは、広く使われている表現性指標がそうでないにもかかわらず、アンサーゼの相対的な性能を正しく予測する方法を示す。
  論文  参考訳（メタデータ） (2025-08-28T15:00:37Z)
• FFTArray: A Python Library for the Implementation of Discretized Multi-Dimensional Fourier Transforms [0.0]
  FFTArrayは,フーリエ変換の一般的な離散化を自動化するPythonライブラリである。 Python Array API標準に基づいて構築されたFFTArrayは、NumPy、JAX、PyTorchといった配列バックエンドとシームレスに統合される。
  論文  参考訳（メタデータ） (2025-07-17T17:05:39Z)
• Exponential Hardness of Reinforcement Learning with Linear Function Approximation [20.066210529358177]
  指数時間仮説に基づく線形強化学習において,特徴・地平線で指数関数的な計算下界を示す。 また、地平線依存に最適化された下界が$exp(sqrtH)$の最もよく知られた上界とほぼ一致することを示す。
  論文  参考訳（メタデータ） (2023-02-25T00:19:49Z)
• FC-PINO: High Precision Physics-Informed Neural Operators via Fourier Continuation [60.706803227003995]
  FC-PINO(Fourier-Continuation-based PINO)アーキテクチャを導入し、PINOの精度と効率を非周期的および非滑らかなPDEに拡張する。 標準的なPINOは、非周期的および非滑らかなPDEを高い精度で、挑戦的なベンチマークで解くのに苦労していることを実証する。 対照的に、提案されたFC-PINOは、正確で堅牢でスケーラブルなソリューションを提供し、PINOの代替案よりも大幅に優れている。
  論文  参考訳（メタデータ） (2022-11-29T06:37:54Z)
• Learning Aggregation Functions [78.47770735205134]
  任意の濃度の集合に対する学習可能なアグリゲータであるLAF(Learning Aggregation Function)を紹介する。 半合成および実データを用いて,LAFが最先端の和(max-)分解アーキテクチャより優れていることを示す実験を報告する。
  論文  参考訳（メタデータ） (2020-12-15T18:28:53Z)
• Finite-Function-Encoding Quantum States [52.77024349608834]
  任意の$d$値論理関数を符号化する有限関数符号化(FFE)を導入する。 それらの構造的特性について検討する。
  論文  参考訳（メタデータ） (2020-12-01T13:53:23Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  強化学習のコアにおける探索・探索トレードオフについて検討する。 特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。 私たちの後悔の限界はエピソードの数とは無関係です。
  論文  参考訳（メタデータ） (2020-11-09T18:32:22Z)
• Learning Set Functions that are Sparse in Non-Orthogonal Fourier Bases [73.53227696624306]
  フーリエスパース集合関数を学習するための新しいアルゴリズム群を提案する。 Walsh-Hadamard変換に焦点をあてた他の研究とは対照的に、我々の新しいアルゴリズムは最近導入された非直交フーリエ変換で機能する。 いくつかの実世界のアプリケーションで有効性を示す。
  論文  参考訳（メタデータ） (2020-10-01T14:31:59Z)
• From Sets to Multisets: Provable Variational Inference for Probabilistic Integer Submodular Models [82.95892656532696]
  サブモジュール関数は機械学習やデータマイニングにおいて広く研究されている。 本研究では,整数部分モジュラ函数に対する連続DR-部分モジュラ拡張を提案する。 整数部分モジュラー関数によって定義される新しい確率モデルを定式化する。
  論文  参考訳（メタデータ） (2020-06-01T22:20:45Z)

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

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