論文の概要: Chamber geometry and specification numbers of Boolean threshold functions

• arxiv url: http://arxiv.org/abs/2606.29477v1
• Date: Sun, 28 Jun 2026 16:12:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-30 18:07:15.937418
• Title: Chamber geometry and specification numbers of Boolean threshold functions
• Title（参考訳）: ブールしきい値関数の室内幾何と仕様数
• Authors: Martin Anthony,
• Abstract要約: 仕様番号 $_n(f)$ は、すべてのしきい値関数の中で$f$-値が$f$を一意に決定する最小の点数である。 しきい値関数は、重みとしきい値の$(n+1)$次元空間における中心超平面配置のチャンバーである。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The specification number $σ_n(f)$ of a Boolean threshold function $f$ on $n$ variables is the least number of points whose $f$-values determine $f$ uniquely among all threshold functions. Its essential points form the unique minimum such set. We develop Zuev's geometric interpretation: the threshold functions are the chambers of a central hyperplane arrangement in the $(n+1)$-dimensional space of weights and thresholds, and the essential points of a function correspond exactly to the facets of its chamber, so the specification number is the chamber's facet number. The lower bound $σ_n(f)\ge n+1$ becomes the fact that a pointed full-dimensional cone has at least $n+1$ facets, with equality for simplicial chambers. The average specification number $\overlineσ_n$ becomes an average facet count. We evaluate this average exactly via the resonance arrangement and bound it through a theorem of Fukuda, Tamura, and Tokuyama, obtaining $\overlineσ_n\le 2n$; hence $\overlineσ_n=Θ(n)$. This settles a question of Gutekunst, Mészáros, and Petersen. The method also extends to polynomial threshold functions. The same geometry links threshold functions with a threshold zonotope, whose vertices are modified Chow vectors. Its one-skeleton is the one-inclusion graph, and a vertex's degree is the specification number of that function. Finally, we treat the operations of Lozin et al. on functions of minimum specification number. Adding a variable and extending on a variable both take the product of a chamber closure with a half-line, preserving simpliciality. For the symmetric-variables extension we give an exact thresholdness criterion and show that minimum specification number is preserved whenever the extension is a threshold function. We also resolve a question they pose concerning a fourth operation.
• Abstract（参考訳）: ブールしきい値関数$f$ on $n$変数の仕様番号$σ_n(f)$は、すべてのしきい値関数の中で$f$が一意に決定される点の最小数である。 その重要な点は、一意的な極小集合を成す。 しきい値関数は、(n+1)$次元の重みとしきい値の空間における中心超平面配置のチャンバーであり、関数の本質点は、そのチャンバーのファセットと正確に一致するので、仕様番号はチャンバーのファセット数である。 下界の$σ_n(f)\ge n+1$ は、尖った全次元円錐が少なくとも$n+1$の面を持ち、単純なチャンバーに等しいという事実となる。 平均仕様番号 $\overlineσ_n$ は平均ファセット数となる。 この平均を共鳴配置によって正確に評価し、福田、田村、徳山の定理により束縛し、$\overlineσ_n\le 2n$ を得る。 これはグテクンスト、メサロス、ピーターセンの問いを解き明かす。 この方法は多項式しきい値関数にも拡張される。 同じ幾何学は閾値関数としきい値 zonotope をリンクし、頂点は Chow ベクトルに修正される。 その1-骨格は1-包含グラフであり、頂点次数はその関数の仕様数である。 最後に、最小仕様数の関数上でのLozin et alの操作を扱う。 変数を追加して変数に拡張することは、チャンバークロージャの積を半直線で取り、単純性を保つ。 対称変数拡張に対しては、正確なしきい値の基準を与え、拡張がしきい値関数であるときに最小仕様番号が保存されることを示す。 また,第4次手術に関する問題も解決する。

関連論文リスト

• Spectral-angular parametrization of open qudit dynamics [0.0]
  一般密度行列 $rho_mathbfr,pmb$ は実パラメータ $n2-1$ によって特徴づけられ、自然に2つの集合に分解される。 重要な観察は、スペクトルパラメータ $mathbfr = (r_1, ldots, r_n-1)$ が自然なリー代数的解釈を受け入れることである。
  論文  参考訳（メタデータ） (2026-04-13T16:02:24Z)
• Nonsmooth Nonparametric Regression via Fractional Laplacian Eigenmaps [14.003044924094597]
  真の回帰関数が必ずしも滑らかでない場合に、非パラメトリック回帰法を開発する。 より具体的には、我々のアプローチは分数ラプラシアンを使い、真の回帰関数が次数$sin (0,1)$のソボレフ空間にある場合を扱うように設計されている。
  論文  参考訳（メタデータ） (2024-02-22T21:47:29Z)
• Near-optimal fitting of ellipsoids to random points [68.12685213894112]
  楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。 我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。 我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
  論文  参考訳（メタデータ） (2022-08-19T18:00:34Z)
• A Variational Quantum Algorithm For Approximating Convex Roofs [0.0]
  絡み合い測度は、まずバイパルタイトヒルベルト空間の純粋な状態に対して定義され、その後凸屋根拡大を通じて混合状態に拡張される。 mathbbN$で$dに対して$f$-$d$拡張と呼ぶ一連の拡張を生成します。 純状態上で定義された絡み合い尺度の$f$-$d$拡張を近似することを目的とした量子変分アルゴリズムを導入する。
  論文  参考訳（メタデータ） (2022-03-04T02:30:35Z)
• Submodular + Concave [53.208470310734825]
  第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。 本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。 このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
  論文  参考訳（メタデータ） (2021-06-09T01:59:55Z)
• Scalable Frank-Wolfe on Generalized Self-concordant Functions via Simple Steps [66.88729048402082]
  一般化自己一致は、多くの学習問題の目的関数に存在する重要な特性である。 検討対象の領域が一様凸あるいは多面体である場合など,様々な症例に対する収束率の改善を示す。
  論文  参考訳（メタデータ） (2021-05-28T15:26:36Z)
• Finding Global Minima via Kernel Approximations [90.42048080064849]
  関数評価のみに基づく滑らかな関数のグローバル最小化を考える。 本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
  論文  参考訳（メタデータ） (2020-12-22T12:59:30Z)

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

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