Generative images have proliferated on Web platforms in social media and online copyright distribution scenarios, and semantic watermarking has increasingly been integrated into diffusion models to support reliable provenance tracking and forgery prevention for web content. Traditional noise-layer-based watermarking, however, remains vulnerable to inversion attacks that can recover embedded signals. To mitigate this, recent content-aware semantic watermarking schemes bind watermark signals to high-level image semantics, constraining local edits that would otherwise disrupt global coherence. Yet, large language models (LLMs) possess structured reasoning capabilities that enable targeted exploration of semantic spaces, allowing locally fine-grained but globally coherent semantic alterations that invalidate such bindings. To expose this overlooked vulnerability, we introduce a Coherence-Preserving Semantic Injection (CSI) attack that leverages LLM-guided semantic manipulation under embedding-space similarity constraints. This alignment enforces visual-semantic consistency while selectively perturbing watermark-relevant semantics, ultimately inducing detector misclassification. Extensive empirical results show that CSI consistently outperforms prevailing attack baselines against content-aware semantic watermarking, revealing a fundamental security weakness of current semantic watermark designs when confronted with LLM-driven semantic perturbations.

In-context learning has been recognized as a key factor in the success of Large Language Models (LLMs). It refers to the model’s ability to learn patterns on the fly from provided in-context examples in the prompt during inference. Previous studies have demonstrated that the Transformer architecture used in LLMs can implement a single-step gradient descent update by processing in-context examples in a single forward pass. Recent work has further shown that, during in-context learning, a looped Transformer can implement multi-step gradient descent updates in forward passes. However, their theoretical results require an exponential number of in-context examples, $n = \exp(\Omega(T))$, where $T$ is the number of loops or passes, to achieve a reasonably low error. In this paper, we study linear looped Transformers in-context learning on linear vector generation tasks. We show that linear looped Transformers can implement multi-step gradient descent efficiently for in-context learning. Our results demonstrate that as long as the input data has a constant condition number, e.g., $n = O(d)$, the linear looped Transformers can achieve a small error by multi-step gradient descent during in-context learning. Furthermore, our preliminary experiments validate our theoretical analysis. Our findings reveal that the Transformer architecture possesses a stronger in-context learning capability than previously understood, offering new insights into the mechanisms behind LLMs and potentially guiding the better design of efficient inference algorithms for LLMs.

This paper introduces Force Matching (ForM), a novel framework for generative modeling that represents an initial exploration into leveraging special relativistic mechanics to enhance the stability of the sampling process. By incorporating the Lorentz factor, ForM imposes a velocity constraint, ensuring that sample velocities remain bounded within a constant limit. This constraint serves as a fundamental mechanism for stabilizing the generative dynamics, leading to a more robust and controlled sampling process. We provide a rigorous theoretical analysis demonstrating that the velocity constraint is preserved throughout the sampling procedure within the ForM framework. To validate the effectiveness of our approach, we conduct extensive empirical evaluations. On the half-moons dataset, ForM significantly outperforms baseline methods, achieving the lowest Euclidean distance loss of 0.714, in contrast to vanilla first-order flow matching (5.853) and first- and second-order flow matching (5.793). Additionally, we perform an ablation study to further investigate the impact of our velocity constraint, reaffirming the superiority of ForM in stabilizing the generative process. The theoretical guarantees and empirical results underscore the potential of integrating special relativity principles into generative modeling. Our findings suggest that ForM provides a promising pathway toward achieving stable, efficient, and flexible generative processes. This work lays the foundation for future advancements in high-dimensional generative modeling, opening new avenues for the application of physical principles in machine learning.

Characterizing the expressive power of the Transformer architecture is critical to understanding its capacity limits and scaling law.Recent works provide the circuit complexity bounds to Transformer-like architecture.On the other hand, position embedding has emerged as a crucial technique in modern large language models, offering superior performance in capturing positional information, which shows great performance for the long context scenario.In this work, we take a circuit complexity perspective and rigorously analyze Transformers augmented with widely adopted positional embeddings.We prove that, under standard complexity assumptions, such models remain incapable of efficiently solving canonical tasks such as arithmetic formula evaluation and Boolean formula value computation.Our results expose a fundamental expressivity limitation that persists despite the remarkable empirical success of positionally-enhanced Transformers.Beyond tightening known complexity bounds, our findings offer new theoretical insights for designing future architectures with provably stronger reasoning and compositional capabilities.

The multiplicative weight update method is a well-known algorithm commonly used for decision making based on recommendations from n experts. Despite being widely used, the classical MWU algorithm suffers from a linear runtime complexity, which limits its efficiency on large problems. Additionally, since expert data may be sensitive, it is important to develop privacy-preserving methods. In this paper, we propose the first data structure that approximates the multiplicative weight update in sublinear time (o(n)) while providing differential privacy guarantees, significantly improving efficiency for large-scale problems. Our data structure both enhances computational efficiency and ensures privacy protection, with theoretical guarantees on both utility and privacy, enabling fast and private decision making.

A recent work by [Larsen, SODA 2023] introduced a faster combinatorial alternative to Bansal’s SDP algorithm for finding a coloring $x \in \\{-1, 1\\}^n$ that approximately minimizes the discrepancy $\mathrm{disc}(A, x) := \\|{A} x \\|_{\infty}$ of a real-valued $m \times n$ matrix $A$. Larsen’s algorithm runs in $\widetilde{O}(mn^2)$ time compared to Bansal’s $\widetilde{O}(mn^{4.5})$-time algorithm, with a slightly weaker logarithmic approximation ratio in terms of the hereditary discrepancy of $A$ [Bansal, FOCS 2010]. We present a combinatorial $\widetilde{O}(\mathrm{nnz}(A) + n^3)$-time algorithm with the same approximation guarantee as Larsen’s, optimal for tall matrices where $m = \mathrm{poly}(n)$. Using a more intricate analysis and fast matrix multiplication, we further achieve a runtime of $\widetilde{O}(\mathrm{nnz}(A) + n^{2.53})$, breaking the cubic barrier for square matrices and surpassing the limitations of linear-programming approaches [Eldan and Singh, RS&A 2018]. Our algorithm relies on two key ideas: (i) a new sketching technique for finding a projection matrix with a short $\ell_2$-basis using implicit leverage-score sampling, and (ii) a data structure for efficiently implementing the iterative Edge-Walk partial-coloring algorithm [Lovett and Meka, SICOMP 2015], and using an alternative analysis to enable “lazy” batch updates with low-rank corrections. Our results nearly close the computational gap between real-valued and binary matrices, for which input-sparsity time coloring was recently obtained by [Jain, Sah and Sawhney, SODA 2023].

We investigate the fundamental limits of transformer-based foundation models, extending our analysis to include Visual Autoregressive (VAR) transformers. VAR represents a big step toward generating images using a novel, scalable, coarse-to-fine “next-scale prediction” framework. These models set a new quality bar, outperforming all previous methods, including Diffusion Transformers, while having state-of-the-art performance for image synthesis tasks. Our primary contributions establish that, for single-head VAR transformers with a single self-attention layer and single interpolation layer, the VAR Transformer is universal. From the statistical perspective, we prove that such simple VAR transformers are universal approximators for any word-to-image Lipschitz functions. Furthermore, we demonstrate that flow-based autoregressive transformers inherit similar approximation capabilities. Our results provide important design principles for effective and computationally efficient VAR Transformer strategies that can be used to extend their utility to more sophisticated VAR models in image generation and other related areas.

As AI research surges in both impact and volume, conferences have imposed submission limits to maintain paper quality and alleviate organizational pressure. In this work, we examine the fairness of desk-rejection systems under submission limits and reveal that existing practices can result in substantial inequities. Specifically, we formally define the paper submission limit problem and identify a critical dilemma: when the number of authors exceeds three, it becomes impossible to reject papers solely based on excessive submissions without negatively impacting innocent authors. Thus, this issue may unfairly affect early-career researchers, as their submissions may be penalized due to co-authors with significantly higher submission counts, while senior researchers with numerous papers face minimal consequences. To address this, we propose an optimization-based fairness-aware desk-rejection mechanism and formally define two fairness metrics: worst-case fairness and average fairness. We prove that optimizing worst-case fairness is NP-hard, whereas average fairness can be efficiently optimized via linear programming. Through case studies, we demonstrate that our proposed system ensures greater equity than existing methods, including those used in CVPR 2025, offering a more socially just approach to managing excessive submissions in AI conferences.

The Fourier transform is a fundamental tool in computer science and signal processing. In particular, when the signal is sparse in the frequency domain---having only $k$ distinct frequencies---sparse Fourier transform (SFT) algorithms can recover the signal in a sublinear time (proportional to the sparsity $k$). Most prior research focused on SFT for discrete signals, designing both randomized and deterministic algorithms for one-dimensional and high-dimensional discrete signals. However, SFT for continuous signals (i.e., $x^*(t)=\sum_{j=1}^k v_j e^{2\pi \mathbf{i} f_j t}$ for $t\in [0,T]$) is a more challenging task. The discrete SFT algorithms are not directly applicable to continuous signals due to the sparsity blow-up from the discretization. Prior to this work, there is a randomized algorithm that achieves an $\ell_2$ recovery guarantee in $\widetilde{O}(k\cdot \mathrm{polylog}(F/\eta))$ time, where $F$ is the band-limit of the frequencies and $\eta$ is the frequency gap. Nevertheless, whether we can solve this problem without using randomness remains open. In this work, we address this gap and introduce the first sublinear-time deterministic sparse Fourier transform algorithm in the continuous setting. Specifically, our algorithm uses $\widetilde{O}(k^2 \cdot \mathrm{polylog}(F/\eta))$ samples and $\widetilde{O}(k^2 \cdot \mathrm{polylog}(F/\eta))$ time to reconstruct the on-grid signal with arbitrary noise that satisfies a mild condition. This is the optimal recovery guarantee that can be achieved by any deterministic approach.

We consider the task of interpolating a $k$-sparse band–limited signal from a small collection of noisy time-domain samples. Exploiting a new analytic framework for hierarchical frequency decomposition that performs systematic noise cancellation, we give the first polynomial-time algorithm with a provable $(3+\sqrt{2}+\epsilon)$-approximation guarantee for continuous interpolation. Our method breaks the long-standing $C > 100$ barrier set by the best previous algorithms, sharply reducing the gap to optimal recovery and establishing a new state of the art for high-accuracy band–limited interpolation. We also give a refined ``shrinking-range'' variant that achieves a $(\sqrt{2}+\varepsilon+c)$-approximation on any sub-interval $(1-c)T$ for some $c \in (0,1)$, which gives even higher interpolation accuracy.

The famous theorem of Fritz John states that any convex body has a unique maximal volume inscribed ellipsoid, known as the John Ellipsoid. Computing the John Ellipsoid is a fundamental problem in convex optimization. In this paper, we focus on approximating the John Ellipsoid inscribed in a convex and centrally symmetric polytope defined by $P := \{ x \in \mathbb{R}^d : -\mathbf{1}_n \leq A x \leq \mathbf{1}_n \},$ where $ A \in \mathbb{R}^{n \times d}$ is a rank-$d$ matrix and $ \mathbf{1}_n \in \mathbb{R}^n $ is the all-ones vector. We develop two efficient algorithms for approximating the John Ellipsoid. The first is a sketching-based algorithm that runs in nearly input-sparsity time $ \widetilde{O}(\mathrm{nnz}(A) + d^\omega) $, where $ \mathrm{nnz}(A) $ denotes the number of nonzero entries in the matrix $A$ and $ \omega \approx 2.37$ is the current matrix multiplication exponent. The second is a treewidth-based algorithm that runs in time $ \widetilde{O}(n \tau^2)$, where $\tau$ is the treewidth of the dual graph of the matrix $A$. Our algorithms significantly improve upon the state-of-the-art running time of $ \widetilde{O}(n d^2) $ achieved by [Cohen, Cousins, Lee, and Yang, COLT 2019].

Flow-based generative models have shown promise in various machine learning applications, but they often face challenges in handling noise and ensuring robustness in trajectory estimation. In this work, we propose NRFlow, a novel extension to flow-based generative modeling that incorporates second-order dynamics through acceleration fields. We develop a comprehensive theoretical framework to analyze the regularization effects of high-order terms and derive noise robustness guarantees. Our method leverages a two-part loss function to simultaneously train first-order velocity fields and high-order acceleration fields, enhancing both smoothness and stability in learned transport trajectories. These results highlight the potential of high-order flow matching for robust generative modeling in complex and noisy environments.

Training neural networks is a fundamental problem in theoretical machine learning. Second-order methods are rarely used in practice due to their high computational cost, even they converge much faster than first-order methods. The state-of-the-art result for the second-order method to train an over-parameterized neural network can run in O(log(1/ϵ)) iterations and each iteration has O(mnd + n3) running time, where n represent the number of data points, d is the dimension of the feature space of each data and m is the width of the neural network [Brand, Peng, Song and Weinstein ITCS 2021]. In this work, we further improve the convergence rate and the running time for each iteration to O(loglog(1/ϵ)) and O(mdτ2) respectively, where m = Ω(n4) and τ is the treewidth of the data matrix and usually very small. Our algorithm has a quadratic convergence rate, so it can be regarded as a truly second-order algorithm. To the best of our knowledge, our algorithm is the first to achieve a quadratic convergence rate for neural network training, with a per-iteration running time of O(mdτ2).

Sampling is a fundamental problem in optimization, machine learning and theoretical computer science. A common region of interest for sampling is the polytope, which is defined by a set of linear inequalities. The algorithm that is sampling from polytopes usually requires heavy matrix algebra, including matrix multiplication, matrix inversion and matrix determinant. In this work, we show how to implement the heavy matrix algebra in the area of sampling in nearly linear time for the polytope that has small treewidth. In particular, given a polytope defined by a matrix A ∈ ℝn×dwith treewidth τ, we improve the running time of each iteration for three typical sampling algorithms for polytopes such as Dikin Walk, Soft-Threshold Dikin Walk and Vaidya Walk from O(nd2) to O(nτ2) by exploiting the small treewidth structures of the matrices.

The rapid spread of fake news on social media has caused great harm to society in recent years, which raises the detection of fake news as an urgent task. Recent methods utilize the interactions among different entities such as authors, subjects, and news articles to model news propagation as a static heterogeneous information network (HIN). However, this is suboptimal since fake news emerges dynamically, and the latent chronological interactions between news in HIN are essential signals for fake news detection. To this end, we model the dynamics of news and associated entities as a News-Driven Dynamic Heterogeneous Information Network (News-DyHIN), where the temporal relationships among news articles are well captured with meta-path based temporal neighbors. With the support of News-DyHIN, we propose a novel fake news detection framework, named D ynam i c H ierarchical A ttention N etwork (DiHAN), which learns news representations via a hierarchical attention mechanism to fuse temporal interactions among news articles. In particular, DiHAN first employs a temporal node level attention to learn the temporal information from meta-path based news neighbors through the modeled News-DyHIN. Then, a semantic attention layer is adopted to fuse different types of meta-path based temporal information for news representation learning. Extensive evaluations conducted on two public real-world datasets demonstrate that our proposed DiHAN achieves significant improvements over established baseline models.