sensor network designers

Abstract: We prove a Borsuk-Ulam theorem for adaptive measurements: if $2^n\le m$, then any $n$ adaptively chosen continuous functionals take identical values at two antipodal points of any sphere in $\mathbb{R}^m$. Consequently, at least $\lceil\log_2(m+1)\rceil$ adaptive continuous measurements are needed to learn the vectors of a ball in $\mathbb{R}^m$ with an error smaller than its radius, which matches the recently obtained upper bound up to one measurement. The bound extends to Bernstein widths in Banach spaces. The main idea of the proof was found by Claude Fable 5, an AI model developed by Anthropic, and we document the development in a last section.

Abstract: Quantile summaries provide a scalable way to estimate the distribution of individual attributes in large datasets that are often distributed across multiple machines or generated by sensor networks. The state-of-the-art summaries with \emph{relative error guarantees} of $\pm \varepsilon\cdot \mathrm{rank}$, offering increasingly higher accuracy towards the distribution's tails, are ReqSketch (Cormode et al., JACM 2023) and the recent streaming algorithm by Gribelyuk et al. (SODA 2025). For inputs of size $N$ and probability $δ$ of exceeding the error bound, ReqSketch achieves space of $O(\varepsilon^{-1}\cdot \log^{1.5}(\varepsilon N)\cdot \sqrt{\log δ^{-1}})$ memory words, and offers \emph{full mergeability}, allowing distributed or parallel processing of datasets. In contrast, the latter algorithm exceeds the lower bound of $Ω(\varepsilon^{-1}\cdot \log(\varepsilon N)\cdot \log\logδ^{-1})$ from (Cormode \& Veselý, PODS 2020) only by a factor of $O(\log\varepsilon^{-1}\cdot (\log \varepsilon^{-1} + \log\log N)\cdot\log^2\logδ^{-1})$, but it lacks the mergeability property, is substantially more involved than ReqSketch, and has unclear practical performance. Both of these data structures consist of relative compactors from ReqSketch that subsample the stream in a structured way and work well in the streaming setting but are difficult to analyze under mergeability. We design a new relative-error quantile summary that achieves full mergeability and also improves the state-of-the-art streaming space bound to $$O(\varepsilon^{-1}\cdot \log(\varepsilon N) \cdot\log \log δ^{-1} \cdot (\log \varepsilon^{-1} + \log \log(\varepsilon N) + \log \log δ^{-1})),$$ which is substantially closer to the lower bound. At the same time, our data structure is simpler than the algorithm from (Gribelyuk et al., SODA 2025) and therefore more suitable for implementation.

Abstract: A natural strategy for inverse problems with scarce labelled data is to transfer relational structure learned from abundant forward-simulation data. We show this strategy fails systematically, even when it satisfies the standard theoretical justification for why structure should help. We prove that approximate structure provides estimation-error benefits whenever the edge error satisfies $Δ< n^2 - kn$, reducing sample complexity from $O(n^2)$ to $O(kn+Δ)$. Structure learned via Neural Relational Inference (NRI) from dynamics prediction satisfies this condition, yet on a source-localisation task across 180 CFD-simulated hydrogen-leak scenarios and 180 acoustic scenarios, it degrades performance by 116% and 201% relative to a flexible, task-optimised attention baseline, while a physics-based prior (Green's function) degrades by only 69-72%. Four independent lines of evidence show this is not a tuning failure: NRI improves only 0.5% when given 18x more training data (versus 16.6% for the task-optimised baseline, $p<0.001$); performance is insensitive to the NRI edge threshold across a wide range; the dynamics-learned graph overlaps the task-optimal graph on only 6% of edges; and two further dynamics-derived structure estimators (correlation- and mutual-information-based) show no measurable benefit over a structure-free baseline, with the correlation-based estimator performing markedly worse. We formalise this gap as a statement about approximation error that the edge-accuracy condition cannot control, and we provide a lightweight transferability test (Jaccard similarity against a partially-observed target-task graph) that separates successful from failed transfer in all four domain/structure pairs we evaluate, using under an hour of computation and 15-20% of target-domain data; we present this as a heuristic calibrated on few cases, not a validated general threshold.

Abstract: We study decentralized multi-agent target search where homogeneous agents communicate intermittently at Poisson-distributed times. Standard unconditional belief fusion wastes communication opportunities by synchronizing agents during high-entropy exploration, when diverse independent beliefs provide better coverage than a premature consensus. We introduce \emph{entropy-gated belief coordination}, in which agents skip fusion while their collective entropy ratio exceeds a threshold~\(θ\) and merge only during exploitation, consistent with the bifurcation structure of nonlinear opinion dynamics and the submodular structure of the per-step information gain objective. We further derive \(\Istep(α,β)\), the expected mutual information per observation step between two agents' binary sensors, as an interpretable, communication-free measure of sensor informativeness that motivates the gating design and guides system-level analysis. Experiments across 103{,}680 trials (nine grid sizes up to \(100{\times}100\), Poisson communication timing, four target movement patterns) show that the Entropy-Gated Trust-Decay Planner (\textsc{EG-TDP}), which adds a detection-probability planner switch in exploitation mode, achieves mean belief quality \(\bar{Q}=0.300\) (mean belief mass at the true target cell, averaged across all trials and steps), a \(58.9\%\) gain over arithmetic mean and a \(37.4\%\) gain over visit-weighted fusion. On representative configurations, EG-TDP also outperforms a joint-Bayesian reference that uses all agents'~observations at every step, despite operating under random intermittent contact only.

Abstract: Physical-field reconstruction and forecasting depend on both measurement density and spatial layout, yet evaluation under a single observation pattern does not characterize performance when that pattern changes. We introduce PDE-OBS, an integrated benchmarking platform spanning numerical data generation, model training, and inference and evaluation under varying observation conditions. It combines 560,000 fields and trajectories from seven partial differential equation families with configurable observation operators and seven adapted baseline methods for stationary reconstruction and short-horizon forecasting. Separating observation construction from physical records allows users to specify parameterized patterns and deterministic mixtures for training and testing while preserving prediction targets and data splits. The evaluation protocol uses references trained for each test pattern to compare models on identical test observations and targets, alongside equal-count groups for spatial-layout comparisons. On a 14,000-record subset, we evaluate 441 trained models under nine test patterns, yielding 3,969 evaluations. Mean cross-pattern error exceeds mean matched-pattern error in all 49 PDE-method pairs, and this finding persists in a configuration-matched subset of 117 models. Denser test observations do not consistently reduce error for a fixed model. Mixed-pattern training on five completed pairs reduces large single-pattern transfer errors, although destination-trained references usually remain more accurate. Together, the benchmark and findings support systematic evaluation of observation-pattern sensitivity and provide a reusable workflow for developing methods under changing measurement conditions. Code: https://github.com/ru1ch3n/PDE-OBS.

Abstract: Over-the-air computation (AirComp) aggregates distributed data through the wireless multiple-access channel, but coherent implementations require channel state information (CSI), phase alignment, and power control, whereas non-coherent energy methods remain affected by fading. Signal superposition at the receive antenna is linear but requires coherence, and energy superposition is linear only in expectation over fading. We introduce occupancy-domain computation (ODC), whose observable is neither a received amplitude nor an energy: the sum is carried by the silence of the shared resources. With exponential Bernoulli activation, the individual silence probabilities multiply, and the server recovers the sum from the idle fraction using binary activity decisions alone, so that once an activation is detected the amplitude that produced it does not enter the estimate. We characterize the maximum-likelihood estimator, optimal load, and a scale-integrated Fisher-information bound for non-adaptive operation over unknown dynamic ranges. We then introduce balanced occupancy computation (BOC), where each device forms a data-dependent quota of random burst placements. This removes the random placement-count fluctuation of Bernoulli activation; under ideal detection, the leading-order asymptotic root-mean-square error of BOC is no larger than that of Bernoulli ODC at any load and approaches $1/\sqrt{2M}$, where $M$ is the number of resource elements, as the number of devices becomes small relative to $M$. We further analyze unknown-scale operation, finite-frame deviations, and heterogeneous detection misses. Simulations validate the theory and compare ODC/BOC with affine non-coherent energy aggregation and REED.

Abstract: We study distributed one-dimensional mean estimation under a 1-bit communication constraint. Each agent observes one sample, drawn independently from an unknown distribution, and returns a single bit in response to a query $Q: \mathbb{R}\to\{0,1\}$ chosen by a central learner. The distribution has mean in $[-λ,λ]$ and $k$-th central moment at most $σ^k$, for a fixed $k>1$. The order-optimal two-stage protocol of Lau and Scarlett uses responses from the first batch to choose the second-batch queries, motivating the question of whether this single round of interaction is necessary. We answer this negatively: for every $k>1$, a non-adaptive protocol attains the adaptive 1-bit minimax rate (and concurrent works reached the same conclusion via different strategies). We further determine the minimax sample complexity among non-adaptive 1-bit estimators when every one-set $Q^{-1}(1)$ is restricted to a union of at most $s$ intervals. Relative to unrestricted non-adaptive 1-bit querying, this constraint adds a term of order $(λσ/(s\varepsilon^2))\log(1/δ)$, giving the full tradeoff between sample complexity and interval complexity to within $k$-dependent constant factors. As a corollary, we identify, order-wise, the minimum interval budget needed to retain the unrestricted 1-bit minimax sample rate.