A collection of classical codes $C_1,\dots,C_m$ has product expansion if every low-weight word in the sum of their extensions to the product space can be written as a sum of words supported on few lines, each line being a codeword of the corresponding $C_i$. For $m=2$ product expansion is equivalent to robust testability of the tensor code, while for $m\ge 3$ it is strictly stronger; it is the hypothesis on the local codes behind recent constructions of good quantum LDPC codes, good quantum locally testable codes, and quantum codes with transversal non-Clifford gates. No explicit family over a fixed field was previously known to achieve constant rate, linear distance for both the code and its dual, and 3-fold product expansion at growing length. We prove that for the one-point evaluation codes $C_i$ of length $N_i=728\cdot27^{\,i-1}$ and pole order $\lfloor N_i/5\rfloor$ on the Garcia--Stichtenoth tower over $\mathbb{F}_{729}$, the triple $(C_i,C_i,C_i)$ has product expansion with a constant independent of $i$. The dual codes $C_i^\perp$ then form an explicit fixed-field family of rate tending to $109/130$ and relative distance at least $8/65$. The proof is geometric: we view the words of the sum code as arrays on the product of three copies of the $i$-th curve of the tower, where the parity checks are sections of a line bundle. An exact generation theorem describes the sum-code words supported on the grid footprint of a suitable divisor. A support-localisation argument then shows that every low-weight array lies on such a divisor, after deleting a small number of coordinates. We also give a sufficient criterion for three-fold product expansion in terms of degree and genus ratios, yielding explicit families over every non-prime finite field of order at least $512$. The principal conclusions have been formally verified in Lean 4.
Vinayak M. Kumar, Ray Li, Jonathan Mosheiff, Gilad Shavit
Thresholds for local properties tell us which guarantees to expect from random linear codes (RLCs) and help us carry those guarantees over to structured codes. A monotone property is $b$-local if a collection of at most $b$ codewords can witness its satisfaction or failure, as in list decoding and list recovery. The threshold of $\mathcal P$ is the code dimension at which the probability that an RLC in $\mathbb{F}_q^n$ satisfies $\mathcal P$ crosses $1/2$ in a sharp transition. We show that the threshold of a $b$-local property $\mathcal P$ is within $O(b)$ dimensions of the expectation threshold. This is the dimension predicted by the best union bound over covers of $\mathcal P$: families of subspaces such that the span of every witness contains at least one member. This gives a general derandomization statement: Any decreasing local property satisfied by RLCs at a given rate holds at a similar rate for pseudorandom ensembles that fool the cover union bound. In addition to previously studied ensembles, these include codes whose parity-check matrix is sampled from a small-bias distribution. Because our threshold characterization applies to all local properties, this derandomization also reaches properties beyond the scope of earlier reductions, including maximum loads in linear hashing for arbitrary input sets, rank-metric list decoding, and list decoding from insertion-deletion errors and burst errors. Our theorem unifies and strengthens prior works on row-symmetric and coordinate-wise linear characterizations, which located the threshold to within $O(q^{2b}\log_q n)$ and $O(b^2+nb/\log_2 q)$ dimensions, respectively. We obtain $O(b)$ error for every $b$-local property, independently of alphabet size. Under suitable pseudorandomness bounds, the rate loss vanishes for every $b=o(n)$, compared to $b=O(\log n)$ for earlier frameworks.
For a text $T$ of length $n$ over an alphabet of size $σ$, its suffix array lists the starting positions of the suffixes of $T$ in lexicographic order, and its inverse suffix array gives the lexicographic rank of the suffix starting at each position. Since the introduction of the FM-index and the compressed suffix array in 2000, both queries have been supported in $O((\log_σn)^ε)$ time using $O(n\logσ)$ bits, for any constant $ε>0$. Yet no nontrivial time-space lower bound for suffix-array queries in compact space was known. We give the first such lower bound: in the cell-probe model with $Θ(\log n)$-bit words, every deterministic $S$-bit data structure with $S\ge n$ answering suffix-array queries on binary strings of length at most $n$ has worst-case query time $Ω(\log\log n/\log((S/n)\log\log n))$. Hence, structures with $O(n(\log\log n)^{O(1)})$ bits need $Ω(\log\log n/\log\log\log n)$ query time, while constant query time requires $Ω(n\log^εn)$ bits for some constant $ε>0$, matching known upper bounds. In particular, no such $O(n)$-bit structure supports constant-time queries, answering the 25-year-old question of Grossi and Vitter. We also give exact complexity-preserving equivalences between suffix-array access and simpler prefix queries on short strings. For every $2\leqσ\leq n$, suffix-array queries are equivalent to prefix-select queries, and inverse-suffix-array queries are equivalent to prefix-special-rank queries. The reductions in both directions preserve all four standard measures up to constant factors: space, query time, preprocessing time, and preprocessing space. Unlike previous reductions, they incur no additive $O(\log\log n)$ query-time term. Thus, the corresponding prefix-query problems capture suffix-array and inverse-suffix-array access without asymptotic loss in any of the four measures.
Single-photon avalanche diodes (SPADs) are essential components of quantum communication receivers. In practical systems, some SPADs exhibit intrinsic step-like changes in dark-count rate (DCR), commonly referred to as random telegraph signal (RTS) noise. Similar RTS-like variations, however, can also arise from stray light, temperature-dependent threshold crossings, cable disturbances, electrical interference, and other readout artifacts. Distinguishing intrinsic RTS from these artifacts is important because they originate from different mechanisms and require different corrective actions. We present a self-referenced diagnostic that primarily uses the low-to-high afterpulse-yield ratio R, together with complementary checks based on DCR-state reproducibility, cross-channel behavior, and event timing. Four commercial SPAD modules were monitored in darkness for more than 920 h. Three exhibited intrinsic DCR switching of 44.59%, 19.33%, and 2.77%, with corresponding R values of $0.9996\pm0.0027$, $1.0050\pm0.0023$, and $1.0027\pm0.0043$, all consistent with unity. Controlled experiments reproduced temperature-related threshold crossings, light leakage, cable-contact artifacts, and artificial electrical injection. These artifacts produced distinct correlation and timing signatures: temperature-related threshold crossings gave intermediate pair-survival responses, cable disturbances and electrical injection generated sub-dead-time events, while light leakage produced simultaneous cross-channel switching and nonreproducible DCR levels. Combining R with orthogonal timing and DCR-based checks provides a practical self-referenced diagnostic framework for distinguishing intrinsic RTS from non-intrinsic artifacts using primarily time-tagged dark-count data.
Guozhen Zhu, Yuqian Hu, Sakila S Jayaweera, Wei-Hsiang Wang, Beibei Wang, K. J. Ray Liu
Indoor context deciphered by ambient sensing underpins many applications, from assisted living to smart buildings, yet remains weakly connected to the language-aligned paradigm of modern multimodal systems. Through billions of IoT devices, ambient WiFi Channel State Information (CSI) captures the indoor context of human activity and environmental dynamics passively via ubiquitous, always-on infrastructure. However, unlike vision or audio, CSI lacks naturally paired text like captions or transcripts, limiting its integration with language-driven AI systems. We present CSI-TextBench, a large-scale dataset and benchmark for aligning CSI data with natural language, unifying 3 sensing benchmarks into 285,790 samples across 7 tasks and pairing them with 2,291 hierarchically structured, label-derived descriptions via many-to-many assignment to construct 2.0 million CSI-text training tuples. Benchmarking 5 alignment methods from 4 paradigm families, we show that contrastive CSI-text alignment matches supervised classifiers without class labels, adapts to unseen classes with few samples, and responds to open-vocabulary natural-language prompts. A single unified model supports compositional scene understanding, answering joint queries over activity, proximity, and identity, achieving 86.9% top-1 accuracy on 140 composite scenes, outperforming task-specific classifier ensembles. CSI-TextBench enables ubiquitous ambient sensing as a language-indexed perception layer, enabling indoor contextual awareness in language-driven AI systems.
Ambient intelligence seeks to continuously understand human presence, activity, and physiology in physical spaces, enabling smart environments, health monitoring, and human-computer interaction. WiFi infrastructure offers a ubiquitous, always-on, and privacy-preserving sensing substrate across billions of IoT devices. Yet ambient sensing with WiFi remains largely fragmented, with most systems relying on task-specific models, labeled data collection, and customized training pipelines. We present AmbientFM, a foundation model for ambient sensing through ubiquitous WiFi signals. AmbientFM is pre-trained on 9.2 million unlabeled Channel State Information (CSI) samples collected over 439 days from 20 commercial device types deployed in real homes, the largest real-world WiFi CSI pre-training corpus reported to date. It learns transferable wireless representations through contrastive learning, masked reconstruction, and physics-informed objectives tailored to wireless signals. With lightweight adaptation, a single backbone transfers to 9 downstream tasks, achieving above 0.90 AUROC on all classification benchmarks and supporting dense spatial reconstruction. AmbientFM reduces the need for labeled data and task-specific design, enabling scalable ambient intelligence on existing wireless infrastructure.