論文の概要: On Collusion-Free Teaching in Planar Graphs

• arxiv url: http://arxiv.org/abs/2610.18714v1
• Date: Tue, 13 Oct 2026 16:57:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-16 20:06:35.275637
• Title: On Collusion-Free Teaching in Planar Graphs
• Title（参考訳）: 平面グラフにおけるコルーシオンフリー教育について
• Abstract要約: 非クラッシング教育は、ゴールドマン・マティアスの共謀回避基準を満たすモデル間の教育の複雑さを最小化する。 NCTD が常に VCdim によって束縛されているかを検討する。 平面グラフにおける閉近傍の概念クラスであっても、NCTD+ と NCTD のどちらが最大でもNP完全であるかどうかを決定することが示される。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Non-clashing teaching minimizes teaching complexity among models satisfying the Goldman--Mathias collusion-avoidance criterion. While the Vapnik--Chervonenkis dimension (VCdim) measures the complexity of learning from samples, non-clashing teaching dimension (NCTD) measures the number of examples required when a teacher can select them. Whether NCTD is always bounded above by VCdim remains a fundamental open question in learning theory. In this paper, we investigate this question for the concept classes of closed neighborhoods in planar graphs. We prove a tight upper bound of two on their NCTD, thereby establishing the conjectured inequality for this family. For the positive variant NCTD+, in which teaching sets contain only positive examples, we obtain a tight upper bound of four. Finally, we show that deciding whether either NCTD+ or NCTD is at most one is NP-complete, even for concept classes of closed neighborhoods in planar graphs. In particular, despite the upper bound of two on NCTD for such classes, distinguishing between NCTD values of one and two remains NP-hard.
• Abstract（参考訳）: 非クラッシング教育は、ゴールドマン・マティアスの共謀回避基準を満たすモデル間の教育の複雑さを最小化する。 Vapnik-Chervonenkis 次元 (VCdim) はサンプルからの学習の複雑さを測定するが、非クラッシング教育次元 (NCTD) は教師がそれを選択できるために必要なサンプルの数を測定する。 NCTD が常に VCdim によって束縛されているか否かは、学習理論における根本的なオープンな問題である。 本稿では,平面グラフにおける閉近傍の概念クラスに対するこの問題について検討する。 NCTD 上の 2 の強い上界を証明し、この族に対する予想不等式を確立する。 正の変種 NCTD+ に対して、授業集合が正の例のみを含む場合、その上界は 4 である。 最後に、平面グラフにおける閉近傍の概念クラスであっても、NCTD+ と NCTD のどちらが最大でもNP完全であるかどうかを決定することを示す。 特に、そのようなクラスに対する NCTD 上の 2 の上限にもかかわらず、1 と 2 の NCTD の値の区別は NP ハードのままである。

関連論文リスト

• The No-Clash Teaching Dimension is Bounded by VC Dimension [0.8205357635912689]
  本研究は,Vapnik-Chervonenkis次元によって,No-Clash Teaching Dimensionが上界であるかどうかを検討する。 任意の有限概念クラスに対して、我々はそのVapnik-Chervonenkis次元に等しい大きさの断片を構成する。
  論文  参考訳（メタデータ） (2026-03-24T02:08:32Z)
• Non-Clashing Teaching in Graphs: Algorithms, Complexity, and Bounds [5.718194486637426]
  グラフ内の閉近傍に対する(正の)非クラッシング教育を考える。 我々は、より一般的なパラメータのクラスのためのFPTアルゴリズムを含む改良されたアルゴリズム結果を提供する。 より広いグラフのクラスに対してより強い上限を得る。
  論文  参考訳（メタデータ） (2026-01-31T11:07:30Z)
• Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back [84.81507553557556]
  マルチクラスPACサンプルの複雑さは2つの異なる次元に支配されていることを示す。 バイナリ分類やオンライン分類とは異なり、マルチクラス学習は本質的に2つの構造パラメータを含む。 ラベル空間削減を行う自己適応型乗算重み付けアルゴリズムに基づく新規なオンライン手続きである。
  論文  参考訳（メタデータ） (2025-11-16T15:47:47Z)
• How hard is learning to cut? Trade-offs and sample complexity [9.721177829831316]
  両スコアに有効である新しいサンプル複雑性の低い境界を示す。 我々は、インスタンスをカットにマッピングする幅広いクラスの$mathcalF$に対して、それらのスコアを最小化するためにインスタンスの未知の分布を学習するには、同じクラス関数から学ぶのと同じくらい多くのサンプル(乗法定数まで)が必要であることを示す。 我々の結果は、制限されたカットセット、すなわちSimplex tableauから学習するケースにも及んでいる。
  論文  参考訳（メタデータ） (2025-05-30T21:41:01Z)
• The Computational Complexity of Positive Non-Clashing Teaching in Graphs [13.564319117200561]
  概念の集合の正の非クラッシング教育次元を計算する際の古典的およびパラメータ化された複雑性について検討する。 我々は、正の非クラッシング教育次元 k=2 のインスタンスに制限された場合でも、問題のNPハードネスを確立する。
  論文  参考訳（メタデータ） (2025-03-08T21:48:02Z)
• A Statistical Learning Perspective on Semi-dual Adversarial Neural Optimal Transport Solvers [70.37553728026309]
  本稿では,ミニマックス二次OT解法により得られた近似OT写像の一般化誤差の上限を確立する。 解析は2次OTに焦点をあてるが、同様の境界は一般的なOTの場合に導出され、将来の研究に期待できる方向を踏むことができると信じている。
  論文  参考訳（メタデータ） (2025-02-03T12:37:20Z)
• Non-Clashing Teaching Maps for Balls in Graphs [0.05356944479760104]
  関連する決定問題 B-NCTD$+$ for NCTD$+$ is NP-complete in split, co-bipartite and bipartite graphs を示す。 また、ETHが失敗しない限り、B-NCTD$+$は、時間で22o(textvc)cdot nO(1)$、カーネルに2o(textvc)cdot nO(1)$を出力するカーネル化アルゴリズムを許可しない。
  論文  参考訳（メタデータ） (2023-09-06T10:02:58Z)
• Lower Bounds for Learning in Revealing POMDPs [88.23337313766355]
  本稿では, 難易度の高い環境下での強化学習(RL)の基本的限界について検討する。 Emphmulti-steping POMDPs に対して、潜伏状態空間依存はサンプル複雑性において少なくとも$Omega(S1.5)$であることを示す。
  論文  参考訳（メタデータ） (2023-02-02T18:59:30Z)
• T2-GNN: Graph Neural Networks for Graphs with Incomplete Features and Structure via Teacher-Student Distillation [65.43245616105052]
  グラフニューラルネットワーク(GNN)は,様々な解析タスクをグラフデータ上で処理する手法として普及している。 本稿では,教師による蒸留に基づく一般GNNフレームワークを提案し,不完全グラフ上でのGNNの性能向上を図る。
  論文  参考訳（メタデータ） (2022-12-24T13:49:44Z)

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

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