論文の概要: CayleyPy Growth: Efficient growth computations and hundreds of new conjectures on Cayley graphs (Brief version)

• arxiv url: http://arxiv.org/abs/2509.19162v1
• Date: Tue, 23 Sep 2025 15:40:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-24 20:41:27.930594
• Title: CayleyPy Growth: Efficient growth computations and hundreds of new conjectures on Cayley graphs (Brief version)
• Title（参考訳）: CayleyPy成長: Cayleyグラフ上の効率的な成長計算と数百の新しい予想(Brief version)
• Authors: A. Chervov, D. Fedoriaka, E. Konstantinova, A. Naumov, I. Kiselev, A. Sheveleva, I. Koltsov, S. Lytkin, A. Smolensky, A. Soibelman, F. Levkovich-Maslyuk, R. Grimov, D. Volovich, A. Isakov, A. Kostin, M. Litvinov, N. Vilkin-Krom, A. Bidzhiev, A. Krasnyi, M. Evseev, E. Geraseva, L. Grunwald, S. Galkin, E. Koldunov, S. Diner, A. Chevychelov, E. Kudasheva, A. Sychev, A. Kravchenko, Z. Kogan, A. Natyrova, L. Shishina, L. Cheldieva, V. Zamkovoy, D. Kovalenko, O. Papulov, S. Kudashev, D. Shiltsov, R. Turtayev, O. Nikitina, D. Mamayeva, S. Nikolenko, M. Obozov, A. Titarenko, A. Dolgorukova, A. Aparnev, O. Debeaupuis, S. Alami C., H. Isambert,
• Abstract要約: CayleyPyはオープンソースのPythonライブラリで、CayleyとSchreierのグラフで計算できる。 GAPやSageのようなシステムと比較して、CayleyPyはより大きなグラフを処理し、桁違いに高速に処理する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This is the third paper of the CayleyPy project applying artificial intelligence to problems in group theory. We announce the first public release of CayleyPy, an open source Python library for computations with Cayley and Schreier graphs. Compared with systems such as GAP and Sage, CayleyPy handles much larger graphs and performs several orders of magnitude faster. Using CayleyPy we obtained about 200 new conjectures on Cayley and Schreier graphs, focused on diameters and growth. For many Cayley graphs of symmetric groups Sn we observe quasi polynomial diameter formulas: a small set of quadratic or linear polynomials indexed by n mod s. We conjecture that this is a general phenomenon, giving efficient diameter computation despite the problem being NP hard. We propose a refinement of the Babai type conjecture on diameters of Sn: n^2/2 + 4n upper bounds in the undirected case, compared to previous O(n^2) bounds. We also provide explicit generator families, related to involutions in a square with whiskers pattern, conjectured to maximize the diameter; search confirms this for all n up to 15. We further conjecture an answer to a question posed by V M Glushkov in 1968 on directed Cayley graphs generated by a cyclic shift and a transposition. For nilpotent groups we conjecture an improvement of J S Ellenberg's results on upper unitriangular matrices over Z/pZ, showing linear dependence of diameter on p. Moreover. Some conjectures are LLM friendly, naturally stated as sorting problems verifiable by algorithms or Python code. To benchmark path finding we created more than 10 Kaggle datasets. CayleyPy works with arbitrary permutation or matrix groups and includes over 100 predefined generators. Our growth computation code outperforms GAP and Sage up to 1000 times in speed and size.
• Abstract（参考訳）: これは、人工知能をグループ理論の問題に適用するCayleyPyプロジェクトの3番目の論文である。 CayleyPyはオープンソースのPythonライブラリで、CayleyとSchreierのグラフで計算できる。 GAPやSageのようなシステムと比較すると、CayleyPyはより大きなグラフを処理し、桁違いに高速に処理する。 CayleyPyを用いて、直径と成長に焦点を当てたケイリーグラフとシュライアーグラフに関する約200の新しい予想を得た。 対称群 Sn の多くのケイリーグラフに対して、準多項式直径公式: n mod s で指数付けられた二次多項式あるいは線型多項式の小さな集合を観察する。 これはNP困難であるにもかかわらず、効率的な直径計算を与える一般的な現象であると推測する。 Sn の直径 n^2/2 + 4n 上界のババイ型予想を、以前の O(n^2) 上界と比較して改善する。 また、ウィスキーパターンを持つ正方形の畳み込みに関連する明示的なジェネレータファミリも提供し、この直径を最大にすることを予想し、探索により全 n に対して 15 まで確認する。 さらに、1968年に V M Glushkov によって提起された、巡回シフトと転置によって生成される有向ケイリーグラフ上の質問に対する答えを予想する。 零群に対しては、Z/pZ 上の上一角行列に対する J S Ellenberg の結果の改善を予想し、p 上の直径の線型依存を示す。 さらに。 一部の予想はLLMフレンドリーであり、アルゴリズムやPythonコードで検証可能なソート問題として自然に述べられている。 パスを見つけるために、私たちは10以上のKaggleデータセットを作成しました。 CayleyPyは任意の置換あるいは行列群で動作し、100以上の事前定義されたジェネレータを含む。 我々の成長計算コードは、GAPとSageを最大1000倍のスピードとサイズで上回ります。

関連論文リスト

• The Geometry of LLM Quantization: GPTQ as Babai's Nearest Plane Algorithm [52.89358421626026]
  GPTQは、LLMスケールでのワンショットポストトレーニング量子化の標準手法の1つとして登場した。 GPTQは古典的最近ベクトル問題に対するババイの最も近い平面アルゴリズムと数学的に同一であることを示す。
  論文  参考訳（メタデータ） (2025-07-24T16:22:18Z)
• Diffusion Models for Cayley Graphs [0.0]
  拡散モデルの枠組みにおける問題を定式化する方法を示す。 本稿では,従来の比較アルゴリズムよりも大幅に改善された逆スコアのアンサッツを提案する。
  論文  参考訳（メタデータ） (2025-03-07T16:33:16Z)
• CayleyPy RL: Pathfinding and Reinforcement Learning on Cayley Graphs [0.0]
  本論文は,大規模グラフ上でのパスフィリングのための効率的な人工知能ベースのアプローチの開発に関する一連の研究の2番目である。 本稿では, 強化学習手法と, 第1報より直接拡散距離法を併用した新しい手法を提案する。 我々は、OEIS-A186783予想に対して、この直径が機械学習と数学的手法によりn(n-1)/2に等しいという強い支持を与える。
  論文  参考訳（メタデータ） (2025-02-25T21:53:41Z)
• Imaginary Hamiltonian variational ansatz for combinatorial optimization problems [3.14105061893604]
  パラメタライズド量子ゲートのツリー配置を導入し、1ラウンド$i$HVAを用いて任意のツリーグラフを正確に解けるようにする。 我々のアンサッツは、最大24ノードと$D leq 5$のグラフに対して、MaxCutを正確に解く。
  論文  参考訳（メタデータ） (2024-08-17T03:34:17Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
  スポンジハッシュは、広く使われている暗号ハッシュアルゴリズムのクラスである。 これまでのところ、不規則な置換は根本的なオープンな問題のままである。 ランダムな2n$-bit置換でゼロペアを見つけるには、少なくとも$Omega(2n/2)$多くのクエリが必要である。
  論文  参考訳（メタデータ） (2024-03-07T18:46:58Z)
• Large-Plaintext Functional Bootstrapping in FHE with Small Bootstrapping Keys [1.6319731389952283]
  機能的ブートストラップは完全同型暗号化(FHE)のコア技術である 本稿では,ベクトル内の任意の関数のルックアップテーブルを符号化し,その係数がより多くのデータを保持できることを示す。 新しいアルゴリズムは、キーサイズが小さく、キースイッチングのキーサイズが小さいことで、キーサイズが大幅に改善され、実行時のコストが一定に向上する。
  論文  参考訳（メタデータ） (2023-10-19T03:30:36Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。 このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。 本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-30T15:57:14Z)
• The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model [0.0]
  量子近似最適化アルゴリズム (QAOA) は最適化問題の近似解を求める。 任意の深さで$D$に対して性能を評価するための反復式を任意の深さ$p$で与える。 我々は、QAOAが無限大の$p$でパリの価値を達成できるという楽観的な予想を立てる。
  論文  参考訳（メタデータ） (2021-10-27T06:35:59Z)
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
  この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。 我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。 標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
  論文  参考訳（メタデータ） (2021-07-09T16:04:24Z)
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
  アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。 ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
  論文  参考訳（メタデータ） (2020-04-25T05:45:59Z)

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

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