Top 10 Arxiv Papers Today in Information Theory


0.0 Mikeys
#1. Design and Analysis of Online Fountain Codes for Intermediate Performance
Jingxuan Huang, Zesong Fei, Congzhe Cao, Ming Xiao
For the benefit of improved intermediate performance, recently online fountain codes attract much research attention. However, there is a trade-off between the intermediate performance and the full recovery overhead for online fountain codes, which prevents them to be improved simultaneously. We analyze this trade-off, and propose to improve both of these two performance. We first propose a method called Online Fountain Codes without Build-up phase (OFCNB) where the degree-1 coded symbols are transmitted at first and the build-up phase is removed to improve the intermediate performance. Then we analyze the performance of OFCNB theoretically. Motivated by the analysis results, we propose Systematic Online Fountain Codes (SOFC) to further reduce the full recovery overhead. Theoretical analysis shows that SOFC has better intermediate performance, and it also requires lower full recovery overhead when the channel erasure rate is lower than a constant. Simulation results verify the analyses and demonstrate the superior performance of...
more | pdf | html
Figures
None.
Tweets
mathITbot: Jingxuan Huang, Zesong Fei, Congzhe Cao, Ming Xiao : Design and Analysis of Online Fountain Codes for Intermediate Performance https://t.co/jFOvVWnpLe https://t.co/ouck9arMDE
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 4
Total Words: 0
Unqiue Words: 0

0.0 Mikeys
#2. Robust Generalization via $α$-Mutual Information
Amedeo Roberto Esposito, Michael Gastpar, Ibrahim Issa
The aim of this work is to provide bounds connecting two probability measures of the same event using R\'enyi $\alpha$-Divergences and Sibson's $\alpha$-Mutual Information, a generalization of respectively the Kullback-Leibler Divergence and Shannon's Mutual Information. A particular case of interest can be found when the two probability measures considered are a joint distribution and the corresponding product of marginals (representing the statistically independent scenario). In this case, a bound using Sibson's $\alpha-$Mutual Information is retrieved, extending a result involving Maximal Leakage to general alphabets. These results have broad applications, from bounding the generalization error of learning algorithms to the more general framework of adaptive data analysis, provided that the divergences and/or information measures used are amenable to such an analysis ({\it i.e.,} are robust to post-processing and compose adaptively). The generalization error bounds are derived with respect to high-probability events but a...
more | pdf | html
Figures
None.
Tweets
Memoirs: Robust Generalization via $\alpha$-Mutual Information. https://t.co/QFJSfB1O87
arxivml: "Robust Generalization via $α$-Mutual Information", Amedeo Roberto Esposito, Michael Gastpar, Ibrahim Issa https://t.co/kftkKML6Ut
mathITbot: Amedeo Roberto Esposito, Michael Gastpar, Ibrahim Issa : Robust Generalization via $α$-Mutual Information https://t.co/mSab7bFS7E https://t.co/OTRLfmecWJ
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 0
Unqiue Words: 0

0.0 Mikeys
#3. On the Capacity of Private Monomial Computation
Yauhen Yakimenka, Hsuan-Yin Lin, Eirik Rosnes
In this work, we consider private monomial computation (PMC) for replicated noncolluding databases. In PMC, a user wishes to privately retrieve an arbitrary multivariate monomial from a candidate set of monomials in $f$ messages over a finite field $\mathbb F_q$, where $q=p^k$ is a power of a prime $p$ and $k \ge 1$, replicated over $n$ databases. We derive the PMC capacity under a technical condition on $p$ and for asymptotically large $q$. The condition on $p$ is satisfied, e.g., for large enough $p$. Also, we present a novel PMC scheme for arbitrary $q$ that is capacity-achieving in the asymptotic case above. Moreover, we present formulas for the entropy of a multivariate monomial and for a set of monomials in uniformly distributed random variables over a finite field, which are used in the derivation of the capacity expression.
more | pdf | html
Figures
None.
Tweets
mathITbot: Yauhen Yakimenka, Hsuan-Yin Lin, Eirik Rosnes : On the Capacity of Private Monomial Computation https://t.co/3LpWt9Rtmt https://t.co/3acKugt2pw
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 0
Unqiue Words: 0

0.0 Mikeys
#4. DNA-Based Storage: Models and Fundamental Limits
Ilan Shomorony, Reinhard Heckel
Due to its longevity and enormous information density, DNA is an attractive medium for archival storage. In this work, we study the fundamental limits and trade-offs of DNA-based storage systems by introducing a new channel model, which we call the noisy shuffling-sampling channel. Motivated by current technological constraints on DNA synthesis and sequencing, this model captures three key distinctive aspects of DNA storage systems: (1) the data is written onto many short DNA molecules; (2) the molecules are corrupted by noise during synthesis and sequencing and (3) the data is read by randomly sampling from the DNA pool. We provide capacity results for this channel under specific noise and sampling assumptions and show that, in many scenarios, a simple index-based coding scheme is optimal.
more | pdf | html
Figures
None.
Tweets
mathITbot: Ilan Shomorony, Reinhard Heckel : DNA-Based Storage: Models and Fundamental Limits https://t.co/j1xIU4Ay4j https://t.co/yZnHob1zeK
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 0
Unqiue Words: 0

0.0 Mikeys
#5. Point-line incidence on Grassmannians and majority logic decoding of Grassmann codes
Peter Beelen, Prasant Singh
In this article, we consider the decoding problem of Grassmann codes using majority logic. We show that for two points of the Grassmannian, there exists a canonical path between these points once a complete flag is fixed. These paths are used to construct a large set of parity checks orthogonal on a coordinate of the code, resulting in a majority decoding algorithm.
more | pdf | html
Figures
None.
Tweets
mathITbot: Peter Beelen, Prasant Singh : Point-line incidence on Grassmannians and majority logic decoding of Grassmann codes https://t.co/TSVkDR7bjE https://t.co/MurlvV9FXq
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 0
Unqiue Words: 0

0.0 Mikeys
#6. Data-Driven Ensembles for Deep and Hard-Decision Hybrid Decoding
Tomer Raviv, Nir Raviv, Yair Be'ery
Ensemble models are widely used to solve complex tasks by their decomposition into multiple simpler tasks, each one solved locally by a single member of the ensemble. Decoding of error-correction codes is a hard problem due to the curse of dimensionality, leading one to consider ensembles-of-decoders as a possible solution. Nonetheless, one must take complexity into account, especially in decoding. We suggest a low-complexity scheme where a single member participates in the decoding of each word. First, the distribution of feasible words is partitioned into non-overlapping regions. Thereafter, specialized experts are formed by independently training each member on a single region. A classical hard-decision decoder (HDD) is employed to map every word to a single expert in an injective manner. FER gains of up to 0.4dB at the waterfall region, and of 1.25dB at the error floor region are achieved for two BCH(63,36) and (63,45) codes with cycle-reduced parity-check matrices, compared to the previous best result of the paper "Active...
more | pdf | html
Figures
Tweets
mathITbot: Tomer Raviv, Nir Raviv, Yair Be'ery : Data-Driven Ensembles for Deep and Hard-Decision Hybrid Decoding https://t.co/wdAZqpvfe7 https://t.co/XrDcKZjtPa
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 4353
Unqiue Words: 1637

0.0 Mikeys
#7. Duplication with transposition distance to the root for $q$-ary strings
Nikita Polyanskii, Ilya Vorobyev
We study the duplication with transposition distance between strings of length $n$ over a $q$-ary alphabet and their roots. In other words, we investigate the number of duplication operations of the form $x = (abcd) \to y = (abcbd)$, where $x$ and $y$ are strings and $a$, $b$, $c$ and $d$ are their substrings, needed to get a $q$-ary string of length $n$ starting from the set of strings without duplications. For exact duplication, we prove that the maximal distance between a string of length at most $n$ and its root has the asymptotic order $n/\log n$. For approximate duplication, where a $\beta$-fraction of symbols may be duplicated incorrectly, we show that the maximal distance has a sharp transition from the order $n/\log n$ to $\log n$ at $\beta=(q-1)/q$. The motivation for this problem comes from genomics, where such duplications represent a special kind of mutation and the distance between a given biological sequence and its root is the smallest number of transposition mutations required to generate the sequence.
more | pdf | html
Figures
None.
Tweets
mathITbot: Nikita Polyanskii, Ilya Vorobyev : Duplication with transposition distance to the root for $q$-ary strings https://t.co/ipgguH4SK9 https://t.co/qF2jwgimo5
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 0
Unqiue Words: 0

0.0 Mikeys
#8. Chebyshev Inertial Landweber Algorithm for Linear Inverse Problems
Tadashi Wadayama, Satoshi Takabe
The Landweber algorithm defined on complex/real Hilbert spaces is a gradient descent algorithm for linear inverse problems. Our contribution is to present a novel method for accelerating convergence of the Landweber algorithm. In this paper, we first extend the theory of the Chebyshev inertial iteration to the Landweber algorithm on Hilbert spaces. An upper bound on the convergence rate clarifies the speed of global convergence of the proposed method. The Chebyshev inertial Landweber algorithm can be applied to wide class of signal recovery problems on a Hilbert space including deconvolution for continuous signals. The theoretical discussion developed in this paper naturally leads to a novel practical signal recovery algorithm. As a demonstration, a MIMO detection algorithm based on the projected Landweber algorithm is derived. The proposed MIMO detection algorithm achieves much smaller symbol error rate compared with the MMSE detector.
more | pdf | html
Figures
None.
Tweets
mathITbot: Tadashi Wadayama, Satoshi Takabe : Chebyshev Inertial Landweber Algorithm for Linear Inverse Problems https://t.co/BDQClBszga https://t.co/okaCr5CJt0
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 0
Unqiue Words: 0

0.0 Mikeys
#9. Constrained Functional Value under General Convexity Conditions with Applications to Distributed Simulation
Yanjun Han
We show a general phenomenon of the constrained functional value for densities satisfying general convexity conditions, which generalizes the observation in Bobkov and Madiman (2011) that the entropy per coordinate in a log-concave random vector in any dimension with given density at the mode has a range of just 1. Specifically, for general functions $\phi$ and $\psi$, we derive upper and lower bounds of density functionals taking the form $I_\phi(f) = \int_{\mathbb{R}^n} \phi(f(x))dx$ assuming the convexity of $\psi^{-1}(f(x))$ for the density, and establish the tightness of these bounds under mild conditions satisfied by most examples. We apply this result to the distributed simulation of continuous random variables, and establish an upper bound of the exact common information for $\beta$-concave joint densities, which is a generalization of the log-concave densities in Li and El Gamal (2017).
more | pdf | html
Figures
None.
Tweets
mathITbot: Yanjun Han : Constrained Functional Value under General Convexity Conditions with Applications to Distributed Simulation https://t.co/hwako4eIBB https://t.co/JsrbBXWVik
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 0
Unqiue Words: 0

0.0 Mikeys
#10. Low Complexity Algorithms for Transmission of Short Blocks over the BSC with Full Feedback
Amaael Antonini, Hengjie Yang, Richard D. Wesel
Building on the work of Horstein, Shayevitz and Feder, and Naghshvar et al., this paper presents algorithms for low-complexity sequential transmission of a $k$-bit message over the binary symmetric channel (BSC) with full, noiseless feedback. To lower complexity, this paper shows that the initial $k$ binary transmissions can be sent before any feedback is required and groups the messages with equal posteriors to reduce the number of posterior updates from exponential in $k$ to linear in $k$. Simulations results demonstrate the achievable rates for this full, noiseless feedback system approach capacity rapidly as a function of $k$, significantly faster than the achievable rate curve of Polyanskiy et al. for a stop feedback system.
more | pdf | html
Figures
None.
Tweets
mathITbot: Amaael Antonini, Hengjie Yang, Richard D. Wesel : Low Complexity Algorithms for Transmission of Short Blocks over the BSC with Full Feedback https://t.co/UjFET6BelO https://t.co/hteMop7sEr
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 0
Unqiue Words: 0

About

Assert is a website where the best academic papers on arXiv (computer science, math, physics), bioRxiv (biology), BITSS (reproducibility), EarthArXiv (earth science), engrXiv (engineering), LawArXiv (law), PsyArXiv (psychology), SocArXiv (social science), and SportRxiv (sport research) bubble to the top each day.

Papers are scored (in real-time) based on how verifiable they are (as determined by their Github repos) and how interesting they are (based on Twitter).

To see top papers, follow us on twitter @assertpub_ (arXiv), @assert_pub (bioRxiv), and @assertpub_dev (everything else).

To see beautiful figures extracted from papers, follow us on Instagram.

Tracking 255,370 papers.

Search
Sort results based on if they are interesting or reproducible.
Interesting
Reproducible
Categories
All
Astrophysics
Cosmology and Nongalactic Astrophysics
Earth and Planetary Astrophysics
Astrophysics of Galaxies
High Energy Astrophysical Phenomena
Instrumentation and Methods for Astrophysics
Solar and Stellar Astrophysics
Condensed Matter
Disordered Systems and Neural Networks
Mesoscale and Nanoscale Physics
Materials Science
Other Condensed Matter
Quantum Gases
Soft Condensed Matter
Statistical Mechanics
Strongly Correlated Electrons
Superconductivity
Computer Science
Artificial Intelligence
Hardware Architecture
Computational Complexity
Computational Engineering, Finance, and Science
Computational Geometry
Computation and Language
Cryptography and Security
Computer Vision and Pattern Recognition
Computers and Society
Databases
Distributed, Parallel, and Cluster Computing
Digital Libraries
Discrete Mathematics
Data Structures and Algorithms
Emerging Technologies
Formal Languages and Automata Theory
General Literature
Graphics
Computer Science and Game Theory
Human-Computer Interaction
Information Retrieval
Information Theory
Machine Learning
Logic in Computer Science
Multiagent Systems
Multimedia
Mathematical Software
Numerical Analysis
Neural and Evolutionary Computing
Networking and Internet Architecture
Other Computer Science
Operating Systems
Performance
Programming Languages
Robotics
Symbolic Computation
Sound
Software Engineering
Social and Information Networks
Systems and Control
Economics
Econometrics
General Economics
Theoretical Economics
Electrical Engineering and Systems Science
Audio and Speech Processing
Image and Video Processing
Signal Processing
General Relativity and Quantum Cosmology
General Relativity and Quantum Cosmology
High Energy Physics - Experiment
High Energy Physics - Experiment
High Energy Physics - Lattice
High Energy Physics - Lattice
High Energy Physics - Phenomenology
High Energy Physics - Phenomenology
High Energy Physics - Theory
High Energy Physics - Theory
Mathematics
Commutative Algebra
Algebraic Geometry
Analysis of PDEs
Algebraic Topology
Classical Analysis and ODEs
Combinatorics
Category Theory
Complex Variables
Differential Geometry
Dynamical Systems
Functional Analysis
General Mathematics
General Topology
Group Theory
Geometric Topology
History and Overview
Information Theory
K-Theory and Homology
Logic
Metric Geometry
Mathematical Physics
Numerical Analysis
Number Theory
Operator Algebras
Optimization and Control
Probability
Quantum Algebra
Rings and Algebras
Representation Theory
Symplectic Geometry
Spectral Theory
Statistics Theory
Mathematical Physics
Mathematical Physics
Nonlinear Sciences
Adaptation and Self-Organizing Systems
Chaotic Dynamics
Cellular Automata and Lattice Gases
Pattern Formation and Solitons
Exactly Solvable and Integrable Systems
Nuclear Experiment
Nuclear Experiment
Nuclear Theory
Nuclear Theory
Physics
Accelerator Physics
Atmospheric and Oceanic Physics
Applied Physics
Atomic and Molecular Clusters
Atomic Physics
Biological Physics
Chemical Physics
Classical Physics
Computational Physics
Data Analysis, Statistics and Probability
Physics Education
Fluid Dynamics
General Physics
Geophysics
History and Philosophy of Physics
Instrumentation and Detectors
Medical Physics
Optics
Plasma Physics
Popular Physics
Physics and Society
Space Physics
Quantitative Biology
Biomolecules
Cell Behavior
Genomics
Molecular Networks
Neurons and Cognition
Other Quantitative Biology
Populations and Evolution
Quantitative Methods
Subcellular Processes
Tissues and Organs
Quantitative Finance
Computational Finance
Economics
General Finance
Mathematical Finance
Portfolio Management
Pricing of Securities
Risk Management
Statistical Finance
Trading and Market Microstructure
Quantum Physics
Quantum Physics
Statistics
Applications
Computation
Methodology
Machine Learning
Other Statistics
Statistics Theory
Feedback
Online
Stats
Tracking 255,370 papers.