Classical communication over quantum channels: does entanglement help in nature?
Peixue Wu
AI 速览：作者提出Schur加权块熵不等式，证明所有相位协变信道（含多能级振幅阻尼、广义退相位、阻尼-退相位信道）在经典通信中不存在纠缠优势。
Can entangling codewords across independent uses of a quantum channel improve the rate of classical communication? An old conjecture states that there is no such entanglement advantage for all channels. Although Hastings's result and follow-up works disproved this conjecture, it turns out that enormous dimension is required to construct a channel where entanglement enhances classical communication. This indicates that there might be no entanglement advantage for many physical channels, or for all low dimensional channels. Motivated by recent progress on (generalized) amplitude damping channels, we propose a general Schur-weighted block entropy inequality, and show that there is no entanglement advantage for all phase-covariant channels including multi-level amplitude damping channels, generalized dephasing channels, and damping-dephasing channels. As a by-product, we also recover the recently established result that there is no entanglement advantage for all qubit channels.
Advanced power adjusting block withholding attacks such as PAW and T-PAW have been analyzed so far under a global-reset version of the proportional scheme (GRP), which is rarely used in practice. In this paper, we analyze T-PAW, which contains FAW and PAW as special cases, under the block-dependent payout schemes deployed in practice: Pay-Per-Last-N-Shares (PPLNS), round-based Proportional (PROP) and exponential-decay (EXP). We derive the revenue ratios analytically, by renewal arguments for PPLNS and through the stationary carry process of an open round for PROP and EXP. We further introduce Power Adjusting Hopping (PAH), where an adversary of any size adjusts its power allocation towards the pool according to the blockwork age of the round without withholding any block, and derive its revenue ratios under PROP and EXP. We show that GRP misestimates the T-PAW gain in a scheme-dependent direction: it overstates the gain under PROP up to an order of magnitude and understates it under EXP for the original slush decay rate. PROP is highly vulnerable to PAH, while EXP faces a trade-off: a slow decay invites PAH and a fast decay invites T-PAW. PPLNS is the least vulnerable scheme: it is immune to PAH and it mitigates, but does not eliminate, T-PAW. All analytical results are verified by Monte Carlo simulations.
On the Fundamental Limits of Prefill-Based Decoding Length Prediction
Haowen Shi, Xuzhe Yan, Fahao Chen, Peng Li
AI 速览：作者指出基于预填充阶段隐状态预测LLM解码长度的精度受自回归解码固有随机性限制，并给出理论界与基准评测建议。
Predicting how many tokens a large language model (LLM) will decode, using only prefill-phase hidden states, is a key primitive for inference scheduling. We show that current benchmarks conflate predictor quality with task hardness: when the target model, dataset, or sampling configuration changes, reported accuracy collapses even though the predictor is unchanged. We trace this instability to an overlooked error source---the inherent stochasticity of autoregressive decoding---and derive bounds that every prefill-side method must obey. Our analysis treats decoding as a stopped stochastic process. The per-step stopping probability of a response is not constant but ramps up over hundreds of steps, so the decode length inherits a central limit theorem from the many local decisions that determine where a response ends; this yields per-prompt normality with an explicit error term, together with an affine variance law $σ=αμ+b$ whose slope is the coefficient of variation of the number of response segments. Empirically, the normal law reproduces the per-prompt MAE and the central mass of the decode-length distribution to within a few percent, and the residual departures from normality (mild right skew, slight excess kurtosis) are the ones predicted by the sampling-noise correction. Under fixed model, data, and sampling conditions, a broad design space of predictors (MLP, EGTP, FiLM, soft-label, and Mixture-of-Experts variants) converges to similar performance close to the bound, confirming that \emph{system error dominates model error}. We argue for a benchmarking protocol that fixes the model, data, and sampling parameters and that reports relative-error metrics alongside absolute ones. Code and analysis tools are available at https://github.com/ShwStone/DecodingPredict.
AI 速览：作者提出面向SCL译码的PAC码速率剖面设计方法，借助条件DEGA与危险路径占用度量构造信息集和稀疏预编码器。
We develop design methodologies for the rate profile of polarization-adjusted convolutional (PAC) codes tailored to successive cancellation list (SCL) decoding. The crux of our approach is two-fold: first is the creation of a modified density evolution Gaussian approximation (DEGA), called conditional DEGA (CDEGA), to analyze the decoding process in the presence of errors; second is the creation of a dangerous-path occupancy metric to find the conditional occupancy of bit-errors in a finite list. Our approach not only illuminates the role of rate-one precoding, but also provides insight into why certain information sets are particularly well suited to PAC codes. We demonstrate the usefulness of CDEGA and dangerous-path metrics with algorithms that create new information sets, as well as precoders that are extremely sparse yet competitive. In particular, we design codes of length $N \leq 512$ with various rates and list sizes, all of which offer at least half a dB gain over traditional PAC codes at an FER of $10^{-3}$ and improve upon state-of-the-art results.
Fast and accurate neural triage decoding of ultra-high-rate quantum LDPC codes
Hong-Ye Hu, Zhenlai Wang, Binzhao Luo, Tao Xiang, Chen Zhao
AI 速览：提出神经分诊解码框架，用综合征一致性自适应分配神经计算，在高码率qLDPC码上兼顾近最优精度与大幅降低的解码延迟。
Quantum error correction is essential for fault-tolerant quantum computing. High-rate quantum low-density parity-check (qLDPC) codes have emerged as a promising approach to reducing the substantial physical qubit overhead of quantum error correction, enabling encoding rates exceeding $1/2$ in blocks of approximately one thousand physical data qubits. However, their practical implementation requires decoders that combine high accuracy with low latency to keep pace with quantum hardware. Existing decoders of high-rate qLDPC codes can achieve high accuracy but often incur substantial computational latency, whereas neural network decoders have yet to be demonstrated for high-rate qLDPC codes. Here, we introduce \emph{neural triage decoding}, a framework that uses syndrome consistency to adaptively allocate neural computation. A local neural message-passing network rapidly predicts error corrections, additional iterations reduce residual syndrome violations, and a rarely invoked diversification stage searches for consistent corrections to the remaining shots. We demonstrate that the \texttt{Triage} decoder can decode ultra-high-rate qLDPC codes encoding a few hundred logical qubits, including lifted-product and Kasai codes, achieving state-of-the-art accuracy comparable to the near optimal algorithmic decoders while reducing decoding latency by approximately one to two orders of magnitude. Our framework is inspired by a rigorous analysis of the exact bitwise marginal decoder, revealing a distance-independent syndrome-inconsistent error floor. In addition, we show the robustness of neural network decoders to mismatched error priors. Our results establish adaptive neural decoding as a promising route towards fast, accurate, and scalable quantum error correction in the near term.
Average pairwise Hamming distance of a subset in a hypercube
Yijia Fang, Hao Huang
AI 速览：作者证明密度为1/8的{0,1}^n子集的平均成对汉明距离至少为(n-3)/2，且等号仅由(n-3)维子立方体达到。
In this note, we prove that for a subset $\mathcal{F}$ of $\{0,1\}^n$ of density $\frac{1}{8}$, its average pairwise Hamming distance is at least $\frac{n-3}{2}$, with equality attained only by $(n-3)$-dimensional subcubes. This answers a question of Lei Yu, and solves an important open case of a more general question posed by Ahlswede and Katona in 1977.
AI 速览：作者提出用状态判别方法研究无辅助噪声量子信道通信，并基于Petz恢复映射构造纠缠生成码与误差界。
We develop a state discrimination approach to unassisted quantum communication through a noisy quantum channel. Starting from the operational duality between entanglement recovery and state discrimination, we construct entanglement-generation codes with explicit decoders constructed from Petz recovery maps. The resulting error bounds hold for every number of channel uses and are expressed in terms of Petz-Rényi coherent information. For product sources, they yield exponential error decay at rates below coherent information.
A Unified Complexity Framework for Quantum Property Testing
Qisheng Wang
AI 速览：作者提出一个基于函数型 tr(φ(dρ))/d 的统一框架，用于推导量子性质检验的样本与查询复杂度下界，并给出熵估计与谱估计的（近）紧复杂度。
We develop a unified framework for analyzing the complexity of quantum property testing through functionals of the form $\mathcal{L}_φ(ρ) = \operatorname{tr}(φ(dρ))/d$, where $ρ$ is an unknown $d$-dimensional quantum state and $φ$ is a given function. A master theorem is established that derives sample complexity lower bounds for estimating $\mathcal{L}_φ(ρ)$ from properties of $φ$, combining Haar-random moment encoding with moment matching and best polynomial approximation. Corresponding query complexity lower bounds follow from quantum sample-to-query lifting. The framework yields (nearly) tight bounds for a broad class of problems, including entropy estimation (von Neumann, Rényi, and Tsallis), closeness estimation (trace distance and Uhlmann fidelity), spectrum estimation, rank testing (operator rank, Schmidt rank, and matrix product states). In particular, combined with known upper bounds, we show that the sample complexity of von Neumann entropy estimation is \[ Θ\!\left(\frac{d^2}{\varepsilon\log^2(d)\max\{1, \varepsilon\log^2(d)\}} + \frac{\log^2(d)}{\varepsilon^2}\right), \] and the sample complexity of spectrum estimation is \[ Θ\!\left(\frac{d^2}{\varepsilon^2\log^2(d)\max\{1, \varepsilon^2\log^2(d)\}}\right). \] In summary, our results resolve several open problems and establish the optimality of 37 quantum algorithms since 2015, up to constant or polylogarithmic factors.
Danial Dehghani, Maximilian Lübke, Zahra Seifaei, Norman Franchi
This paper investigates the value of communica- tion (VoC) in cooperative multi-agent tracking under rate- constrained information exchange. Although prior work has studied distributed tracking, quantized communication, and robust fusion, it remains unclear at what communication rate most of the achievable tracking gain is obtained, beyond which additional communication resources yield only marginal benefit. We consider stationary agents that observe a moving target through heterogeneous range and bearing measurements, perform local extended Kalman filtering (EKF), quantize their posterior state means, and fuse exchanged information via covariance intersection (CI). Performance is evaluated versus communication rate relative to no-communication baselines, a centralized oracle, and a CI-perfect reference. The results show that communication is not uniformly beneficial: very low rates can degrade performance due to coarse quantization, whereas moderate rates recover most of the achievable gain. In the considered scenario, increasing the rate from 4 to 12 bit/s per agent reduces the root-mean-square error (RMSE) from 13.93 m to 6.35 m, while a further increase to 32 bit/s per agent improves it only marginally to 5.93 m. This reveals a clear knee region at moderate rates, beyond which the remaining loss is mainly due to the conservatism of the fusion architecture. Overall, the proposed framework characterizes low-rate degradation, communication-efficient operation, and diminishing returns, while highlighting the joint role of rate and sensing geometry in determining communication benefit.
We develop a unified framework for the instantaneous total level crossing rate (LCR) of products of independent positive nonstationary fading processes. Universal upper and lower bounds are first derived from an exact decomposition of the product derivative and signed crossing imbalance, requiring only factor-wise crossing statistics. We then introduce the drifting Gaussian-derivative (DGD) class, in which each conditional derivative is Gaussian with possibly nonzero drift. For products of DGD factors, an exact Gaussian-mixture representation yields bounds that jointly capture aggregate drift and derivative fluctuations. The lower bound reduces under stationarity to a known $\ell_2$ bound, whereas, to the best of the author's knowledge, the upper bound is new even in the stationary case. Furthermore, the bounds are asymptotically exact in drift-dominated regimes. The framework is specialized to nonstationary Double-Rayleigh fading and to quasi-identically distributed DGD factors, with closed forms for products of $α$-$μ$ envelopes. Numerical results show that the DGD bounds closely bracket the exact LCR.
We complete the determination of the minimum possible length of eight-dimensional binary self-orthogonal codes with given minimum distance. For dimension nine we give exact values and bounds for minimum distance at most $64$. By exploiting the geometric reformulation of linear codes as multisets of points, we fully redo the classification for dimension at most seven in a simplified and computer-free manner. As a by-product we prove the non-existence of $[93,9,44]_2$ codes and show several divisibility results for putative optimal nine-dimensional binary codes.
The Sinkhorn divergence, the debiased entropic optimal transport cost, determines a metric tensor on probability measures defined along curves, due to Lavenant et al. We construct a real-analytic Hilbert manifold of measures, the smooth stratum, on which this tensor is a weak Riemannian metric, and we continue Eguchi's construction of a geometry from a divergence to the third order. The stratum consists of the measures with a positive Sobolev density on a closed Riemannian manifold, and the strata form a scale whose intersection is the Fréchet manifold of smooth positive densities of Ay. Following it, we characterize the metric through the gradients of mean values: its cotangent form is a spectral reweighting of the Dirichlet form of a Markov chain, so the metric is of the same kind as the Fisher-Rao and the Otto metric, and on the stratum it is bounded by a multiple of the Fisher-Rao metric (but not conversely). At third order, the Sinkhorn divergence is self-dual: both connection forms of Eguchi's construction coincide with the Levi-Civita form of the metric, and the cubic tensor vanishes, as a consequence of the transposition symmetry of the transport problem. On every stratum, the Levi-Civita form is represented, so the stratum has a real-analytic Levi-Civita connection, which on the Fréchet manifold is the connection of Ay and Schwachhöfer.
Oumaïma Bounhar, Thomas Chêne, Ghaya Rekaya-Ben Othman, Oussama Damen
Reconfigurable Intelligent Surfaces (RIS) are a promising solution for improving millimeter-wave (mmWave) communications by controlling signal propagation. Yet, selecting the optimal RIS configuration remains challenging due to the high-dimensional search space and signaling overhead. We propose a Deep Reinforcement Learning (DRL) framework for blind passive beamforming, where a Deep Q-Learning (DQL) agent learns an adaptive policy to select near-optimal RIS configurations while sounding only few codewords, without channel state information. Results show that our approach outperforms Q-Learning (QL) and conventional baselines in convergence, performance, and overhead reduction.
Wen Fang, Xianxian Li, Jun Liu, Jie Luo, Yongxin Tong, Ke Xu
We study self-reference and solution independence in Boolean $K$-SAT as a finite analogue of Gödel incompleteness. Independence is defined through factorial moments of the solution count. Constant-width random formulas fail this criterion due to correlations among overlapping assignments. At a covering threshold, logarithmic-width random CNFs have a Poisson solution count, with positive probabilities of unsatisfiability and unique satisfiability. Replacing a redundant clause by one falsified by the unique solution yields an unsatisfiable companion preserving the unsigned incidence graph. For every permitted local view of a good uniquely satisfiable formula, an unsatisfiable companion preserves that view. Irreducibility defeats deterministic and bounded-error evaluators using $N^c$ clause queries, for fixed $0<c<1$. It establishes a local information obstruction, not an unrestricted time lower bound. For fixed $δ>0$, transcripts of $N^{1-δ}$ queries leave $N-o(N)$ bits of witness entropy. On typical support graphs, expansion yields linear Resolution width, linear PC/PCR and SOS degree, and exponential proof size. Bounds hold for semantic Cutting Planes under a partition condition and for Positivstellensatz with bounded product width, uniformly over unsatisfiable support-preserving signings. Structural evidence and the limits of acceleration strategies motivate the self-referential $K$-SAT exhaustive-search hypothesis (SRK-ESH): no uniform deterministic algorithm deciding the promise family achieves a fixed proportional saving in the exponent. This dual-evidence criterion combines intrinsic hardness mechanisms with algorithmic evidence. We interpret this hypothesis as a quantitative projection of the Gödel-style local--global gap. The information obstruction constrains quantum local observation and statistical learning from bounded local information.
Byrne, Gluesing-Luerssen, and Ravagnani determined the number of codewords with a prescribed nonzero support in a linear maximum sum-rank distance code whose blocks have a common number of columns. Their formula depends only on the code parameters and the support dimensions. Evaluating it for arbitrary parameters gives a family of necessary nonnegativity conditions for existence. We prove their conjecture that this family is equivalent to the condition at the vector of total dimension $d+1$ obtained by filling the longest blocks first, where $d$ is the distance parameter. The resulting explicit criterion applies over every finite field $\mathbb F_q$, for all row numbers $n_i\leqslant m$ and $1\leqslant d<N$, where $m$ is the common number of columns and $N$ is the total number of rows. It also covers the boundary cases in which this vector fills each of its nonzero blocks completely, not explicitly included in the conjecture's displayed parameter range. The proof uses a generating function and an exchange identity to reduce the problem to vectors obtained by filling the longest blocks first. We then estimate alternating sums of elementary symmetric polynomials, with a separate argument for $q=2$. The dual conditions admit the same reduction. For codes that exist, the joint condition follows from sphere-packing bounds for the code and its dual. An infinite family of parameters satisfies the joint condition but admits no such linear code.
Alessio Baldelli, Davide Orsucci, Francisco Lázaro, Massimo Battaglioni
Stabilizer codes are often constructed within the Calderbank--Shor--Steane (CSS) framework, where two mutually orthogonal binary classical codes define $X$ and $Z$-type stabilizer generators. While this structure is algebraically convenient, additional non-CSS constraints may help suppress low-weight logical operators and improve decoding performance in the finite-length regime. We thus introduce quantum XYZ stabilizer codes, whose parity-check matrix (PCM) is built from three pairwise orthogonal binary PCMs associated with $X$-, $Y$-, and $Z$-type stabilizer generators. A nontrivial point is that an XYZ code instance is not automatically genuinely non-CSS: the same stabilizer group may admit a CSS generating set. We characterize this collapse, obtaining algebraic and rank conditions for deciding when the $Y$-type checks are redundant and when they define genuinely non-CSS stabilizer constraints. We also derive upper and lower bounds on the quantum minimum distance, including bounds for mixed Pauli logical operators. The novel framework includes a known non-CSS topological code, namely the XYZ$^2$ hexagonal code, and yields also sparse finite-length quantum low-density parity-check (qLDPC) constructions from intersecting-subset and quasi-dyadic code families. Simulations under depolarizing code-capacity noise and quaternary belief propagation decoding show that the proposed XYZ qLDPC instances can outperform representative CSS qLDPC instances with similar finite-length parameters.
This paper investigates an uplink rate-splitting multiple access (RSMA) network empowered by a Rydberg atomic quantum receiver (RAQR) to maximize energy efficiency (EE). To overcome the amplitude-only measurement limitation of the considered direct readout RAQR, we devise a phase alignment mechanism that linearizes the received signal while retaining full channel energy, thereby enabling tractable optimization. The resulting non-convex fractional EE problem is transformed via Dinkelbach's method. For IoT scenarios with symmetric rate requirements, we derive exact closed-form power allocation from the Karush-Kuhn-Tucker (KKT) conditions, which yields a globally optimal bisection search with negligible computational latency. For asymmetric rate requirements, we develop a generalized block coordinate descent-based power allocation (BCD-PA) framework that eliminates reliance on expensive interior-point solvers. We further propose a low-complexity paired allocation (LC-Paired) that exploits user pairing and closed-form bandwidth solutions via the Lambert-W function. Simulation results confirm that the KKT-based scheme attains the highest EE, while the BCD-PA offers a flexible complexity-performance trade-off. The LC-Paired scheme drastically reduces computational cost with only moderate EE degradation.
A decoding method is proposed for polar codes under channels with strong phase noise. In contrast to traditional SC decoding, where recursions are performed on scalar soft information such as probabilities, the proposed decoding recurses over probability density functions defined on the phase-noise variable. To make the density-level recursion computationally tractable, we represent each log-density by its spectrum, and derive approximate formulas for the spectrum recursion, therefore, the proposed method is termed log-density spectrum recursion (LDSR). Numerical results are given under strong phase noise and AWGN, showing that a prominent superiority of error performance is achieved by LDSR in comparison with traditional SC and Kalman-based methods.
We study the length of maximum distance separable algebraic geometry codes from curves of arbitrary positive genus. For fixed genus, we prove that the asymptotic ratio of the length to the field size is at most $1/2$ when both the dimension and the codimension grow faster than the logarithm of the field size. We also give explicit bounds under logarithmic dimension conditions. The bounds hold in every characteristic and are uniform in the curve and the evaluation set. The proof combines character sums on the Jacobian with an estimate for sums of distinct points.
Coded distributed computing (CDC) mitigates the Shuffle communication bottleneck through coded multicast, but existing schemes with predetermined worker populations do not directly adapt to worker arrivals and disconnections. To address these dynamics, we propose a dynamic CDC scheme that preserves surviving workers' caches and Reduce assignments while exploiting the storage brought by arriving clusters. The model accommodates general MapReduce tasks under a placement that is partly fixed and partly new. The scheme uses Cartesian products of cluster-wise placement delivery arrays (PDAs) for file placement. A delivery-aware greedy algorithm reassigns abandoned Reduce functions, and a Communication Array allows workers with no Reduce function to serve as coded transmitters. For arbitrary feasible disconnections, the scheme's exact communication load is derived. A converse bound under one-shot communication shows that, in the absence of disconnections, the scheme lies within a factor of 2 of the lower bound under these assumptions when new clusters arrive, and within a factor of 4 otherwise.
Does there exist an 8-variable balanced Boolean function with nonlinearity 118? This is a famous and long-standing open problem in Boolean functions. In this paper, we give a negative answer to this open problem, and prove that the maximum nonlinearity of balanced Boolean functions in 8 variables is 116, establishing the 8-variable instance of Dobbertin's conjectured recursion for the minimum Walsh peak of balanced functions. Equivalently, the covering radius of the Reed--Muller code RM(1,8) in 0-resilient Boolean functions is 116. We deduce the result by obtaining a quadratic form of polar rank 6, and reducing the problem to the existence of a 6-variable Boolean function with nonlinearity greater than 26 whose Hamming distance to a bent function is between 4 and 6.
We study the maximal length of MDS algebraic geometry codes from genus-two curves over finite fields. Let $C_\mathcal{ L}(D,G)$ be such a code over $\mathbb F_q$, with length $n$ and dimension $k$. Assume that $3\leq k\leq n-3$. We prove that $n<(2q+10\sqrt q+16)/3$. This bound holds for every prime power $q$ and for both parities of $k$. It gives a uniform upper bound of $2q/3+O(\sqrt q)$ for the maximal length. The explicit bound is strictly smaller than $q+1$ when $q\geq125$.
Consider two terminals that observe correlated uniform binary vectors and separately compress their observations to one bit. We prove that, for every blocklength and every correlation parameter in $(-1,1)$, the Fisher information retained by the resulting pair of bits is maximized by matching parity functions of an appropriate degree, thereby resolving a conjecture of Amari and Kobayashi. The proof combines a Fourier-based bound on the derivative of the normalized covariance with a scalar inequality for signed polynomials subject to a global range constraint.
By exploiting the spatial selectivity of wireless channels, physical layer security (PLS) protects confidential wireless transmissions. Flexible reflectors (FRs), which are passive metallic plates mounted on movable platforms, offer a low-cost and low-complexity solution for reshaping the propagation environment. However, their potential for secrecy-oriented signal propagation shaping has not been explored. In this paper, we study an FR-aided secure communication over non-line-of-sight links and jointly optimize the positions and rotations of FRs to maximize the secrecy rate under geometric reflection and mutual-blocking constraints. For the single-FR case, we propose a Fibonacci segmentation search (FSS) method, which partitions the feasible region into multiple unimodal intervals and obtains the optimal solution with Fibonacci search over the unimodal intervals. To reduce the computational overhead, we also propose a low-complexity cross-entropy search (CES) method, which employs Gaussian mixture model-based adaptive importance sampling to localize promising search intervals before deterministic refinement. After deriving the blocked placement interval induced by the deployed FRs and integrating it into a sequential deployment scheme, we extend the FSS and CES methods to the multi-FR case. Simulation results show that our proposed FSS method achieves significant secrecy rate performance gains over various benchmark schemes, and our proposed CES method achieves a favorable runtime-performance tradeoff. These results indicate that FRs provide a low-cost and reconfigurable mechanism for PLS.
Proximity gaps and correlated agreement underpin the soundness of interactive oracle proofs. We establish these properties for general one-point algebraic geometry (AG) codes, extending corresponding results for Reed-Solomon codes. For codes of length $n$ over $\mathbb F_q$ with designed distance $n-m$, write $ρ=m/n$ and fix $ρ\in(0,1)$. For polynomial curves of degree at most $\ell$ and any $0<\varepsilon<1$, we prove correlated agreement with multiplicative slack $\varepsilon$ and soundness $O(\ell(\ell+1)/(\varepsilon q))$ whenever $e\le(1-\varepsilon)(n-m)/2$, with no additional genus penalty. This gives asymptotically good AG code families from Garcia--Stichtenoth tower of unbounded length over a fixed field with soundness bounds independent of $n$, beyond the RS restriction $n\le q$. We also establish mutual correlated agreement up to radius $(1-\sqrtρ-η)n$, with soundness $O(\ell n/(η^3q))$ for $0<η<1-\sqrtρ$. Our half designed distance proof combines auxiliary divisors, simultaneous Berlekamp-Welch interpolation, and error-incidence counting to obtain a common polynomial representation without a Polishchuk-Spielman divisibility lemma. Finally, two counterexamples on the Garcia-Stichtenoth tower show limitations beyond half the minimum distance, at radii below the Johnson bound and with positive slack. The first requires a positive constant soundness lower bound independent of $q$ and $n$, precluding a uniform $O(1/q)$ guarantee throughout the Johnson regime. The second fixes the field and lets the relative gap above half distance tend to zero while ruling out correlated agreement for every soundness parameter $σ<1$, with positive limiting rate and relative error radius.
We study Gibbs averaging of finite Markov chains with a prescribed stationary distribution $π$. Given a transition matrix $P$ and the Gibbs kernel $G$ induced by a state-space partition, we prove that $GPG$ is an information projection for every admissible Bregman generator $φ$, with divergences defined using transition probabilities relative to $π$. A Pythagorean identity characterizes this projection and recovers the relative entropy and weighted Frobenius cases. A dual characterization identifies $GPG$ as a kernel closest to stationarity among those with the same projection chain as $P$; for relative entropy, it maximizes the entropy rate. The identities also give monotonicity under partition coarsening. For every reversible ergodic baseline $P$, Gibbs averaging cannot increase the squared weighted Frobenius distance to stationarity at any positive integer time, and the inequality is strict unless $P=GPG$. The corresponding mixing time therefore cannot increase. To choose the partition, we identify the divergence of $G$ from stationarity as the exact worst-case divergence of $GPG$ over all $π$-stationary baselines $P$. This objective depends only on the block masses. We give an exact algorithm for concave block costs, including those arising from relative entropy and power generators $φ(u)=u^p$ with $1<p<2$, and a greedy approximation algorithm with a provable guarantee for $p>2$. For power generators $φ(u)=u^p$ with $p>1$, the objective is proportional to Tsallis entropy of order $2-p$: its minimization favors imbalanced block masses when $1<p<2$ and balanced block masses when $p>2$, while all $k$-block partitions have the same objective value when $p=2$. A numerical experiment compares the resulting projected chains with a local Metropolis sampler on a multi-modal $π$.
Semantic entropy, the entropy of the meanings among a language model's sampled answers, is estimated from the verdicts of a judge that declares pairs of answers equivalent or not, and automatic judges err in ways that depend on the answers they compare. The existing minimax theory covers only judges whose false-equivalence probability is the same for all pairs. We model a known judge that declares two answers with meanings $a$ and $b$ equivalent with probability $q+ΔM_{ab}$, for a symmetric matrix $M$ and $q$ bounded away from $0$ and $1$, and show that for three meanings the rate is set by tree statistics on four answers, while on an open set of channels the consistency threshold is set by trees on five. For every channel in an explicit open class, the minimax squared risk is of order $N^{-1/3}$ with $N=n^4Δ^6$ on polynomial weak windows on which $n^5Δ^8$ exceeds a multiple of $\log n$, and of order $\min\{1,N^{-1/3}\}$ on every polynomial weak window when the tree functions on at most four vertices are injective. The exponent comes from a cubic degeneracy at the equitable point. On an open set of channels in the class, the four-vertex tree functions take equal values at two distributions with different entropies. For such a channel, on every polynomial weak window, the minimax risk is of the order of the sum of $\min\{1,N^{-1/3}\}$ and a term that decays exponentially in $n^5Δ^8$, so no estimator is consistent while $n^5Δ^8$ stays bounded, even as $N\to\infty$. For $Δ=n^{-β}$ with $β>1/2$, channels of the class with injective four-vertex tree functions allow consistent estimation exactly for $β<2/3$, and the channels of this open set exactly for $β<5/8$, at which the risk exponent drops from $1/12$ to $0$. Computer-assisted certificates show that both kinds of channels occur on open sets.
Universal coding of integers (UCI) provides prefix codes for positive integers such that, for every nonincreasing source distribution $P$, the average codeword length under $P$ stays within $K$ times $\max\{1,H(P)\}$. For a given UCI $\mathcal{C}$, the smallest such constant $K$ is called the minimum expansion factor of $\mathcal{C}$, denoted $C_{\mathcal{C}}^{*}$. Let $C^{*}\triangleq \inf \{C_{\mathcal{C}}^{*}\}$ over all UCIs. A UCI attaining $C^{*}$, or a family of UCIs attaining $C^{*}$ in the limit, is called optimal. It is currently known that $2\le C^{*}\le 2.0386$. In this paper, we construct a family of one-point plus uniform-tail distributions and prove that, for every UCI, a distribution in this family attains the worst-case ratio; thus, the family is least favorable for the UCI problem. We further establish an inequality, called the \emph{UCI inequality}, which plays the same role for UCI as the Kraft inequality does for prefix codes: for any real number $B\ge 1$, it decides whether $B$ lies below or above $C^*$. The UCI inequality gives an equivalent definition of $C^*$. By numerical computation, we determine $C^* = 2.00012475703610197861701176297579886254\cdots$, the first $38$ decimal digits being certified. Once $C^*$ is known, we can theoretically construct the optimal UCI.
In this paper, we demonstrate that complex bandlimited signals can be uniquely recovered (up to a global phase factor) from two families of wavelet transform magnitudes, sampled at twice the Nyquist rate in two frequency bins. These families come from translations of the fixed dilated Morlet wavelet and a fixed companion wavelet. The companion wavelet admits an augmented Morlet--Gaussian representation. We rewrite the two families as two modulated Gaussian convolution measurements of an auxiliary bandlimited signal. Using a Gaussian convolution uniqueness result, we prove that samples on \((4B)^{-1}\mathbb{Z}\) determine every signal in \(PW_B^2\) (up to a global phase factor). Compared with earlier wavelet phase retrieval results, our approach requires significantly fewer sampling points.
We study distributed storage over public communication channels where privacy is realized using shared secret keys. Specifically, a user wishes to store a file across $L$ servers such that any subset of at least $t$ servers can reconstruct the file, while any subset of at most $z$ colluding servers learns no more than a fraction $α$ of the file. Unlike classical secret-sharing models that assume secure communication channels between the user and each server, we consider a setting where all transmissions occur over a public channel and the user shares an individual secret key of length $n$ bits with each server. For a fixed key length $n$, we characterize the trade-off between the privacy leakage parameter $α$ and the maximum file size that can be securely stored. Additionally, we determine the minimum local randomness, public communication, and storage required to achieve this optimal trade-off.