論文の概要: Bilinear Hulls for Support Splitting: Characterization, Optimization, and Applications

• arxiv url: http://arxiv.org/abs/2611.01337v1
• Date: Sat, 31 Oct 2026 23:11:12 GMT
• ステータス: 情報取得中
• システム内更新日: 2026-11-03 19:55:44.886834
• Title: Bilinear Hulls for Support Splitting: Characterization, Optimization, and Applications
• Title（参考訳）: Bilinear Hulls for Support Splitting: キャラクタリゼーション、最適化、応用
• Abstract要約: 数学的には、船体が定義されている標準内積を代替の双線型形式に置き換えることで、このコストがどれだけ低下するかを数学的に研究する。 LEP ベースの LESS と PKP ベースの PERK が我々のフレームワークの外部にあるのに対して,PEP ベースの SPECK は$-q$ のコスト削減を認めていることを確認した。
• 参考スコア（独自算出の注目度）: 1.4656201740804355
• License:
• Abstract: Sendrier's Support Splitting Algorithm (SSA) is the standard solver for the Permutation Equivalence Problem (PEP); its cost is dominated by a term that grows exponentially in the hull dimension. We study, mathematically, how much this cost can be lowered by replacing the standard inner product, on which the hull is defined, with an alternative bilinear form. Two structural results give a complete answer: only a narrow two-parameter family of bilinear forms produces a hull on which SSA can still operate, namely those whose matrix in the standard basis is a linear combination of the identity and the all-ones matrix; and even within this family the hull dimension drops by at most one (with the reduction achieved on every self-dual code whose length is coprime to the field characteristic). Together, these results give a tight upper bound: since SSA on a code with hull dimension $h$ has cost dominated by $q^h$, replacing the standard hull with $\mathrm{Hull}_M$ lowers this dominant term from $q^h$ to at best $q^{h-1}$, so no bilinear-form generalization of the inner product can reduce the SSA cost by more than a factor of $q$, the field size. Going beyond this requires invariants outside the bilinear framework. As an application, we verify that PEP-based SPECK admits the factor-$q$ cost reduction, while LEP-based LESS and PKP-based PERK lie outside our framework. A SageMath implementation of the bilinear-hull preprocessing confirms feasibility at SPECK's recommended length $n = 252$.
• Abstract（参考訳）: Sendrier's Support Splitting Algorithm (SSA) はPermutation Equivalence Problem (PEP) の標準的な解法であり、そのコストは船体次元において指数関数的に増大する用語によって支配される。 数学的には、船体が定義されている標準内積を代替の双線型形式に置き換えることで、このコストがどれだけ低下するかを数学的に研究する。 2つの構造的結果は完全な答えを与える: 双線型形式の狭い2パラメータの族のみが SSA がまだ操作できる船体、すなわち標準基底の行列が恒等式と全単項行列の線型結合であるものを生成する。 船体次元が $h$ の符号上の SSA は$q^h$ で支配されるので、標準船体を $\mathrm{Hull}_M$ に置き換えることで、この支配的な項を$q^h$ から$q^{h-1}$ に下げる。 これを超えるためには、双線形フレームワーク以外の不変性が必要である。 LEPベースのLESSとPKPベースのPERKは私たちのフレームワークの外にあるが、アプリケーションとして、PEPベースのSPECKが$-q$のコスト削減を認めていることを検証する。 ビリニアハル前処理のSageMath実装は、SPECKの推奨長さ$n = 252$で実現可能であることを確認した。

関連論文リスト

• Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma [70.99943094379263]
  有界ラディウス系におけるスパース半定値プログラムに対する最初の準時間古典的解法を与える。 我々の主な技術的貢献は、ハミルトンのギブス状態を同時に表す古典的な手続きである。
  論文  参考訳（メタデータ） (2026-09-30T17:51:21Z)
• Optimistic Rates for Multiclass PAC Learning [39.91890433860882]
  最悪のマルチクラス境界は、最高の分類器が既にほぼ正しいときに小さくならない。 ナタラジャン次元のクラス $d_N$ と Daniely-Shalev-Shwartz 次元 $d_DS$ に対して、最適余剰リスクは2つのエンドポイントで知られている。 固定オラクルリスクが$Lstar$であれば、最適な過剰リスクは$widetilde(sqrtLstar d_N/n+d_DS/n)$で、アルファベットサイズは一様である。
  論文  参考訳（メタデータ） (2026-08-11T12:46:03Z)
• SSTQ:Privacy-Preserving Vector Quantization via Subsampled Stochastic TurboQuant [79.24089819400126]
  Subsampled TurboQuant (SSTQ) は、オーバーコンプリートな等幅のタイトフレーム、座標サブサンプリング、プライバシ対応量子化を組み合わせたフレームワークである。 SSTQは平均2乗誤差スケーリングを実現し、クライアントあたり$lceil log N il + b$ bitsを使用する。 また、コードブックに依存したMSEスケーリングを$O(4b)$から$O(2b)$に削減する、プライバシを意識したコードブックの目的も導出します。
  論文  参考訳（メタデータ） (2026-08-05T17:51:25Z)
• On the Curse of Dimensionality in Private Sparse Covariance Estimation and PCA [20.109939947492954]
  作用素ノルムにおける高次元微分プライベート(DP)共分散推定と主成分分析(PCA)について検討する。 プライベートでない設定では、$mathsfpoly(k, log d)$ サンプルがこれら2つの問題を解決するのに十分であることが知られている。 DPの下では,PCAに対する$mathsfpoly(k, log d)$サンプル複雑性が可能であることを示す。
  論文  参考訳（メタデータ） (2026-06-20T08:38:51Z)
• Efficient Mean Curvature Computation on High-Dimensional Data Manifolds [52.452902154360565]
  高次元データセットの各点における局所的な平均曲率の推定は、機械学習アルゴリズムの重要な要素である。 本稿では,このコストを桁違いに削減する2つの補完的貢献を紹介する。 実世界のデータセットの実験では、オリジナルの実装と比較して50倍から300倍のスピードアップが確認されている。
  論文  参考訳（メタデータ） (2026-06-04T16:04:31Z)
• Scaling Federated Linear Contextual Bandits via Sketching [49.12000877146222]
  本稿では,FSCLB(Federated Sketch Contextual Linear Bandits)を提案する。 合成と実世界の両方のデータセットの実験では、FSCLBは計算と通信のコストを90%以上削減している。
  論文  参考訳（メタデータ） (2026-05-01T08:22:06Z)
• Quantum Data Loading for Carleman Linearized Systems: Application to the Lattice-Boltzmann Equation [0.0]
  任意の平方行列を非ユニタリ項の線形結合(LCNU)に分解し、各非ユニタリ項をユニタリ行列に埋め込む。 LCNU戦略のTゲートコストを,(1)ブロックオーラクルの符号化,(2)変分量子線形解法と組み合わせて見積もる。
  論文  参考訳（メタデータ） (2026-05-01T00:10:50Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。 我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
  論文  参考訳（メタデータ） (2023-02-03T03:19:14Z)
• Hashing embeddings of optimal dimension, with applications to linear least squares [1.2891210250935143]
  スケッチの射影次元$m$で最適である$sgeq 1$のスケッチ行列に対して、サブスペース埋め込み特性を提示する。 これらの結果をLinear Least Squares (LLS) の特殊なケースに適用し,これらの問題に対する汎用ソフトウェアパッケージであるSki-LLSを開発する。
  論文  参考訳（メタデータ） (2021-05-25T10:35:13Z)
• Variance-Aware Confidence Set: Variance-Dependent Bound for Linear Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
  線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。 線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。 線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
  論文  参考訳（メタデータ） (2021-01-29T18:57:52Z)

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

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