Executing service workflows with directed acyclic graph (DAG) dependencies over wireless distributed computing networks requires joint control of function placement, routing, and scheduling, together with synchronization of inputs from the same request at merge points. We study throughput-optimal control of these networks under stochastic request arrivals, time-varying wireless links, and interference constraints. We use a valid mapping abstraction that assigns each service function to a computation node and each DAG dependency to a routing path. Using this abstraction, we characterize the network capacity region to support service DAGs, and prove that synchronizing the packets of a request at merge points does not shrink the region. We develop Dynamic Computing Network Control for service DAGs (DCNC-DAG), a dynamic control policy that selects queue-aware valid mappings and schedules service DAG execution by nearest-to-origin (NTO) while enforcing input synchronization at merge points. With exact minimum-cost valid mappings, DCNC-DAG is throughput-optimal and ensures rate stability of the physical queues under bounded arrivals. These guarantees hold for any fixed finite interval between mapping updates, even when mapping decisions rely on boundedly stale queue length information. For larger service DAGs, we develop DCNC-DAG-H, which replaces exact mapping optimization with a queue-aware heuristic. Simulations show that DCNC-DAG supports $2.7\times$-$5.5\times$ the throughput of queue-blind baselines, while DCNC-DAG-H achieves up to $2.68\times$ those of the corresponding baselines on larger workflow and AI service DAGs.
The binary perceptron is a random constraint satisfaction problem that asks for a sign vector satisfying a system of random linear inequalities. Its solution space has a strikingly extreme geometry: at every positive constraint density, all but a vanishing fraction of the solutions are isolated. Yet polynomial-time algorithms find solutions at small enough constraint density, which raises the question of how efficient algorithms navigate such a landscape. Linear programming is a natural algorithm to study here, but its analysis has so far been limited to a single round. Li, Schramm, and Zhou (STOC 2025) analyzed one linear program followed by iterative rounding. In this work, we overcome this limitation and give a precise analysis of iterated linear programming for the binary perceptron. (1) For Gaussian matrices and any fixed number of rounds, we characterize the iterated linear programs exactly through a deterministic state-evolution recursion. (2) Adding a final rounding step, we obtain a randomized polynomial-time algorithm for the binary perceptron. Numerical evaluations of the recursion provide evidence that it succeeds at constraint density $α=0.60$ with zero margin, well beyond the range $α\le0.1$ guaranteed by the single-LP analysis and $α\approx0.327$ (Jo and Lee, 2026), the best guarantee so far. (3) We establish universality, showing that the same characterization holds for matrices with i.i.d. entries drawn from any centered, unit-variance subgaussian law. The key idea of our proof is that, although conditioning on earlier rounds makes the matrix non-Gaussian, its conditional law can be computed explicitly and remains close to a Gaussian law, so the convex Gaussian min-max theorem applies in every round. For universality, we compare Gaussian and subgaussian matrices through the Lindeberg principle, using a regularized version of each linear program.
Quyu Kong Alibaba Group, Xu Zhang Alibaba Group, Zhenyu Yang The Hong Kong University of Science and Technology, Nolan Gao, Chen Liu The University of Queensland, Panrong Tong Alibaba Cloud, Chenglin Cai Alibaba Group, Hanzhang Zhou 等 13 位作者
While AndroidWorld has become the dominant mobile-use benchmark due to its reproducible environment and deterministic evaluation, recent agents achieving over 90% success rates indicate saturation and motivate the need for greater challenge. In addition, its environment lacks key application categories, such as e-commerce and enterprise communication, and does not reflect realistic mobile-use scenarios characterized by vague user instructions and hybrid tool usage. We introduce MobileWorld, a substantially more challenging benchmark with 201 tasks across 20 applications that reflects real-world usage through long-horizon, cross-application workflows requiring nearly twice as many steps (27.8 vs. 14.3) and featuring significantly more multi-app tasks (62.2% vs. 9.5%) than AndroidWorld. MobileWorld balances production-grade utility and reproducible evaluation using open-source alternatives to industry standards (e.g., Mattermost for Slack), enabling full observability through source code modification and direct database access. Beyond standard GUI manipulation, MobileWorld introduces novel task categories including agent-user interaction and Model Context Protocol (MCP)-augmented tasks for evaluating agents in user-aware, hybrid-tool scenarios. We develop a planner-executor framework with extended action spaces supporting user interactions and MCP calls. Results show a sharp performance drop from AndroidWorld, with the best agentic framework and end-to-end model achieving 51.7% and 20.9% success rates, respectively, highlighting substantial room for future research.
尚无 AI 解读，展示原文摘要
cs.CL · cs.AI
Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) · 2026 · 正式发表