論文の概要: Counting and Covering in Nearest-Neighbour Representations of Boolean Functions

• arxiv url: http://arxiv.org/abs/2609.23094v1
• Date: Sat, 19 Sep 2026 16:04:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-22 20:29:00.675303
• Title: Counting and Covering in Nearest-Neighbour Representations of Boolean Functions
• Title（参考訳）: ブール関数の近傍近傍表現におけるカウントと被覆
• Abstract要約: ブール関数を表すために必要となるプロトタイプの数を最寄りの分類により検討する。 プロトタイプはユークリッド空間の任意の点かもしれないし、あるいはブール立方体の中に自乗する必要があるかもしれない。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the number of prototypes needed to represent Boolean functions by nearest-neighbour classification. There are two distinct settings: the prototypes may be arbitrary points of Euclidean space, or they may themselves be required to lie in the Boolean cube. For unrestricted prototypes, we strengthen a known lower bound for almost all Boolean functions. The bound applies simultaneously to nearest-neighbour voting rules with any number of voting neighbours, and substantially narrows the gap with the known general upper bound. We obtain a VC-dimension bound for classes with a bounded number of prototypes, and show that it is sharp in order in dimensions at least four. We then study Boolean prototypes, beginning with symmetric threshold functions. A connection with covering designs expresses the minimum number of prototypes at every threshold level exactly in terms of a covering number, and leads to further exact results for related monotone functions, including disjunctive extensions and a characterisation of when a representation with a single negative prototype is possible. For a uniformly random Boolean function, the Boolean nearest-neighbour complexity, as a proportion of the cube, is asymptotically close either to one half or to one, with explicit limiting probabilities. In particular, almost every Boolean function requires at least approximately half as many prototypes as there are points in the cube, and one half is the largest proportion for which such a lower bound holds. Finally, we consider arbitrary symmetric Boolean functions. Their Boolean nearest-neighbour complexity is closely approximated by a weighted vertex-cover problem on paths. As a consequence, a uniformly random symmetric function typically requires prototypes amounting to $11/20$ of the cube. This is much larger than the upper bounds known when the prototypes are allowed to lie anywhere in Euclidean space.
• Abstract（参考訳）: ブール関数を表すのに必要なプロトタイプの数を最寄りの分類により検討する。 プロトタイプはユークリッド空間の任意の点かもしれないし、あるいはブール立方体の中に置かなければならないかもしれない。 制限のないプロトタイプに対しては、ほとんどすべてのブール函数に対する既知の下界を強化する。 この境界は、近隣の投票規則と、近隣の投票規則とを同時に適用し、既知の一般上限とのギャップを著しく狭める。 我々は、有界なプロトタイプ数を持つクラスに対して有界なVC次元を求め、それが少なくとも4次元の順序でシャープであることを示す。 次に、対称しきい値関数から始まるブールプロトタイプについて研究する。 被覆設計との接続は、被覆数の観点から、各しきい値レベルで最小限のプロトタイプ数を表現し、単一の負のプロトタイプを持つ表現が可能である場合の解法的拡張や特徴付けを含む、関連する単調関数のさらなる正確な結果をもたらす。 均一にランダムなブール函数に対して、ブール近傍の複雑性は立方体の比として、漸近的に半分か1に近づき、明示的な極限確率を持つ。 特に、ほぼすべてのブール函数は立方体に点が存在するため、少なくとも約半分のプロトタイプを必要とし、一方はそのような下界が持つ最大の比例である。 最後に、任意の対称ブール関数を考える。 ブール近傍の複雑性は、経路上の重み付き頂点被覆問題によって密接に近似される。 その結果、一様ランダム対称函数は通常、立方体の11/20$のプロトタイプを必要とする。 これは、プロトタイプがユークリッド空間の任意の場所に置かれることが許されたときの上限よりもはるかに大きい。

関連論文リスト

• The Head Complexity of Boolean Functions in Single-Layer Attention [2.2727733134290813]
  単層アテンションのみのモデルで関数を計算するのに必要なアテンションヘッドの最小数について検討する。 k$headは$k$-bitパリティを計算するが、$(k+1)$-bitパリティを計算できない。 また、埋め込み次元と数値精度のためのコンパクト性境界を確立する。
  論文  参考訳（メタデータ） (2026-09-03T16:22:02Z)
• Closed-Form Optimal Quantum Circuits for Single-Query Identification of Boolean Functions [0.0]
  ブラックボックス(オークル)アクセスを許容した未知の単一ビットブール関数の最小誤差同定について検討した。 完全に構成的なソリューション – 明示的な状態準備と明示的な測定ユニタリ – を与えます。 結果として得られる回路の深さは低く、固定ゲートセットを使用し、(この最小設定では)入力状態の絡み合いは不要である。
  論文  参考訳（メタデータ） (2025-12-17T19:16:00Z)
• Another generalization of Hadamard test: Optimal sample complexities for learning functions on the unitary group [0.0]
  未知のユニタリ演算の性質を推定することは、量子情報科学の基本的な課題である。 任意の可積分関数の標本効率推定のための統一的なフレームワークを提案する。 提案手法は,アダマール試験を一般化し,表現理論からツールを利用する。
  論文  参考訳（メタデータ） (2025-09-06T13:09:50Z)
• Ehrenfeucht-Haussler Rank and Chain of Thought [51.33559894954108]
  本稿では、よく知られたトランスフォーマーアーキテクチャを基盤とした、ランクの新たな特徴付けについて述べる。 関数 $f$ のランクは、単一層変換器が要求する思考ステップの EmphChain の最小値に対応していることを示す。 また、マルチヘッド単一層トランスをキャプチャするマルチヘッドランクの概念を導入し、有界なマルチヘッドランクを持つ関数クラスのPAC学習性の解析を行う。
  論文  参考訳（メタデータ） (2025-01-22T16:30:58Z)
• Approximate degree lower bounds for oracle identification problems [19.001036556917818]
  本稿では,特定のオラクル識別問題に対する近似次数下界を証明するためのフレームワークを提案する。 我々の下界は、大域関数と等値関数に対するランダムな通信上界によって駆動される。
  論文  参考訳（メタデータ） (2023-03-07T14:30:28Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
  本研究は,統計的学習性を示すために近似ネットワークを必要とする統計有意(SM)近似の形式的定義を提案する。 回路とチューリングマシンの2つの機能クラスに対するSM近似について検討する。
  論文  参考訳（メタデータ） (2021-07-28T04:28:55Z)
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
  この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。 我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。 標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
  論文  参考訳（メタデータ） (2021-07-09T16:04:24Z)
• Learning Weakly Convex Sets in Metric Spaces [2.0618817976970103]
  機械学習理論における中心的な問題は、ゼロエラーを持つ一貫した仮説を効率的に見つけることができるかどうかである。 このアルゴリズムの一般的な考え方は、弱凸仮説の場合にまで拡張可能であることを示す。
  論文  参考訳（メタデータ） (2021-05-10T23:00:02Z)
• Finding Global Minima via Kernel Approximations [90.42048080064849]
  関数評価のみに基づく滑らかな関数のグローバル最小化を考える。 本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
  論文  参考訳（メタデータ） (2020-12-22T12:59:30Z)

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

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