Clause substitution creates local blind spot in K-SAT
Indistinguishable SAT/UNSAT pairs force wide clauses in Resolution and push proof size toward 2^N.
· “Self-Referential K-SAT and the Finite Analogue of G\"odel's Incompleteness Theorem”
cs.IT
Information Theory
Covers theoretical and experimental aspects of information theory and coding. Includes material in ACM Subject Class E.4 and intersects with H.1.1.
sort pith recommended most recent
Link failures cap LEO capacity scalability at O(1/n)
Under a Markov model of ISL states, scalability rises to an optimum then falls toward zero as satellite count grows.
· “Capacity Scalability of LEO Constellations With Dynamic Link Failures”
One qubit turns sensors into exponential learners
Coupling one control qubit to a sensor learns a kth Fourier feature in O(k) shots; Gaussian sensors need exponentially many.
· “Exponential quantum advantage for learning signals with a single qubit”
Environment carries data by distinguishable physical states sensed via RF
Multi-snapshot sensing produces a reliability field that turns state distinction into a geometric codebook problem with an optimal finite-
· “Embodied Communication: Sensing-Induced Reliability Fields and Capacity Bounds”
F4-concatenated codes produce optimal binary LRCs
Outer linear codes over four elements yield binary locally repairable codes that meet the Griesmer-like bound and an improved Johnson-like 2
· “Constructions of locally repairable codes via concatenated codes”
Niho functions are locally-APN exactly when Walsh spectrum has four values
The equivalence also fixes the four nonzero weights of the related cyclic codes and determines their differential and boomerang spectra.
· “Walsh Spectrum and Boomerang Properties of Locally-APN Niho Functions”
Dual UAV networks eliminate C2 outages in emergency deliveries
Hovering base stations and moving delivery drones coordinate to maintain reliable links and lower hardware costs after disasters.
No lattice PID stays consistent past two sources
Closed forms fix the two-source case while auxiliary-variable measures avoid contradictions for larger collections.
Cluster decoder gives exact erasure decoding at linear cost
Splitting the residual graph into biconnected clusters turns peeling into maximum-likelihood decoding for quantum LDPC codes.
· “Cluster Decomposition for Improved Erasure Decoding of Quantum LDPC Codes”
Switching off idle radio heads cuts C-RAN power by 20 percent
A joint RRH-association, fronthaul, and power-allocation loop beats max-SINR and saves over 20% power in dense networks.
· “Power-Efficient Resource Allocation in Massive MIMO Aided Cloud RANs”
Tu–Deng conjecture proved for every k and t
Every eligible pair count now obeys the 2^{k−1} bound, settling a cryptographic conjecture from 2011.
Exact common-information formula proven for correlated Gaussians
For any nonzero correlation, exact synthesis costs more than approximate synthesis; the exact gap is now known.
· “Exact Common Information and Exact Channel Synthesis for Correlated Gaussian Sources”
General adversaries make consensus pay an n^{1/d} tax
Projective-geometry adversary families lift the Ω(Ln) baseline to Ω(L n^{1+1/d}) bits for agreement and broadcast.
· “Multivalued Consensus: General Adversaries Require More Communication”
E-detectors exactly capture ARL-safe alarm times
Any alarm rule with average run length at least b is a threshold crossing of an e-detector; strong rules also bound every adaptive horizon.
Amortized communication equals zero-error information cost
Exact limit resolves the global-error direct sum conjecture and corrects set-disjointness scaling.
· “Zero-error information equals amortized communication complexity”
Identification capacity capped by entanglement-assisted rate
Every quantum channel's ID rate is capped by its entanglement-assisted capacity; low-noise channels meet it.
· “The entanglement-assisted transmission capacity is a strong converse bound for identification”
Two gate families generate every Clifford gate a CSS code allows
Phase/CZ circuits and mirrors span the whole code-preserving Clifford group; two-local stacks go full on 78 codes.
· “Beyond transversality: structure of Clifford circuits for CSS codes”
Multi-distribution functionals reduce to integrals of coincidence divergences
Monotonicity under data processing and additivity on independent products force every such functional to an integral over four strata
Any sequence reduces to a poly-time random one in quasi-polynomial time
The reduction uses only n plus little-o-n oracle bits and equates decompression ratios to Kolmogorov complexity rates.
Valuation bound decides QPP-interleaved Zadoff-Chu equivalence
The quadratic coefficient a must meet a prime-dependent valuation threshold at every p^α exactly dividing N.
· “A Local Valuation Criterion for Quadratic-Permutation Interleaved Zadoff--Chu Sequences”
Explicit measure makes entropy fifth derivative positive
This violates the conjectured sign pattern under heat flow and overturns Gaussian optimality and entropy power claims.
· “A Counterexample to the Gaussian Completely Monotone Conjecture”
Uniform convergence at scale γ equals learnability at γ/2
Exact equivalence for bounded real-valued classes closes scale gaps in PAC learning and gives sharp IPM evaluability thresholds
· “Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale”
AI agent designs cell-edge power control at 99.5% of best solver
Unattended, it rewrote architecture, loss and features to hit 600x cheaper inference.
· “Agentic Autoresearch for Cell-Edge Power Control: Radically Redefining the Researcher's Role”
Adaptive clustering lifts wireless delivery by up to 9.8 points
Grouping peers by reliability and coding within and across clusters cuts latency 10-23% and raises retention up to 30%.
Moving codebooks with SNR beat fixed optimal packings by factor n/2
Reoptimizing at each SNR shrinks the error constant from 4n to 8 for n+2 signals.
Readout capacity is the product of all but the smallest budget
A finite spectral readout can identify at most the product of all but one direction's label budgets.
APN ortho-derivative components all have algebraic degree n-2
Every nonzero component of the ortho-derivative has algebraic degree exactly n-2.
BCH code radii: exact at four errors
Four-error radius is exactly 11 for large fields, and every higher order is pinned within a fixed gap.
Discrete diffusion sampling can adapt to data structure
A leave-one-out sampler needs O(DTC/ε) parallel steps, bypassing the dimension-scaling barrier of standard τ-leaping.
· “Provably adaptive sampling with uniform and remasking discrete diffusion models”
Hypercube inequalities for partition charges proven in all dimensions
Both inequality branches were numerical checks before; this proof makes them analytic for every dimension.
Exact rate-exponent curve for distributed binary hypothesis testing
A sandwich of known bounds closes for DSBS and product nulls, giving exact error exponents at every rate.
· “Exact Rate Exponent Tradeoff for New Classes of Distributed Hypothesis Testing Problems”
Finite geometry builds sensing matrices with 1/q^2 coherence
Explicit subspace-count formulas yield computable sizes and deterministic sparse-recovery guarantees.
· “Compressed sensing matrices from orthogonal spaces over finite fields of odd characteristic”
Kalman filter cuts phi-OTDR sensitivity threshold by ~35 dB
Phase stays measurable below -3 dB uncertainty at SNR down to -32 dB, versus 3.5 dB with conventional I/Q demodulation.
Learned transceiver beats NOMA and RSMA for 2 to 8 users
Per-user decoder cost stays linear in user count, not exponential, at finite blocklengths.
Two-sided AI works with legacy 5G: 4x throughput at low SNR
Plus a model table for channel adaptation and gradient-free fine-tuning that cuts communication 15,000x.
· “Rethinking the Foundations of Two-Sided AI Models for 6G”
A wireless sensor can sometimes beat a safety deadline by predicting the future
Predictive lookahead in threshold detection is redundant exactly when the monitored direction is a left-eigenvector of the dynamics with a…
· “React or Predict? A Spectral Rule for Wireless Threshold Detection”
This paper resolves a question Massey posed in 1978: for lossily compressing a stream of…
For any p<1/2, linear encoders achieve exactly the time-sharing rate-distortion tradeoff for Bernoulli(p) sources, confirming Massey's…
· “Entropy of Bernoulli Measures Conditioned on Affine Subspaces and a Problem of Ancheta--Massey”
This paper analyzes soft GRAND
Under channel switching or drift, the mismatch between the channel model used to order guesses and the real channel can be bounded, giving…
Random linear codes hit O(1/ε) list size at average radius
A random F_q-linear code at capacity rate stays decodable under the stricter average-distance test.
Small entropy-power deficits on compact groups force near-uniformity
A tiny entropy-power gap puts each summand within O(sqrt(delta log(1/delta))) of the uniform law.
Null-steering jammers deliver both security and wireless power in HAPS
New formulas predict joint rate-energy coverage and secrecy from ρ, D, and jammer power.
· “Secure Wireless Information Transfer and Energy Harvesting in HAPS-Based Network”
No sensing design beats a rank-only stability floor
Rank-one Gaussian sensors attain it; a convex recovery rule stays stable at optimal sampling scale.
· “Optimal Condition Numbers in Low-Rank Positive Semidefinite Matrix Sensing”
Dynamic filters pay extra bits at every fixed error rate
A new lower bound forces a positive per-key excess over the static information bound for every fixed error rate.
· “Beyond the Static Barrier for Ordinary Dynamic Approximate Membership”
Closed-form updates match near-optimal beamforming at 1% of the runtime
Per-AP and per-SIM-layer updates replace general-purpose solvers in weighted sum-rate beamforming.
Missing variance term closes source-coding second-order gap
At fixed error, the √n dispersion equals the full optimizer-density variance, settling the known converse gap.
QR codes yield infinite small-field quantum LRCs with growing distance
Most earlier quantum LRC constructions need large alphabets; this one works for qubits, qutrits, and beyond.
· “Quantum Locally Repairable Codes from Negacyclic and Repeated-Root Cyclic Codes over Small Fields”
MPAC codes beat PAC codes by pruning low-weight codewords
Partial convolution plus frozen-set row combinations lowers the error floor at the same decoding budget.
Compress wide networks to a width set by data dimension
Hidden layers shrink to a width fixed by input dimension and the error budget, with no fine-tuning.
· “Width-Independent Compressibility of Deep Neural Networks”
One model adapts rate, noise, and content for wireless images
Tail-structured sparsity turns each token's allocation into one small index, beating fixed-allocation learned JSCC.
· “Single-Model Adaptive Wireless Image Transmission via Feature Sparsity Regularization”
Force energy timetables measurement info in diffusion inversion
Expected squared smoothed-likelihood force equals entropy dissipation, giving one exact budget for when measurements act.
· “Posterior Information Dynamics of Diffusion Models for Linear Inverse Problems”
Wi-Fi wake schedules provably within 5.77x of optimal age
A Target Wake Time scheduler now comes with a constant-factor guarantee on information age under per-station energy budgets.
One closed formula captures fading-averaged packet error to ~1%
Short-packet reliability over any Nakagami-m channel becomes one special-function evaluation, not a numerical integral.
One formula counts skew-constacyclic code classes
Over finite fields the count is a divisor sum; isometry merges more only when m|n.
· “The first tight classification of skew-constacyclic codes over finite fields”
One selectable port lifts cell-free random access by 1.39 dB
Perfect-channel port selection adds 1.39 dB; the paper's full receiver cuts 62-dB error rate from 7% to 3%.
One identity turns Ville-to-PAC-Bayes bounds into equalities
Each tail bound becomes an identity with a named closed-form slack: Gibbs tilt, overshoot, or certificate deficit.
· “Information on trajectories: martingales and random times”
Survey maps which bent functions escape the Maiorana-McFarland class
A single subspace condition separates new bent functions from rearranged Maiorana-McFarland ones.
· “Bent Functions and the Completed Maiorana-McFarland Class”
Honeycomb bound beats best-known binary-code rate limits
First level of a representation hierarchy outdoes both the MRRW-era and quantum-channel curves at every distance.
Fair draws from a biased source cost an exact entropy product
The 1971 fair-sampling rule's mean wait is a product over Rényi entropies; binary extraction runs in near-linear time.
· “Algorithms, Complexity, and Entropy of the Bernard-Letac Fair-Sampling Construction”
Exact read counts for retrieving any m symbols in DNA codes
Systematic MDS, simplex, and balanced quasi-arc encoders now have closed-form average retrieval times.
0.949 bit/s/Hz: task-aware radio queries beat uncertainty baselines
A one-label variance-reduction identity ties channel calibration to downstream task risk in multi-UAV control.
Rate-profile learning beats WMMSE on active IRS by 260x
A real-domain IA scheme needs CSI only at the IRS and turns sum-rate optimization into eigenvalue checks.
· “Real Interference Alignment for Active IRS-Aided Systems: A Rate-Profile Learning-Based Approach”
Zipf regret costs one bit per discovered symbol
A depth-averaged Bayesian prior matches the symbol-discovery rate and beats specialized estimators on large alphabets.
Four capabilities cover wireless resilience
Robustness, adaptability, survivability, recoverability: the hierarchy that ties them to mechanisms and trade-offs.
Robot feedback's job depends on who approves the action
Sender-side feedback fetches missing evidence; receiver-side feedback trims what is already there.
· “The Verification Gap in Networked Physical AI: A Post-Semantic Communication Framework”
A geometric construction lowers DNA read expectation to 0.8628
Weak arcs on the fundamental simplex build explicit storage multisets that beat the previous bound over every finite field.
· “Weak arcs and applications to the DNA-based storage access problem”
Chips reproduce the spectra of hyperbolic lattices
Four ways of reading a quantum circuit converge on fabricated devices whose measured modes match curved-space graphs.
Cellular base station plus idle access points beats cell-free ISAC
Hybrid design claims higher sum throughput and sensing accuracy with half the fronthaul connections.
· “Integrated Sensing and Communications over Hierarchical Cellular and Cell-Free MIMO Systems”
Single-qubit measurements nail mixedness testing at ~sqrt(10)^N/eps^2
A randomized Pauli-basis protocol nearly closes the gap between O(4^N) and Omega(sqrt(8)^N) copies.
Reliability targets size and place indoor 5G radio nodes
Stochastic geometry counts the nodes, then clustering and min-cut place them and form cells for indoor users.
Two-layer BD-SIM beats six-layer diagonal SIM for ISAC
Intra-layer coupling lets a two-layer metasurface match a six-layer one for joint sensing and communication.
Abelian codes beat best-known distance records
A genetic search over cyclotomic cosets yields [169,18,87]_3 and [175,18,90]_3.
· “Constructing Good Abelian Codes via Shift Bounds and Genetic Algorithms”
A few path values beat fixed neural channel codes
Sending a variable path list adapts to each channel and transfers to new arrays without retraining.
· “GCNO: Gramian Chebyshev Neural Operator for Physics-Based Compression of Wireless Channels”
Polar and Reed-Muller weights reduce to monomial orbits
Below twice the minimum distance, weight counting is orbit counting.
Closed-form updates slash RIS-ISAC beamforming time 120-fold
A constraints-separation solver keeps sensing beam gain on par with SCA and SDR while cutting runtime.
· “Joint Beamforming and Phase Shifts Design for RIS-Enabled RSMA-ISAC Systems”
Adaptive 1-bit quantization matches the optimal change-detection speed
A new CUSUM variant tunes its 1-bit threshold on the fly and reaches the information-theoretic delay limit.
· “Quickest Change Detection in Parametric Models With 1-Bit Measurements”
Quantum entropy estimates now match lower bounds up to log factors
Two new estimator designs, one per order range, close the Rényi and Tsallis sample-complexity gaps.
· “Nearly Sample-Optimal Estimators for Quantum R\'enyi and Tsallis Entropies”
Conditional guesswork tails get explicit decay rates
Method-of-types proof yields closed-form exponents via tilted distributions, with a password-security estimate.
· “Tail exponents of conditional guesswork via the method of types”
k-NN derivative trick makes Chernoff information estimable
Directly estimating the Rényi-derivative gives a consistent Bayesian error-exponent estimator from raw samples.
Five points on a conic produce new near-MDS codes
For odd fields q, it computes all weights and separates the new codes from prior families by a geometric invariant.
· “Near-MDS codes of lengths q+6 and q+7 from conics in PG(2,q), q odd”
Small scene models beat bigger general CSI feedback model
A 2.6 KB statistical fingerprint finds the right pretrained model, saving 300–1000 samples and 100 epochs.
· “Learnware for CSI Feedback: Scene-specific Small Models Can Do Big”
