跳到正文
研踪PaperTrail

YOUR RESEARCH, IN SIGHT

让下一篇重要论文，不再错过。

覆盖计算机全学科，以 AI 为快捷入口。关注方向、作者和关键词，把发现变成持续的研究积累。

部分采集异常
正在读取账号与研究记录…

全站更新概况

+0新增论文
+0其中 AI 相关
+1已有论文修订
+100新增 AI 导读

arXiv 最近完成扫描：2026-11-09 02:00 · 全站最近入库：2026-11-08 06:02各信源进度 →

统计口径与数据新鲜度

统计 2026-11-08 02:47 — 2026-11-09 02:47（北京时间） · 点击数字查看对应简报；AI 相关包含在新增论文内。

最近完成检查：2026-11-09 02:00最近发现新增版本：2026-11-08 06:02库内论文最新更新时间：2026-11-06 02:59

每分钟刷新已保存的数据。空检查不代表采集异常；新收录可能包含历史论文。AI 导读按新增版本计数。

17,100 已收录论文14,661 AI 相关4,057 有修订112 HF 社区发现

浏览论文库

研究日报 / 周报 →按信源浏览 →

时间范围跟随排序：版本更新、本站收录或首次发表。最新收录可能包含历史论文。部分信源异常，查看状态 →

找到 328 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-09 01:58（北京时间）
新论文 · v1arXiv:2611.04444

Binary Huffman Coding with Unequal Letter Costs Is NP-Complete

L. Sunil Chandran, Rishikesh Gajjala

原文摘要

Binary prefix coding assigns prefix-free binary words to symbols to minimize their frequency-weighted cost. Huffman solved the equal-letter-cost case in polynomial time in 1952 [Proc. IRE'52]. For unequal letter costs, Karp gave an integer-programming formulation in 1961 [IRE Trans. Inf. Theory'61]. Exact polynomial-time algorithms for fixed integer costs were given by Golin and Rote [IEEE Trans. Inf. Theory'98] and Bradford, Golin, Larmore, and Rytter [J. Algorithms'02]. For input-dependent costs, Golin, Mathieu, and Young gave a polynomial-time approximation scheme [SICOMP'12]. The exact complexity when letter costs are part of the input had remained unresolved. We resolve this $65$-year-old problem by proving that deciding whether there exists a binary prefix-free code of frequency-weighted cost at most a given threshold is NP-complete, even when the letter costs are consecutive positive integers $(M,M+1)$ supplied as part of the input. All frequencies, letter costs, and thresholds are encoded in binary. Consequently, finding an optimal code is NP-hard. Our proof uses two polynomial-time reductions, starting from Planar Independent Set. The intermediate problem prescribes the number of leaves at each depth of a full ordered binary tree and minimizes a signed linear score on their sorted right-edge counts. The first reduction represents an independent-set verification program by a tree growing level by level. A fixed-profile identity converts narrow coordinate restrictions into linear penalties that enforce the computation. The second reduction adds large dyadic terms to the symbol frequencies to force prescribed depths. These terms contribute a constant to the weighted number of ones, leaving smaller signed perturbations to reproduce the tree score.

cs.DS · cs.CC · cs.CG · cs.IT

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.05430

On the most informative Boolean function under noise

Dimiter Kramer, Mert Saglam

原文摘要

Let $X$ be a uniform random bit string and $Y$ be obtained by flipping each bit of $X$ independently with probability $p$. Let $C$ be a random bit obtained as a function of $Y$. We show that $\mathbf{I}(C:X)\le \mathbf{I}(Y_1:X)$ for all $p\in[0,1]$, which resolves a conjecture posed by Courtade and Kumar in 2013.

cs.IT · math.CO

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2607.28907

Domain-Adaptive Deep Joint Source-Channel Coding for Image Classification

Yishen Li, Xuechen Chen, Xiaoheng Deng, Hao Zhang

原文摘要

Deep joint source--channel coding (Deep JSCC) can suffer from domain shift between training and deployment data. We study single-source domain adaptation for image classification over wireless channels. A Gaussian example shows that improving channel quality does not necessarily improve target-domain accuracy under a fixed source-trained classifier. We further proposed an information objective to reduce domain information while preserving class information. Motivated by the analysis, we develop a domain-adaptive Deep JSCC method that combines class-wise adversarial alignment with pseudo-label supervised contrastive learning. The former uses all target samples to reduce class-conditional domain differences, while the latter selects high-confidence target samples to obtain class-discriminative received representations. We relate these losses to the information objective, and analyze the effects of pseudo-label errors and confidence-based selection. Experiments on SVHN--MNIST and PACS over AWGN and Rayleigh channels demonstrate improved target-domain classification without additional inference-time networks. The proposed method achieves 98.15\% accuracy on SVHN $\rightarrow$ MNIST at 10~dB CSNR.

cs.IT · cs.CV · eess.SP

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2611.00647

Cyclotomic polynomials with trinomial irreducible factors over finite fields

Li Zhu, Hongfeng Wu

原文摘要

We classify the pairs $(q,n)$, where $q$ is a prime power, $n>1$, and $\gcd(n,q)=1$, for which every irreducible factor of $Φ_n(x)$ over $\F_q$ has exactly three nonzero terms. The positive support exponents of these factors have a common greatest common divisor, which gives a unique reduction by a power substitution. The reduced degree is two in odd characteristic and belongs to $\{2,3,4\}$ in characteristic two; the cubic and quartic cases arise by scalar substitution from the layers of orders $7$ and $15$. This yields necessary and sufficient arithmetic conditions on $(q,n)$ and explicit factorizations. Among the classified families, precisely those arising from quartic bases have a divisor layer containing an irreducible factor with more than three terms.

math.NT · cs.IT

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04363

A Conditional Quantum Kac-Bernstein Theorem

Hesam Hosseini, Jinpei Zhao, Masahito Hayashi

原文摘要

We establish a conditional quantum Kac-Bernstein theorem for mixing of two independent, finite-mode bosonic inputs with quantum memories. We characterize exactly when the outputs are conditionally independent given both memories. Each input then decomposes into orthogonal memory sectors sharing a common Gaussian state on the physical system and a bosonic memory factor, up to sector-dependent physical displacements. In particular, triviality of the common bosonic factor implies separability of the inputs, as occurs whenever either memory has finite-dimensional support.

quant-ph · cs.IT · math-ph

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2611.00100

Optimality of the $D_4$ lattice quantizer

Tianle Liu

原文摘要

We prove that the root lattice $D_4$ uniquely minimizes the normalized second moment among four-dimensional lattices, up to similarity. The minimum is $13/(120\sqrt{2})$. The proof reduces the problem to polynomial inequalities on three secondary cones. We derive the second-moment formulas geometrically and give explicit polynomial certificates that can be checked by coefficient comparison. We also derive a lower bound for lattice quantizers in every dimension at least two from the number of Voronoi facets, using a comparison with circular cones and concavity in the solid angle. This bound strictly improves the sphere bound and recovers the hexagonal value in dimension two.

math.MG · cs.IT · math.CO

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04341

Pairwise Distortion Distribution with Graph-Based Importance Sampling for Quantization Error and Intrinsic Dimension Estimation

Xi Chen, Carl Nuzman, Shirin Jalali

原文摘要

Quantifying the dimensionality of data is a fundamental need in machine learning and signal processing applications such as representation learning, data compression, and inverse problems, where the extrinsic dimension in which the data is presented can be very different from the intrinsic dimension that determines the operational performance. Various concepts, such as Rényi information dimension, rate-distortion dimension, and quantization dimension are useful here. Despite their theoretical significance, estimating these measures are challenging given their asymptotic definitions. Recent research has shown that analyzing the pairwise distortion distribution (PDD) of a data source can provide a tractable lower bound on the distortion of random codebook quantization, from which a tractable notion of intrinsic dimension can be derived. In this paper we extend this line of research in three main ways. First, we develop a related upper bound on distortion of random codebook quantization. Second, we improve the computability of both the lower and upper bounds, using a graph-based adaptive importance sampling approach. Third, we leverage the bounds to define new notions of intrinsic dimension which form upper and lower bounds on the Rényi information dimension, rate-distortion dimension, and quantization dimension, and which can be empirically estimated from unknown data sources. We illustrate the concepts by analyzing several artificial and empirical distributions.

cs.IT · stat.ML

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2610.19691

Efficient construction of subspace design codes over constant alphabet

Shu Liu

原文摘要

Subspace-design codes form a central unifying framework in coding theory, connecting probabilistic existence results and explicit algebraically structured constructions. The two core families are folded Reed-Solomon codes and univariate multiplicity codes, both possessing the subspace-design property. These codes reach list-decoding capacity with polynomial-size lists, but their alphabet size grows with code length and hurts practical efficiency. Goyal, Guruswami, and Hsieh achieved a major breakthrough: they constructed the first explicit subspace-design codes over constant-size alphabets via the Alon-Edmonds-Luby expander framework, settling an open problem and showing subspace-design properties can hold without large alphabets. Despite recent progress, constructing subspace-design codes with low-complexity efficient encoding remains a critical open challenge. This work gives an explicit construction of r-dimensional subspace-design codes over a constant alphabet whose size grows exponentially with r. By comparison, Goyal et al. (FOCS 2026) built r-dimensional subspace-design codes with alphabet size doubly exponential in r squared. Our construction is computationally efficient: encoding scales quadratically with block length and linearly with dimension r in field operations. We use modified algebraic geometry codes, replacing rational evaluation points with higher-degree places to obtain a valid additive code. To confirm parameter bounds, we use Moore matrices to analyze determinants with many zero entries. We also generalize univariate multiplicity codes, originally built from Reed-Solomon codes, to algebraic geometry codes, and prove these AG-multiplicity codes achieve optimal parameters.

cs.IT

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04285

Optimal Communication for Distributed Sparse Histogram Aggregation

Fangwei Ye, Yijun Fan

原文摘要

Histogram estimation is a fundamental primitive in distributed data analysis, with applications in counting queries and federated learning. In many settings, the universe of categories is enormous, yet each user's data involves only a small subset, yielding sparse local histograms. This raises a natural question: To what extent can local sparsity reduce the communication needed to estimate the global histogram? We answer this question by characterizing the communication complexity of distributed sparse histogram estimation under prescribed $\ell_1$ distortion and failure probability constraints. Our upper bound is achieved by a randomized covering scheme that optimizes how accurately each user represents its local histogram to reduce communication. By exploiting the distortion budget directly rather than imposing unbiasedness, the scheme achieves lower communication costs than standard unbiased sampling and hashing constructions. We establish the scheme's first-order optimality through a lower bound based on local support identification. The key step is to relate communication cost directly to the number of active coordinates revealed by each user's message, rather than to bound information about the aggregate via distance-based Fano's inequalities. This characterization further quantifies how the communication advantage of heterogeneous over homogeneous encoders varies across parameter regimes.

cs.IT

查看论文
arXiv ↗PDF ↗
版本更新 · v6arXiv:2412.03774

Refining Concentration Bounds for Gaussian Quadratic Chaos with Applications

Kamyar Moshksar

原文摘要

This paper studies concentration of measure for Gaussian quadratic chaos in the non-asymptotic regime. We begin by tightening the classic Hanson-Wright inequality, where we increase its absolute constant $κ$ from 0.125 to at least 0.1457 in the symmetric case. We present a sharper version of Laurent-Massart inequality (LMI), which increases $κ$ from the largest available value of $1-\frac{\sqrt{3}}{2}\approx 0.134$ to $\frac{9-\sqrt{17}}{32}\approx 0.152$ in the positive-semidefinite case. We develop a sequence of inequalities indexed by $m\ge1$ that involve Schatten norms of the underlying matrix. The case $m=1$ recovers HWI. The bounds undergo a phase transition in the sense that if the tail parameter is smaller than a critical threshold $τ_c$, then $m=1$ is the tightest, whereas if it is larger than $τ_c$, then $m=\infty$ is the tightest. This leads to a novel bound called the $m_\infty$ bound. All HWI, LMI and the $m_\infty$ inequality rely on Markov's inequality. By avoiding Markov's inequality, we introduce the strong and weak $χ^2$ inequalities. We provide a list of concentration bounds that depend only on the operator norm in the positive-definite case, namely, the $m_\infty$ bound, the weak $χ^2$ bound, relaxed versions of HWI and LMI, and the so-called large-deviations bound. The sharpest among these is shown to be always either the $m_\infty$ bound or the weak $χ^2$ bound. By utilizing conditioning, modified versions of $m_\infty$, $χ^2$, and HW inequalities of various orders are proposed, all of which can be significantly tighter than the original inequalities. By leveraging the Ruben-Kotz expansion for the distribution of a positive-definite quadratic form, we introduce the Ruben-Kotz inequalities (RKIs) for general symmetric quadratic forms. A key advantage of RKIs is that they provide an explicit upper bound on the approximation gap.

math.PR · cs.IT

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04179

Hardware-Efficient Reinforcement-Learned Scheduling for Quantum LDPC Decoders

Mohsen Moradi, Vahid Nourozi, Wei Tang, David Mitchell

原文摘要

Quantum low-density parity-check (QLDPC) codes are promising for fault-tolerant quantum computing, but their decoding algorithms present significant hardware implementation challenges. Reinforcement-learned sequential belief propagation (RL-S) improves the error-correction performance of conventional belief propagation (BP) through adaptive variable-node scheduling. However, its heap-based priority management introduces substantial hardware overhead. This paper presents hardware implementations of BP, RL-S, and bucket-based reinforcement-learned BP (BRL-S) for the [[288,12,18]] bivariate bicycle QLDPC code. The BRL-S architectures employ quantized priorities and first-in, first-out (FIFO) buckets to simplify scheduling. Three configurations with two, four, and eight priority levels are evaluated. FPGA synthesis results demonstrate that BRL-S reduces lookup-table utilization by approximately 68--72% compared with RL-S. ASIC synthesis further shows reductions of 63--67% in area and 64--69% in estimated power consumption. These results demonstrate that bucket-based scheduling substantially improves the hardware efficiency of reinforcement-learned QLDPC decoders.

cs.IT · quant-ph

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2610.12357

Improved Local Leakage Resilience of Shamir Secret Sharing and Worst-Case Optimal Polynomial Intersection

Yihang Sun, Mary Wootters

原文摘要

We study two problems: Local Leakage Resilience (LLR) for Shamir secret sharing, and worst-case Optimal Polynomial Intersection (OPI), over a prime field $\mathbb{F}_p$. For a polynomial $Q(X)$ of degree less than $k$, LLR for Shamir secret sharing asks what a few leaked bits from each of the $n$ shares $Q(α_1), \ldots, Q(α_n)$ reveal about $Q(0)$. Given (worst-case) input lists $S_1, \ldots, S_n \subset \mathbb{F}_p$, OPI seeks a polynomial $Q(X)$ so that $Q(α_i) \in S_i$ for as many $i$ as possible. Leveraging recent connections between these two problems due to (Sun, Wootters 2026), we improve the state-of-the-art for both problems. For LLR, we show that there is some constant $δ> 0$ so that Shamir secret-sharing is one-bit LLR (only a negligible amount about $Q(0)$ is learned) whenever $R := k/n \geq 1/2 - δ$. This is the first result to break the so-called ``one-half barrier'' for LLR, and improves over the previous best known result, requiring $R \geq 0.668$ (Kasser, 2025). For OPI, we give a quantum algorithm that finds a polynomial $Q(X)$ that agrees with at least a $\mathsf{SCL}_ρ(R)-\varepsilon$ fraction of the lists, for every fixed $\varepsilon>0$, where $\mathsf{SCL}_ρ$ is the \emph{semicircle law} of (Jordan et al., 2025). This improves previous algorithmic (and existential) results of (Jo, 2026) and (Horinaga, Yamakawa, 2026). We also give further improved existential results for all OPI instances; and when the evaluation points $α_i$ are chosen at random, for every rate $R > 0$ we show that, with high probability, for worst-case $S_i$ there exists \emph{perfect} solution. Finally, we adapt the hardness result of (Yamakawa, Zhandry, 2024) to apply to OPI (rather than a folded version); this gives an unconditional separation between the quantum and classical hardness of OPI relative to a membership oracle.

quant-ph · cs.CR · cs.DM · cs.IT

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04023

Making Every Edit Count: Efficient Binary Edit Correction at the Gilbert-Varshamov Bound

Ryan Gabrys, Shubhransh Singhvi, Eitan Yaakobi

原文摘要

We construct binary codes that attain the classical Gilbert-Varshamov redundancy guarantee for a fixed number of edit errors, with deterministic polynomial-time construction, encoding, and decoding. For every fixed integer $t\ge 1$ and all sufficiently large block lengths $n$, our codes correct any combination of at most $t$ insertions, deletions, and substitutions in total, with redundancy at most $2t\log_2 n+O_t(1)$. All algorithms run in polynomial time in $n$ for fixed $t$, and decoding recovers the original information message. This realizes the classical counting guarantee algorithmically without enumerating the exponentially large space of binary words.

cs.IT

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.03979

On the optimality of truncation among binary linear sketches

Robinson D. H. Cung, Adway Girish, Emre Telatar

原文摘要

We study statistical inference and function evaluation problems in which the input binary vector is available only through a binary linear sketch, i.e., a fixed number of parity measurements. We show that under a certain monotonicity condition, simply truncating the input by retaining a subset of its coordinates is optimal among all linear sketches of the same size. In particular, this applies to distributed testing of correlations of binary vectors when they are of opposite signs and evaluating unate Boolean functions on uniformly random inputs. Additionally, given that truncation is optimal, we immediately have lower bounds for arbitrary binary linear sketches. To illustrate this application, we consider the one-way communication complexity of a distributional graph connectivity problem on $n$ vertices and show that truncation, and hence all binary linear sketches, requires $Θ(n \log n)$ bits to achieve constant error, while a nonlinear protocol only requires $O(\log n)$ bits.

cs.DS · cs.CC · cs.IT

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2610.35933

Deterministic Causal Quantization with Bounded Error: Adaptive Reconstruction and Entropy bounds

Rama Cont, Massoud Heidari

原文摘要

We study compression of real-valued stationary sources under a deterministic error bound: every sample must be reconstructed within a prescribed tolerance $\varepsilon$ on every input sequence. Reconstructions are causal, depending only on present and past inputs. Rates are measured by the entropy of the quantizer output, which block entropy coding can approach, and compared with the minimum rate of unrestricted block quantization under the same error constraint. A uniform scalar quantizer with cells of width $2\varepsilon$ is within one bit per sample of this minimum whenever finite-entropy scalar quantization is possible, without density, independence, or mixing assumptions. Under entropy and Sobolev regularity conditions, the gap is at most $2\mathcal{J}\varepsilon^2/(π^2\ln 2)$, where $\mathcal{J}$ is the asymptotic Fisher information per sample. Thus the cost of causal reconstruction vanishes at a quadratic rate as the tolerance decreases. A uniform grid, however, cannot adapt to the source. We construct an adaptive quantizer whose encoder and decoder maintain a common finite set of reconstruction values, updated from the transmitted symbols alone; suitable initialization reproduces any uniform grid. When its initial values are at least $\varepsilon$ apart, its rate is within two bits per sample of the minimum for every such source. For sources uniform within separated intervals of width $2\varepsilon$, storing the interval centers attains the minimum and its Shannon lower bound. Such configurations can outperform every uniform grid of the same cell width: over sources with well-separated intervals, the best uniform grid's worst-case excess rate is $1/(2\ln 2)\approx 0.72$ bit per sample.

cs.IT · math.PR

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2610.22272

The Information Bottleneck and the Privacy Funnel are NP-hard

Roberto Bruno, Ugo Vaccaro

原文摘要

Given a joint distribution $P_{XY}$ of random variables $X,Y$ on finite alphabets, the information bottleneck method seeks a representation $T$ of $X$ that is as informative as possible about $Y$ while compressing $X$; the privacy funnel asks for a representation that discloses much about $X$ while leaking little about $Y$. In both scenarios $T$ and $Y$ are conditionally independent given $X$. We show that computing the optimal value $\operatorname{IB}(P_{XY},R) = \sup_T \{ I(Y;T) : I(X;T) \le R \}$ of the information bottleneck problem, as well as its Lagrangian relaxation $L_β(P_{XY}) = \sup_T [ I(Y;T) - βI(X;T) ]$, is NP-hard. Moreover, unless $\mathrm{P} = \mathrm{NP}$, neither $\operatorname{IB}(P_{XY},R)$ nor $L_β(P_{XY})$ can be approximated in polynomial time within an additive error of order $|\mathcal{X}|^{-(1+α)}$, for every fixed $α> 0$. We also prove that computing the privacy funnel $\operatorname{PF}(P_{XY},r) = \inf_T \{ I(Y;T) : I(X;T) \ge r \}$ and its Lagrangian relaxation $Λ_β(P_{XY}) = \inf_T [ I(Y;T) - βI(X;T) ]$ is NP-hard, and that, unless $\mathrm{P} = \mathrm{NP}$, neither can be approximated in polynomial time within an additive error of order $|\mathcal{X}|^{-2}$.

cs.IT

查看论文
arXiv ↗PDF ↗
版本更新 · v5arXiv:2608.28469

Distributed Cross-Layer Optimization for Covert Multi-Hop, Multi-Modal Networks: Exponentially Fast Convergence and Robust Tracking

Sirin Chakraborty, Andrea Panebianco, Yuchen Tian, Kevin S Chan, Fikadu Dagefu, Yin Sun, Ness B. Shroff

原文摘要

This paper develops the first distributed cross-layer algorithm for joint congestion control, routing, scheduling, and power control in covert multi-hop, multi-modal wireless networks, where adversarial wardens (Willies) monitor radio modalities via energy detection. The Detection Error Probability (DEP), the probability that a Willie fails to reliably detect ongoing transmissions, is generally non-concave in the transmit powers, making DEP-based covert network optimization challenging. We resolve this by constructing the tightest concave lower bound on the log-DEP, yielding a conservative convex problem that guarantees satisfaction of the original DEP constraints and unifies hard covertness constraints and covertness-utility maximization in a single problem. We develop a Parallel Proximal Alternating Direction Method of Multipliers (PP-ADMM) algorithm for the resulting cross-layer problem and prove global Q-linear convergence, i.e., exponentially fast convergence, to the set of optimal solutions under standard regularity conditions. Numerical results confirm linear convergence and demonstrate robust tracking performance under channel fading and Willie mobility.

cs.IT · eess.SP

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.03884

Timely Ground-Station Status Delivery via UAV-Assisted Data Collection and Hierarchical RL

Xiangjian Gao, Mohammad Moltafet, Hamid R. Sadjadpour

原文摘要

We consider a UAV-assisted status-update system in which a rotary-wing unmanned aerial vehicle (UAV) collects updates from multiple sensors, stores the newest update of each sensor, and forwards selected buffered updates to a ground station (GS). We minimize a weighted sum of the time-average GS-side age of information (AoI) and UAV energy consumption over a finite horizon. The optimization is subject to half-duplex operation, sensor and UAV energy-causality constraints, transmission-rate and power limits, and a terminal-location constraint. Because collection changes the information age at the UAV but does not reduce the GS-side AoI until the buffered update is forwarded, mobility, collection, and forwarding decisions are coupled over time. We use a hierarchical AoI-energy actor-critic (HAE-AC) controller in which a coarse-timescale actor selects return-feasible UAV movements, while a deterministic per-slot scheduler constructs feasible collection or forwarding sets and assigns the minimum transmit power required for each scheduled transmission. In a 100-sensor deployment, HAE-AC reduces the average GS-side AoI by about 22% relative to an adaptive staleness-gated benchmark. Compared with forward-upon-collection, selective buffered forwarding reduces the number of downlink bursts by roughly 30% while increasing the number of collections per sensor by more than 23%.

cs.IT · eess.SP · eess.SY

查看论文
arXiv ↗PDF ↗
版本更新 · v3arXiv:2603.04530

Complete Diagrammatic Axiomatisations of Relative Entropy

Ralph Sarkis, Fabio Zanasi

原文摘要

Relative entropy is a fundamental class of distances between probability distributions, with widespread applications in probability theory, statistics, and machine learning. In this work, we study relative entropy from a categorical perspective, viewing it as a quantitative enrichment of categories of stochastic matrices. We consider two natural monoidal structures on stochastic matrices, given by the Kronecker product and the direct sum. Our main results are complete axiomatisations of Kullback-Leibler divergence and, more generally, of Rényi divergences of arbitrary order, for each such structure. Our axiomatic theories are formulated within the framework of quantitative monoidal algebra, using a graphical language of string diagrams enriched with quantitative equations.

cs.LO · cs.IT · math.CT

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.03871

Survival-Time Risk Beyond Low-Order Channel Models: Identifiability and Scheduling

Ruifeng Zheng, Zhihan Xu, Pit Hofmann, Frank H. P. Fitzek

原文摘要

This paper investigates whether low-order packet-loss statistics suffice to assess survival-time risk under bursty packet losses, i.e., the probability that no update succeeds for a prescribed number of consecutive slots. Conventional models, such as the Gilbert model, characterize packet losses using the loss rate and mean burst length, but channels sharing these statistics may exhibit substantially different failure risks. We characterize the Markov channels one order above a given low-order fit that share its statistics and analyze their risks under acknowledgment-based scheduling with transmission budgets. We show that, with dense transmission attempts, risk is primarily governed by loss persistence beyond the modeled memory, and the worst-case channel need not be the most persistent one. Under limited budgets, retry spacing makes loss relapse probabilities important and can reverse the risk ordering of compatible channels. Numerical and measurement results show that low-order models can substantially underestimate the risk, highlighting the need for scheduling-dependent channel statistics.

cs.NI · cs.IT

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.03816

Data-Driven Spectrum Access Technologies for 6G

Foad Sohrabi, Harish Viswanathan, Sivarama Venkatesan, Jinfeng Du, Aliye Özge Kaya, Navin Hathiramani, Pavan Koteshwar Srinath

原文摘要

The surge in global mobile traffic, driven by 5G adoption and emerging applications, necessitates new spectrum allocations for 6G systems. With most major swaths of spectrum below 15 GHz already allocated to other services, co-existence between cellular and incumbent services such as satellite or radar systems is critical to make such spectrum accessible for 6G. At the same time, the advent of artificial intelligence offers a new opportunity for designing more efficient spectrum sharing techniques. This paper presents four novel data-driven spectrum access techniques to enable efficient use of spectrum for the 6G era: 1) co-existence technique for efficient protection of fixed incumbent receivers within an established protection area; 2) data-driven approach for protecting satellite receivers via control of radiated power above the horizon; 3) spectrum sensing-based fast-time-scale physical resource block blanking; and 4) base station-based spectrum occupancy detection to enable fast-time-scale spectrum sharing with satellite and non-terrestrial network incumbents. These techniques leverage artificial intelligence and extreme multiple-input multiple-output capabilities to enable efficient spectrum co-existence/sharing while maintaining cellular network performance.

eess.SP · cs.IT

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.03639

Quantum channel tomography: optimal bounds in the near-boundary regime

Kean Chen, Aadil Oufkir

原文摘要

Quantum channel tomography (also known as quantum process tomography) is a fundamental task in quantum information and quantum computing, aiming to learn the full description of an unknown quantum channel from black-box queries. For channels with input dimension $d_1$, output dimension $d_2$, and Kraus rank at most $r$, [CGO+26] identifies the dilation rate $τ=rd_2/d_1\geq 1$ as a key parameter governing a Heisenberg-to-classical transition in query complexity. While the optimal bounds in the boundary regime ($τ=1$) and the away-from-boundary regime ($τ\geq 1+Ω(1)$) are now known, the precise behavior in the near-boundary regime ($1<τ<1+o(1)$) has remained unresolved. In this paper, we close this gap, thereby fully settling the query complexity of quantum channel tomography. Specifically, we show that the query complexity is - $Ω(rd_1d_2/\varepsilon^2)$ for diamond norm error $\varepsilon$, matching the upper bound by [MB26, CGO+26], - $Θ(d_1^2/\varepsilon+\min\{(τ-1)d_1^2,(τ-1)^2d_1^2d_2^2\}/\varepsilon^2)$ for Choi trace norm error $\varepsilon$. Our results reveal two qualitatively different forms of the Heisenberg-to-classical transition. For diamond norm tomography, the Heisenberg scaling disappears suddenly as soon as $τ$ leaves the boundary regime. In contrast, Choi trace norm tomography exhibits a gradual transition from Heisenberg to classical scaling as $τ$ moves from the boundary regime to the away-from-boundary regime.

quant-ph · cs.IT

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.03599

Should We Combine Our Data? Algorithms and Limits for Privately Assessing Data Sharing

Mahdi Haghifam, Kumar Kshitij Patel, Avrim Blum, Giulia Fanti, Juba Ziani

原文摘要

In this paper, we study when two parties should pool their data to train a machine learning model. Two agents, Alice and Bob, each hold a sensitive labeled dataset and want to train a classifier from a given hypothesis class $\mathcal{H}$. Even when each party's dataset can be perfectly classified on its own, the two parties may follow conflicting labeling standards or have selection biases that affect their features and label sets, such that no single classifier in $\mathcal{H}$ fits their combined data. Before committing to data sharing, Alice and Bob therefore want to test whether a single classifier in $\mathcal{H}$ can jointly fit both datasets---without revealing their individual data points to one another. We formalize this problem from a learning-theoretic viewpoint via $\operatorname{opt}_\mathcal{H}$, the minimum \emph{number of mistakes} made by any hypothesis in $\mathcal{H}$ on their pooled data. Through interactive communication, the agents must distinguish $\operatorname{opt}_\mathcal{H}=0$ (compatible datasets) from $\operatorname{opt}_\mathcal{H}\geq t$ (conflicting datasets) under pure $\varepsilon$-two-party differential privacy. A trusted curator could do this with $t=O(1/\varepsilon)$, and we ask how small $t$ can be without one. For thresholds on the real line over a domain of size $m$, we show that the optimal $t$ is $\tildeΘ(\log\log m/\varepsilon)$, exponentially smaller than the $Θ(\log m/\varepsilon)$ samples needed to privately learn thresholds, even with a curator. For halfspaces in $\mathbb{R}^d$, the dependence on $m$ jumps to $\log(m)$: we give a protocol with $t=\tilde{O}(d^3\log m/\varepsilon)$ and show that some domains require $t=Ω(d\log(m/d)/\varepsilon)$.

cs.LG · cs.DS · cs.IT

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.03578

Uniform Sampling of Linear Codes with Prescribed Hull Dimension

Keita Ishizuka

原文摘要

We give exactly uniform samplers for linear codes with prescribed hull dimension, for the Euclidean, Hermitian, and symplectic inner products and over finite fields of every characteristic. Except for the Euclidean form over fields of odd characteristic, these are the first uniform samplers for arbitrary prescribed hull dimension. Each sample costs an expected $O(k^2 N + k \log q)$ field operations for codes of dimension $k$ in a space of dimension $N$ over $\mathbb{F}_q$ or $\mathbb{F}_{q^2}$.

cs.IT · math.CO

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.03558

Quantum Private Information Retrieval on Forests

Mohamed Nomeir, Sennur Ulukus

原文摘要

We consider the problem of graph private information retrieval (PIR) in the quantum setting. We focus on a specific type of graphs, namely the forest graphs. A forest graph is a union of disjoint trees. We consider the quantum setting where all the servers share an entangled state. Each server is allowed to send only one qudit per retrieval round. We design a scheme for the forest graphs that achieves the rate of $\frac{3}{N}$. The scheme uses a GHZ state as the initial entangled state between the servers prior to the scheme initiation. We compare our scheme with the only work done in the literature that considered the quantum setting of graph PIR. We show that our scheme is more efficient in this setting. We derive the quantum capacity for the case of $G=3K_2$, which is equal to $4/6$. $G=3K_2$ is a special case of the forest graph. We design a scheme that is specialized for this graph, achieving a rate equal to $4/6$ and provide the corresponding matching upper bound, establishing it as the capacity.

cs.IT · cs.CR · cs.NI · eess.SP · quant-ph

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.03545

An information-geometric formulation of distributed computation

Alberto Liardi, George Blackburne, Pedro A. M. Mediano

原文摘要

Understanding how complex systems perform computations, i.e. how they store, transmit, and transform information across their components, is a major goal across the natural sciences. However, characterising genuinely collective computations across multiple inputs and outputs that cannot be reduced to contributions from individual components remains an open problem. In this work, we introduce $Φ\text{ID}^{IG}$, a geometric theory of information dynamics that captures irreducible collective phenomena and enables a complete decomposition of multi-input multi-output operations into interpretable computational modes, providing a complete informational profile of a system. We first validate our framework to identify and quantify distinct computational modes in discrete and Gaussian systems with known ground truth. We then apply it to uncover the computational architecture of complex systems across synthetic and real-world scenarios, including chaotic maps, where distinct universality classes are associated with characteristic modes of computation; brain anatomy of over 100 mammalian species, revealing an evolutionary shift towards more distributed computation in the human neocortex; and financial markets, where collective computations recover the modular organisation of market sectors. Overall, our results show how complex systems can be quantitatively investigated through multidimensional computational portraits derived from the geometry of their underlying probability distributions.

cs.IT

查看论文
arXiv ↗PDF ↗
版本更新 · v7arXiv:2601.14252

Semantic Completeness for Correct Maintenance: A Strict Hierarchy of Typing and Inheritance

Tristan Simas

原文摘要

Removing nominal types or inheritance is defended as reducing burden; cited Java and Go rationales measure no comparison. Correct maintenance minimizes outside answers and repair obligations, preserving required answers and excluding invalid states. Answers identify meanings, memberships, and required implementations. Five capacities form a strict chain. With nominal identities fixed, only multiple contract and implementation parents attain the answer-and-repair optimum on every finite declared history. Incomplete mechanisms force slop: answers restated in code or tooling. In 20 pinned multiple-inheritance Python projects, recovered implementation-class pairs grouped by source class would need outside supply: 12,880 without inheritance, 8,792 under first parents, 739 under sound one-parent optima (checked), zero with multiple parents. With provider and state carriers fixed, state-bearing rows alone force 236 outside pairs. Java and C# interface defaults supply no instance state. At least 24 of 65 size-qualified wheels among the top 150 pure-Python downloads have positive recovered gap (36.9%, 34 unscored). For distinct, independently changing implementations, the ancestry gap is the exact outside-pair minimum with one parent supplying only required pairs, even with reparenting, infinite helpers, delegation, or generators. Zero gap and one-parent contract coverage hold iff class sets nest or are disjoint. Identical records with distinct answers need the confusability graph's chromatic number of keys. Every tree-shaped growth step inserting an off-path provider strictly between ancestors forces one-parent repair. Every snapshot in our constructed history has gap zero, yet repair obligations recur each step; multiple parents add one edge per step. At fixed design costs, bans never lower optima; savings imply suboptimal unrestricted choices.

cs.IT · cs.PL

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.03484

On the Failure Probability of Quantum Leftover Hashing with Bad Seeds

Asker Friis Bach, Isabel Moreno Babuglia, Jonatan Bohr Brask

原文摘要

We study hashing against quantum adversaries, as used in cryptographic applications, and provide bounds on the probability of failure in practical settings where seeds might be reused and might be non-ideal. Randomness extraction and privacy amplification are key components of quantum cryptographic protocols, such as quantum randomness generation or key distribution, that allow the compression of partially secure raw data into shorter output with high security. To ensure the security of any cryptographic construction that integrates them, it is desirable to establish composable security. This can be done by using methods based on universal hashing and leveraging the general leftover hash lemma, which allows extraction of near-uniform random numbers from an imperfect entropy source by sampling from an almost two-universal family of hash functions using a seed. This approach is taken in many practical implementations, commonly using Toeplitz hashing. The lemma provides an upper bound $\varepsilon$ on the distance of the output to uniform randomness, which holds on average over the choice of seeds. It makes no claim that any particular seed yields near-uniform random numbers. This poses a problem for practical applications where a seed is sampled once and reused for many rounds (blockwise hashing). Here, we study the subset of \textit{bad} seeds yielding far-from-uniform outputs. We show that randomness extraction against quantum side information is guaranteed to produce $δ$-close-to-uniform random numbers except with failure probability $\left(\frac{\varepsilon}δ\right)^2$. This result is generalised to blockwise hashing providing a guarantee of the security of $k$ rounds except with failure probability $\big(\frac{(2k-1)\varepsilon}δ\big)^2$. Moreover, we extend the general leftover hash lemma to blockwise hashing and relax the assumption of almost two-universality.

quant-ph · cs.IT

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.03440

Beyond GNSS: Leveraging LEO Satellite Signals of Opportunity for Doppler Positioning

Md. Ali Hasan, M. Humayun Kabir, Sangmin Han, Wonjae Shin, H. Vincent Poor

原文摘要

Large constellations of low Earth orbit (LEO) satellites provide ubiquitous global connectivity; yet, their rapid motion introduces significant Doppler shift effects. While challenging for communication, these effects can be leveraged for precise user terminal (UT) positioning, particularly in GNSS-denied environments where traditional satellite-based navigation struggles. Unlike GNSS, most LEO satellites lack dedicated navigation signals, motivating signals-of-opportunity (SOPs) approaches that repurpose existing LEO signals and use publicly available two-line element (TLE) files for orbital information, although ephemeris errors can limit accuracy. This article explores the fundamental principles, challenges, and enabling technologies for LEO-based Doppler shift positioning, highlighting its advantages over conventional non-Doppler methods, and discussing future research directions. Furthermore, to facilitate realistic and reproducible performance evaluation beyond stochastic modeling, we propose SionnaNTN-RT, a ray tracing framework for non-terrestrial network (NTN) built upon Sionna, enabling end-to-end simulation of Doppler-based positioning. Simulation results demonstrate that Doppler-based positioning can achieve high positioning accuracy in both urban and open-sky environments, highlighting its promise for next-generation positioning systems.

cs.IT · eess.SY

查看论文
arXiv ↗PDF ↗
版本更新 · v2arXiv:2610.12358

Subspace Uncertainty and Sharp Sampling Thresholds on the Boolean Cube

Thomas Weinberger

原文摘要

For a known finite-dimensional model subspace, classical Gaussian regression theory guarantees that least squares eventually attains the parametric rate, with prediction error scaling as the subspace dimension divided by the sample size. Yet subspaces with the same number of unknown coefficients can require very different sample sizes to reach this regime. For subspaces of polynomials on the Boolean cube, a fundamental question is how restrictions on degree and ambient dimension jointly determine this threshold. Our main result sharply characterizes the worst-subspace minimax sample threshold over a substantial parameter range, revealing an exponential dependence on degree and precisely quantifying the joint effects of degree, ambient dimension, and subspace dimension. A small modification of our lower-bound construction reveals a strong separation: a single subspace can admit noiseless recovery with optimal sample complexity independent of degree, yet require essentially the worst-case sample size, exponential in degree, to attain the noisy parametric rate. To establish the sampling lower bound, we sharpen the Polyanskiy-Samorodnitsky uncertainty principle (J. Funct. Anal., '19) to uniformly optimal precision and extend its concentration guarantee to large subspaces in which every function concentrates most of its energy on one shared Hamming ball. The sampling upper bound follows from the sharp moment bound of Kirshner and Samorodnitsky (IEEE Trans. Inf. Theory, '21) combined with empirical-process bounds.

math.PR · cs.IT · cs.LG · math.CO

查看论文
arXiv ↗PDF ↗