7 papers
When Does Tool Use Increase the Expressive Power of Finite-Precision Recurrent Models?
Nikola Zubić, Qian Li, Yuyi Wang +1
Modern sequence models are increasingly deployed as agents that interleave token generation with calls to external tools. We study when such tool access increases computational exp…
Rethinking the Role of Positional Encoding: Sliding-Window Transformers without PE Remain Turing Complete
Qian Li, Xinyu Mao, Shang-Hua Teng
Positional encoding (PE) is widely viewed as necessary for transformers to process ordered sequences: without them, the next-token map appears permutation-invariant in its context…
On the Expressive Power and Limitations of Multi-Layer SSMs
Nikola Zubić, Qian Li, Yuyi Wang +1
We study how depth, finite precision, state dimension, and chain-of-thought (CoT) affect the expressive power of multi-layer state-space models (SSMs). For the explicit-table -f…
Solving No-wait Scheduling for Time-Sensitive Networks with Daisy-Chain Topology
Qian Li, Henan Liu, Heng Liu +1
Time-Sensitive Networking (TSN) is a set of standards aiming to enable deterministic and predictable communication over Ethernet networks. However, as the standards of TSN do not s…
Efficient Turing Machine Simulation with Transformers
Qian Li, Yuyi Wang
Constant bit-size Transformers are known to be Turing complete, but existing constructions require chain-of-thought (CoT) steps per simulated Turing machine (TM) step, le…
Constant Bit-size Transformers Are Turing Complete
Qian Li, Yuyi Wang
We prove that any Turing machine running on inputs of arbitrary length can be simulated by a constant bit-size transformer, as long as the context window is sufficiently long. This…
A Simple Distributed Algorithm for Sparse Fractional Covering and Packing Problems
Qian Li, Minghui Ouyang, Yuyi Wang
This paper presents a distributed algorithm in the CONGEST model that achieves a -approximation for row-sparse fractional covering problems (RS-FCP) and the dual column-spar…