論文の概要: Sunflowers and Ramsey problems for restricted intersections
- arxiv url: http://arxiv.org/abs/2504.15264v1
- Date: Mon, 21 Apr 2025 17:46:21 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-04-29 14:21:31.684596
- Title: Sunflowers and Ramsey problems for restricted intersections
- Title（参考訳）: 制限交叉に対するサンフラワーとラムゼー問題
- Authors: Barnabás Janzer, Zhihan Jin, Benny Sudakov, Kewen Wu,
- Abstract要約: F"uredi's famous semilattice lemma の変種が発見され、これは強力なデルタ系法における鍵となるツールである。
また,本手法の応用として,F"uredi's famous semilattice lemma の変種を求める。
- 参考スコア（独自算出の注目度）: 1.2201929092786905
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Extremal problems on set systems with restricted intersections have been an important part of combinatorics in the last 70 year. In this paper, we study the following Ramsey version of these problems. Given a set $L\subseteq \{0,\dots,k-1\}$ and a family $\mathcal{F}$ of $k$-element sets which does not contain a sunflower with $m$ petals whose kernel size is in $L$, how large a subfamily of $\mathcal{F}$ can we find in which no pair has intersection size in $L$? We give matching upper and lower bounds, determining the dependence on $m$ for all $k$ and $L$. This problem also finds applications in quantum computing. As an application of our techniques, we also obtain a variant of F\"uredi's celebrated semilattice lemma, which is a key tool in the powerful delta-system method. We prove that one cannot remove the double-exponential dependency on the uniformity in F\"uredi's result, however, we provide an alternative with significantly better, single-exponential dependency on the parameters, which is still strong enough for most applications of the delta-system method.
- Abstract（参考訳）: 制限交叉を持つ集合系の極端問題は、過去70年間、組合せ論において重要な部分を占めてきた。
本稿では,これらの問題のラムジー版について述べる。
集合 $L\subseteq \{0,\dots,k-1\}$ とファミリ $\mathcal{F}$ of $k$-element set は、カーネルサイズが$L$のサンフラワーと$m$ペダルを含まない。
一致した上限と下限を与え、すべての$k$と$L$に対する$m$への依存を決定する。
この問題は量子コンピューティングにも応用できる。
また,本手法の応用として,F\"uredi's famous semilattice lemma の変種を求める。
F\"uredi の結果の均一性に対する二重指数依存を除去できないことが証明されているが、デルタ系法のほとんどの応用にはまだ十分強いパラメータに対するより優れた単一指数依存の代替手段を提供する。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - Simultaneously Solving FBSDEs with Neural Operators of Logarithmic Depth, Constant Width, and Sub-Linear Rank [8.517406772939292]
フォワード・バックワード微分方程式(FBSDEs)は、最適制御、ゲーム理論、経済学、数学ファイナンスの中心である。
Small'' NOs は FBSDEs の構造された族に対する解演算子を均一に近似できることを示す。
また、同様の深さ、幅、ランクの畳み込みNOは、解作用素を楕円型PDEの広いクラスに近似することができることを示す。
論文 参考訳（メタデータ） (2024-10-18T18:01:40Z) - Variance-Reduced Fast Krasnoselkii-Mann Methods for Finite-Sum Root-Finding Problems [8.0153031008486]
有限和共役方程式 $Gx = 0$ を解くために, 分散還元を伴う高速クラスクラスKrasnoselkii-Mann 法を提案する。
我々のアルゴリズムは単一ループであり、より広範なルートフィンディングアルゴリズムのために特別に設計された、偏りのない分散還元推定器の新たなファミリーを利用する。
数値実験は我々のアルゴリズムを検証し、最先端の手法と比較して有望な性能を示す。
論文 参考訳（メタデータ） (2024-06-04T15:23:29Z) - Efficient Solution of Point-Line Absolute Pose [52.775981113238046]
点や線である可能性のある特徴間の3D--2D対応に基づくポーズ推定の特定の問題を再検討する。
得られた解法は数値的に安定かつ高速であることを示す。
論文 参考訳（メタデータ） (2024-04-25T12:09:16Z) - Box Facets and Cut Facets of Lifted Multicut Polytopes [2.531156266686649]
昇降型マルチカット問題の線形プログラム定式化について検討する。
2進線形プログラムのカット不等式がファセットを定義するかどうかを決定することはNPハードであることを示す。
論文 参考訳（メタデータ） (2024-02-26T18:37:16Z) - Tight Bounds for Quantum Phase Estimation and Related Problems [0.90238471756546]
精度$delta$と誤差確率$epsilon$は$Omegaleft(frac1deltalog1epsilonright)$であることを示す。
また、多くのアドバイス(アドバイス準備ユニタリの応用)を持つことは、コストを大幅に削減することはなく、また、$U$の固有値に関する知識も少なくないことも示している。
論文 参考訳（メタデータ） (2023-05-08T17:46:01Z) - Near-optimal fitting of ellipsoids to random points [68.12685213894112]
楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。
我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。
我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
論文 参考訳（メタデータ） (2022-08-19T18:00:34Z) - Linear Hashing with $\ell_\infty$ guarantees and two-sided Kakeya bounds [0.8594140167290096]
有限体上のランダムに選択された線型写像が $ell_infty$ の意味でよいハッシュ関数を与えることを示す。
負荷分散文献[RS98]からの既知のバウンダリにより、この結果は厳密であり、線形関数とトラリーランダム関数がエントロピー損失の定数因子であることを示す。
論文 参考訳（メタデータ） (2022-04-04T17:21:10Z) - 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) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-20T04:29:18Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳（メタデータ） (2020-05-13T16:44:12Z) - Curse of Dimensionality on Randomized Smoothing for Certifiable
Robustness [151.67113334248464]
我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。
我々はCIFARに関する実験結果を示し,その理論を検証した。
論文 参考訳（メタデータ） (2020-02-08T22:02:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。