Fugu-MT 論文翻訳(概要): Contradiction Graphs Determine VC Dimension

論文の概要: Contradiction Graphs Determine VC Dimension

arxiv url: http://arxiv.org/abs/2605.20434v1
Date: Tue, 19 May 2026 19:30:46 GMT
ステータス: 翻訳完了
システム内更新日: 2026-05-21 19:19:56.345858
Title: Contradiction Graphs Determine VC Dimension
Title（参考訳）: コントラディショングラフによるVC次元決定
Authors: Jesse Campbell, Daniel Ibaibarriaga, Lev Reyzin,
Abstract要約: 二項概念クラスに関連する矛盾グラフについて検討する。我々の主な結果は、単一のグラフ $G_m(H)$ が閾値述語 $mathrmVCdim(H)ge m$ を決定することである。
参考スコア（独自算出の注目度）: 0.45880283710344055
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We study the contradiction graphs associated with binary concept classes. For a class $H \subseteq \{0,1\}^X$, the order-$m$ contradiction graph $G_m(H)$ has as vertices the $H$-realizable labeled sequences of length $m$, with two vertices adjacent when the two sequences assign opposite labels to some common domain point. Our main result is that the single graph $G_m(H)$ determines the threshold predicate $\mathrm{VCdim}(H)\ge m$. Consequently, the full sequence $(G_m(H))_{m \ge 1}$ determines the exact VC dimension and, in particular, detects finite versus infinite VC dimension, answering a question posed by Alon et al. (2024).
Abstract（参考訳）: 二項概念クラスに関連する矛盾グラフについて検討する。クラス $H \subseteq \{0,1\}^X$ に対して、オーダー-$m$矛盾グラフ $G_m(H)$ は、長さ $m$ の$H$実現可能なラベル付き列を頂点として持つ。我々の主な結果は、単一のグラフ $G_m(H)$ が閾値述語 $\mathrm{VCdim}(H)\ge m$ を決定することである。その結果、完全列 $(G_m(H))_{m \ge 1}$ は正確なVC次元を決定し、特に有限または無限のVC次元を検出し、Alon et al (2024) の問いに答える。

関連論文リスト

Schur States, Average Mixing, and Counting Trees on Line Graphs' CTQW [0.0]
有限単純グラフ上の複素数値エッジ重みの族を、ライングラフ上の連続時間量子ウォークから生じる$G$で紹介する。構造的機構 -- $ellG$ の 2$ 固有空間 -- を同定し、通常の場合を超える一様可換状態を与える。
論文参考訳（メタデータ） (2026-05-03T16:31:26Z)
Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
携帯電話からYouTubeやTikTokなどのソーシャルメディアサイトにアップロードされたユーザー生成ビデオ(UGV)は、短くて繰り返しではない。我々は、ガーシュゴリンディスクアライメント(GDA)に基づく高速グラフサンプリングにより、遷移UGVを複数のディスクに線形時間で要約する。提案アルゴリズムは,最先端の手法と比較して,映像の要約性能が向上し,複雑さが大幅に低減されていることを示す。
論文参考訳（メタデータ） (2024-08-03T20:08:02Z)
Ridge Leverage Score Sampling for $\ell_p$ Subspace Approximation [47.790126028106734]
NPハードネスに対処するための一般的なアプローチは、強力なコアセットを計算することである。我々は$ell_p$サブスペース近似を$tilde O(kepsilon-4/p)$ for $p2$と$tilde O(kp/2epsilon-p)$ for $p>2$に対して強コアセットを構築するアルゴリズムを得る。
論文参考訳（メタデータ） (2024-07-03T16:49:28Z)
Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
論文参考訳（メタデータ） (2023-04-17T10:38:08Z)
Algebraic Aspects of Boundaries in the Kitaev Quantum Double Model [77.34726150561087]
我々は、Ksubseteq G$ の部分群に基づく境界の体系的な扱いを、バルクの Kokuev 量子倍 D(G)$ モデルで提供する。境界サイトは$*$-subalgebra $Xisubseteq D(G)$の表現であり、その構造を強い$*$-準ホップ代数として説明する。治療の応用として、水平方向の$K=G$と垂直方向の$K=e$に基づく境界付きパッチを調査し、量子コンピュータでどのように使用できるかを示す。
論文参考訳（メタデータ） (2022-08-12T15:05:07Z)
Universality of the fully connected vertex in Laplacian continuous-time quantum walk problems [0.0]
連続時間量子ウォーク(CTQW)がハミルトニアン$H=ガンマ L$で、グラフ$G$に依存しないことを証明する。本研究では,空間探索と量子輸送に本研究の結果を適用した。
論文参考訳（メタデータ） (2022-02-28T14:33:44Z)
Fast Computation of Generalized Eigenvectors for Manifold Graph Embedding [38.902986549367434]
我々は、高速実行に既存の高速極端固有ベクトル計算アルゴリズムを利用する。我々の埋め込みは文献の中では最速であり、多様体グラフのクラスタリング性能は最高のものとなっている。
論文参考訳（メタデータ） (2021-12-15T03:45:39Z)
Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文参考訳（メタデータ） (2021-10-21T18:43:00Z)
Exact Matching of Random Graphs with Constant Correlation [2.578242050187029]
本稿では, ErdHos--R'enyi グラフに対するグラフマッチングやネットワークアライメントの問題を扱う。これはグラフ同型問題のうるさい平均ケース版と見なすことができる。
論文参考訳（メタデータ） (2021-10-11T05:07:50Z)
A common variable minimax theorem for graphs [3.0079490585515343]
我々は、$mathcalG$の全てのグラフに対して滑らかな非定数関数が存在するかどうかを同時に理解し、それが存在するかどうかをどうやって見つけるかという問題を研究する。
論文参考訳（メタデータ） (2021-07-30T16:47:25Z)

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