Computer Science & Mathematics

Exact backprojection of a spaceborne SAR collection needs one interpolated read per pixel for every pulse; for the 12,207 by 8,808 pixel Umbra image of the Panama Canal this balloons to 1.6 trillion reads. FastSAR is an open-source library for SAR image formation on CPUs, NVIDIA GPUs and Google TPUs, with factorized backprojection, exact backprojection and polar format behind one Python interface and readers for the vendors' phase-history files. Its factorized kernels form the Panama image in 11.2 s on a 16-vCPU instance, 3.0 s on an NVIDIA L4, 0.6 s on an H100 and 2.9 s on a TPU v6e, with errors of -56 to -63 dB relative to a float64 exact backprojection in three regions over six cloud devices; the L4, a modest GPU, gives the lowest cost of the six at 0.59 US dollars per thousand images. At exact backprojection FastSAR is as fast as the MatX backprojection example, by far the fastest open-source implementation found (10.9 against 11.6 s at the same accuracy, with MatX's pixel coordinates in float64); its factorized algorithm is 3.8 times faster than MatX, and its polar format forms the image in 1.4 s on the L4 at -32 dB. On five Capella collections in three modes the worst-region error is below -59 dB.

We present new constructions of vertex fault-tolerant (VFT) $(α,β)$-spanners with substantially improved size bounds. Given a bound $f$ on the number of vertex faults, an $f$-VFT $(α,β)$-spanner is a subgraph of $G$ that preserves an $(α,β)$-spanner of $G- F$ for every fault set $F \subseteq V$ with $|F| \le f$. Most existing constructions of VFT $(α,β)$-spanners rely on a black-box sampling technique that incurs an exponential blow-up compared to their non-fault-tolerant counterparts. We develop two independent techniques for constructing $f$-VFT $(α,β)$-spanners that improve the dependence on $f$, reducing it to polynomial overhead. For every unweighted graph $G=(V,E)$ on $n$ vertices, stretch parameter $k$, and fault parameter $f$, we show: (i) $f$-VFT $(O_ε(k^ε), O_ε(k))$-spanners with $\tilde{O}(f^{exp(1/ε)}\cdot n^{1+1/k})$ edges for any $ε\in (0,1)$. For any fixed constant $ε$, this introduces a $poly(f)$ overhead compared to the non-faulty constructions of [Ben-Levy and Parter, SODA 2020] and [Chechik and Lifshitz, SODA 2026]. (ii) For any $δ\in (0,1)$, an $f$-VFT $\left(O_δ(\sqrt{k}),O_δ(k) \right)$-spanner of size $\tilde{O}(f^{1+δ} \cdot n^{1+\frac{1}{k}})$. Hence, it incurs a size overhead of only $f^{1+δ}$ compared to the above-mentioned non-faulty analogs. (iii) $f$-VFT $(k,k-1)$ spanner of size $O(k^3 \cdot f \cdot n^{1+\frac{1}{k}})$, nearly matching the lower bound $Ω(f^{1-\frac{1}{k}}n^{1+\frac{1}{k}})$ known for $f$-VFT $(2k-1,0)$ spanners by [Bodwin et al., SODA 2018]. The first result is obtained via a new adaptation of the Baswana--Sen framework to the VFT $(α,β)$ setting. The other two bounds follow from a highly involved analysis of a natural extension of the fault-tolerant greedy spanner.

Dataset search remains a bottleneck in data analysis workflows, as existing systems largely rely on keyword matching or shallow retrieval that fail to capture user intent. To facilitate intent-driven search, we present two retrieval components to equip multi-faceted dataset search interfaces through natural language. First, we propose Hypothetical Schema Embeddings (HySE) that uses a language model to generate task-aligned hypothetical table schemas which are used for embedding-based retrieval, bridging the gap between intent and table content. We introduce KaggleDS, a corpus comprising 6,503 tables and diverse task-queries derived from Kaggle, and show that HySE consistently improves recall over strong keyword and embedding-based baselines, as well as over a dense table retriever fine-tuned on KaggleDS. We also show that HySE generalizes to end-to-end question answering on, for example, the NQ-Tables dataset, a corpus of 169,898 Wikipedia tables with human-written queries, where HySE improves Recall@10 by +6.0 pp over dense retrieval baselines. Second, we introduce FlexPrune, which translates dataset constraints expressed in natural-language into SQL predicates over a customizable metadata index, enabling filtering across arbitrary metadata attributes. Combined with HySE, FlexPrune increases Recall@10 by +6.0 pp over dense retrieval followed by tag-based filtering. Our results show that natural-language-based retrieval supporting task and metadata queries offers a viable alternative to schema-level keyword search in dataset search.

We initiate the study of the meta-mathematics of algebraic circuit lower bounds, aiming both to gain insight into the methods sufficient and necessary to prove algebraic circuit lower bounds, and to contribute to the study of bounded arithmetic as a logical foundation for complexity lower bounds. We demonstrate that while algebraic circuit lower bounds are hard for somewhat weak proof systems such as Polynomial Calculus Resolution ($\mathsf{PCR}$), contemporary lower bounds are efficiently provable in proof systems and bounded arithmetic theories corresponding to $\mathsf{NC}^2$, such as $\mathsf{VNC}^2$ and the corresponding class of propositional Frege proofs of quasipolynomial-size. Moreover, going below $\mathsf{VNC}^2$ into algebraic constant-depth reasoning is likely insufficient to efficiently prove already constant-depth algebraic circuit lower bounds. Under an algebraic analogue of the Krajicek--Razborov conjecture, our results suggest that proving superpolynomial lower bounds for general algebraic circuits will require stronger reasoning than that used in the rank-based proofs studied here. Specifically, we show the following.

Estimating unobserved forces in mechanistic systems is a central task of scientific machine learning. Approximate Gaussian filtering methods that synthesize mechanistic and empirical information have shown remarkable capacity in jointly identifying latent processes together with the system state in a single forward-backward pass. The resulting latent force ODE filter framework channels information from observational data specifically into the unknown parts of the system. This work addresses open questions about calibration and stability of the method. We show that the joint posterior over state and force is the reweighted conventional latent force posterior. This uncovers a crucial dependence of the stability of the method on the prior variance of the system state, which effectively controls the flow of information from observations to the latent force through the mechanistic system. From this insight, we construct an improved algorithm that provides stable and calibrated plug-and-play inference. We demonstrate the improved framework on several simulated experimental settings.

Two-phase flow in porous media arises in a wide range of applications in engineering and science. A fundamental challenge in its numerical simulation is that the approximation of the saturation transport equation can violate the maximum principle, and spurious oscillations can appear even when the solution remains within physical bounds. In this work, we propose a bound-preserving anti-oscillation postprocessing limiter for discontinuous Galerkin discretizations of the two-phase flow system on non-matching meshes. An optimization-based cell average limiter enforces the prescribed bounds on the cell averages while preserving global mass by minimizing the $L^2$ distance to the original cell averages. To suppress the remaining oscillations, the cell average limiter is combined with a minmod limiter, which is activated only in the cells identified by a troubled-cell detector to avoid unnecessary loss of accuracy, and a Zhang-Shu scaling limiter subsequently enforces the bounds on point values. In addition, we prove that the cell average limiter preserves the accuracy of the numerical solution at a fixed time on non-matching meshes. Numerical experiments on homogeneous, non-homogeneous, and fractured porous media demonstrate the accuracy and robustness of the proposed method.

World action models have demonstrated promising performance in robot policy learning, yet their high inference latency remains a critical bottleneck for real-world deployment. Recent approaches have sought to improve inference efficiency by reducing test-time future-frame imagination or accelerating action prediction. However, these methods often leverage representations from all video world model layers without explicitly considering their varying relevance to action prediction, leading to redundant computation and suboptimal representation utilization. In this work, we propose TurboWAM, a fast world action model that efficiently aggregates structured world representations conditioned on action predictions. Specifically, TurboWAM introduces a structured world representation aggregation module that adaptively fuses representations from different world model layers according to their relevance to the evolving action denoising state. Furthermore, TurboWAM employs a structured action supervision mechanism that adaptively modulates gradients from action supervision across different world model layers during backward propagation, facilitating world representation learning. During inference, by reducing the number of world model layers executed and caching relevant representations across action denoising steps, TurboWAM substantially reduces computational overhead. Extensive experiments on multiple robot manipulation benchmarks demonstrate that TurboWAM achieves low inference latency while maintaining competitive task success rates compared with state-of-the-art methods.

We propose a parametrization-free framework for estimating the second fundamental form and the principal curvatures of a submanifold of $\mathbb{R}^d$. The method uses the closest point projections of a few short random rays and recovers the curvature from the curves that these projections induce on the submanifold, without coordinate charts or local fitting. We analyze the geometry of the induced curves and characterize when they are geodesics. For hypersurfaces, these results give two algorithms with error bounds: a least squares reconstruction of the second fundamental form from the curvatures of the induced curves, and a direct estimate of all principal curvatures from the eigenvalues of a $d\times d$ matrix built from $d$ rays, which needs no normal information and costs $\mathcal{O}(d^3)$ besides the projections. In higher codimension, we can also recover the second fundamental form one normal direction at a time. On point clouds, where the projection becomes a nearest neighbor query, we bound the additional error. Experiments confirm the predicted rates for hypersurfaces in up to $128$ dimensions, for surfaces of codimension up to $98$, and on point clouds, demonstrating the effectiveness of the proposed framework in practice.

This paper studies a reconfigurable intelligent surface (RIS)-assisted indoor architecture for extended reality (XR) applications, where multiple access points (APs) simultaneously serve multiple users over a shared frequency channel under a centralized AP controller. We formulate a non-convex sum-rate maximization problem with coupled AP precoders and RIS phase shifts, and develop a centralized alternating optimization (AO) framework for joint design. We rigorously prove that the proposed AO guarantees monotonic improvement of the sum rate that converges to a coordinate-wise stationary point, despite the non-convexity of the resulting subproblems. Although AO provides reliable performance, its iterative nature limits real-time applicability as the system dimension grows. To overcome this limitation, we propose a supervised learning-assisted approach that leverages AO-generated solutions to significantly accelerate convergence. Simulation results demonstrate that the proposed framework achieves near-optimal performance with substantially fewer AO iterations, which makes it well-suited for latency-critical RIS-assisted XR deployments.

Text-to-SQL systems achieve remarkable accuracy on academic benchmarks, yet performance drops dramatically in enterprise deployments. This gap stems from a fundamental assumption: existing approaches require complete schema documentation, but enterprise databases typically lack comprehensive documentation, featuring cryptic naming and implicit relationships. We present the first text-to-SQL framework that operates without schema documentation, instead learning database structure from historical query logs. Query logs encode implicit structural knowledge: which tables are queried together, how they join, and what columns map to business concepts. We construct a knowledge graph from parsed query patterns and introduce entity-driven GraphRAG retrieval that grounds user questions in domain terminology rather than relying solely on embedding similarity. Validated on both an industrial deployment with expert evaluation and the Beaver benchmark, our approach substantially outperforms similarity-based retrieval methods, the dominant industry approach, in both executability and answer quality. On Beaver, we achieve 95.7% execution validity compared to 60.8% for embedding-based retrieval, with expert data engineers preferring our system 70% to 10% on internal deployment. Our work demonstrates that text-to-SQL can operate effectively in schema-ambiguous enterprise environments, enabling natural language database interfaces "in the wild".

Bimanual robotic control requires simultaneous management of distinct functional demands under motor noise, energetic costs, and communication delays. We investigate how learning responsibility should be organised across modular controllers and the two arms in a simulated musculoskeletal system with two communicating recurrent controllers. Using a 2 x 2 design, we compare differential versus shared controller objectives and fixed versus balanced hand-task assignments. Task-aligned functional specialisation was strongest when differential objectives were combined with a fixed assignment aligned with contralateral control routing. This condition achieved the highest canonical-task performance and control efficiency, reaching 81.33% bimanual success. Its advantage over shared objectives increased with motor noise but narrowed under stronger energy penalties. Stronger specialisation also reduced hand-role flexibility: reversing the hand roles decreased bimanual success by 80.46 percentage points under Differential-Fixed training, compared with 1.51 percentage points under Shared-Balanced training. These results show that controller objectives and hand-task experience jointly determine functional organisation. Stronger role-specific specialisation favours performance and efficiency when roles remain stable, whereas more distributed training favours interchangeability when roles change.

Pipelines that require structured outputs from hosted language models often specify a Pydantic schema in the prompt, validate the response, and retry when validation fails. Although native structured-output modes provide an alternative, application-side validation remains important for enforcing custom constraints. Yet pipeline reliability is often summarized by a single validity rate, which obscures why outputs fail and which interventions may help. We introduce a fine-grained taxonomy of schema-conformance failures and a deterministic classifier that assigns failure categories from model responses and Pydantic validation errors. We apply this framework to 3,997 generation attempts across nine OpenAI and Anthropic model/API configurations, using questions from HotpotQA and FinanceBench. Our results show that similar validity rates can mask different failure patterns, and that dominant failure categories vary with schema constraints and task. Markdown-fenced JSON is the most common failure: among 681 fenced failures, only 48.0% pass validation after fence removal, while the remainder conceal additional violations, predominantly field-length violations. In an exploratory prompt ablation, variants that suppress fences appear to shift failures toward length violations, but the shift is consistent with exposing violations that were already present, illustrating how aggregate validity rates can obscure changes in failure composition. We derive four engineering practices for validator, schema, retry and evaluation design, three supported by our data and one, on retry feedback, proposed but not tested, and release the classifier, completions, and annotations.

Large language models increasingly act as partners in everyday communication. In these interactions, useful assistance may require not only answering, but also asking the right questions that surface knowledge gaps, assumptions, and alternatives. In this study, we refer to such epistemic question-asking as model curiosity, and introduce a theory-grounded taxonomy that distinguishes curiosity-oriented questions from generic model questioning. Across four conversation datasets, we find that curiosity-oriented questions remain rare (17-28% of all questions), but are associated with more exploratory and epistemically rich subsequent user responses, with varying patterns across datasets. We further conduct a human study to evaluate the usefulness of model curiosity, finding that curiosity can encourage exploration, especially in advice, creative, and research contexts. These findings have implications for building LLMs that ask more selectively to support deeper exploration and human-AI collaboration.

Speech Emotion Recognition (SER) is important in human-machine interactions, enabling machines to detect and classify human emotions from solely human speech. Speech emotion recognition (SER) benchmarks routinely report accuracies above 90 percent, yet these models fail when deployed or tested on diverse speakers. The papers overlook a fundamental issue: models may be learning speaker identity and tone rather than generalized emotional cues. We introduce a two-condition audit protocol that measures, for any published SER model, how much of its reported performance survives when speakers are held out. Each model is evaluated twice under identical architecture, features, and training recipe: a control condition that reproduces the common random-split practice, and a strict speaker-independent condition with disjoint speakers. We apply the protocol to seven model configurations from five published papers, spanning convolutional, recurrent, transformer, vision-transformer, and self-supervised wav2vec2 architectures, on RAVDESS, EMO-DB, and SAVEE, with a fourth corpus (EARS) as an external check. Across 21 model-dataset pairs, published headline numbers reproduce close to the control but drop by 6.9 to 63.1 percentage points under strict speaker independence. Our results quantify speaker memorization as a dominant, previously unmeasured component of published SER performance, and we recommend two-condition reporting as a community standard.

Continual learning is the ability of LLM agents to improve over time by acquiring, refining, and applying knowledge from experience while retaining useful prior knowledge. It is essential for agents learning over long time horizons, yet current evaluations largely assess individual task performance rather than improvement through accumulated experience. We introduce Continual Learning Exam (CLE), a large-scale benchmark developed by 50+ domain experts to measure experience-driven improvement in realistic professional workflows. CLE comprises 120 human-authored tasks, each organised as a five-level ladder, yielding 600 levels spanning 89 professional roles across 12 occupational domains. Agents must pass each level to unlock the next, with later levels building on experience accumulated during earlier assignments. An evaluation agent assesses each submission against human-authored rubrics. We compare a single-submission setting with one that provides diagnostic feedback after failure and allows one revision. Across 17 harness-model configurations using frontier LLMs, feedback and revision yield a median completion gain of 5.3 percentage points. Yet the best-performing system clears only 47.7% of levels and completes all five levels in just 23.3% of tasks, highlighting the difficulty of sustained learning from experience for existing frontier LLMs. As such, the dataset can also be used to post-train LLMs to strengthen their continual learning capabilities.