論文の概要: Sublinear-Time Reconfiguration of Programmable Matter with Joint Movements
- arxiv url: http://arxiv.org/abs/2603.10720v1
- Date: Wed, 11 Mar 2026 12:52:12 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-03-21 18:33:56.686945
- Title: Sublinear-Time Reconfiguration of Programmable Matter with Joint Movements
- Title（参考訳）: 関節運動を伴うプログラム可能な物質のサブ線形時間再構成
- Authors: Manish Kumar, Othon Michail, Andreas Padalkin, Christian Scheideler,
- Abstract要約: 我々は,アメーバが平行して拡張・収縮する関節運動拡張に焦点を当てた。
本研究は, 補助仮定を使わずに, 関節運動モデルがサブ線形再構成をサポートすることを示す。
中心的なオープンな問題は、このモデル内の普遍的な再構成が多対数的あるいは定数時間で達成できるかどうかである。
- 参考スコア（独自算出の注目度）: 1.2381839952925602
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study centralized reconfiguration problems for geometric amoebot structures. A set of $n$ amoebots occupy nodes on the triangular grid and can reconfigure via expansion and contraction operations. We focus on the joint movement extension, where amoebots may expand and contract in parallel, enabling coordinated motion of larger substructures. Prior work introduced this extension and analyzed reconfiguration under additional assumptions such as metamodules. In contrast, we investigate the intrinsic dynamics of reconfiguration without such assumptions by restricting attention to centralized algorithms, leaving distributed solutions for future work. We study the reconfiguration problem between two classes of amoebot structures $A$ and $B$: For every structure $S\in A$, the goal is to compute a schedule that reconfigures $S$ into some structure $S'\in B$. Our focus is on sublinear-time algorithms. We affirmatively answer the open problem by Padalkin et al. (Auton. Robots, 2025) whether a within-the-model sublinear-time universal reconfiguration algorithm is possible, by proving that any structure can be reconfigured into a canonical line-segment structure in $O(\sqrt{n}\log n)$ rounds. Additionally, we give a constant-time algorithm for reconfiguring any spiral structure into a line segment. These results are enabled by new constant-time primitives that facilitate efficient parallel movement. Our findings demonstrate that the joint movement model supports sublinear reconfiguration without auxiliary assumptions. A central open question is whether universal reconfiguration within this model can be achieved in polylogarithmic or even constant time.
- Abstract（参考訳）: 幾何学的アメーボット構造に対する集中的再構成問題について検討する。
1組の$n$アメーボットは三角形のグリッド上のノードを占有し、拡張と収縮操作によって再構成することができる。
我々は,アメーバが平行に拡張・収縮し,より大きなサブ構造の協調運動を可能にする関節運動拡張に焦点を当てた。
以前の作業では、この拡張を導入し、メタモジュールのような追加の仮定の下で再構成を分析した。
これとは対照的に、このような仮定を伴わない再構成の本質的なダイナミクスについて、集中型アルゴリズムに注意を集中させ、分散ソリューションを今後の作業に残すことで検討する。
我々は、アメーボット構造の2つのクラス間の再構成問題を$A$と$B$: 全ての構造に対して$S\in A$に対して、$S$をある構造に再構成するスケジュールを計算することを目的としている。
サブ線形時間アルゴリズムに重点を置いています。
我々はPadalkin et al (Auton. Robots, 2025) によるオープンな問題に対して,任意の構造が$O(\sqrt{n}\log n)$ラウンドの正則線分構造に再構成可能であることを証明することによって,モデル内のサブ線形時間的普遍的再構成アルゴリズムが可能であるかどうかを肯定的に答える。
さらに,任意のスパイラル構造をラインセグメントに再構成する定数時間アルゴリズムを提案する。
これらの結果は、効率的な並列移動を容易にする新しい定数時間プリミティブによって実現される。
本研究は, 補助仮定を使わずに, 関節運動モデルがサブ線形再構成をサポートすることを示す。
中心的なオープンな問題は、このモデル内の普遍的な再構成が多対数的あるいは定数時間で達成できるかどうかである。
関連論文リスト
- Memory-Amortized Inference: A Topological Unification of Search, Closure, and Structure [6.0044467881527614]
単一の幾何学基板の位相遷移として学習と記憶を統一する形式的フレームワークであるtextbfMemory-Amortized Inference (MAI) を提案する。
我々は,高複雑さ探索を低複雑さ検索に変換することによって認知が機能することを示す。
この枠組みは、遅い思考(推論)から速い思考(直観)の出現に関する厳密な説明を提供する。
論文 参考訳（メタデータ） (2025-11-28T16:28:24Z) - A Quantifier-Reversal Approximation Paradigm for Recurrent Neural Networks [1.096028999747108]
本稿では,量子化器の順序を逆転する近似パラダイムを基本的に導入する。
各ターゲット関数$f$に対して、固定トポロジと固定重みを持つ単一リカレントニューラルネットワーク(RNN)を構築する。
我々のRNN構造は、基盤となる深いフィードフォワードReLUネットワーク近似理論をエミュレートする。
論文 参考訳（メタデータ） (2025-11-19T10:43:48Z) - A Support-Set Algorithm for Optimization Problems with Nonnegative and Orthogonal Constraints [9.143066261696683]
サポートセットを固定することにより、最小化サブプロブレムの大域的な解は、少なくとも$n$非ゼロなエントリを持つ閉形式で計算できることが示される。
中心となる要素は、ゼロでないエントリの配置を調整するサポートセットのための戦略的に考案された更新スキームである。
非負のPCA,クラスタリング,コミュニティ検出など,実世界のアプリケーションでは,数値的な結果が強く支持されている。
論文 参考訳（メタデータ） (2025-11-05T13:03:41Z) - Bootstrapping as a Morphism: An Arithmetic Geometry Approach to Asymptotically Faster Homomorphic Encryption [0.9179857807576733]
本稿では,従来の回路評価モデルを完全にバイパスするブートストラップ手法を提案する。
直射射影としてブートストラップ操作を再構成するために,現代の算術幾何学のツールを適用した。
我々の研究は、$O(d cdot textpoly(log q))$、$d$が環次元、$q$が暗号文である完全かつ確実に正しいブートストラップアルゴリズムである。
論文 参考訳（メタデータ） (2025-09-29T03:39:01Z) - Directional Non-Commutative Monoidal Structures for Compositional Embeddings in Machine Learning [0.0]
指向性非可換モノイド作用素上に構築された合成埋め込みのための新しい構造を導入する。
我々の構成では、各軸 i に対して異なる合成演算子 circ_i を定義し、大域的な可換性を与えることなく、各軸に沿って連想結合を保証する。
すべての軸特異作用素は互いに可換であり、一貫した交叉軸合成を可能にする大域的交換法則を強制する。
論文 参考訳（メタデータ） (2025-05-21T13:27:14Z) - Shuffled Autoregression For Motion Interpolation [53.61556200049156]
この作業は、モーションタスクのためのディープラーニングソリューションを提供することを目的としている。
本稿では,自己回帰を任意の(シャッフルされた)順序で生成するために拡張する,emphShuffled AutoRegressionと呼ばれる新しいフレームワークを提案する。
また,3つのステージを終端から終端の時空間運動変換器に組み込んだ依存グラフの構築手法を提案する。
論文 参考訳（メタデータ） (2023-06-10T07:14:59Z) - DepGraph: Towards Any Structural Pruning [68.40343338847664]
我々は、CNN、RNN、GNN、Transformersのような任意のアーキテクチャの一般的な構造解析について研究する。
本稿では,階層間の依存関係を明示的にモデル化し,包括的にグループ化してプルーニングを行う汎用かつ完全自動な手法であるemphDependency Graph(DepGraph)を提案する。
本研究では,画像用ResNe(X)t,DenseNet,MobileNet,Vision Transformer,グラフ用GAT,3Dポイントクラウド用DGCNN,言語用LSTMなど,さまざまなアーキテクチャやタスクに関する手法を広範囲に評価し,言語用LSTMと並行して示す。
論文 参考訳（メタデータ） (2023-01-30T14:02:33Z) - A Recursively Recurrent Neural Network (R2N2) Architecture for Learning
Iterative Algorithms [64.3064050603721]
本研究では,リカレントニューラルネットワーク (R2N2) にランゲ・クッタニューラルネットワークを一般化し,リカレントニューラルネットワークを最適化した反復アルゴリズムの設計を行う。
本稿では, 線形方程式系に対するクリロフ解法, 非線形方程式系に対するニュートン・クリロフ解法, 常微分方程式に対するルンゲ・クッタ解法と類似の繰り返しを計算問題クラスの入力・出力データに対して提案した超構造内における重みパラメータの正規化について述べる。
論文 参考訳（メタデータ） (2022-11-22T16:30:33Z) - Competitive Mirror Descent [67.31015611281225]
制約のある競合最適化には、制約の対象となる競合する目的を最小化しようとする複数のエージェントが含まれる。
本稿では, 競合ミラー降下法(CMD)を提案する。
特別の場合として、正の円錐上の問題に対する新しい競合乗法重みアルゴリズムを得る。
論文 参考訳（メタデータ） (2020-06-17T22:11:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。