This paper presents a near-quadratic-time algorithm that correctly matches almost all nodes of two correlated Erdős-Rényi graphs without any incorrect matches. Each graph has average degree $λ$ and its edges are subsampled from a common parent Erdős-Rényi graph with $n$ nodes, with subsampling probability $s$. The nodes of one graph are then relabeled by an unknown permutation. The algorithm is built on a test for correlated versus independent Galton-Watson trees with approximated likelihood ratios. For every constant $s>\sqrt{C_{\mathrm{Otter}}}$, where $C_{\mathrm{Otter}}\approx0.338$ is Otter's tree-counting constant, and every $λ=ω(1)$ with $λ=(\log n)^{O(1)}$, the algorithm outputs a partial matching of size $n-o(n)$ that contains no incorrect matches with high probability. If, in addition, $λs\ge(1+ε)\log n$ for a constant $ε>0$, a seeded completion step recovers the permutation exactly. In both cases, the time complexity of the algorithm is $n^{2+o(1)}$ with high probability, whereas previous polynomial-time algorithms with the same guarantees either have a time-complexity bound whose exponent goes to $\infty$ as $s$ approaches $\sqrt{C_{\mathrm{Otter}}}$ from above, or apply only when $s$ is close to $1$.
Edge user/service scheduling governs where and how AI services are executed under limited communication and computing resources. Existing edge scheduling frameworks typically assume numerically specified service requirements, such as latency bounds and energy budgets. However, users often express ambiguous and context-dependent expectations in natural language, creating a gap between user intent and scheduling decisions. We propose semantic contract-guided edge potential scheduling (STEPS), a natural language-driven framework that introduces semantic contracts as executable interfaces between user-side semantics and edge-side decisions. A large language model (LLM)-assisted semantic parser extracts service requirements and raw confidence scores from natural language requests. Confidence calibration and interpretable mapping rules convert these outputs into preference weights, fulfillment bounds, and semantic uncertainty. STEPS formulates intended per-slot edge scheduling as an exact potential game for execution-node selection, computing-resource provisioning, and bandwidth allocation, followed by capacity-feasible resource realization. Fulfillment-driven feedback signals enable adaptive scheduling under evolving service and network conditions. We establish the existence of pure-strategy Nash equilibrium, prove finite-step convergence of uncapped strict best-response dynamics, and characterize the boundedness of projected adaptive-control parameters. Experiments under synthetic and Melbourne-based hybrid settings demonstrate improved contract fulfillment and reduced service loss relative to several adapted benchmarks. Post-drift evaluations further show that feedback adaptation improves fulfillment and admission coverage under the tested conditions.
Zhifeng Gu, Ying Chen, Rui Jiang, Lei Yi, Bing Wang
Experience can help embodied agents turn high-level plans into grounded actions, but transferring it across tasks remains challenging: previously effective strategies may be inapplicable to the current state or fail to produce their intended outcomes. We present EmbodiExp, a framework for constructing transferable experiences and composing them online during embodied task execution. Our key observation is that tasks often share subgoals whose completion can be assessed independently of overall task success. We therefore introduce an outcome-grounded subgoal experience that specifies a subgoal, applicability conditions, an adaptable policy, and a verifiable outcome. During execution, applicable experiences guide action generation, while verified outcomes can establish the conditions required by subsequent experiences, enabling online composition. Subgoal-level outcome attribution further enables failure utilization: failed trajectories can still contribute verified local successes and condition-specific guidance on actions to avoid. Experiments on multiple embodied benchmarks under a fold-based protocol with frozen experience banks demonstrate the effectiveness of EmbodiExp.