論文の概要: Optimal Unambiguous DNFs and Alon-Saks-Seymour
- arxiv url: http://arxiv.org/abs/2608.02533v1
- Date: Mon, 03 Aug 2026 17:26:54 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-04 15:07:25.729555
- Title: Optimal Unambiguous DNFs and Alon-Saks-Seymour
- Title（参考訳）: 最適不明瞭DNFとアロン-サクス-スキーモア
- Abstract要約: 幅が$O(n)$だが、$0$-certificate complexity $(n2)$ の DNF を構築する。
我々はDNFを通信問題に持ち上げる定数サイズのガジェットで持ち上げる定理を証明した。
このことは、アロン・サクス・シーモア予想の最適反響につながる。
- 参考スコア（独自算出の注目度）: 7.0223797053352
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We construct unambiguous DNFs having width $O(n)$ but $0$-certificate complexity $Ω(n^2)$. By utilizing the special structure of these DNFs, we prove a lifting theorem with a constant-sized gadget that lifts the DNF to a communication problem, while losslessly translating the separation in certificate complexity to a separation in communication complexity. This leads to an optimal refutation of the Alon-Saks-Seymour conjecture, as well as an optimal communication lower bound for the Clique versus Independent Set problem, improving the previous results of Balodis, Ben-David, Göös, Jain and Kothari (FOCS 2021, SICOMP 2023) by several doubly logarithmic factors. As further applications of our construction to query complexity and learning theory, we exhibit: (a) a family of Boolean functions that has an optimal quartic separation between certificate complexity and approximate degree, and (b) a sample compression lower bound of $Ω(\sqrt{\log c})$ for multiclass concept classes over $c$ labels.
- Abstract（参考訳）: 我々は、幅が$O(n)$であるが、$0$-certificate complexity $Ω(n^2)$の曖昧なDNFを構成する。
これらのDNFの特別な構造を利用して、DNFを通信問題に引き上げる一定サイズのガジェットを用いてリフト定理を証明し、通信複雑性の分離を通信複雑性の分離に無意味に変換する。
このことは、アロン・サクス=シーモア予想の最適解と、Clique対Independent Set問題に対する最適な通信下界を導き、いくつかの二重対数因子によるバロディス、ベンダビッド、ゲース、ジャイナ、コタリ(FOCS 2021, SICOMP 2023)の以前の結果を改善した。
複雑性と学習理論を問合せするための我々の構築のさらなる応用として、以下を示す。
(a)証明複雑性と近似度との間に最適なクォート的分離を有するブール関数の族、及び
(b)$c$ラベル上のマルチクラス概念クラスに対して$Ω(\sqrt{\log c})$のサンプル圧縮下界。
関連論文リスト
- A Near-Quartic Separation Between Certificate Complexity and Quantum Query Complexity [0.0]
合計ブール関数$f$, $Q(f) = widetildeO(sqrt[4]C(f))$, $Q(f)$は有界エラー量子クエリ複雑性を示し、$C(f)$は証明複雑性を表す。
論文 参考訳（メタデータ） (2026-09-10T15:04:28Z) - AI-Assisted Discovery of Convex Relaxations via Dual Agents [56.60366723277675]
すべての許容関数に対して下界が成り立ち、より強い境界を与える凸緩和から従うことを示す。
理論は各エージェントを検証し、反例を検索し、報告されたすべての境界はインターバルにおける明示的な二重実現可能な点によって認証される。
論文 参考訳（メタデータ） (2026-06-30T06:10:25Z) - Tight $L_\infty$ Sample Complexity for Low-Degree and Sparse Boolean Polynomials [2.5199066832791535]
ブールハイパーキューブ上でのサロゲートの学習問題について検討する。
通常の$L$型保証よりも、均一な$L_infty$-error保証が必要です。
本結果は,最適化セーフなサロゲートを学習する際のサンプルの複雑さの厳密な証明を提供する。
論文 参考訳（メタデータ） (2026-06-15T22:00:03Z) - Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale [54.65053906803857]
実数値関数クラスが一様収束と学習可能性を示す最適尺度について検討する。
本研究の主な成果は,PAC学習の基本定理のスケール敏感な一般化である。
また、定量的サンプルの複雑さと評価可能性に関するオープンな質問をいくつか取り上げる。
論文 参考訳（メタデータ） (2026-05-13T15:41:30Z) - On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularization [54.77408659142336]
Kullback-Leibler (KL) の正規化は、オフラインの意思決定で広く使われている。
大規模な正規化の下では$tildeO(SAC*/)$のサンプル複雑性を実現する。
また、よりシャープなサンプル複雑性の下界も提供し、これは正規化強度の全範囲にわたる上界と一致する。
論文 参考訳（メタデータ） (2026-05-04T01:46:35Z) - Kolmogorov Complexity Bounds for LLM Steganography and a Perplexity-Based Detection Proxy [2.0305676256390934]
大きな言語モデルは、テキストを書き直して隠れペイロードを埋め込むことができる。
このような埋め込みにおける情報理論のコストについて検討する。
色に基づくLCMステガノグラフィースキームによる予備実験は、理論予測を支持する。
論文 参考訳（メタデータ） (2026-03-23T04:40:46Z) - Quantum State-Aware Query Complexity: Krylov Compression and Polynomial Query Duality [0.0]
この状態認識の観点は、量子クエリによるKrylov/Favard近似という最悪のケース境界を洗練させ、状態依存のスペクトル構造が均一な設計よりも大幅に節約できるかを説明している。
論文 参考訳（メタデータ） (2025-10-13T18:00:03Z) - Rate optimal learning of equilibria from data [63.14746189846806]
マルチエージェント・イミテーション・ラーニング(MAIL)における理論的ギャップは,非対話的MAILの限界を特徴づけ,ほぼ最適なサンプル複雑性を持つ最初の対話的アルゴリズムを提示することによって解決する。
インタラクティブな設定では、報酬のない強化学習と対話型MAILを組み合わせたフレームワークを導入し、それをMAIL-WARMというアルゴリズムでインスタンス化する。
我々は,我々の理論を裏付ける数値的な結果を提供し,グリッドワールドのような環境において,行動クローンが学習に失敗する状況を示す。
論文 参考訳（メタデータ） (2025-10-10T12:28:35Z) - The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem [53.446980306786095]
スムースブースターは任意の例にあまり重みを付けない分布を生成する。
もともとは耐雑音性のために導入されたが、そのようなブースターは微分プライバシー、軽度、量子学習理論にも応用されている。
論文 参考訳（メタデータ） (2024-09-17T23:09:25Z) - Matrix Discrepancy from Quantum Communication [13.782852293291494]
我々は,不一致の最小化と(量子)通信複雑性の新たな関連性を開発する。
対称$n times n$$A_1,ldots,A_n$ with $|A_i| leq 1$ and $|A_i|_F leq n1/4$ に対し、pm 1n において $sum_i leq n x_i A_i$ の最大固有値が最大となる符号 $x が存在することを示す。
論文 参考訳（メタデータ） (2021-10-19T16:51:11Z) - Permutation Compressors for Provably Faster Distributed Nonconvex
Optimization [68.8204255655161]
本稿では,Gorbunov et al (2021) の MARINA 法が,理論的な通信複雑性の観点から最先端の手法とみなすことができることを示す。
MARINAの理論は、古典的な独立圧縮機設定を超えて、潜在的にエミュレートされた圧縮機の理論を支持するものである。
論文 参考訳（メタデータ） (2021-10-07T09:38:15Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。