論文の概要: Tales of Hoffman: from a distance

• arxiv url: http://arxiv.org/abs/2512.13187v1
• Date: Mon, 15 Dec 2025 10:51:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-16 17:54:56.628174
• Title: Tales of Hoffman: from a distance
• Title（参考訳）: ホフマン物語 遠くから
• Authors: Aida Abiad, Jan Meeus,
• Abstract要約: ホフマンは、隣接固有値を持つグラフ $G$ が$(G)geq 1+$ を満たすことを証明した。 我々は、この固有値を距離=k$設定に有界に拡張し、それに対応する量子距離グラフも下限であることを示すことによって、その強化を示す。
• 参考スコア（独自算出の注目度）: 2.2917707112773598
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Hoffman proved that a graph $G$ with adjacency eigenvalues $λ_1\geq \cdots \geq λ_n$ and chromatic number $χ(G)$ satisfies $χ(G)\geq 1+κ,$ where $κ$ is the smallest integer such that $$λ_1+\sum_{i=1}^κλ_{n+1-i}\leq 0.$$ We extend this eigenvalue bound to the distance-$k$ setting, and also show a strengthening of it by proving that it also lower bounds the corresponding quantum distance coloring graph parameter. The new bound depends on a degree-$k$ polynomial which can be chosen freely, so one needs to make a good choice of the polynomial to obtain as strong a bound as possible. We thus propose linear programming methods to optimize it. We also investigate the implications of the new bound for the quantum distance chromatic number, showing that it is sharp for some classes of graphs. Finally, we extend the Hoffman bound to the distance setting of the vector chromatic number. Our results extend and unify several previous bounds in the literature.
• Abstract（参考訳）: Hoffman は、隣接固有値を持つグラフ $G$ が $λ_1\geq \cdots \geq λ_n$ およびクロマティック数 $\(G)$ satisfies $\(G)\geq 1+κ,$ ここで $κ$ は最小整数であり、$$λ_1+\sum_{i=1}^κλ_{n+1-i}\leq 0.$ この固有値が距離$k$設定に結びついていることを証明し、対応する量子距離有色グラフパラメータを下限にすることでその強化を示すことを証明した。 新しい境界は自由選択できる次数-$k$多項式に依存するので、可能な限り強い境界を得るためには多項式のよい選択をする必要がある。 そこで我々は,最適化のための線形プログラミング手法を提案する。 また、量子距離色数に対する新しい境界の影響について検討し、グラフのいくつかのクラスに対して鋭いことを示す。 最後に、ホフマンをベクトル色数の距離設定に有界に拡張する。 我々の結果は、文学におけるいくつかの過去の境界を拡大し、統一する。

関連論文リスト

• Quantum speed-ups for solving semidefinite relaxations of polynomial optimization [3.1798318618973362]
  最適化のためのラッサール階層値を近似するための量子アルゴリズムについて検討する。 我々は,行列乗法重みに基づく量子アルゴリズムを提案し,その精度を$_k$と近似する。 QRAMを使わずに必要なブロックエンコーディングの実装方法を示す。
  論文  参考訳（メタデータ） (2025-11-18T11:48:33Z)
• Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
  本研究では、量子ビットの対数数を用いて、加算誤差$epsilonDelta_k$まで値を近似する量子アルゴリズムを提案する。 この分析における重要な技術的ステップは、適切なランダム初期状態の準備であり、最終的には閾値よりも小さい固有値の数を効率的に数えることができる。
  論文  参考訳（メタデータ） (2025-08-28T17:04:18Z)
• Quantum and classical query complexities of functions of matrices [0.0]
  任意の連続関数 $f(x):[-1,1]rightarrow [-1,1]$ に対して、計算の量子クエリ複雑性 $brai f(A) ketjpm varepsilon/4$ は$Omega(widetildedeg_varepsilon(f))$ で制限される。
  論文  参考訳（メタデータ） (2023-11-13T00:45:41Z)
• Quantum and classical low-degree learning via a dimension-free Remez inequality [52.12931955662553]
  ハイパーグリッド上の関数をポリトーラス上の高調波拡張に関連付ける新しい方法を示す。 巡回群 $exp(2pi i k/K)_k=1K$ の積に対して函数の上限が$f$であることを示す。 我々は最近、超キューブやキュービット上の観測可能な観測値の低次学習を、同様に効率的に行う方法として、EI22, CHP, VZ22を引用して、新しい空間に拡張した。
  論文  参考訳（メタデータ） (2023-01-04T04:15:40Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。 すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
  論文  参考訳（メタデータ） (2022-09-04T10:01:39Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
  論文  参考訳（メタデータ） (2022-03-17T23:52:08Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。 実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
  論文  参考訳（メタデータ） (2021-10-21T18:43:00Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)
• Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem [4.549831511476248]
  すべてのブール関数に対して、$f$, $bullet quad mathrmdeg(f) = O(widetildemathrmdeg(f)2)$:$f$の次数は、f$の近似次数において最も自明な二次数であることを示す。 f$ がその隣接行列で指定される $n$-頂点グラフの非単調グラフ特性であるならば、$mathrmQ(f)=Omega(n)$ もまた最適である。
  論文  参考訳（メタデータ） (2020-10-23T19:21:28Z)
• Q-learning with Uniformly Bounded Variance: Large Discounting is Not a Barrier to Fast Learning [7.6146285961466]
  我々は、すべての$gamma 1$に対して一様に束縛されたサンプル複雑性を持つ新しいアルゴリズムのクラスを導入する。 最適化されたステップサイズシーケンスとQ-ラーニングアルゴリズムの共分散は、1/(1-ガンマ)$の二次関数であることを示す。
  論文  参考訳（メタデータ） (2020-02-24T15:12:41Z)

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

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