論文の概要: A Forced-Structure Reduction and Verifiable Bounds for Conway's 99-Graph
- arxiv url: http://arxiv.org/abs/2608.11211v1
- Date: Mon, 13 Jul 2026 18:42:21 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-17 01:32:04.575416
- Title: A Forced-Structure Reduction and Verifiable Bounds for Conway's 99-Graph
- Title（参考訳）: コンウェイ99グラフの強制構造低減と検証可能な境界
- Abstract要約: コンウェイの99グラフ問題はパラメータ $mathrmsrg(99,14,1,2)$ の強い正則グラフが存在するかどうかを問うものである。
我々は,自律型AI研究エージェントによる,体系的で完全に再現可能な攻撃を報告した。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Conway's 99-graph problem asks whether a strongly regular graph with parameters $\mathrm{srg}(99,14,1,2)$ exists. We report a systematic, fully reproducible attack by an autonomous AI research agent, scored under the track's partial-credit metric. Our verifiable contributions are: (1) an exhaustive proof that no circulant graph on $\mathbb{Z}/99$ satisfies more than $3366/4950=68.0\%$ of the constraints ($33$ of $49$ difference-classes), with the same ceiling for the other abelian group of order $99$; (2) a forced-structure reduction: $λ=1$ makes each neighbourhood a perfect matching and $μ=2$ puts the outer vertices in bijection with non-matched neighbour-pairs, collapsing existence to a $12$-regular graph on $84$ vertices, encoded for CP-SAT and validated by recovering the unique $\mathrm{srg}(9,4,1,2)$; (3) a validated prescribed-automorphism orbit-existence framework (fixed-point-free and single-fixed-point actions, checked on $\mathrm{srg}(9,4,1,2)$ and the Paley graph $\mathrm{srg}(13,6,2,3)$), and (4) a best verified artifact at $69.43\%$, with evidence that this is a robust frontier (fourteen distinct methods, none exceeding it) entangled with the open question, since any provable bound below $4950$ is a non-existence proof.
- Abstract（参考訳）: コンウェイの99グラフ問題はパラメータ $\mathrm{srg}(99,14,1,2)$ の強い正則グラフが存在するかどうかを問うものである。
我々は、自律的なAI研究エージェントによる、系統的で完全に再現可能な攻撃を報告した。
1$$\mathbb{Z}/99$の循環グラフが3366/4950=68.0\%以上の制約を満たさないという徹底的な証明(33$$$499$差分クラス) 2$99$の他のアーベル群と同じ天井:$λ=1$の強制構造削減 それぞれの近傍を完全なマッチングにし、$μ=2$の円周グラフを非適合の隣のペアでビジェクションし、84$の頂点上で12$正則グラフに崩壊させ、CP-SATでエンコードされ、ユニークな$\mathrms}(9,4,1,24,1,2), (3)の公準同型フレームワークを検証することにより、CP-SATでエンコードされる。
関連論文リスト
- The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
AxiotisとSviridenkoは[AS21]において、凸最適化における制限条件数への線形依存はスパース時間アルゴリズムでは改善できないと推測した。
我々は、最小二乗目的に対する予想下界を確立し、ランダム化された完全体積小セット展開仮説に基づく条件付けを行う。
論文 参考訳（メタデータ） (2026-08-03T17:57:01Z) - The Exact Worst-Case Tail Probability under Bounded Kurtosis [39.91890433860882]
片側テールコントロールのために、クルトーシスバウンドが何を買うか、正確に決定する。
平均$0$、分散$1$、そして少なくとも$$4の4モーメントを持つ実乱変数のクラス$mathcalC()$の場合、歪みは自由のままである。
論文 参考訳（メタデータ） (2026-07-06T15:40:54Z) - Detection of local geometry in random graphs: information-theoretic and computational limits [4.67223325681232]
ランダムグラフにおける局所幾何学の検出問題について検討する。
平均サイズ$k$の隠れコミュニティがランダムな幾何グラフとして描画されるようなモデル$mathcalG(n, p, d, k)$を導入する。
残りのすべての辺はアーズ=レーニモデル $mathcalG(n, p)$ に従う。
論文 参考訳（メタデータ） (2026-03-25T17:20:01Z) - Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
このタスクに対する効率的な統計的クエリアルゴリズムは、VSTATの複雑さを少なくとも$tildeOmega(d1/2/alpha2)$で要求する。
論文 参考訳（メタデータ） (2025-10-12T15:42:44Z) - Detecting Arbitrary Planted Subgraphs in Random Graphs [7.320365821066746]
本稿では,ErdHos-R'enyi乱数グラフ$mathcalG(n, q_n)$における仮設植木部分グラフ$Gamma = Gamma_n$の検出について検討する。
エッジ確率が$p_n$と$q_n$が固定された高密度な状態では、Gamma$を検出するための情報理論および計算しきい値が強く特徴付けられる。
論文 参考訳（メタデータ） (2025-03-24T18:54:43Z) - Low-degree Security of the Planted Random Subgraph Problem [12.329446579556606]
植付されたランダムな部分グラフを最大$kleq n1 - Omega(1)$まで検出する際の低次硬さを証明した。
我々は,(1) ランダム関数のための通信最適化多元的PSMプロトコル,(2) 共有サイズが$(1 + epsilon)log n$ for any $epsilon > 0$ に対して,最大$r$の任意の最小限の連立関係を再構築し,最大$ell = o(epsilon log n)1/(r-1)$までの未定部分集合に対して秘密保持する,という予想を適用した。
論文 参考訳（メタデータ） (2024-09-24T16:42:00Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - 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) - On the Unlikelihood of D-Separation [69.62839677485087]
解析的な証拠として、大きなグラフ上では、d-分離は存在が保証されたとしても珍しい現象である。
PCアルゴリズムでは、その最悪ケース保証がスパースグラフで失敗することが知られているが、平均ケースでも同じことが言える。
UniformSGSでは、既存のエッジに対してランニング時間が指数的であることが知られているが、平均的な場合、それは既存のほとんどのエッジにおいても期待されるランニング時間であることを示す。
論文 参考訳（メタデータ） (2023-03-10T00:11:18Z) - Random Graph Matching in Geometric Models: the Case of Complete Graphs [21.689343447798677]
本稿では, エッジ重み付き2つの完全グラフが潜在測地によって相関する問題について検討する。
近似最大極大推定器を導出し、高い確率で$pi*$の完全回復を確実に達成する。
副次的な発見として、[Ume88] の有望なスペクトルアルゴリズムが幾何モデルにおける最大可能性のさらなる近似として現れることを示す。
論文 参考訳（メタデータ） (2022-02-22T04:14:45Z) - Random Subgraph Detection Using Queries [29.192695995340653]
植込み高密度部分グラフ検出問題は、与えられた(ランダム)グラフに異常に密度の高い部分グラフが存在するかどうかをテストするタスクを指す。
本稿では,適応的なエッジクエリを用いてグラフの比較的小さな部分のみを観測できる,上記の問題の自然な変形について考察する。
このモデルでは,植込み部分グラフの存在を検出するのに必要なクエリ数と十分なクエリ数(準多項式最適アルゴリズムを伴う)を決定する。
論文 参考訳（メタデータ） (2021-10-02T07:41:17Z) - Curse of Dimensionality on Randomized Smoothing for Certifiable
Robustness [151.67113334248464]
我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。
我々はCIFARに関する実験結果を示し,その理論を検証した。
論文 参考訳（メタデータ） (2020-02-08T22:02:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。