Computer Vision
Physis-Lang: Self-Evolving Language as a Physical Representation for Video World Model
Liming Lu, Xianzheng Ma, Wenkun He et al. (+14 more)
Video world models are expected to predict how the physical world evolves, yet they often produce visually plausible
videos that violate basic physical principles. Existing approaches commonly assume that natural
language is insufficient to represent the physical knowledge required for reliable generation, and therefore introduce additional visual, latent, numerical, or planning-based signals. We revisit this assumption and introduce Physis-Lang, a self-evolving framework that treats physical
language as a shared and optimizable representation across data curation, model training, and
video generation. Physis-Lang represents physical processes through
language that describes their relevant entities, causes, interactions, governing principles, temporal
evolution, and effects. To improve this representation, we construct PhysCapBench, which decomposes physical processes into atomic assertions and evaluates captions using recall and precision. An agentic loop iteratively analyzes assertion-level errors and refines the instruction used to produce physical captions. Physis-Lang further converts model deficiencies into textual descriptions and uses
language-guided
retrieval to identify visually diverse
videos that cover missing physical processes. Experiments on four widely used physical
video benchmarks with Wan and Cosmos backbones demonstrate consistent improvements in physical plausibility. Notably, starting from open-source Cosmos3-Nano backbones, our Physis-Lang-enhanced models surpass the leading proprietary Veo 3.1 model.
Read the full abstract ▾
All authors Liming Lu, Xianzheng Ma, Wenkun He, Guanqi Zhan, Yilin Zhao, Junyu Chen, Mengyao Xu, Jiaojiao Fan, Wenhang Ge, Yuchao Gu, Yunze Liu, Boyi Li, Zhen Dong, Victor Prisacariu, Ming-Yu Liu, Song Han, Han Cai
Computer Vision
ViTeX-Bench: Benchmarking High-Fidelity Video Scene Text Editing
Xinghao Chen, Xiangbo Gao, Jiongze Yu et al. (+2 more)
Recent
video generation is increasingly realistic and controllable, yet
video editing remains less developed, particularly for precise local edits that must preserve the original scene dynamics.
Video scene text editing replaces text on scene surfaces, such as storefront signs, whiteboards, and product labels, while preserving the surrounding content, motion, and camera dynamics. Although scene text editing is well studied for images,
video scene text editing that achieves high visual quality, temporal consistency, and edit locality remains underexplored. Existing resources offer limited paired real-
video data, and general
video-editing metrics do not directly measure whether the requested text remains correct over time. We introduce ViTeX-Bench, a
benchmark suite comprising ViTeX-
Dataset and a three-axis evaluation protocol. The
dataset contains 387 real-world 720p
videos with text-region masks and editing instructions: 230 provide reviewed, pipeline-generated paired edits for training, and 157 form a frozen evaluation split. The protocol evaluates text correctness, visual and temporal quality, and edit locality through 13 metrics, with one primary metric per axis and a Pareto comparison of their trade-offs. OCR calibration, human evaluation, and annotation-sensitivity analyses support the interpretation of these scores. Across eight baselines from four editing families, accurate text, temporal stability, and scene preservation remain difficult to achieve together. We also release ViTeX-Edit-14B, an open-source reference editor fine-tuned on the paired training split with motion-aligned glyph-
video conditioning. It achieves CharAcc 0.688, the highest mean among the evaluated
video-native editors, and the lowest comparable text-crop Warp among raw editor outputs. ViTeX-Bench provides a reproducible foundation for studying these trade-offs in
video scene text editing.
Read the full abstract ▾
All authors Xinghao Chen, Xiangbo Gao, Jiongze Yu, Yuheng Wu, Zhengzhong Tu
Computer Vision
AssemblyWorld: Rethinking 3D Assembly with General-Purpose Agents
Jiahao Zhang, Yeying Fan, Moitreya Chatterjee et al. (+5 more)
The task of 3D assembly requires translating an understanding of parts and their relationships into precise spatial arrangements. Can pretrained general-purpose
agents assemble objects through visual interaction without additional assembly-specific fine-tuning? To investigate this question, we introduce AssemblyWorld, an interactive 3D environment in which
agents inspect rendered views and manipulate supplied rigid parts, guided by images or assembly manuals when available.
Agents perceive part geometry through 2D views rather than direct access to mesh vertices or faces, while their resulting assemblies are evaluated geometrically. Building on this environment, we construct AssemblyWorldBench, comprising 100 assembly tasks across 80 objects spanning furniture, industrial assembly, and fracture reassembly. Evaluating eight
agent systems reveals substantial differences in their capabilities. The strongest system achieves 80.9% part accuracy but 59.4% complete-assembly success. The evaluated open-source systems lag substantially behind their stronger closed-source peers in both execution reliability and assembly accuracy. Analyses of visual references, interaction trajectories, and failures show how
agents revise assemblies while leaving residual positioning errors. AssemblyWorld provides a common setting for both assessing the capabilities of interactive assembly
agents and characterizing the gap between approximate structure recovery and precise reconstruction.
Read the full abstract ▾
All authors Jiahao Zhang, Yeying Fan, Moitreya Chatterjee, Suhas Lohit, Bernhard Egger, Tim K. Marks, Anoop Cherian, Stephen Gould
Cryptography and Security · Cross-listed from quant-ph
On The Simplest Quantum-Secure Block Cipher
Gorjan Alagic, Joseph Carolan, Christian Majenz et al. (+1 more)
Pseudorandom permutations are ubiquitous in theoretical and applied cryptography. PRPs that offer security even against adversaries making
quantum queries are of increasing interest, and used in applications ranging from constructing pseudorandom
unitaries to separating SZK from BQP. A successful framework for constructing classically-secure PRPs is the key-alternating Even-Mansour approach, which interleaves applications of public permutations with additions of round keys. The single-round construction is already classically secure in the ideal permutation model (IPM), with added rounds offering improved concrete security. However, in the
quantum-query setting, the status of this framework is presently unclear. A simple
quantum-query attack based on Simon's
algorithm breaks the one-round cipher. For two or more rounds, security is only known against non-adaptive adversaries who must prepare all queries in advance. In this work, we show that the two-round Even-Mansour cipher is information theoretically secure in the IPM against adversaries making polynomially-many adaptive forward and inverse
quantum queries to all available oracles. Our proof uses compressed permutation oracles and a specially crafted isometry relating the ideal and real experiments. We also show that this construction is minimal, in the sense that essentially any cipher constructed via a single call to a public permutation is quantumly insecure.
Read the full abstract ▾
All authors Gorjan Alagic, Joseph Carolan, Christian Majenz, Saliha Tokat
Computer Vision
Image Classifiers are Efficient Self-Supervised Video Representation Learners
Owais Iqbal, Sudipta Sarkar, Shyam Marjit et al. (+3 more)
We introduce VideoMSN, a Masked Siamese Network framework for efficient self-supervised spatio-temporal representation learning in
videos. Instead of relying on heavy 3D architectures or reconstruction-based autoencoders for learning with unlabeled data, we repurpose standard image
Vision Transformers by representing
videos as super images which are grids composed of frames sampled from
videos. From each super image, we construct two views: one with spatial patch masking and the other with temporal frame masking, ensuring no information leakage across frames. A shared
Vision Transformer (ViT) encoder aligns their
embeddings using a masked Siamese loss, capturing both motion and appearance cues without reconstruction. Our decoder-free formulation leverages an image foundation model towards efficient
video representation learning. Starting from pretrained DINO-v3 and DeiT-v3 image encoders, VideoMSN achieves state-of-the-art performance on Kinetics-400, UCF101, and HMDB51 while requiring up to $32\times$ fewer and $160\times$ fewer
video pretraining epochs compared to prior
video self-supervised learning methods. Our proposed approach also shows strong performance in low-shot classification, confirming the transferability of the learned representations in a label-scarce scenario. Project Page: https://cvir.github.io/projects/videomsn.
Read the full abstract ▾
All authors Owais Iqbal, Sudipta Sarkar, Shyam Marjit, Omprakash Chakraborty, Anirban Chakraborty, Abir Das
Computational Complexity · Cross-listed from quant-ph
Gibbs Sampling in the Shattered Phase by Decoded Quantum Interferometry
Leo Zhou, Noah Shutty, Mark Sellke et al. (+1 more)
We apply Decoded
Quantum Interferometry (DQI) to sample from the Gibbs measures of classical Ising
spin Hamiltonians. We show that this Gibbs sampling problem reduces to a
quantum decoding problem, and the temperature achievable by DQI is determined by the performance of decoding
algorithms. We then focus on the task of Gibbs sampling for classical Ising $k$-
spin glasses (or Max-$k$-XORSAT) on random Erdős-Rényi hypergraphs with average degree $D\ge k$. In a temperature range beginning asymptotically at the predicted dynamical phase transition, $\beta_{\rm dyn}(k,D) = \sqrt{(2\ln k)/D}\times [1+o_{k\to\infty}(1)]$, we show that shattering and disorder chaos form a topological barrier that obstructs many
algorithms, including Glauber dynamics and any
algorithm whose output distribution is "stable" under perturbations of the input. In contrast, we prove that this barrier can be broken both by a classical
algorithm based on Prange's method, and by DQI equipped with a
quantum decoder. For example, when $D=\alpha k$ with fixed $\alpha>1$, both Prange's
algorithm and DQI can sample at any inverse temperature $\beta < \tanh^{-1}(1/\alpha)$ for sufficiently large $k$, well beyond the dynamical threshold $\beta_{\rm dyn} \sim \sqrt{2\ln k / (\alpha k)}$. Therefore, our results show that DQI can overcome topological barriers that obstruct stable
algorithms.
Read the full abstract ▾
All authors Leo Zhou, Noah Shutty, Mark Sellke, Stephen P. Jordan
Numerical Analysis
A Fast Nonuniform Solver for the Poisson Equation over a Disk
Charlie Pyle and Prabir Daripa
We study fast numerical methods for the Poisson equation on a disk within the FFTRR (Fast
Fourier Transform Radial Recurrence) framework, which is built on Green's function representations. Classical FFTRR schemes apply FFTs in the azimuthal variable and evaluate mode-by-mode radial recurrences, achieving a complexity of \(O(MN\log N)\) on an \(N\times M\) uniform grid. However, they require a uniformly spaced azimuthal mesh of \(N\) points. In this work we develop a Nonuniform (NUFFTRR) solver that admits nonuniform grids in both the radial and azimuthal directions while retaining the favorable structure of the original FFTRR formulation. The azimuthal analysis-synthesis step is implemented using either a dense NUDFT least-squares solver or one of two NUFFT-based iterative schemes: a Toeplitz solver using circulant-preconditioned conjugate gradients (PCG), and a preconditioned conjugate gradient for least squares (PCGLS) solver with Pipe–Menon density compensation. These yield azimuthal complexities \(O(N^3 + MN^2)\) for the NUDFT variant and \(O(K_{\mathrm{iter}} MN\log N)\) for the NUFFT-based variants on an \(N\times M\) grid and Krylov iteration count \(K_{\mathrm{iter}}\). Numerical experiments on nonuniform meshes demonstrate that the proposed method is robust, spectrally accurate in the azimuthal variable, and competitive in runtime with existing fast Poisson solvers. We make use of vectorization and batched BLAS/GPU-accelerated linear
algebra operations to eliminate explicit loops while also formulating azimuthal and radial steps entirely in terms of dense array operations, FFTs, and NUFFTs, allowing for straightforward GPU acceleration. The implementation is released as an open-source Python package at https://github.com/CharliePyle4/NUFFTRR_Poisson, and its methodology can be extended directly to related
elliptic problems such as the Helmholtz equation.
Read the full abstract ▾
Robotics
Ego4WAM: What Matters When Scaling Egocentric Human Data for Robot Learning?
Zhihao Sun, Liu Liu, Xinjiang Wang et al. (+6 more)
Egocentric human data provides a scalable source of experience for
robot learning, but varies substantially in human-
robot alignment, behavioral coverage, and available supervision. Existing work shows favorable scaling with increasing human data, but it remains unclear which data properties drive downstream
robot gains and how to use such data throughout the training pipeline. We present a systematic study of
egocentric human data with different
alignment and supervision under a unified world-action model framework. With the model backbone fixed, we disentangle the effects of human-
robot alignment, data duration and task diversity, action supervision, and data usage strategies. We find that aligned human demonstrations substantially improve out-of-distribution generalization and reduce target-task
robot data requirements; data duration and task diversity affect downstream capabilities differently; and
video-only supervision remains effective without action labels, providing a strong foundation for subsequent
video-action training. We validate these findings through closed-loop policy evaluation on both real
robots and RoboDojo. Rather than treating data duration as the sole scaling axis, Ego4WAM shows how
alignment, task diversity, available supervision, and usage strategy jointly shape the value of
egocentric human data for
robot learning.
Read the full abstract ▾
All authors Zhihao Sun, Liu Liu, Xinjiang Wang, Haoyi Jiang, Wei Feng, Huiqiang Zhang, Xiaosong Jia, Zhizhong Su, Zuxuan Wu
Computation and Language
EvoDuet: Bilevel Co-Evolution of Web Searching and Task Solving for Scientific Discovery
Young-Jun Lee, Jinheon Baek, Soyeong Jeong et al. (+5 more)
Evolutionary search with large
language models (LLMs) can stall when progress requires external knowledge the model lacks. Supplying relevant documents helps, but simply adding web search tool can keep returning the same pages as solutions change. We introduce EvoDuet, a bi-level optimization method that co-evolves solutions and search queries with fixed model parameters. At each iteration, a
retrieval gate lets the LLM assess its knowledge gap and choose to retrieve new documents, reuse stored ones, or proceed without them. An inner loop refines queries and ranks documents by the solution scores they are predicted to yield; an outer loop generates candidates in parallel from these documents and records the evaluated outcomes for later searches. Across 21 optimization tasks with one candidate per iteration, EvoDuet raises OpenEvolve's normalized discovery gain from 74.1% to 78.0% with GPT-5.6-Luna and from 61.3% to 82.3% with Gemini-3.8-Flash, whereas Qwen3.5-9B does not benefit. Our best runs surpass the previously reported best scores on eight tasks, including Swap Reduction on Q20 and Rosetta, and match them on three more. EvoDuet also improves with other scaffolds (e.g., Top-K, EvoX) on Sums/Diffs and Denoising, demonstrating its applicability across evolutionary search scaffolds.
Read the full abstract ▾
All authors Young-Jun Lee, Jinheon Baek, Soyeong Jeong, Minki Kang, Seungyeon Jwa, Jonghyun Choi, Seungho Han, Dongyeop Kang
Distributed Computing · Cross-listed from quant-ph
Local Relaxation Hierarchies for Quantum Ground State Energies: Convergence Guarantees and Message Passing Algorithms
Sheng-Ku Lin, Ricardo Rivera Cardoso and Roberto Bondesan
Convex relaxation hierarchies provide lower bounds to the ground state energy of
quantum many-body systems that can be computed in
polynomial time on a classical computer, at any fixed hierarchy level. However, scaling these methods to large systems and accurate approximations remains challenging due to the computational cost of traditional solvers and the scarcity of efficiency guarantees. In this work, we develop local relaxation hierarchies and efficient, highly parallelisable message passing
algorithms for estimating the relaxed ground state energies. We show that the first level of the hierarchy—based on local consistency of pairwise reduced density
matrices—is exact for commuting
Hamiltonians on trees. We further establish that another hierarchy, based on consistent intervals, converges exponentially fast in the interval size to the ground state energy for weak perturbations of separable
Hamiltonians on a chain, thereby providing an efficient classical
algorithm for these systems. Then, we introduce two variants of message passing
algorithms that run in $\mathcal{O}(n/\epsilon^2)$ and $\mathcal{O}(n/\epsilon)$ time for any fixed level of the local hierarchy on bounded-degree graphs, where $\epsilon$ is the precision for the relaxed ground state energy per site. This assumes that the optimal messages have $\mathcal{O}(1)$ norm—a condition we observe in practical settings in our experiments. These
algorithms are based on the subgradient method and the Nesterov-type accelerated gradient descent method applied to an
entropy-smoothed objective. Finally, we
benchmark the message passing
algorithms across different
quantum Hamiltonians,
lattice geometries, and relaxation levels, validating the theoretical predictions and their potential to surpass standard convex optimisation solvers for this problem. We release the resulting library at github.com/rick1924/gse-message-passing.
Read the full abstract ▾
Machine Learning
Is Weight Tying Still Beneficial for Decoder-Only LLMs in Private Settings Under DP-SGD?
Razan El Mais, Ali Chehab, Ibrahim Issa et al. (+1 more)
Differentially Private
Stochastic Gradient Descent (DP-SGD) is a leading approach for
privacy-preserving fine-tuning of large
language models (LLMs). Many decoder-only LLMs employ weight tying between input and output
embeddings, a design choice originally introduced for parameter efficiency and improved
language modeling performance in the non-private setting. However, the impact of weight tying under differentially private training remains largely unexplored. In this work, we investigate the role of weight tying in the DP setting using GPT2 and DistilGPT2 as representative decoder-only architectures. Interestingly, we find that untied
embeddings consistently outperform weight-tied models under DP-SGD, achieving gains of up to 4.74% points in accuracy on SST-2, QNLI, and QQP. Beyond improved utility, untying
embeddings enables the use of
memory-efficient ghost clipping for DP-SGD. By contrast, weight tying introduces shared-parameter interactions that complicate standard ghost norm computation and largely negate its computational advantages. As a result, untied models achieve over 60% lower
memory usage while preserving the benefits of ghost clipping. Our results indicate that untied
embeddings provide a more effective and scalable design for differentially private training of decoder-only LLMs and highlight the need to revisit standard LLM architectural choices in the
privacy-preserving setting.
Read the full abstract ▾
All authors Razan El Mais, Ali Chehab, Ibrahim Issa, Razane Tajeddine
Computational Complexity
A Noise Operator Approach to Quantum Query Complexity and Time-Space Tradeoff Lower Bounds
Paul Beame, Blake Holman and Niels Kornerup
Time and space (
memory) are two of the most important measures of cost in computation, even more so for
quantum computation. Yet, our tools for proving unconditional
quantum tradeoffs between time and space are surprisingly limited. The first
quantum time-space tradeoff lower bounds were proven for sorting by Klauck, Špalek and de Wolf. Unfortunately, their method is limited to proving output-oblivious lower bounds (i.e. the lower bounds only apply to
algorithms with a non-adaptive output schedule) and other methods have yielded nothing beyond output-oblivious lower bounds for sorting. Here, we prove the first fully general
quantum time-space tradeoff lower bound for sorting. We do so by introducing a novel method based on the noise operator to add to the analysis toolkit for proving
quantum query and time-space tradeoff lower bounds. By combining our resulting
quantum noise stability bound with
quantum recording query methods, we prove an $\Omega(n^{4/3} (\log \log n)/(S^{1/3} \log n))$ lower bound on the number of queries that a fully general
quantum algorithm with at most $S$
qubits of
memory requires to sort $n$ numbers from $[n^2]$. Applying our noise operator argument involves purely classical
reasoning, which makes it particularly simple to use. We also use it to prove that, for any strongly universal (pairwise independent) hash function family $H$ from $n$ bits to $m$ bits, almost all hash functions in $H$ require any
algorithm with at most $S$
qubits of
memory to make $\Omega(nm/S)$
quantum queries to input $x$ in order to compute $h(x)$, even with very small success probability. Previously, Mansour, Nisan, and Tiwari had shown a matching classical lower bound for computing $h(x)$ with both $h$ and $x$ as inputs using their hash mixing lemma. Our noise operator method allows us to use a related property of hash functions to prove our
quantum lower bounds.
Read the full abstract ▾
Computer Vision
I Have a Stream: Making Self-Supervised Learning Work on Continuous Video
Ivan Martinović, Lukas Knobel and Yuki M. Asano
Self-supervised learning draws inspiration from infant visual development, yet standard training pipelines bear little resemblance to it: images are independently sampled and globally shuffled across epochs. We study self-supervised learning from continuous
video streams, where frames are consumed in temporal order using strict sliding-window batches, without global reshuffling or multi-epoch replay. To this end, we construct WT++, a 95-hour urban walking-tour
video dataset for streaming pretraining. Combined with a comprehensive evaluation suite we find that contrastive and
distillation-based methods struggle in this setting, while MAE is more robust but still falls short of standard i.i.d. pretraining. We find that high inter-batch similarity, caused by sliding-window consumption across consecutive batches, does not explain this gap. The main challenge is high intra-batch similarity, where frames within each batch are near-duplicates. To mitigate this, we propose StreamMAE, which preserves the core MAE reconstruction objective while adapting the input pipeline with stream-aware regularization and motion-biased crop selection. StreamMAE outperforms streaming baselines, matches i.i.d. MAE trained on the same
video data, remains competitive with ImageNet-pretrained MAE, and scales positively as the pretraining stream grows from 12 to 95 hours.
Read the full abstract ▾
Artificial Intelligence
Turbo Harness: Instance-Adaptive Harness Optimization
Tunyu Zhang, Hao Wang, Kai Xu et al. (+1 more)
Automating the search for effective harnesses is an important step toward enabling
agents to recursively self-improve. Existing harness optimizations typically produce a single global harness that is applied uniformly across task instances. However, a harness that works well on average may not be optimal for every instance. We introduce Turbo Harness, a framework that can adapt a globally optimized harness to each instance by reusing information generated during the original optimization process. Specifically, Turbo Harness recycles artifacts produced during a completed global harness optimization run, and summarizes them into a structured playbook. We train a harness editor to leverage this prior optimization experience to generate instance-specific patches to the global harness. At inference time, the editor uses the instance and the playbook to construct a tailored harness in which the execution model operates. Through numerical experiments, we show that Turbo Harness consistently outperforms existing harness optimization baselines across seven
benchmarks spanning interactive
agent tasks, software engineering, and long-horizon terminal tasks.
Read the full abstract ▾
All authors Tunyu Zhang, Hao Wang, Kai Xu, Dimitris N. Metaxas
Artificial Intelligence
Ziyan Jiang, Jingbo Yang, Jiabao Ji et al. (+5 more)
As interactive 3D worlds are increasingly used to study intelligent behavior, it becomes important to develop efficient pipelines for identifying anomalies in these simulated environments, such as floating objects, traversable walls, or objects inconsistent with the surrounding scene.
Multimodal AI systems, including
vision-
language models (VLMs) and
vision-
language-action models (VLAs), have shown potential for automating this task. However, 3D world
auditing is complex, requiring the close coupling of two distinct capabilities: action, to navigate the 3D world and search for anomalies systematically and efficiently; and visual
reasoning, to understand the environment and identify anomalies from
multimodal observations. It remains largely unexplored whether
multimodal agents can effectively couple these two capabilities, using visual
reasoning to identify potential anomalies while taking actions to validate them. In this paper, we introduce WorldAuditBench, a
benchmark for 3D world
auditing comprising 213 anomaly tasks across 13 environments built with Unreal Engine 5 and Three.js, spanning five anomaly families. We evaluate five frontier models under a fixed exploration budget using two
auditing paradigms: VLA-based exploration followed by VLM-based anomaly identification, and an end-to-end VLM
agent in which visual
reasoning directly guides action selection. Across the evaluated models and two paradigms, success rates range from 6.6% to 42.3%, substantially below human performance (83.4%). Through the task of world
auditing, WorldAuditBench provides a testbed for studying how
multimodal agents couple action and visual
reasoning in interactive 3D environments, while highlighting current limitations in their ability to gather and interpret evidence during exploration.
Read the full abstract ▾
All authors Ziyan Jiang, Jingbo Yang, Jiabao Ji, Yujian Liu, Qiucheng Wu, Tommi Jaakkola, Yang Zhang, Shiyu Chang
Artificial Intelligence
Cogentic: Multi-Agent Orchestration for Automated Proof Discovery
Yang Cai, Vineet Gupta, Yanchen Jiang et al. (+4 more)
We present Cogentic, a multi-
agent harness for automated proof discovery on open research problems. While frontier
language models can generate strong mathematical ideas in a single shot, single-shot generation is often insufficient for open problems that require exploring multiple competing
conjectures, overcoming subtle technical obstructions, and retaining intermediate progress over a long horizon. Cogentic addresses these challenges through an iterative prove-verify loop in which an orchestrator allocates a population of independent provers across distinct proof directions, subjects their output to
adversarial verification by several specialized components, and promotes confirmed intermediate results into a persistent verified ledger that later rounds build on. The harness is designed to be able to solve research-level math and theoretical computer science problems. Using either Gemini 3.1 Pro or an early version of Gemini 4 Argon as the base model, Cogentic produced novel results on open problems across online learning, auction theory, and mechanism design. Each result was independently verified by domain experts and is developed in full in companion papers. We list these results, and new ones as they are verified, at https://sites.google.com/view/cogentic .
Read the full abstract ▾
All authors Yang Cai, Vineet Gupta, Yanchen Jiang, Christopher Liaw, Aranyak Mehta, Grigoris Velegkas, Di Wang
Computational Complexity · Cross-listed from quant-ph
Computational Work Extraction: The Complexity of Catalysts
Atul Singh Arora, Shantanav Chakraborty, Alexandru Cojocaru et al. (+2 more)
We prove maximal separations: $n$-
qubit systems can have $\Theta(n)$ ergotropy, while every efficient process extracts negligible work, even for
Hamiltonians consisting of single-
qubit terms. We establish an unconditional existential separation and give an explicit construction in the random oracle model. Assuming the existence of
quantum-secure pseudorandom functions, this separation extends to the plain model. This work uncovers an important connection between ergotropy and the complexity of catalytic computation—computation where auxiliary
qubits must be finally restored to their initial state. Relative to a random oracle, we establish relational and decision problems that: (i) can be solved efficiently with $\lambda$ catalysts; but (ii) cannot be solved by any
algorithm with $c\lambda$ catalysts, for any $c<1$. We show this by proving query lower bounds for
quantum-space bounded
algorithms. As a consequence, for computational ergotropy, catalysts prove to be surprisingly powerful—there is a family of
Hamiltonians and states for which catalysts enable efficient extraction of the full $\Theta(n)$ ergotropy, while every efficient non-catalytic process extracts negligible work. Furthermore, catalysts also allow us to introduce and instantiate the notion of pseudoergotropy—analogous to pseudorandomness. On the other hand, we show catalysts do not change (information-theoretic) ergotropy. Finally, our work also sheds light on the classical aspect of the problem. First, most of our constructions rely on classical states and
Hamiltonians and therefore imply analogous results for classical ergotropy. Second, we show that certain proof of quantumness protocols can be used to generically separate classical and
quantum catalytic ergotropy.
Read the full abstract ▾
All authors Atul Singh Arora, Shantanav Chakraborty, Alexandru Cojocaru, Sreyas Saminathan, Uttam Singh
Computer Vision
MatLoom: Layered Text-to-Material Generation in a Compact Program Space
Anson Y. Lam, Shuqing Li and Michael R. Lyu
Material generation should produce not only an appearance, but also the rules that construct it. We introduce MatLoom, a compact, layer-oriented
language for text-to-material generation with pretrained
language models. Each program composes alpha-masked layers whose shared spatial expressions define coverage and physically based rendering (PBR) channels, making dependencies between patterns, color, and relief explicit. A standalone interpreter evaluates the program into material maps, while the source retains named fields and layer parameters for subsequent authoring. Without task-specific fine-tuning, our pipeline uses parser-guided repair and preview-based critique to revise material designs, then searches noise seeds while keeping each candidate's remaining source fixed. On a curated
benchmark of 141
prompts evaluated with six backbones, our best-performing configuration achieves higher mean scores than three
diffusion baselines on all four flat-layout
prompt-
alignment metrics. Its initial programs already exceed all three baselines on mean BLIPScore, before critique or seed search. Retained programs have a median length of 21 lines when pooled across backbones. In a blind four-way comparison involving 30 participants and 20
prompts, our renders receive 59.2% of choices, compared with 19.3% for the most-preferred baseline. Compact executable programs thus offer a way to generate
prompt-aligned materials while retaining their construction as part of the asset.
Read the full abstract ▾
Cryptography and Security · Cross-listed from quant-ph
Exponential quantum speedup for $\mathbb{F}_3^n$-Subset-Sum? Or, rigorous classical algorithms for Binary-Error LWE
Robin Kothari, Tony Metger, Ryan O'Donnell et al. (+2 more)
We study vector subset sum over $\mathbb{F}_3^n$: given $m$ random vectors from $\mathbb{F}_3^n$, find a nonempty subset that sums to zero; the smaller $m$, the more difficult it is to find such a subset. Chen, Liu, and Zhandry (EUROCRYPT'22) introduced an efficient
quantum algorithm that solves this problem when $m\approx n^2/2$, where a naive classical
algorithm would require exponential time. Subsequently, Kothari, O'Donnell, and Wu (STOC'2026) gave an efficient classical
algorithm that only requires $m \approx n^2/3$ vectors, thus removing the hope for an exponential
quantum advantage in this parameter regime. Using the framework of Chen, Liu, and Zhandry, we give
quantum algorithms that require much fewer input vectors, renewing the possibility of an exponential
quantum speedup: for any fixed $\epsilon>0$, our
quantum algorithm solves $\mathbb{F}_3$-subset sum in
polynomial time with $m=\epsilon\cdot n^2$ vectors. More generally, we establish a full sample–time tradeoff that interpolates between exponential and
polynomial runtime. The main ingredient is a deterministic classical
algorithm for the binary-error Learning-with-Errors problem, which is of independent cryptographic interest. For this, we rigorously establish a sample–time tradeoff that was predicted by earlier algebraic heuristics. For vector subset sums over larger fields, we also significantly improve classical
algorithms in Kothari, O'Donnell, and Wu (STOC'2026).
Read the full abstract ▾
All authors Robin Kothari, Tony Metger, Ryan O'Donnell, Noah Shutty, Kewen Wu
Computer Vision
Atomizer-IO: Beyond Pixels, Patches and Grids
Hugo Riffaud de Turckheim, Sylvain Lobry, Nicolas Houdré et al. (+3 more)
Most
vision architectures assume that observations lie on a regular grid, an effective abstraction for natural images but a restrictive one for sensing data whose channels, temporal sampling, spatial resolution, and geometry can vary. Generic set-based architectures remove the grid, but also remove useful spatial inductive biases. We introduce Atomizer-IO, an architecture that places observations first and derives structure from their physical relationships. Building on top of an atomic representation of the data, each observation is described by its measurement and acquisition metadata, while local cross-
attention maps observations to anchor points that can be arbitrarily placed. We evaluate this design by progressively relaxing the grid assumption, from varying input raster configurations and incomplete channel sets to flexible output density and, ultimately, inputs without a raster grid. Atomizer-IO is competitive with flexible EO-specific architectures on most tasks, while offering post-training control over inference cost and competitive compute–performance trade-offs. The same formulation extends without architectural redesign to unordered 3D point clouds, showing that the atomic interface generalizes beyond regular raster inputs. These results suggest that pixels, patches, and grids do not need to define the interface of a sensing architecture.
Read the full abstract ▾
All authors Hugo Riffaud de Turckheim, Sylvain Lobry, Nicolas Houdré, Damien Robert, Roberto Interdonato, Diego Marcos
Information Theory · Cross-listed from quant-ph
Local Automorphism-Aware Syndrome Compilation for General Quantum LDPC Codes
Eugenio Durazo Rocha, Olai Å. Mostad, Hsuan-Yin Lin et al. (+1 more)
Low-depth syndrome extraction for Calderbank-Shor-Steane (CSS)
quantum low-density parity-check codes can be formulated as a proper ordered edge-coloring problem subject to
quantum parity constraints. A proper edge-coloring of the CSS Tanner graph ensures that each data or ancilla
qubit participates in at most one two-
qubit gate per layer, but does not guarantee a valid interleaving of the X- and Z-check measurements as for every overlapping X/Z check pair, the number of shared data
qubits on which the X interaction precedes the Z interaction must be even. The minimum number of colors in a proper ordered edge-coloring satisfying the
quantum parity constraints equals the minimum two-
qubit depth when each stabilizer check is measured with a single ancilla. We introduce local
automorphism-aware syndrome compilation (LocalASC), which reduces the constraint system to edge-orbit variables under a subgroup of the Tanner graph
automorphisms and lifts each feasible orbit assignment to the full graph. Although the $6$-layer degree lower bound is unattainable for the published weight-$6$ IBM bivariate bicycle codes, we show that this is not universal among two-block CSS codes. Among code instances for which the maximum check weight equals the maximum Tanner graph degree, LocalASC finds depth-optimal syndrome-extraction schedules for several two-block CSS codes with odd component weights, including instances with unequal odd weights. We also obtain lower-bound-saturating syndrome-extraction schedules for several
quantum Tanner codes satisfying the same degree condition. To obtain the subgroups used by LocalASC without computing the full
automorphism group of the Tanner graph, we construct translation subgroups for two-block group-
algebra CSS codes over abelian groups. For
quantum Tanner codes, we give conditions under which square-complex
symmetries extend to Tanner graph
automorphisms.
Read the full abstract ▾
All authors Eugenio Durazo Rocha, Olai Å. Mostad, Hsuan-Yin Lin, Eirik Rosnes
Computer Vision
GLARE: Generating Listening Heads with Appropriate Reactions
Zikai Liao, Yumin Suh, Yi Ouyang et al. (+3 more)
While talking head generation has advanced rapidly, generating natural listener behavior in dyadic conversations, which know when to react, how to react, and with what type of response, remains underexplored. Existing dyadic
datasets lack fine-grained listener reaction annotations, and prevailing evaluation metrics inherited from talking-head and
video generation measure visual realism rather than whether a listener reacted appropriately. We address these gaps along three aspects. First, we curate a listening-head-specific
dataset built from RealTalk and Seamless Interaction, comprising approximately 147 hours of paired speaker-listener
videos with 64,557 event-level reaction annotations across six categories: nodding, head shaking, smiling, laughing, frowning, and surprised. Second, we introduce an audio-driven baseline built on a flow-matching
transformer, namely GLARE, with prosody conditioning derived from Qwen2-Audio and a temporal reaction loss that explicitly supervises frame-wise reactions. Third, we propose a reaction-oriented evaluation protocol that jointly measures reaction occurrence (R-F1), temporal
alignment (R-tIoU), asymmetric temporal deviation (R-ATD), and reaction-region visual quality (R-FID), giving a more behaviorally grounded assessment than visual-quality-only metrics. Experiment results show consistent gains over prior listening-head methods in both visual fidelity and reaction-level metrics, suggesting that reaction-aware data, modeling, and evaluation are critical for natural listening behavior.
Read the full abstract ▾
All authors Zikai Liao, Yumin Suh, Yi Ouyang, Yi-Lun Lee, Yi-Hsuan Tsai, Zhaozheng Yin
Machine Learning
Scaling Laws for Looped Mixture of Experts
Yanbei Chen, Anirudh Goyal and Raghuraman Krishnamoorthi
Looped
transformers and Mixture-of-Experts (MoE) offer complementary routes to efficient scaling: recurrence increases computational depth at fixed parameters, while MoE sparsity expands total capacity at fixed active compute. Yet existing scaling laws model recurrence or sparsity in isolation. In this work, we introduce Loop Scaling Laws, the first scaling law to jointly model recurrence and sparsity alongside model size and data. At its core is a bounded, sparsity-conditional recurrence mapping that characterizes the effective-parameter gain from looping and how sparsity raises this gain. The laws predict the held-out loss of looped models more accurately than prior alternatives, and recover the standard dense and MoE scaling laws as special cases. Beyond prediction, the fitted laws provide a principled foundation for designing looped MoE models under compute and
memory constraints. Downstream evaluations further demonstrate the complementary benefits of the two axes: sparsity delivers ~3x active-parameter efficiency, recurrence yields ~2x total-parameter efficiency on
reasoning, and joint scaling further advances the performance frontier. As a practical extension, we show these gains hold at trillion-
token scale: at matched training compute, a looped MoE with law-derived recurrence matches a ~2x larger non-looped MoE on the
reasoning benchmarks, while enabling test-time scaling through recurrence.
Read the full abstract ▾
Information Theory · Cross-listed from quant-ph
Explicit Capacity-Achieving Quantum LDPC Codes List Decodable in Near-linear Time
William Gay, Fernando Granha Jeronimo and Abhi Shukul
In classical coding theory, the quest for explicit codes achieving list decoding capacity has been an important driving force. While random codes are easily shown to achieve capacity, an explicit construction was only discovered decades later in the seminal work [Guruswami and Rudra, STOC 2006]. In
quantum coding theory, it is highly desirable that a code family be LDPC. While good
quantum codes were known for decades, obtaining the additional LDPC property was elusive. In fact, only very recently that good
quantum LDPC codes were discovered in a breakthrough work [Panteleev and Kalachev, STOC 2022]. In this context, a natural question is to ask for an explicit family of
quantum codes achieving list decoding capacity while also possessing the important LDPC property. In this work, we provide (to the best of our knowledge) the first explicit constructions of
quantum LDPC codes achieving list decoding capacity, namely, with a list decoding radius approaching the
quantum Singleton bound with constant list sizes. Furthermore, we provide near-linear time (in the block-length) list decoding
algorithms approaching capacity. Our explicit code construction are based on expander graphs via the
quantum analogue of Alon-Edmonds-Luby (AEL) amplification [Bergamaschi, Golowich and Gunn, STOC 2024], and this enables the important LDPC property. Our efficient list decoding
algorithms are obtained by generalizing the classical expander-based weak-regularity list decoding
algorithms [Srivastava and Tulsiani, FOCS 2025] [Jeronimo and Singh, 2025] to suitable instantiations of
quantum AEL.
Read the full abstract ▾
Machine Learning
Compression Footprints as Security Signals for Model-Poisoning Defense in Federated Learning
Sachi Shome and William Eiers
Lossy compression is widely used in
Federated Learning (FL) but is generally treated as an error source, while conventional poisoning defenses inspect update geometry. In this work, we instead treat the compressor's response as a security signal: the input-dependent distortion and payload behavior induced by lossy compression can expose differences between honest and attack-generated updates. We introduce the concept of a compression footprint: the low-dimensional collection of reconstruction, directional, sparsity, and payload statistics induced by a lossy compressor. We characterize sufficient conditions under which compression footprints separate honest and malicious updates, and operationalize our findings in the CRAFT (Compression-guided Robust Aggregation via Footprint Trust) server-side robust aggregation method. Crucially, under a strict honest-majority assumption, CRAFT uses server-verifiable footprints, requires no client-side metadata nor knowledge of the number of malicious clients, and adds no communication beyond the compressed FL pipeline. Moreover, while CRAFT assumes a strict honest majority, it does not require the number of malicious clients to be known in advance. We observe that error-bounded lossy compressor (EBLC) footprints provide stronger separation than Top-K footprints and that footprint trust suppresses malicious influence. We evaluate CRAFT under IID client data with 36% malicious participation across six standard model-poisoning attacks, three
datasets, and six robust aggregation baselines, finding that CRAFT consistently achieves the best accuracy in 7 out of 18 settings and within 1.7 percentage points of the best in the others. Our results show that lossy compression can serve as both a communication mechanism and a security signal for robust aggregation in FL.
Read the full abstract ▾
Computational Complexity · Cross-listed from quant-ph
Planted Cliques and Quantum Symmetry-Adapted Measurements
Vojtech Havlicek, Jordan Docter and Subhash Khot
We study how
quantum encodings and
symmetry-adapted measurements preserve information for planted-clique detection from one classical graph. For $k=\lfloor n^{1/2-\varepsilon}\rfloor$, with fixed $0<\varepsilon<1/2$, detection is statistically possible but conjectured hard for
polynomial-time classical
algorithms. For a compact binary phase encoding, we prove that constant-advantage detection requires $\Omega(n^{1+2\varepsilon}\ln^2 n)$ copies of the phase state of the same graph, even under arbitrary joint measurements. In the large-copy limit, the optimal decision rule thresholds the total number of $k$-cliques in the graph and its complement, but this characterization provides no efficient detector. We therefore explore measurements guided by the
symmetries of the input distributions, starting with the efficient Schur transform on the full graph register. We show that weak Schur sampling, which measures only the representation label, depends only on edge count and has vanishing distinguishing power in this regime. When the label and multiplicity registers are discarded, the remaining
quantum states are almost perfectly distinguishable. We show that the support of the planted state occupies only a vanishing fraction of the graph
Hilbert space. Any subspace containing it still permits near-perfect detection if its relative dimension also vanishes. This gives us freedom to choose a subspace that is easier to measure. We propose exploring subgroup isotypic measurements to find such subspaces. Whether they can yield an efficient detector remains open. Finally, we show that a single supplied coherent
quantum sample permits efficient detection, yielding a conditional computational separation from one classical sample under
quantum planted-clique hardness.
Read the full abstract ▾
Robotics
DynaHarness: A Dynamic Physical Harness for Self-Evolving Robot Agents
Haoyuan Deng, Jiebin Liu, Tengxiao Zhang et al. (+3 more)
Pretrained
robot policies provide useful action priors, but long-horizon manipulation still requires coordination between semantic
reasoning and physical execution. Semantic
reasoning operates at a coarser timescale than physical interaction, while episode-level failures provide limited guidance on which system component should be revised. We propose DynaHarness, a dynamic physical harness that couples semantic
reasoning with physical governance through a shared execution contract and turns failure evidence into validated capability revisions. To be more specific, the slow
brain proposes capabilities and symbolic arguments, while the fast
brain grounds and monitors commands, refuses unresolved actions, substitutes capabilities, and requests replans when needed. The physical execution contract bounds each accepted command and records execution evidence across analytic skills, recovery skills, and the frozen VLA. Failure attribution localizes faults in these records and directs targeted revisions of reusable capabilities or execution mechanisms. Paired regression checks govern admission or rejection, closing the self-
evolution loop. On LIBERO-Pro, DynaHarness achieves 75.2% on 800 newly sampled initial states, compared with 17.5% for the frozen policy. With the same capability library, full dynamic execution reaches 74.0% versus 63.9% under nominal one-step replanning. This demonstrates the value of DynaHarness as a dynamic physical harness that governs how existing capabilities are grounded, monitored, and coordinated during execution. Our project page is at https://denghaoyuan123.github.io/Dynaharness_page/.
Read the full abstract ▾
All authors Haoyuan Deng, Jiebin Liu, Tengxiao Zhang, Langning Yan, Hongye Cao, Ziwei Wang
Computer Vision
Yong Xien Chng, Tianyi Chen, Wenwen Tong et al. (+7 more)
Improving text-to-image models has traditionally relied on increasing model size or the number of denoising steps. In this work, we explore an alternative way to scale computation by repeatedly running shared
Transformer blocks within each denoising step, effectively increasing computational depth while keeping the parameter count fixed. This looped computation enables iterative refinement of internal representations without explicit
reasoning tokens. However, naive looping fails to consistently improve image quality. We trace this problem to weak supervision across intermediate loops and unregulated
attention updates that progressively erode local information. To overcome these challenges, we propose Looped
Diffusion Transformer (Looped-DiT), which combines deep supervision across intermediate loops with self-modulating
attention to stabilize looped feature updates. Under matched-parameter and matched-compute settings, Looped-DiT consistently outperforms non-looped baselines. Notably, a 260M-parameter looped model can surpass a model 6.5x larger across multiple text-to-image
benchmarks while requiring 4.9x lower inference compute. Beyond this performance gain, we find that looped computation can offer a more effective form of iterative computation for
diffusion models, with increasing loop depth yielding larger gains than adding more denoising steps under a fixed inference budget. Furthermore, deeper loops can progressively correct mistakes made in earlier loops, exhibiting behaviors suggestive of latent
reasoning. Together, these results show that looped computation offers a promising way to scale visual generation models.
Read the full abstract ▾
All authors Yong Xien Chng, Tianyi Chen, Wenwen Tong, Haiwen Diao, Zhongang Cai, Lei Yang, Ziwei Liu, Lewei Lu, Dahua Lin, Gao Huang
Artificial Intelligence
How Much of a Harness Does a Strong Agent Need for Autonomous ML Engineering?
Kirill Brilliantov, Alejandro Hernández-Cano and Emmanuel Abbé
Recent autonomous machine learning engineering (MLE)
agents have made significant progress on public leaderboards. Often motivated by progress stagnation over long-horizon cycles and limited Large
Language Model (LLM) primitives, modern MLE
agents are deployed on top of increasingly elaborate machinery: multi-
agent orchestrators, dedicated
retrieval subagents, and more. While such harnesses expand, the use of more primitive but improved coding
agents - where LLMs have direct access to the execution environment through read, write, and bash primitives - has received little
attention in the field. In this paper we find that, under an equal time budget and the same frontier LLM backbone, open-source state-of-the-art harnesses provide no advantages over a single session of a minimal-harness coding
agent baseline, pointing to the backbone as the primary driver for performance. Via a series of large-scale systematic ablation studies, we argue that the machinery layers become redundant in the coding
agent setting. We conclude that the effort spent elaborating hand-crafted harnesses around strong models yields poor returns for current MLE
benchmarks.
Read the full abstract ▾
Data Structures and Algorithms · Cross-listed from quant-ph
Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma
Fernando G.S.L. Brandão, Alexander M. Dalzell, András Gilyén et al. (+1 more)
We give the first sublinear-time classical solvers for sparse semidefinite programs in the bounded-radius regime, without low-rank assumptions or Frobenius norm dependence on the constraint
matrices. For constant precision and bounded primal and dual radii, prior
quantum algorithms of Brandão et al. (2019) and van Apeldoorn and Gilyén (2019) achieved $\widetilde{O}(\sqrt{n}+\sqrt{m})$ dependence on
matrix dimension $n$ and constraint number $m$. Compared with the $\widetilde{O}(mn)$ runtime of existing classical methods, this suggests a quartic
quantum speedup when $m \approx n$. Beyond a usual Grover speedup, this separation relies on the
Quantum OR lemma, whose sample-reuse mechanism decouples the cost of Gibbs-state preparation from constraint search. We show that this reuse mechanism is classically realizable for sparse SDPs. Our main technical contribution is a classical procedure for simultaneously estimating many expectation values with respect to a sparse
Hamiltonian's Gibbs state. This combines randomized Lánczos filtering with an efficient sampling-based
estimator. We also introduce a
stochastic online-learning framework for SDP solving, substantially improving accuracy-dependence over standard oracle-based MMWU approaches. Let $s$ denote the the input
matrix sparsity and $\gamma:=Rr/\varepsilon$ capture dependence on the primal $(R)$ and dual $(r)$ radii as well as target accuracy $(\varepsilon)$. When $\gamma^2\leq\min\{m,n/s\}$, our solver runs in time $\widetilde{O}\left(ns\gamma^{4.5}+ms\gamma^2\right)$. For $\gamma=O(1)$, this is $\widetilde{O}\left((n+m)s\right)$ and sublinear in the $O(mns)$ input size. Similar to the
quantum algorithms, this matches known lower bounds with respect to $m$ and $n$, up to logarithmic factors. This implies that, with respect to dimensions $m$ and $n$, there is no super-quadratic
quantum advantage for generic sparse SDP solving.
Read the full abstract ▾
All authors Fernando G.S.L. Brandão, Alexander M. Dalzell, András Gilyén, Francisca Vasconcelos