概要 - マッチングの単調回路複雑度
タイトル
マッチングの単調回路複雑度
時間
2025-07-21 23:13:29
著者
{"Bruno Cavalar","Mika Göös","Artur Riazanov","Anastasia Sofronova","Dmitry Sokolov"}
カテゴリ
{cs.CC,math.CO}
リンク
http://arxiv.org/abs/2507.16105v1
PDF リンク
http://arxiv.org/pdf/2507.16105v1
概要
ブルーノ・カバラ、ミカ・ゴーゼ、アールチュール・リアザノフ、アナスタシア・ソフロノワ、ディミトリ・ソコロフの論文は、n次元グラフ上の二部対称マッチング関数が少なくとも2^nサイズのモノトーン回路を必要とすることを確立しました。これは、ラズボロフ（1985年）のn^Ω(log n)の前の下界を改善しました。証明は標準の近似法と新しいバラッド・レマ（マッチング用）を組み合わせて行われました。 ポイント： * この論文は、二部対称マッチングが少なくとも2^nサイズのモノトーン回路を必要とすることを示し、ラズボロフ（1985年）のn^Ω(log n)の前の下界を改善しました。 * 証明は、入力領域上の分布を定義し、小さいモノトーン回路で関数が計算された場合、それが小さいモノトーンDNFで近似できることを示す標準の近似法を使用しています。 * 証明の技術的な鍵は、モノトーンDNFが単一の項で安全に置き換えられる状況を特定することです。 * この論文はまた、「奇数因子」関数に対する下界も証明しており、グラフがすべての度が奇数の拡張子グラフを含む場合に1を出力する関数です。 * 証明は、Zq-満足問題などの他の分布や関数にも拡張されます。 * この結果は、グラフの性質の複雑さやモノトーン回路の力に影響を与えます。
推奨論文
時間までのイベントモデルを使用して、新しい長期的なUNOSデータセットを通じて心臓移植における待機リスト死亡率予測のベンチマーク評価
メグレズ2 技術報告
RealBench：リアルワールドIPデザインを使用したVerilog生成モデルのベンチマーク評価
MIRAGE-Bench: LLMエージェントが幻覚を見ており、どこにそれらを見つけるか
視覚と言語のトレーニングは分類学的知識の展開を助けますが、それを根本的に変えるものではありません
「真空圧縮強化微メートル尺度蒸気セル磁力計」
AbGen: 科学研究のための消去研究設計と評価における大規模言語モデルの評価
多スケールの神経PDEサローグラットの予測とダウンスケーリングへの適用：海流への応用
自回归時間序列のための効率的な因果発見
凸二次最大化におけるアクティブセット法の無条件の下界