* [176] L. A. Nelson, S. A. Rappaport and P. C. Joss  “The Evolution of Ultrashort Period Binary Systems”  In _ApJ_ 304, 1986, pp. 231  DOI: 10.1086/164156
  * [177] F. Nicastro et al.  “Observations of the missing baryons in the warm-hot intergalactic medium”  In _Nature_ 558.7710, 2018, pp. 406–409  DOI: 10.1038/s41586-018-0204-1
  * [178] Ray P. Norris et al.  “Unexpected circular radio objects at high Galactic latitude”  In _Publications of the Astronomical Society of Australia_ 38, 2021, pp. e003  DOI: 10.1017/pasa.2020.52
  * [179] J. A. Nousek  “Evidence for a Canonical Gamma-Ray Burst Afterglow Light Curve in the Swift XRT Data”  In _ApJ_ 642, 2006, pp. 389–400  DOI: 10.1086/500724
  * [180] Gor Oganesyan et al.  “Structured Jets and X-Ray Plateaus in Gamma-Ray Burst Phenomena”  In _ApJ_ 893.2, 2020, pp. 88  DOI: 10.3847/1538-4357/ab8221
  * [181] P. Padovani, A. Turcati and E. Resconi  “AGN outflows as neutrino sources: an observational test”  In _Mon. Not. Roy. Astron. Soc._ 477.3, 2018, pp. 3469–3479  DOI: 10.1093/mnras/sty877
  * [182] P. Padovani, M. Petropoulou, P. Giommi and E. Resconi  “A simplified view of blazars: the neutrino background”  In _MNRAS_ 452.2, 2015, pp. 1877–1887  DOI: 10.1093/mnras/stv1467
  * [183] P. Padovani et al.  “ESO-Athena Synergy White Paper”  In _arXiv e-prints_ , 2017  arXiv:1705.06064 [astro-ph.HE]
  * [184] P. Padovani et al.  “Dissecting the region around IceCube-170922A: the blazar TXS 0506+056 as the first cosmic neutrino source”  In _Mon. Not. Roy. Astron. Soc._ 480.1, 2018, pp. 192–203  DOI: 10.1093/mnras/sty1852
  * [185] F. Panessa et al.  “The X-ray and radio connection in low-luminosity active nuclei”  In _A &A_ 467, 2007, pp. 519–527  DOI: 10.1051/0004-6361:20066943
  * [186] Vasileios Paschalidis, Jane Bright, Milton Ruiz and Roman Gold  “Minidisk Dynamics in Accreting, Spinning Black Hole Binaries: Simulations in Full General Relativity”  In _ApJ Letters_ 910.2, 2021, pp. L26  DOI: 10.3847/2041-8213/abee21
  * [187] D. J. Patnaude and R. A. Fesen  “Proper Motions and Brightness Variations of Nonthermal X-ray Filaments in the Cassiopeia A Supernova Remnant”  In _ApJ_ 697, 2009, pp. 535–543  DOI: 10.1088/0004-637X/697/1/535
  * [188] M. Petropoulou and A. Mastichiadis  “Bethe-Heitler emission in BL Lacs: filling the gap between X-rays and $\gamma$-rays”  In _MNRAS_ 447.1, 2015, pp. 36–48  DOI: 10.1093/mnras/stu2364
  * [189] L. Piro et al.  “A long-lived neutron star merger remnant in GW170817: constraints and clues from X-ray observations”  In _MNRAS_ 483.2, 2019, pp. 1912–1921  DOI: 10.1093/mnras/sty3047
  * [190] Ph. Podsiadlowski, S. Rappaport and Z. Han  “On the formation and evolution of black hole binaries”  In _MNRAS_ 341.2, 2003, pp. 385–404  DOI: 10.1046/j.1365-8711.2003.06464.x
  * [191] M. Punturo  “The Einstein Telescope: A third-generation gravitational wave observatory”  In _Class. Quant. Grav._ 27, 2010, pp. 194002  DOI: 10.1088/0264-9381/27/19/194002
  * [192] G. Ramsay et al.  “Physical properties of AM CVn stars: New insights from Gaia DR2”  In _A &A_ 620, 2018, pp. A141  DOI: 10.1051/0004-6361/201834261
  * [193] S. Rappaport, P. C. Joss and R. F. Webbink  “The evolution of highly compact binary stellar systems.”  In _ApJ_ 254, 1982, pp. 616–640  DOI: 10.1086/159772
  * [194] David Reitze  “Cosmic Explorer: The U.S. Contribution to Gravitational-Wave Astronomy beyond LIGO”  In _Bull. Am. Astron. Soc._ 51, 2019, pp. 035  arXiv:1907.04833 [astro-ph.IM]
  * [195] C. Ricci et al.  “The close environments of accreting massive black holes are shaped by radiative feedback”  In _Nature_ 549, 2017, pp. 488–491  DOI: 10.1038/nature23906
  * [196] C. Ricci et al.  “The Destruction and Recreation of the X-Ray Corona in a Changing-look Active Galactic Nucleus”  In _ApJ Letters_ 898.1, 2020, pp. L1  DOI: 10.3847/2041-8213/ab91a1
  * [197] R. Ricci et al.  “Searching for the radio remnants of short-duration gamma-ray bursts”  In _MNRAS_ 500.2, 2021, pp. 1708–1720  DOI: 10.1093/mnras/staa3241
  * [198] C. Righi, F. Tavecchio and S. Inoue  “Neutrino emission from BL Lac objects: the role of radiatively inefficient accretion flows”  In _Mon. Not. Roy. Astron. Soc._ 483.1, 2019, pp. L127–L131  DOI: 10.1093/mnrasl/sly231
  * [199] Justin L. Ripley, Brian D. Metzger, Almudena Arcones and Gabriel Martínez-Pinedo  “X-ray decay lines from heavy nuclei in supernova remnants as a probe of the r-process origin and the birth periods of magnetars”  In _MNRAS_ 438.4, 2014, pp. 3243–3254  DOI: 10.1093/mnras/stt2434
  * [200] C. Roedig, J. H. Krolik and M. C. Miller  “Observational Signatures of Binary Supermassive Black Holes”  In _ApJ_ 785, 2014, pp. 115  DOI: 10.1088/0004-637X/785/2/115
  * [201] E. M. Rossi et al.  “Black hole mergers: the first light”  In _MNRAS_ 401, 2010, pp. 2021–2035  DOI: 10.1111/j.1365-2966.2009.15802.x
  * [202] S. Rosswog et al.  “Mass ejection in neutron star mergers”  In _A &A_ 341, 1999, pp. 499–526  arXiv:astro-ph/9811367 [astro-ph]
  * [203] S. Rosswog et al.  “The first direct double neutron star merger detection: Implications for cosmic nucleosynthesis”  In _A &A_ 615, 2018, pp. A132  DOI: 10.1051/0004-6361/201732117
  * [204] A. Rowlinson, A. Patruno and P. T. O’Brien  “A deceleration search for magnetar pulsations in the X-ray plateaus of short GRBs”  In _MNRAS_ 472.1, 2017, pp. 1152–1161  DOI: 10.1093/mnras/stx2023
  * [205] Geoffrey Ryan, Hendrik van Eerten, Luigi Piro and Eleonora Troja  “Gamma-Ray Burst Afterglows in the Multimessenger Era: Numerical Models and Closure Relations”  In _ApJ_ 896.2, 2020, pp. 166  DOI: 10.3847/1538-4357/ab93cf
  * [206] O. S. Salafia, G. Ghirlanda, S. Ascenzi and G. Ghisellini  “On-axis view of GRB 170817A”  In _A &A_ 628, 2019, pp. A18  DOI: 10.1051/0004-6361/201935831
  * [207] O. S. Salafia, C. Barbieri, S. Ascenzi and M. Toffano  “Gamma-ray burst jet propagation, development of angular structure, and the luminosity function”  In _A &A_ 636, 2020, pp. A105  DOI: 10.1051/0004-6361/201936335
  * [208] R. Sari, T. Piran and R. Narayan  “Spectra and Light Curves of Gamma-Ray Burst Afterglows”  In _ApJ Letters_ 497, 1998, pp. L17–L20  DOI: 10.1086/311269
  * [209] Bangalore Sathyaprakash et al.  “Extreme gravity and fundamental physics”  In _BAAS_ 51.3, 2019, pp. 251  arXiv:1903.09221 [astro-ph.HE]
  * [210] Bangalore Sathyaprakash et al.  “Multimessenger universe with gravitational waves from binary systems”  In _BAAS_ 51.3, 2019, pp. 276  arXiv:1903.09277 [astro-ph.HE]
  * [211] R. Saxton, S. Komossa, K. Auchettl and P. G. Jonker  “X-Ray Properties of TDEs”  In _Science & Space Review_ 216.5, 2020, pp. 85  DOI: 10.1007/s11214-020-00708-4
  * [212] B. F. Schutz  “Determining the Hubble constant from gravitational wave observations”  In _Nature_ 323, 1986, pp. 310  DOI: 10.1038/323310a0
  * [213] A. Sesana, J. Gair, E. Berti and M. Volonteri  “Reconstructing the massive black hole cosmic history through gravitational waves”  In _Physical Review Letters_ 83.4, 2011, pp. 044036  DOI: 10.1103/PhysRevD.83.044036
  * [214] Yong Shao, Xiang-Dong Li and Zi-Gao Dai  “A Population of Neutron Star Ultraluminous X-Ray Sources with a Helium Star Companion”  In _ApJ_ 886.2, 2019, pp. 118  DOI: 10.3847/1538-4357/ab4d50
  * [215] S. L. Shapiro  “Black holes, disks, and jets following binary mergers and stellar collapse: The narrow range of electromagnetic luminosities and accretion rates”  In _Physical Review Letters_ 95.10, 2017, pp. 101303  DOI: 10.1103/PhysRevD.95.101303
  * [216] David Shoemaker and LIGO Scientific Collaboration  “Gravitational wave astronomy with LIGO and similar detectors in the next decade”  In _BAAS_ 51.3, 2019, pp. 452
  * [217] Daniel M. Siegel and Riccardo Ciolfi  “Electromagnetic Emission from Long-lived Binary Neutron Star Merger Remnants. II. Lightcurves and Spectra”  In _ApJ_ 819.1, 2016, pp. 15  DOI: 10.3847/0004-637X/819/1/15
  * [218] P. Slane et al.  “Nonthermal X-Ray emission from the shell-type supernova remnant G347.3-0.5”  In _ApJ_ 525, 1999, pp. 357–367  URL: http://adsabs.harvard.edu/cgi-bin/nph-bib_query?bibcode=1999ApJ...525..357S&db_key=AST
  * [219] P. Slane  “RX J0852.0-4622: Another nonthermal shell-type supernova remnant (G266.2-1.2)”  In _ApJ_ 548, 2001, pp. 814–819  URL: http://adsabs.harvard.edu/cgi-bin/nph-bib_query?bibcode=2001ApJ...548..814S&db_key=AST
  * [220] Ian Smail, David W. Hogg, Lin Yan and Judith G. Cohen  “Deep Optical Galaxy Counts with the Keck Telescope”  In _ApJ Letters_ 449, 1995, pp. L105  DOI: 10.1086/309647
  * [221] Thomas P. Sotiriou  “Detecting Lorentz Violations with Gravitational Waves from Black Hole Binaries”  In _Phys. Rev. Lett._ 120.4, 2018, pp. 041104  DOI: 10.1103/PhysRevLett.120.041104
  * [222] Nora L. Strotjohann, Marek Kowalski and Anna Franckowiak  “Eddington bias for cosmic neutrino sources”  In _Astron. Astrophys._ 622, 2019, pp. L9  DOI: 10.1051/0004-6361/201834750
  * [223] Kazuya Takahashi and Kunihito Ioka  “Inverse reconstruction of jet structure from off-axis gamma-ray burst afterglows”  In _MNRAS_ 497.1, 2020, pp. 1217–1235  DOI: 10.1093/mnras/staa1984
  * [224] N. Tamanini et al.  “Science with the space-based interferometer eLISA. III: probing the expansion of the universe using gravitational wave standard sirens”  In _Journal of Cosmology and Astroparticle Physics_ 4, 2016, pp. 002  DOI: 10.1088/1475-7516/2016/04/002
  * [225] Y. Tang, Z. Haiman and A. MacFadyen  “The late inspiral of supermassive black hole binaries with circumbinary gas discs in the LISA band”  In _MNRAS_ 476, 2018, pp. 2249–2257  DOI: 10.1093/mnras/sty423
  * [226] Y. Tang, A. MacFadyen and Z. Haiman  “On the orbital evolution of supermassive black hole binaries with circumbinary accretion discs”  In _MNRAS_ 469, 2017, pp. 4258–4267  DOI: 10.1093/mnras/stx1130
  * [227] Thomas M. Tauris  “Disentangling Coalescing Neutron-Star-White-Dwarf Binaries for LISA”  In _Phys. Rev. Lett._ 121.13, 2018, pp. 131105  DOI: 10.1103/PhysRevLett.121.131105
  * [228] Yuichi Terashima and Andrew S. Wilson  “Chandra Snapshot Observations of Low-Luminosity Active Galactic Nuclei with a Compact Radio Source”  In _ApJ_ 583.1, 2003, pp. 145–158  DOI: 10.1086/345339
  * [229] The Fermi-LAT Collaboration  “Gamma rays from Fast Black-Hole Winds”  In _arXiv e-prints_ , 2021  arXiv:2105.11469 [astro-ph.HE]
  * [230] The IceCube-Gen2 Collaboration et al.  “IceCube-Gen2: The Window to the Extreme Universe”  In _arXiv e-prints_ , 2020  arXiv:2008.04323 [astro-ph.HE]
  * [231] S. Toonen, M. Hollands, B. T. Gänsicke and T. Boekholt  “The binarity of the local white dwarf population”  In _A &A_ 602, 2017, pp. A16  DOI: 10.1051/0004-6361/201629978
  * [232] E. Troja et al.  “A luminous blue kilonova and an off-axis jet from a compact binary merger at z = 0.1341”  In _Nature Communications_ 9, 2018, pp. 4089  DOI: 10.1038/s41467-018-06558-7
  * [233] E. Troja et al.  “The outflow structure of GW170817 from late-time broad-band observations”  In _MNRAS_ 478.1, 2018, pp. L18–L23  DOI: 10.1093/mnrasl/sly061
  * [234] E. Troja et al.  “A year in the life of GW 170817: the rise and fall of a structured jet from a binary neutron star merger”  In _MNRAS_ 489.2, 2019, pp. 1919–1926  DOI: 10.1093/mnras/stz2248
  * [235] E. Troja et al.  “A thousand days after the merger: Continued X-ray emission from GW170817”  In _MNRAS_ 498.4, 2020, pp. 5643–5651  DOI: 10.1093/mnras/staa2626
  * [236] David Tsang et al.  “Resonant Shattering of Neutron Star Crusts”  In _Phys.Rev.Lett._ 108.1, 2012, pp. 011102  DOI: 10.1103/PhysRevLett.108.011102
  * [237] H. J. van Eerten  “Simulation and physical model based gamma-ray burst afterglow analysis”  In _Journal of High Energy Astrophysics_ 7, 2015, pp. 23–34  DOI: 10.1016/j.jheap.2015.04.004
  * [238] J. Van Schelt et al.  “First Results from the CARIBU Facility: Mass Measurements on the r-Process Path”  In _Phys. Rev. Lett._ 111.6, 2013, pp. 061102  DOI: 10.1103/PhysRevLett.111.061102
  * [239] R. V. Vasudevan and A. C. Fabian  “Simultaneous X-ray/optical/UV snapshots of active galactic nuclei from XMM-Newton: spectral energy distributions for the reverberation mapped sample”  In _MNRAS_ 392, 2009, pp. 1124–1140  DOI: 10.1111/j.1365-2966.2008.14108.x
  * [240] R. V. Vasudevan, R. F. Mushotzky, L. M. Winter and A. C. Fabian  “Optical-to-X-ray emission in low-absorption AGN: results from the Swift–BAT 9-month catalogue”  In _Monthly Notices of the Royal Astronomical Society_ 399.3, 2009, pp. 1553–1575  DOI: 10.1111/j.1365-2966.2009.15371.x
  * [241] VERITAS Collaboration and V. A. Acciari  “A connection between star formation activity and cosmic rays in the starburst galaxy M82”  In _Nature_ 462.7274, 2009, pp. 770–772  DOI: 10.1038/nature08557
  * [242] T. Vernstrom et al.  “Deep 3-GHz observations of the Lockman Hole North with the Very Large Array - II. Catalogue and $\mu$Jy source properties”  In _MNRAS_ 462.3, 2016, pp. 2934–2949  DOI: 10.1093/mnras/stw1836
  * [243] J. Vink  “The Kinematics of Kepler’s Supernova Remnant as Revealed by Chandra”  In _ApJ_ 689, 2008, pp. 231–241  DOI: 10.1086/592375
  * [244] J. Vink et al.  “Slow temperature equilibration behind the shock front of SN 1006”  In _ApJ Letters_ 587, 2003, pp. 31–34  URL: http://adsabs.harvard.edu/cgi-bin/nph-bib_query?bibcode=2003ApJ...584..758V&db_key=AST
  * [245] J. Vink, R. Yamazaki, E. A. Helder and K. M. Schure  “The Relation Between Post-shock Temperature, Cosmic-ray Pressure, and Cosmic-ray Escape for Non-relativistic Shocks”  In _ApJ_ 722, 2010, pp. 1727–1734  DOI: 10.1088/0004-637X/722/2/1727
  * [246] J. Vink, S. Broersen, A. Bykov and S. Gabici  “On the electron-ion temperature ratio established by collisionless shocks”  In _A &A_ 579, 2015, pp. A13  DOI: 10.1051/0004-6361/201424612
  * [247] Salvatore Vitale and Matthew Evans  “Parameter estimation for binary black holes with networks of third generation gravitational-wave detectors”  In _Phys. Rev. D_ 95.6, 2017, pp. 064052  DOI: 10.1103/PhysRevD.95.064052
  * [248] Salvatore Vitale and Chris Whittle  “Characterization of binary black holes by heterogeneous gravitational-wave networks”  In _Phys. Rev. D_ 98.2, 2018, pp. 024029  DOI: 10.1103/PhysRevD.98.024029
  * [249] Salvatore Vitale, Will M. Farr, Ken Ng and Carl L. Rodriguez  “Measuring the star formation rate with gravitational waves from binary black holes”  In _Astrophys. J._ 886.1, 2019, pp. L1  DOI: 10.3847/2041-8213/ab50c0
  * [250] G. Mark Voit  “Tracing cosmic evolution with clusters of galaxies”  In _Reviews of Modern Physics_ 77.1, 2005, pp. 207–258  DOI: 10.1103/RevModPhys.77.207
  * [251] M. Volonteri  “Formation of supermassive black holes”  In _The Astronomy and Astrophysics Review_ 18, 2010, pp. 279–315  DOI: 10.1007/s00159-010-0029-x
  * [252] Xilu Wang and Brian D. Fields  “Are starburst galaxies proton calorimeters?”  In _MNRAS_ 474.3, 2018, pp. 4073–4088  DOI: 10.1093/mnras/stx2917
  * [253] Zi-Yi Wang, Ruo-Yu Liu and Xiang-Yu Wang  “Testing the equivalence principle and Lorentz invariance with PeV neutrinos from blazar flares”  In _Phys. Rev. Lett._ 116.15, 2016, pp. 151101  DOI: 10.1103/PhysRevLett.116.151101
  * [254] R. F. Webbink  “The evolution of low-mass close binary systems. VI. Population II W Ursae Majoris systems.”  In _ApJ_ 227, 1979, pp. 178–184  DOI: 10.1086/156717
  * [255] Jun-Jie Wei, Xue-Feng Wu, He Gao and Peter M sz ros  “Limits on the Neutrino Velocity, Lorentz Invariance, and the Weak Equivalence Principle with TeV Neutrinos from Gamma-Ray Bursts”  In _JCAP_ 1608.08, 2016, pp. 031  DOI: 10.1088/1475-7516/2016/08/031
  * [256] Jun-Jie Wei et al.  “Multimessenger tests of Einstein’s weak equivalence principle and Lorentz invariance with a high-energy neutrino from a flaring blazar”  In _JHEAp_ 22, 2019, pp. 1–4  DOI: 10.1016/j.jheap.2019.01.002
  * [257] N. E. White et al.  “The Gamow Explorer: a Gamma-Ray Burst Observatory to study the high redshift universe and enable multi-messenger astrophysics”  In _UV, X-Ray, and Gamma-Ray Space Instrumentation for Astronomy XXII_ 11821 SPIE, 2021, pp. 87 –100  International Society for OpticsPhotonics  URL: https://doi.org/10.1117/12.2599293
  * [258] R. A. M. J. Wijers, M. J. Rees and P. Meszaros  “Shocked by GRB 970228: the afterglow of a cosmological fireball”  In _MNRAS_ 288, 1997, pp. L51–L56  DOI: 10.1093/mnras/288.4.L51
  * [259] B. J. Williams et al.  “An X-Ray and Radio Study of the Varying Expansion Velocities in Tychos Supernova Remnant”  In _ApJ Letters_ 823, 2016, pp. L32  DOI: 10.3847/2041-8205/823/2/L32
  * [260] R. Willingale, G. Pareschi, F. Christensen and J.-W. den Herder  “The Hot and Energetic Universe: The Optical Design of the Athena+ Mirror”  In _arXiv e-prints_ , 2013  arXiv:1307.1709 [astro-ph.IM]
  * [261] Meng-Ru Wu et al.  “Finding the Remnants of the Milky Way’s Last Neutron Star Mergers”  In _ApJ_ 880.1, 2019, pp. 23  DOI: 10.3847/1538-4357/ab2593
  * [262] Xiaoyi Xie, Jonathan Zrake and Andrew MacFadyen  “Numerical Simulations of the Jet Dynamics and Synchrotron Radiation of Binary Neutron Star Merger Event GW170817/GRB 170817A”  In _ApJ_ 863.1, 2018, pp. 58  DOI: 10.3847/1538-4357/aacf9c
  * [263] H. Yamaguchi et al.  “The Refined Shock Velocity of the X-Ray Filaments in the RCW 86 Northeast Rim”  In _ApJ Letters_ 820, 2016, pp. L3  DOI: 10.3847/2041-8205/820/1/L3
  * [264] Jinyi Yang et al.  “Pōniuā’ena: A Luminous z = 7.5 Quasar Hosting a 1.5 Billion Solar Mass Black Hole”  In _ApJ Letters_ 897.1, 2020, pp. L14  DOI: 10.3847/2041-8213/ab9c26
  * [265] Chengchao Yuan et al.  “Post-merger Jets from Supermassive Black Hole Coalescences as Electromagnetic Counterparts of Gravitational Wave Emission”  In _ApJ Letters_ 911.1, 2021, pp. L15  DOI: 10.3847/2041-8213/abee24
  * [266] B. Zhang et al.  “Physical Processes Shaping Gamma-Ray Burst X-Ray Afterglow Light Curves: Theoretical Implications from the Swift X-Ray Telescope Observations”  In _ApJ_ 642, 2006, pp. 354–370  DOI: 10.1086/500723
  * [267] Jonathan Zrake, Xiaoyi Xie and Andrew MacFadyen  “Radio Sky Maps of the GRB 170817A Afterglow from Simulations”  In _ApJ Letters_ 865.1, 2018, pp. L2  DOI: 10.3847/2041-8213/aaddf8

## Acronym List

AGN | active galactic nucleus/nuclei
---|---
AMON | Astrophysical Multi-messenger Observatory Network
AM CVn | accreting white dwarf binary
ARCA | Astroparticle Research with Cosmics in the Abyss
ASST |  Athena Science Study Team
BNS | binary neutron star
BH | black hole
BSM | beyond the standard model
CARIBU | CAlifornium Rare Isotope Breeder Upgrade
CGM | circum-galactic medium
CTA | Cherenkov Telescope Array
CV | cataclysmic variable
CR | cosmic-ray
EBL | extragalactic background light
EM | electromagnetic
EMRI | extreme mass ratio inspiral
EoS | Equation of State
ESA | European Space Agency
ET | Einstein Telescope
DWD | double white dwarf
Fermi GBM | Fermi Gamma-Ray Burst Monitor
FoV | Field of View
FRIB | Facility for Rare Isotope Beams
GBH | galactic black hole
GRB | gamma ray burst
GW | gravitational wave
IGM | intergalactic medium
IMRI | intermediate mass ratio inspiral
ISM | interstellar medium
IRT | infrared telescope
HAWC | High Altitude Water Cherenkov
HEW | half energy width
HMXB | high-mass X-ray binary
$\Lambda$CDM | lambda cold dark matter
LGBR | long-duration GRB
LMXB | low-mass X-ray binary
LST | large-sized telescope

LVI | Lorentz violation invariance
---|---
MBH | massive black hole
MOS | mission observation simulator
MS | main sequence
MST | medium-sized telescope
NS | neutron star
ORC | odd radio circle
Pop-II | population II
Pop-III | population III
PWN(e) | pulsar wind nebula(e)
QCD | quantum chromodynamics
RS | reverse shock
RSF | resonant shattering flare
SGBR | short-duration GRB
SMBH | super-massive black hole
SMBHMs | super massive blach hole mergers
$S/N$ | signal-to-noise ratio
SN(e) | supernova(e)
SNIa | Supernova Ia
SNcc | core collapse supernova
SNR | supernova remnant
SST | small-sized telescope
SXI | Soft X-ray Imager
TDE | tidal disruption event
ToO | Target of Opportunity
UCXB | ultra-compact X-ray binary
ULX | ultra-luminous X-ray source
VHE | very-high-energy
VLBI | Very Long Baseline Interferometry
WD | white dwarf
WFI | Wide Field Imager
WHIM | warm-hot intergalactic medium
X-IFU | X-ray Integral Field Unit
XGIS | X-Gamma-ray Imaging Spectrometer


# Random Access in Distributed Source Coding ††thanks: S. Vatedka is with the
Department of Electrical Engineering, Indian Institute of Technology
Hyderabad, India. V. Chandar is with DE Shaw, New York, USA. A. Tchamkerten is
with the Department of Communications and Electronics, Telecom Paris, Institut
Polytechnique de Paris, France.
The work of S. Vatedka was supported by a seed grant from IIT Hyderabad and a
Start-Up Research grant (SRG/2020/000910) from the Science and Engineering
Research Board, India.
This work has been submitted in part to the 2022 IEEE International Symposium
on Information Theory.

Shashank Vatedka  Venkat Chandar  Aslan Tchamkerten

###### Abstract

The lossless compression of a single source $X^{n}$ was recently shown to be
achievable with a notion of strong locality; any $X_{i}$ can be decoded from a
_constant_ number of compressed bits, with a vanishing in $n$ probability of
error. In contrast with the single source setup, we show that for two
separately encoded sources $(X^{n},Y^{n})$, lossless compression and strong
locality is generally not possible. More precisely, we show that for the class
of “confusable” sources strong locality cannot be achieved whenever one of the
sources is compressed below its entropy. In this case, irrespectively of $n$,
the probability of error of decoding any $(X_{i},Y_{i})$ is lower bounded by
$2^{-O(d_{\mathrm{loc}})}$, where $d_{\mathrm{loc}}$ denotes the number of
compressed bits accessed by the local decoder. Conversely, if the source is
not confusable, strong locality is possible even if one of the sources is
compressed below its entropy. Results extend to any number of sources.

##  I Introduction

The amount of data generated in many applications such as astronomy and
genomics has highlighted the growing need for compression schemes that allows
to interact and manipulate data directly in the compressed domain [1, 2, 3, 4,
5, 6, 7]. Indeed, traditional compression schemes such as Lempel-Ziv [8, 9]
are suboptimal in this regard since the recovery of even a single message
symbol necessitates to decompress the entire dataset. Accordingly, this paper
focuses on providing random access in the compressed domain, where short
fragments of data can be recovered without accessing the entire compressed
sequence.

For the single source setup, [10, 11] showed that a strong notion of locality
holds: for any rate above entropy there exists an encoder and a local decoder
which probes a constant number $d_{\mathrm{loc}}$ (independent of $n$) of
compressed symbols, and yet achieves vanishing error probability as $n$ grows.
Note that the naive concatenation scheme where the source is decomposed into
$n/b$ consecutive blocks of some size $b$, each of which independently
compressed at a desired rate $R>H(X)$, is not strongly local. Indeed, any
$X_{i}$ is independent of all $n/b$ sub-block codewords, except one which
reveals $b$ message symbols, and $X_{i}$ in particular. Hence, only “weak”
locality holds in the sense that for the local decoder error probability to
vanish, the number $d_{\mathrm{loc}}$ of probed symbols—here equal to the sub-
block codeword length $b\cdot R$—must grow with $n$.

In this paper we address the question whether strong locality extends to the
Slepian-Wolf distributed compression of two sources $X^{n}$ and $Y^{n}$: given
$(R_{1},R_{2})$ within the Slepian-Wolf rate region, is it possible to design
a fix-length compressor and a local decompressor with $d_{\mathrm{loc}}=O(1)$
and whose error probability is $o(1)$ as $n$ grows?

Obviously, if each source is compressed above its entropy then strong locality
holds simply by duplicating the results of [10, 11] separately for each of the
sources. Note also that the naive concatenation scheme—wherein $(X^{n},Y^{n})$
is decomposed into consecutive sub-blocks of size $b$ each of which encoded
via Slepian-Wolf coding—achieves weak locality at any $(R_{1},R_{2})$ within
the Slepian-Wolf rate region. So the interesting question is whether strong
locality holds when at least one of the sources is compressed below its
entropy.

Our main result says that strong locality is generally impossible. More
precisely, suppose $p_{XY}$ is “confusable,” in the sense that, for every
$x_{1}$ and $x_{2}$ in $\cal{X}$ there exists $y\in\cal{Y}$ such that
$p_{XY}(x_{1},y)>0$ and $p_{XY}(x_{2},y)>0$. In this case, if $R_{1}<H(X)$,
the probability of wrongly decoding any particular $(X_{i},Y_{i})$ is lower
bounded by $2^{-\Theta(d_{\mathrm{loc}})}$. Moreover, this conclusion holds
even if the decoder tries to decode only $X_{i}$ with the full cooperation of
the $Y$-transmitter that provides $Y^{n}$ uncompressed. Conversely, if
$p_{XY}$ is not confusable, then strong locality is possible for some
$R_{1}<H(X)$ and $R_{2}=H(Y)$.

As a consequence, when the source is confusable, the naive scheme is order
optimal in the tradeoff between local error probability and number of probes.
However, observe that both the encoding and the decoding procedures of the
naive scheme are tied to the sub-block length $b$ which governs the error
probability of the local decoder. In particular, there is no point for the
local decoder to probe more than $b$ bits; even if both codewords are entirely
probed, that is $d_{\mathrm{loc}}=n(R_{1}+R_{2})$, the error probability
remains the same as if $d_{\mathrm{loc}}=n(R_{1}+R_{2})$. Thus, to lower the
error probability of the local decoder, the encoding procedure must be
modified as well. We address this issue through a hierarchical compression
scheme whose local decoder achieves an error probability that decreases as
$d_{\mathrm{loc}}$ increases, without modifying the encoding. Specifically,
for any $(R_{1},R_{2})$ within the Slepian-Wolf rate region, and for every
$1>\eta>2^{-2^{O(\log n)}}$, the local decoder achieves
$P_{e}^{(\mathrm{loc})}\leq\eta$ with
$d_{\mathrm{loc}}=\mathrm{poly}(\log(1/\eta))$.

###  I-A Literature on locally decodable compression

Local decoding has been studied extensively in the context of compressed data
structures by the computer science community; see, e.g., [12, 13, 14, 15, 16,
17] and the references therein. Most of these results hold under the word-RAM
model which assumes that operations (memory access, arithmetic operations) on
$w$-bit words take constant time. The word size $w$ is typically chosen to be
$\Theta(\log n)$ bits, motivated in part by on-chip type of applications where
data transfer happens through a common memory bus for both data and addressing
(hence $w=\Theta(\log n)$ bits), and partly by the fact that certain proof
techniques work only when $w=\Omega(\log n)$.

In the word-RAM model, it is possible to compress any sequence to its
empirical entropy and still be able to locally decode any message symbol in
constant time [12, 13]. Most approaches modify the Lempel-Ziv class of
algorithms to provide efficient local decodability [18, 19, 20]. Similar
results also hold for compression of correlated data  _et al._ [21], and
efficient recovery of short substrings of the message [22, 23, 24, 18].
However, all of these schemes require the local decoder to probe at least
$O(\log n)$ compressed bits to recover any source symbol.

In this work, the decoding cost is measured by the _number of compressed bits_
that need to be accessed in order to recover a single source symbol, sometimes
referred to as the _local decodability_ [25], or the _bit-probe complexity_ in
the literature [26].

The problem of locally decodable source coding of random sequences was first
studied by [27, 25]. They showed that any compressor with $d_{\mathrm{loc}}=2$
cannot achieve a rate below the trivial rate $\log|\mathcal{X}|$, and any
_linear_ source code that achieves $d_{\mathrm{loc}}=\Theta(1)$ necessarily
operates at a trivial compression rate ($R=1$ for binary sources). Later, [10]
showed that rate $H(X)+\varepsilon$ and local decodability
$d_{\mathrm{loc}}=\Theta(\frac{1}{\varepsilon}\log\frac{1}{\varepsilon})$ is
achievable. They also provided a converse result for non-dyadic sources:
$d_{\mathrm{loc}}=\Omega(\log(1/\varepsilon))$ for any compression scheme that
achieves rate $H(X)+\varepsilon$. A similar scheme was given in [11] for
Markov sources and they could compress the source to the entropy rate and
achieve
$d_{\mathrm{loc}}(1)=\Theta(\frac{1}{\varepsilon^{2}}\log\frac{1}{\varepsilon})$.
A common feature of the code construction in both papers is the use of the
bitvector compressor of Buhrman _et al._ [28] which in turn is a nonexplicit
construction based on expander graphs.

All the above papers on the bit-probe model consider fixed-length block
coding. Variable-length source coding was investigated by Pananjady and
Courtade [29] who gave upper and lower bounds on the achievable rate for the
compression of sparse sequences under local decodability constraints. The
works [30, 31] considered simultaenous local decodability and update
efficiency. In particular, [30] designed a compressor whose average-case local
decodability (defined as the expected number of bits that need to be probed to
recover any $X_{i}$) and the average-case update efficiency (the expected
number of bits that need to be read and written in order to update a single
$X_{i}$) both scale as
$O\left(\frac{1}{\varepsilon^{2}}\log\frac{1}{\varepsilon}\right)$. In fact,
our scheme for distributed compression with locality is inspired by the
multilevel compression scheme in [30]. The paper [31] designed a compression
scheme whose worst-case local decodability and update efficiency scales as
$O(\log\log n)$. More recently, [32] implemented a version of the
concatenation scheme and evaluated its performance on practical datasets.

###  I-B Paper organization

In Section II, we introduce notions of localities and formally define the
problem. In Section III, we present our results. In Sections IV and V, we
prove the results, and in Section VI, we discuss the extension to more than
two sources. In Section VII, we draw concluding remarks.

##  II Preliminaries and Statement of the Problem

###  II-A Distributed compression without locality (Slepian-Wolf coding)

Let $(X^{n},Y^{n})$ be $n$ independent copies of a pair of random variables
$(X,Y)\sim p_{XY}$ defined over some alphabet ${\cal{X}}\times{\cal{Y}}$.
Without loss of generality, we assume that ${\cal{X}}=\\{x:p_{X}(x)>0\\}$ and
${\cal{Y}}=\\{y:p_{Y}(y)>0\\}$. Sequences $X^{n}$ and $Y^{n}$ represent two
sources of information separately encoded into binary codewords
$C^{nR_{1}}(X^{n})$ and $C^{nR_{2}}(Y^{n})$ at rate $R_{1}$ and $R_{2}$,
respectively. Upon receiving these codewords, a receiver outputs sources
estimates $(\hat{X}^{n},\hat{Y}^{n})$ and makes an error with probability

$P_{e}\overset{\text{def}}{=}\mathrm{Pr}[(\hat{X}^{n},\hat{Y}^{n})\neq({X}^{n},{Y}^{n})].$

The rate region is the closure of the set of rate pairs $(R_{1},R_{2})$ for
which $P_{e}\to 0$ as $n\to\infty$, and is given by:

######  Theorem 1 ([33], [34]).

The rate region of a source $p_{XY}$ is the set of pairs $(R_{1},R_{2})$ that
satisfy

$\displaystyle R_{1}$ $\displaystyle\geq H(X|Y)$ $\displaystyle R_{2}$
$\displaystyle\geq H(Y|X)$ $\displaystyle R_{1}+R_{2}$ $\displaystyle\geq
H(X,Y).$ (1)

Moreover, for any $(R_{1},R_{2})$ in the interior of the rate region, and any
$\varepsilon>0$, there exist a sequence of coding schemes operating at rates
at most $R_{1}+\varepsilon$ and $R_{2}+\varepsilon$ such that

$P_{e}\overset{\text{def}}{=}\mathrm{Pr}[(\hat{X}^{n},\hat{Y}^{n})\neq(X^{n},Y^{n})]\leq
2^{-n(E-\varepsilon)},$

where $E$ is a constant that depends on $R_{1},R_{2}$ and $p_{XY}$.

###  II-B Distributed compression with locality

####  II-B1 Local decoder

Given encodings $C^{nR_{1}}(X^{n})$ and $C^{nR_{2}}(Y^{n})$, a local decoder
takes as input $i\in[n]$,111$[n]\overset{\text{def}}{=}\\{1,2,\ldots,n\\}$ and
probes/reads a fixed set $\mathcal{I}_{i}$ of components from
$C^{nR_{1}}(X^{n})$ and $C^{nR_{2}}(Y^{n})$, which we simply denote as
$C_{\mathcal{I}_{i}}$,222In the sequel, we will use the same
$C_{\mathcal{I}_{i}}$ notation for both the two-source setup and the single
source setup. For the former, $C_{\mathcal{I}_{i}}$ refers to the set of
codewords components from $C^{nR_{1}}(X^{n})$ and $C^{nR_{2}}(Y^{n})$ used to
identify $(X_{i},Y_{1})$, and for the latter $C_{\mathcal{I}_{i}}$ refers to
the set of codeword components from $C^{nR}(X^{n})$ to identify $X_{i}$ only.
The worst-case local decodability and error probability are defined as

$d_{\mathrm{loc}}\overset{\text{def}}{=}\max_{1\leq i\leq n}d(i),$ (2)

where $d(i)\overset{\text{def}}{=}|\mathcal{I}_{i}|$, and

$P_{e}^{(\mathrm{loc})}\overset{\text{def}}{=}\max_{1\leq i\leq
n}\mathrm{Pr}[(\hat{X}_{i},\hat{Y}_{i})\neq(X_{i},Y_{i})].$

A few words about $\mathcal{I}_{i}$. Note first that $\mathcal{I}_{i}$ is
allowed to contain different sets of components from $C^{nR_{1}}$ and
$C^{nR_{2}}$. It should be non-adaptively chosen, that is, conditioned on the
index $i$, set $\mathcal{I}_{i}$ should be independent of $(X^{n},Y^{n})$.
Note that to $d_{\mathrm{loc}}$ adaptive queries correspond (at most)
$2^{d_{\mathrm{loc}}}$ non-adaptive queries. Therefore, a lower bound on the
probability of error for nonadaptive local decoders (the main contribution of
this paper) translates into a corresponding lower bound for adaptive decoders.
Finally, notice that even though $\mathcal{I}_{i}$ is non-adaptively chosen,
it could still be a random set, in which case $d(i)$ is defined as the
essential supremum of $|\mathcal{I}_{i}|$.

####  II-B2 Strong vs. weak locality

A rate pair $(R_{1},R_{2})$ is said to be achievable with _strong locality_ if

$P_{e}^{(\mathrm{loc})}=o(1)\quad\text{and}\quad
d_{\mathrm{loc}}=\Theta(1)\quad\text{as}\>\>n\to\infty.$

That is, by probing only a constant number (independent of $n$) of symbols,
the error probability of the local decoder goes to zero as the blocklength
increases. By contrast, $(R_{1},R_{2})$ is said to be achievable with _weak
locality_ if

$P_{e}^{(\mathrm{loc})}=o(1)\quad\text{and}\quad
d_{\mathrm{loc}}=\omega(1)\quad\text{as}\>\>n\to\infty.$

Weak locality is always achievable through the naive concatenation scheme that
decomposes source sequences $X^{n}$ and $Y^{n}$ into consecutive blocks of
size $b$

$X^{b}(j)\overset{\text{def}}{=}X_{(j-1)b+1}^{jb}\overset{\text{def}}{=}(X_{(j-1)b+1},X_{(j-1)b+1},\ldots,X_{jb})$
$Y^{b}(j)\overset{\text{def}}{=}Y_{(j-1)b+1}^{jb}\overset{\text{def}}{=}(Y_{(j-1)b+1},Y_{(j-1)b+1},\ldots,Y_{jb})$

for $j=1,2,\ldots$ and compresses each block $(X^{b}(j),Y^{b}(j))$
independently using a Slepian-Wolf code operating at the desired
$(R_{1},R_{2})$. Given $i\in[n]$, the local decoder accesses block $j=\lceil
i/b\rceil$ of each of the sources (thereby reads $b(R_{1}+R_{2})$ compressed
bits), and outputs the estimates of the $i$-th bit of $X^{n}$ and $Y^{n}$. By
letting $d_{\mathrm{loc}}=b(R_{1}+R_{2})$ in Theorem 1 we get:

######  Corollary 1 (Naive concatenation).

For any source $p_{XY}$ and any $(R_{1},R_{2})$ in the interior of the rate
region, the concatenation scheme achieves weak locality:

$P_{e}^{(\mathrm{loc})}\leq 2^{-\Theta(d_{\mathrm{loc}})}.$

###  II-C Statement of the problem

By contrast with weak locality, whether strong locality is generally
achievable is much less clear. In fact, it is only recently that strong
locality was shown to be achievable for the single source setup at any
lossless compression rate $R>H(X)$ [35, 36]. For the Slepian-Wolf setup at
hand, this result implies that strong locality holds for any $(R_{1},R_{2})$
such that $R_{1}>H(X)$ and $R_{2}>H(Y)$. In this regime, sources can be
encoded using the single source strongly local codes of [35, 36], separately
for source $X^{n}$ and source $Y^{n}$—and ignore dependency between $X^{n}$
and $Y^{n}$. Does this conclusion extend to the entire lossless rate region,
when at least one of the sources is encoded at a rate below its entropy?

##  III Main results

Our main result stated next answers the above question in the negative: if the
source is “confusable”, strong locality is impossible whenever one of the
sources is compressed below its entropy.

######  Definition 1 (Source confusability).

Source $p_{XY}$ is said to be $\mathcal{X}$-confusable if for every
$x_{1},x_{2}\in{\cal{X}}$, there exists $y\in{\cal{Y}}$ such that
$p_{XY}(x_{1},y)>0$ and $p_{XY}(x_{2},y)>0$.

Hence, any source with full support, that is $p_{XY}(x,y)>0$ for all
$(x,y)\in{\cal{X}}\times{\cal{Y}}$, is both $\mathcal{X}$\- and
$\mathcal{Y}$-confusable. An example of an $\mathcal{X}$-confusable source
which does not have full support is $p_{XY}$ where $p_{X}=$ Bernoulli($p$),
$0<p<1$, and where $p_{Y|X}$ is a $Z$ channel with crossover parameter
$0<\varepsilon<1$. If $p_{Y|X}$ is the perfect binary channel, then $p_{XY}$
is not confusable, and this is the only possibility if $\cal{X}$ and $\cal{Y}$
are binary.

The set of all codewords components probed by a local decoder to estimate
$(X_{i},Y_{i})$, or only $X_{i}$ for the single source setup, is simply
denoted as $C_{\mathcal{I}_{i}}$.

######  Theorem 2.

Suppose source $p_{XY}$ is $\mathcal{X}$-confusable. Suppose $X^{n}$ is
encoded into codeword $C^{nR_{1}}$ with $R_{1}<H(X)$. Then

$\max_{1\leq i\leq n}\mathrm{Pr}[\hat{X}_{i}(C_{{\mathcal{I}}_{i}},Y^{n})\neq
X_{i}]\geq 2^{-\Theta(d_{\mathrm{loc}})},$

where $\hat{X}_{i}(C_{{\mathcal{I}}_{i}},Y^{n})$ denotes any estimator of
source symbol $X_{i}$ given observations $C_{{\mathcal{I}}_{i}}$ and $Y^{n}$,
where $C_{{\mathcal{I}}_{i}}$ denotes any subset of the components
$C^{nR_{1}}$ with cardinality at most $d_{\mathrm{loc}}$.

This result says that if the source is $\mathcal{X}$-confusable, then strong
locality (even when restricted to the $X$-source only) is impossible whenever
$R_{1}<H(X)$; not even the full cooperation of the $Y$-transmitter through the
transmission of the uncompressed source $Y^{n}$ allows to achieve strong
locality. A particular version of this theorem for doubly symmetric sources,
where $p_{X}$ is the Bernoulli($1/2$) distribution and where $p_{Y|X}$
corresponds to a BSC($\rho$) for some crossover parameter $0<\rho<1/2$, was
proved in [37].

The $\mathcal{X}$-confusability property turns out to be necessary for Theorem
2 to hold:

######  Theorem 3.

Suppose source $p_{XY}$ is not $\mathcal{X}$-confusable. Then, it is possible
to achieve strong locality at some $R_{1}<H(X)$ and $R_{2}=H(Y)$.

###### Proof.

If $p_{XY}$ is not $\mathcal{X}$-confusable, then there exists
$x_{1},x_{2}\in\mathcal{X}$ such that, for any $y\in\mathcal{Y}$, either
$p_{XY}(x_{1},y)>0$ or $p_{XY}(x_{2},y)>0$ (recall that without loss of
generality $p_{Y}(y)>0$ for any $y\in{\cal{Y}}$). Therefore, conditioned on
$X\in\\{x_{1},x_{2}\\}$, the knowledge of $Y$ reveals whether $X=x_{1}$ or
$X=x_{2}$.

Let $\mathcal{X}=\\{1,2,\ldots,|{\cal{X}}|\\}$, and suppose without loss of
generality that $(x_{1},x_{2})=(1,2)$. Define the new source $U^{n}$ over the
reduced alphabet $\\{2,3,\ldots,|{\cal{X}}|\\}$ as

$U_{i}=\begin{cases}2&\text{ if }X_{i}\in\\{1,2\\}\\\ X_{i}&\text{ if
}X_{i}\neq\\{1,2\\}.\\\ \end{cases}$

Clearly, $H(U)<H(X)$ and $(U,Y)$ determine $(X,Y)$. We can therefore compress
$U^{n}$ and $Y^{n}$ independently at rates $R_{1}=H(U)<H(X)$ and $R_{2}=H(Y)$
using the compressors of [11, 10] to achieve strong locality. ∎

From Corollary 1, the naive concatenation scheme achieves a local error
probability that decays as $2^{-\Theta(d_{\mathrm{loc}})}$, and this is order
optimal by Theorem 2 for non-confusable sources. However, a weakness of the
concatenation scheme is that its local decoding procedure is tied to a
specific value of $d_{\mathrm{loc}}$ which is equal to the sub-block length
$b$. In particular, if $b=\Theta(1)$, then, because the concatenation scheme
encodes each sub-block independently, it is impossible to recover
$(X^{n},Y^{n})$ with vanishing probability of error as $n$ grows, even after
reading the entire compressed sequences(!) Our second contribution is a
compression scheme whose local decoder has an error probability that decreases
with the number of probed symbols. The performance of this scheme is given in
the following theorem:

######  Theorem 4.

For any $(R_{1},R_{2})$ in the interior of the rate region, there exists a
rate $(R_{1},R_{2})$ distributed compression scheme such that for every
$1>\eta>2^{-2^{O(\log n)}}$ specified at the decoder, the local decoder probes
$d_{\mathrm{loc}}=\mathrm{poly}(\log(1/\eta))$ bits and achieves
$P_{e}^{(\mathrm{loc})}\leq\eta$.

The above results easily generalize to more than two sources, see Section VI.

_Note:_ The present paper differs from the paper [37] submitted to ISIT 2022
mainly in that it establishes the impossibility of strong locality (Theorem 2)
for the most general class of sources (confusable sources), and not only for
the specific class of doubly symmetric binary sources. In fact, the arguments
used in [37] do not extend beyond sources with full-support. The arguments
used here are not only more general, but also more direct than those in [37].
Theorem 3 is new and [37] contains mostly a sketch of the proof of Theorem 4.
Theorems 5, 6, and 7 that extend the above results to more than two sources
(see Section VI) did not formally appear in [37].

##  IV Local Decoding Error Probability Lower bound

In this section we prove Theorem 2.

###  IV-A Preliminaries

######  Lemma 1 (Reverse hypercontractivity [38]).

Let $(V,W)$ be two random variables with full support distribution $p_{V,W}$
over some finite alphabet $\cal{V}\times\cal{W}$—$p_{V,W}(v,w)>0$ for all
$(v,w)\in\cal{V}\times\cal{W}$. Then, for every
$\mathcal{A}\subset{\cal{V}}^{n}$ and $\mathcal{B}\subset{\cal{W}}^{n}$, we
have

$\mathrm{Pr}[V^{n}\in\mathcal{A},W^{n}\in\mathcal{B}]\geq\left(\mathrm{Pr}[V^{n}\in\mathcal{A}]\right)^{\alpha}\left(\mathrm{Pr}[W^{n}\in\mathcal{B}]\right)^{\beta}$

for some finite constants $\alpha,\beta$.333More precisely, $\alpha$ and
$\beta$ are in $(1,\infty)$, but for the purpose of this paper the exact
values of $\alpha$ and $\beta$ (as functions of $p_{VW}$) are irrelevant.

One key element in proving Theorem 2 is to consider the following coupling.
Given $p_{X,Y}$, define random variable $\tilde{X}$ so that

$X-Y-\tilde{X}$

forms a Markov chain and so that444Hence, $(X,Y)$ and $(\tilde{X},Y)$ form a
coupling.

$p_{X|Y}=p_{\tilde{X}|Y}.$

Observe that if $p_{XY}$ is $\mathcal{X}$-confusable, then for any given
$(x,\tilde{x})\in{\cal{X}}\times{\cal{X}}$ there exists $y$, with $p_{Y}(y)>0$
(recall that without loss of generality $p_{Y}(y)>0$ for any $y\in{\cal{Y}}$),
for which

$p_{X,\tilde{X}}(x,\tilde{x}|y)=p_{X|Y}(x|y)p_{\tilde{X}|Y}(\widetilde{x}|y)>0.$

Hence, we have:

######  Lemma 2.

If $p_{XY}$ is $\mathcal{X}$-confusable, then $p_{X\widetilde{X}}$ has full
support.

######  Lemma 3 (Rate-distortion).

Let $X^{n}$ be an i.i.d. sequence encoded into binary codeword $C^{nR}$ at
rate $R<H(X)$. Suppose the code has a local decoder with worst-case local
decodability $d_{\mathrm{loc}}=\max_{1\leq i\leq n}d(i)\in[n]$. Then, there
exists a constant $\delta>0$ that depends only on $R$ such that for any
estimator $\hat{X}_{i}(C_{\mathcal{I}_{i}})$ of $X_{i}$ we have

$\delta\leq\max_{1\leq i\leq
n}\mathrm{Pr}[\hat{X}_{i}(C_{\mathcal{I}_{i}})\neq X_{i}],$

and for any maximizer index $i$ there exists $c\in\\{0,1\\}^{d(i)}$ such that

$\mathrm{Pr}[\hat{X}_{i}(C_{\mathcal{I}_{i}})\neq
X_{i},C_{\mathcal{I}_{i}}=c]\geq\delta 2^{-{d_{\mathrm{loc}}}}.$

###### Proof of Lemma 3.

The converse to Shannon’s lossy source coding theorem implies that if
$R<H(X)$, there exists a $\delta=\delta(R)>0$ such that

$\mathbb{E}d_{H}(X^{n},\hat{X}^{n})=\sum_{i=1}^{n}\mathrm{Pr}[\hat{X}_{i}(C_{\mathcal{I}_{i}})\neq
X_{i}]\geq n\delta$

where $d_{H}(X^{n},\hat{X}^{n})$ denotes the Hamming distance between $X^{n}$
and $\hat{X}^{n}$. Hence, there is at least one index $1\leq i\leq n$ such
that

$\delta\leq\mathrm{Pr}[\hat{X}_{i}(C_{\mathcal{I}_{i}})\neq X_{i}].$

Expanding the right-hand side and assuming a worst-case local decodability of
$d_{\mathrm{loc}}\in[n]$ we have

$\displaystyle\delta$
$\displaystyle\leq\mathrm{Pr}[\hat{X}_{i}(C_{\mathcal{I}_{i}})\neq X_{i}]$
$\displaystyle=\sum_{c\in\\{0,1\\}^{d(i)}}\mathrm{Pr}[\hat{X}_{i}(C_{\mathcal{I}_{i}})\neq
X_{i},C_{\mathcal{I}_{i}}=c]$ $\displaystyle\leq
2^{d_{\mathrm{loc}}}\max_{c\in\\{0,1\\}^{d(i)}}\mathrm{Pr}[\hat{X}_{i}(C_{\mathcal{I}_{i}})\neq
X_{i},C_{\mathcal{I}_{i}}=c].$

This concludes the proof. ∎

###  IV-B Proof of Theorem 2

Suppose $p_{XY}$ is confusable. Suppose $X^{n}$ is compressed at rate
$R_{1}<H(X)$, and that the local decoder has locality $d_{\mathrm{loc}}$. From
Lemma 3, there exists an index $i\in[n]$ and a local codeword
$c\in\\{0,1\\}^{d(i)}$, with $d(i)\leq d_{\mathrm{loc}}$, such that

$\mathrm{Pr}[X_{i}\neq\bar{x},C_{\mathcal{I}_{i}}=c]\geq\delta
2^{-{d_{\mathrm{loc}}}}\geq\delta|\mathcal{X}|^{-d_{\mathrm{loc}}},$ (3)

where

$\bar{x}\overset{\text{def}}{=}\arg\max_{x}\mathrm{Pr}[X_{i}=x|C_{\mathcal{I}_{i}}(X^{n})=c]$

is the MAP estimate given $C_{\mathcal{I}_{i}}=c$. Moreover, it must be the
case that

$\mathrm{Pr}[X_{i}=\bar{x}|C_{\mathcal{I}_{i}}=c]\geq\frac{1}{|\mathcal{X}|},$
(4)

for otherwise the probabilities would not sum to one. From (3) and (4) it then
follows that

$\mathrm{Pr}[X_{i}=\bar{x},C_{\mathcal{I}_{i}}=c]=\mathrm{Pr}[X_{i}=\bar{x}|C_{\mathcal{I}_{i}}=c]\mathrm{Pr}[C_{\mathcal{I}_{i}}=c]\geq\delta\frac{2^{-{d_{\mathrm{loc}}}}}{|\mathcal{X}|}\geq\delta|\mathcal{X}|^{-d_{\mathrm{loc}}-1}.$
(5)

The key to proving Theorem 2 is the following lemma:

######  Lemma 4.

Fix source $p_{XY}$. Suppose $X^{n}$ is encoded into codeword $C^{nR}(X^{n})$
at some rate $R\geq 0$. Fix $i\in[n]$ and let
$\hat{X}_{i}(C_{\mathcal{I}_{i}},Y^{n})$ be an estimator of $X_{i}$ with the
knowledge of both $C_{\mathcal{I}_{i}}(X^{n})$ and $Y^{n}$. Then, for any
realization $c$ of $C_{\mathcal{I}_{i}}(X^{n})$, we have:

$\mathrm{Pr}(\hat{X}_{i}(C_{\mathcal{I}_{i}},Y^{n})\neq
X_{i},C_{\mathcal{I}_{i}}(X^{n})=c)\geq\mathrm{Pr}[X_{i}=\bar{x},\tilde{X}_{i}\neq\bar{x},C_{\mathcal{I}_{i}}(X^{n})=C_{\mathcal{I}_{i}}(\tilde{X}^{n})=c]$

where

$\bar{x}\overset{\text{def}}{=}\arg\max_{x}\mathrm{Pr}[X_{i}=x|C_{\mathcal{I}_{i}}(X^{n})=c].$

###### Proof of Theorem 2.

Suppose the source is confusable and suppose $X^{n}$ is compressed at rate
$R_{1}<H(X)$. From Lemma 4, we have

$\displaystyle\mathrm{Pr}(\hat{X}_{i}(C_{\mathcal{I}_{i}},Y^{n})\neq
X_{i},C_{\mathcal{I}_{i}}(X^{n})=c)$
$\displaystyle\geq\mathrm{Pr}[X_{i}=\bar{x},\tilde{X}_{i}\neq\bar{x},C_{\mathcal{I}_{i}}(X^{n})=C_{\mathcal{I}_{i}}(\tilde{X}^{n})=c].$

Now, since $p_{XY}$ is confusable, we have that $p_{X\widetilde{X}}$ has full
support by Lemma 2, and therefore from Lemma 1 there exist finite constants
$\alpha,\beta$ such that

$\displaystyle\mathrm{Pr}[X_{i}=\bar{x},\tilde{X}_{i}\neq\bar{x},C_{\mathcal{I}_{i}}(X^{n})=C_{\mathcal{I}_{i}}(\tilde{X}^{n})=c]$
$\displaystyle\geq(\mathrm{Pr}[X_{i}=\bar{x},C_{\mathcal{I}_{i}}(X^{n})=c])^{\alpha}(\mathrm{Pr}[\tilde{X}_{i}\neq\bar{x},C_{\mathcal{I}_{i}}(\tilde{X}^{n})=c])^{\beta}$
$\displaystyle=2^{-\Theta(d_{\mathrm{loc}})},$

where the equality follows from (5). We therefore conclude that

$\mathrm{Pr}(\hat{X}_{i}(C_{\mathcal{I}_{i}},Y^{n})\neq X_{i})\geq
2^{-\Theta(d_{\mathrm{loc}})},$

which completes the proof. ∎

###### Proof of Lemma 4.

For any estimator $\hat{X}_{i}(C_{\mathcal{I}_{i}},Y^{n})$ of $X_{i}$, we have

$\displaystyle\mathrm{Pr}(\hat{X}_{i}(C_{\mathcal{I}_{i}},Y^{n})\neq
X_{i},\;C_{\mathcal{I}_{i}}(X^{n})=c)\geq\mathrm{Pr}(\hat{E}(C_{\mathcal{I}_{i}},Y^{n})\neq
E(X_{i}),\;C_{\mathcal{I}_{i}}(X^{n})=c)$
$\displaystyle=\sum_{y^{n}}\mathrm{Pr}(\hat{E}(C_{\mathcal{I}_{i}},Y^{n})\neq
E(X_{i}),\;C_{\mathcal{I}_{i}}(X^{n})=c|Y^{n}=y^{n})\mathrm{Pr}(Y^{n}=y^{n})$
$\displaystyle\geq\sum_{y^{n}}\mathrm{Pr}(Y^{n}=y^{n})\min\\{\mathrm{Pr}[X_{i}=\bar{x},\;C_{\mathcal{I}_{i}}(X^{n})=c|Y^{n}=y^{n}],\mathrm{Pr}[X_{i}\neq\bar{x},\;C_{\mathcal{I}_{i}}(X^{n})=c|Y^{n}=y^{n}]\\}$
(6)

where $\hat{E}(C_{\mathcal{I}_{i}},Y^{n})$ is an estimator of the binary
random variable $E(X_{i})$, defined to be equal to zero if $X_{i}=\bar{x}$ and
one if $X_{i}\neq\bar{x}$; and where the right-hand side of the second
inequality is the error probability of the optimal (MAP) estimator $\hat{X}$
with the foreknowledge of $Y^{n}$.

By multiplying the minimum on the right-hand side by

$\max\\{\mathrm{Pr}[X_{i}=\bar{x},\;C_{\mathcal{I}_{i}}(X^{n})=c|Y^{n}=y^{n}],\mathrm{Pr}[X_{i}\neq\bar{x},C_{\mathcal{I}_{i}}(X^{n})=c|Y^{n}=y^{n}]\\},$

which is at most one, from (IV-B) we get

$\displaystyle\mathrm{Pr}(\hat{X}_{i}(C_{\mathcal{I}_{i}},Y^{n})\neq
X_{i},\;C_{\mathcal{I}_{i}}(X^{n})=c)\geq\sum_{y^{n}}\mathrm{Pr}(Y^{n}=y^{n})\bigg{(}\min\\{\cdot\\}\times\max\\{\cdot\\}\bigg{)}$
$\displaystyle=\sum_{y^{n}}\mathrm{Pr}(Y^{n}=y^{n})\mathrm{Pr}[X_{i}=\bar{x},C_{\mathcal{I}_{i}}(X^{n})=c|Y^{n}=y^{n}]\times\mathrm{Pr}[X_{i}\neq\bar{x},C_{\mathcal{I}_{i}}(X^{n})=c|Y^{n}=y^{n}]$
$\displaystyle=\sum_{y^{n}}\mathrm{Pr}(Y^{n}=y^{n})\mathrm{Pr}[X_{i}=\bar{x},C_{\mathcal{I}_{i}}(X^{n})=c|Y^{n}=y^{n}]\times\mathrm{Pr}[\tilde{X}_{i}=\bar{x},C_{\mathcal{I}_{i}}(\tilde{X}^{n})=c|Y^{n}=y^{n}]$
$\displaystyle=\mathrm{Pr}[X_{i}=\bar{x},\tilde{X}_{i}\neq\bar{x},C_{\mathcal{I}_{i}}(X^{n})=C_{\mathcal{I}_{i}}(\tilde{X}^{n})=c]$

where the second equality follows from the Markov chain $X-Y-\tilde{X}$. This
yields the desired result. ∎

##  V An explicit local decoder

We now describe a locally decodable compression scheme that has the properties
guaranteed by Theorem 4.

We want a scheme that achieves the following: For any fixed $\delta>0$ and
$(R_{1},R_{2})$ within the Slepian-Wolf rate region,

  * •

The sequences $(X^{n},Y^{n})$ are independently compressed to rates
$(R_{1}+\delta,R_{2}+\delta)$ respectively.

  * •

For any $i\in[n]$ and $1>\eta>2^{-2^{O(\log n)}}$ specified at the receiver,
the local decoder probes $\mathrm{poly}(\log(1/\eta))$ compressed bits, and
outputs $(\hat{X}_{i},\hat{Y}_{i})$ which satisfies

$P_{e}^{(\mathrm{loc})}=\mathrm{Pr}[(\hat{X}_{i},\hat{Y}_{i})\neq(X_{i},Y_{i})]\leq\eta.$

Our coding scheme is inspired by that in [30], and is a hierarchical
compression scheme. The compressed bits consist of various blocks and are
spread across multiple “levels” $1\leq\ell\leq\ell_{\max}$. At level $\ell=0$,
each compressed block is obtained by encoding constant-sized substrings of the
source using a standard Slepian-Wolf code. The compressed bits at level 0 is
obtained by applying the naive concatenation scheme defined in Section II-B2
with $b=O(1)$. This guarantees that any pair of source symbols can be
recovered with $2^{-\Theta(b)}=O(1)$ probability of error. The compressed bits
at the higher level can be viewed as additional refinement bits that are
probed only when we desire a lower probability of error. By probing blocks
corresponding to higher levels, we obtain a more reliable estimate of
$(X_{i},Y_{i})$. The compressed blocks at level $\ell$ are obtained by using a
random binning scheme applied to blocks of size $b_{\ell}$, where $b_{\ell}$
is growing with $\ell$. However, the rates for higher levels is chosen to
decay with $\ell$. The key challenge is to choose the parameters carefully so
that the additional bits corresponding to higher levels essentially lead to no
loss in terms of the overall compression rates.

####  V-1 Parameters

We choose555Since we only aim to get order-optimal results, we have not
attempted to optimize over the various parameters. a sufficiently small
$\varepsilon_{0}>0$, positive integers

$b_{0}=n_{0}$ (7)

which are constants independent of $n$, and

$k_{0}^{(1)}=\lceil(R_{1}+\varepsilon_{0})b_{0}\rceil\text{ and
}k_{0}^{(2)}=\lceil(R_{2}+\varepsilon_{1})b_{1}\rceil$ (8)

such that the probability of error of a Slepian-Wolf code for sequences of
length $b_{0}$ satisfies

$\mathrm{Pr}[(\hat{X}^{b_{0}},\hat{Y}^{b_{0}})\neq(X^{b_{0}},Y^{b_{0}})]\leq
2^{-\beta\varepsilon_{0}b_{0}}\leq\delta^{\prime}$

where $\beta>0$ depends on $p_{XY},R_{1},R_{2}$ only and $0<\delta^{\prime}<1$
is a parameter that determines an upper bound on the probability of local
decoding error that can be achieved.

For each $\ell=1,2,\ldots,\ell_{\mathrm{max}}$, define

$\displaystyle\varepsilon_{\ell}$
$\displaystyle=\varepsilon_{\ell-1}/2=\epsilon_{0}/2^{\ell}$ $\displaystyle
b_{\ell}$ $\displaystyle=16b_{\ell-1}=16^{\ell}b_{0}$ $\displaystyle n_{\ell}$
$\displaystyle=b_{\ell}n_{\ell-1}=4^{\ell(\ell+1)}b_{0}^{\ell+1}$
$\displaystyle k_{\ell}^{(1)}$
$\displaystyle=\varepsilon_{\ell}n_{\ell}\left(\beta+|\mathcal{X}|+\frac{b_{\ell}}{n_{\ell}}\log\frac{e2^{\ell}}{\varepsilon_{0}}\right)$
$\displaystyle k_{\ell}^{(2)}$
$\displaystyle=\varepsilon_{\ell}n_{\ell}\left(\beta+|\mathcal{Y}|+\frac{b_{\ell}}{n_{\ell}}\log\frac{e2^{\ell}}{\varepsilon_{0}}\right)$
(9)

####  V-2 Encoder

The encoder works as follows:

  * •

_Level 0:_ At this level, each encoder partitions the $n$ symbols it has
(i.e., $X^{n}$ or $Y^{n}$) into blocks of $b_{0}$ consecutive symbols each,
and compresses this using a standard Slepian-Wolf code where the compressed
lengths are given by (8). To set up some notation, let us define for
$i=1,2,\ldots,n/b_{0}$, the $i$th (source) block at level $0$ to be
$X^{b_{0}}(0,i)=X_{(i-1)b_{0}+1}^{ib_{0}}$, and
$Y^{b_{0}}(0,i)=Y_{(i-1)b_{0}+1}^{ib_{0}}$. Likewise, let
$U^{k_{0}^{(1)}}(0,i)$ and $V^{k_{0}^{(2)}}(0,i)$ denote the respective
compressed blocks at level $0$, i.e., these are obtained by applying the
Slepian-Wolf random binning encoder [39, Chapter 10] on $X^{b_{0}}(0,i)$ and
$Y^{b_{0}}(0,i)$ respectively. For every sequence in $\mathcal{X}^{b_{0}}$
(resp. $\mathcal{Y}^{b_{0}}$), we assign a codeword of length $k_{0}^{(1)}$
(resp. $k_{0}^{(2)}$) independently and uniformly at random and this is used
to encode each $X^{b_{0}}(0,i)$ (resp. $Y^{b_{0}}(0,i)$). The compressed
blocks are therefore random hashes of the respective source blocks.

  * •

_Level $\ell$, for $\ell>0$:_ At higher levels, the compression works
similarly. The respective encoders obtain $U^{k_{\ell}^{(1)}}(\ell,i)$ and
$V^{k_{\ell}^{(2)}}(\ell,i)$ by taking random hashes of
$X^{n_{\ell}}(\ell,i)=X_{(i-1)n_{\ell}+1}^{in_{\ell}}$ and
$Y^{n_{\ell}}(\ell,i)=X_{(i-1)n_{\ell}+1}^{in_{\ell}}$ respectively (for
$\ell=1,2,\ldots,\ell_{\mathrm{max}}$). In other words, for every sequence of
length $n_{\ell}$, we assign a codeword of length $k_{\ell}^{(1)}$ (to encode
$X^{n}$) or $k_{\ell}^{(2)}$ (to encode $Y^{n}$) independently and uniformly
at random.

It is worth pointing out that most of the entropy of the compressed sequence
lies in the level-0 codewords. For $\ell>0$, the rates
$k_{\ell}^{(1)}/n_{\ell}$ and $k_{\ell}^{(2)}/n_{\ell}$ are exponentially
decaying functions of $\ell$.

####  V-3 Local decoder

The local decoder takes two parameters as input: a location $i\in[n]$, and
$\ell_{d}\in\\{0,1,2,\ldots,\ell_{\mathrm{max}}\\}$. The first parameter
specifies which $(X_{i},Y_{i})$ the decoder wishes to recover. The second
parameter specifies the number of bits to probe (which decides the probability
of error). For a specified $\ell_{d}$, the local decoder probes
$2^{O(\ell_{d}^{2})}$ compressed bits, and the probability of error is
$2^{-2^{\tilde{O}(\ell_{d}^{2})}}$. This statement will be made more precise
shortly.

The decoder works by probing compressed bits up to level $\ell_{d}$ as
follows:

  * •

The decoder first finds which level-$\ell_{d}$ chunk the desired location $i$
lies in. In other words, it sets $i_{\ell_{d}}=\lceil i/n_{\ell_{d}}\rceil$.
It then reads all the compressed chunks up to level $\ell_{d}$ corresponding
to the symbols $X_{(i_{d}-1)n_{\ell_{d}}+1}^{i_{d}n_{\ell_{d}}}$.

  * •

The decoder now iteratively improves its estimate by processing the compressed
bits from level $0$ to level $\ell_{d}$ as follows:

    * –

At level 0, the decoder uses the Slepian-Wolf decoder to obtain the level-0
estimates of $X_{(i_{d}-1)n_{\ell_{d}}+1}^{i_{d}n_{\ell_{d}}}$. Call this
estimate as $\hat{X}_{(i_{d}-1)n_{\ell_{d}}+1}^{i_{d}n_{\ell_{d}}}(0)$.

    * –

For all subsequent levels $\ell\in\\{1,2,\ldots,\ell_{d}\\}$, the decoder does
the following. Suppose that we want to estimate
$(X^{n_{\ell}}(\ell,i),Y^{n_{\ell}}(\ell,i))$ assuming that we already have
the level $\ell-1$ estimate. The decoder outputs
$(\hat{X}^{{n_{\ell}}}(\ell,i),\hat{Y}^{{n_{\ell}}}(\ell,i))=(x^{n_{\ell}},y^{n_{\ell}})$
if $(x^{n_{\ell}},y^{n_{\ell}})$ is the unique pair of sequences which match
$U^{k_{\ell}^{(1)}}(\ell,i),V^{k_{\ell}^{(2)}}(\ell,i)$ and also match at
least $(1-\varepsilon_{\ell})b_{\ell}$ of the level-$(\ell-1)$ estimated
blocks. If there is no such unique sequence, then the level-$\ell$ decoder
outputs the zero sequence.

######  Lemma 5.

For any given parameters $(i,\ell_{d})$, the number of bits probed by the
local decoder is

$d_{\mathrm{loc}}(\ell_{d})\leq
b_{0}^{\ell_{d}+1}4^{\ell_{d}(\ell_{d}+1)}(R_{1}+R_{2}+\gamma_{1}\varepsilon_{0})\leq
2^{\gamma_{2}\ell_{d}^{2}}$

where $\gamma_{1}$ is a constant that only depends on $p_{XY},R_{1},R_{2}$,
while $\gamma_{2}$ may depend on $p_{XY},R_{1},R_{2},\varepsilon_{0},b_{0}$.

###### Proof.

The total number of compressed bits probed is equal to

$\displaystyle d_{\mathrm{loc}}(\ell_{d})$
$\displaystyle=\sum_{\ell=0}^{\ell_{d}}\frac{n_{\ell_{d}}}{n_{\ell}}(k_{\ell}^{(1)}+k_{\ell}^{(2)})$
$\displaystyle\leq n_{\ell_{d}}(R_{1}+R_{2}+\gamma_{2}\varepsilon_{0})$
$\displaystyle=b_{0}^{\ell_{d}+1}4^{\ell_{d}(\ell_{d}+1)}(R_{1}+R_{2}+\gamma_{1}\varepsilon_{0})$

where $\gamma_{1}$ is a constant that only depends on $p_{XY},R_{1},R_{2}$. ∎

######  Lemma 6.

For any given parameters $(i,\ell_{d})$, the probability of error of decoding
$X^{n_{\ell_{d}}},Y^{n_{\ell_{d}}}$ after decoding up to level $\ell_{d}$ is
upper bounded as follows

$P_{e}^{(\ell_{d})}\leq
2^{-\beta(\varepsilon_{0}b_{0})^{\ell+1}2^{\ell^{2}}}=2^{-2^{O(\log
d_{\mathrm{loc}}(\ell_{d}))}}$

###### Proof.

We will derive the bound by obtaining an upper bound on $P_{e}^{(\ell)}$ in
terms of $P_{e}^{(\ell-1)}$. For $\ell=0$, we know that

$P_{e}^{(0)}\leq 2^{-\beta\varepsilon_{0}b_{0}}$

for a suitable constant $\beta>0$.

For decoding at level $\ell>1$, there are two possible error events:

  1. 1.

Event $\mathcal{E}_{1}$: More than $\varepsilon_{\ell}b_{\ell}$ blocks were
decoded incorrectly at level $\ell-1$

  2. 2.

Event $\mathcal{E}_{2}$: There is an incorrect pair of sequences
$(\tilde{x}^{n_{\ell}},\tilde{y}^{n_{\ell}})$ that has the same level-$\ell$
hash/codeword as the true sequence and matches the $(\ell-1)$-level decoded
sequence on at least $(1-\varepsilon_{\ell})b_{\ell}$ blocks.

The overall probability of error is then

$P_{e}^{(\ell)}\leq\mathrm{Pr}[\mathcal{E}_{1}]+\mathrm{Pr}[\mathcal{E}_{2}|\mathcal{E}_{1}^{c}].$

We will bound the two terms separately. For the first term, observe that

$\displaystyle\mathrm{Pr}[\mathcal{E}_{1}]$
$\displaystyle\leq\begin{pmatrix}b_{\ell}\\\
\varepsilon_{\ell}b_{\ell}\end{pmatrix}\left(P_{e}^{(\ell-1)}\right)^{\varepsilon_{\ell}b_{\ell}}$
$\displaystyle\leq\left(\frac{eP_{e}^{(\ell-1)}}{\varepsilon_{\ell}}\right)^{\varepsilon_{\ell}b_{\ell}}$
$\displaystyle\leq\left(\frac{e2^{-\beta(\varepsilon_{0}b_{0})^{\ell}2^{(\ell-1)^{2}}}}{\varepsilon_{0}/2^{\ell}}\right)^{\varepsilon_{0}b_{0}8^{\ell}}$

where in the last step, we have assumed that $P_{e}^{(\ell-1)}\leq
2^{-\beta(\varepsilon_{0}b_{0})^{\ell}2^{(\ell-1)^{2}}}$. Rewriting the right-
hand side, we get

$\displaystyle\mathrm{Pr}[\mathcal{E}_{1}]$
$\displaystyle\leq\exp_{2}\left(-\beta(\varepsilon_{0}b_{0})^{\ell+1}2^{\ell^{2}+\ell+1}+\log\left(\frac{e2^{\ell}}{\varepsilon_{0}}\epsilon_{0}b_{0}8^{\ell}\right)\right)$

Since $\varepsilon_{0}b_{0}$ is large enough, the second term is at least
twice that of the first. Therefore,

$\displaystyle\mathrm{Pr}[\mathcal{E}_{1}]$
$\displaystyle\leq\exp_{2}\left(-\beta(\varepsilon_{0}b_{0})^{\ell+1}2^{\ell^{2}+\ell}\right)\leq\frac{2^{-\beta(\varepsilon_{0}b_{0})^{\ell+1}2^{\ell^{2}}}}{2}$
(10)

To compute the probability of the second error event, let us define
$\mathcal{E}_{2}^{A}$ (resp. $\mathcal{E}_{2}^{B}$) to be the event that there
is an incorrect sequences $\tilde{x}^{n_{\ell}}$ (resp.
$\tilde{y}^{n_{\ell}})$) that has the same hash as the true sequence and
matches the $(\ell-1)$-level decoded sequence on at least
$(1-\varepsilon_{\ell})b_{\ell}$ blocks. We have,

$\displaystyle\mathrm{Pr}[\mathcal{E}_{2}^{A}|\mathcal{E}_{1}^{c}]$
$\displaystyle\leq\begin{pmatrix}b_{\ell}\\\
\varepsilon_{\ell}b_{\ell}\end{pmatrix}|\mathcal{X}|^{\varepsilon_{\ell}n_{\ell}}2^{-k_{\ell}^{(1)}}$
$\displaystyle\leq\left(\frac{e}{\varepsilon_{\ell}}\right)^{\varepsilon_{\ell}b_{\ell}}|\mathcal{X}|^{\varepsilon_{\ell}n_{\ell}}2^{-k_{\ell}^{(1)}}$

Substituting for $k_{\ell}^{(1)}$ in the above and simplifying, we get

$\mathrm{Pr}[\mathcal{E}_{2}^{A}|\mathcal{E}_{1}^{c}]\leq
2^{-\beta\epsilon_{\ell}n_{\ell}}\leq\frac{2^{-\beta(\varepsilon_{0}b_{0})^{\ell+1}2^{\ell^{2}}}}{4}$
(11)

Similarly,

$\mathrm{Pr}[\mathcal{E}_{2}^{B}|\mathcal{E}_{1}^{c}]\leq
2^{-\beta\epsilon_{\ell}n_{\ell}}\leq\frac{2^{-\beta(\varepsilon_{0}b_{0})^{\ell+1}2^{\ell^{2}}}}{4}$
(12)

Combining (10), (11) and (12), we get

$\displaystyle P_{e}^{(\ell)}$
$\displaystyle\leq\mathrm{Pr}[\mathcal{E}_{1}]+\mathrm{Pr}[\mathcal{E}_{2}^{A}|\mathcal{E}_{1}^{c}]+\mathrm{Pr}[\mathcal{E}_{2}^{B}|\mathcal{E}_{1}^{c}]$
$\displaystyle\leq 2^{-\beta(\varepsilon_{0}b_{0})^{\ell+1}2^{\ell^{2}}},$

which completes the proof. ∎

##  VI Extension to $k>2$ sources

We first extend Theorem 2 to a $k$-source distribution
$p_{X_{1},\ldots,X_{k}}$ defined over alphabet
$\mathcal{X}_{1}\times\cdots\times\mathcal{X}_{k}$. Let the source be
$\mathcal{X}_{1}$-confusable if for every
$x_{1},x_{1}^{\prime}\in\mathcal{X}_{1}$, there exist
$(x_{2},x_{3},\ldots,x_{k})$ for which
$p_{X_{1},\ldots,X_{k}}(x_{1},\ldots,x_{k})>0$ and
$p_{X_{1},\ldots,X_{k}}(x_{1}^{\prime},\ldots,x_{k})>0$. Observe that this
condition holds if and only if for every
$x_{1},x_{1}^{\prime}\in\mathcal{X}_{1}$, there exist an index $i\geq 2$ and
$x_{i}\in\mathcal{X}_{i}$ for which $p_{X_{1}X_{i}}(x_{1},x_{i})>0$ and
$p_{X_{1},X_{i}}(x_{1}^{\prime},x_{i})>0$. Now if we repeat the same line of
arguments as for the proof of Theorem 2, but with the side information $Y^{n}$
replaced by all sources except $X_{1}^{n}$, that is
$X_{2}^{n},\ldots,X_{k}^{n}$, we get:

######  Theorem 5 (Confusable, $k\geq 2$ sources).

Suppose source $p_{X_{1},\ldots,X_{k}}$ is $\mathcal{X}_{1}$-confusable. If
$X^{n}_{1}$ is compressed at rate $R_{1}<H(X_{1})$, then

$\max_{1\leq i\leq
n}\mathrm{Pr}[\hat{X}_{1i}(C_{{\mathcal{I}}_{1i}}(X^{n}_{1}),X_{2}^{n},\ldots,X_{k}^{n})\neq
X_{1i}]\geq 2^{-\Theta(d_{\mathrm{loc}})},$

where
$\hat{X}_{1i}(C_{{\mathcal{I}}_{1i}}(X^{n}_{1}),X_{2}^{n},\ldots,X_{k}^{n})$
is any estimator of the $i$-th symbol of source $X_{1}^{n}$ given at most
$d_{\mathrm{loc}}$ components $C_{{\mathcal{I}}_{1i}}(X^{n}_{1})$ of
$C^{nR_{1}}(X_{1}^{n})$ and $(X_{2}^{n},\ldots,X_{k}^{n})$.

Similarly, Theorem 3 immediately generalizes to

######  Theorem 6 (Non-confusable, $k\geq 2$ sources ).

Suppose source $p_{X_{1},\ldots,X_{k}}$ is not $\mathcal{X}_{1}$-confusable.
Then, it is possible to achieve strong locality at some $R_{1}<H(X_{1})$ and
$R_{i}=H(X_{i})$, $i\in\\{2,\ldots,k\\}$.

The coding scheme of Section V easily extends to more than two sources, with
the same encoding scheme for each source, and an identical local decoder:

######  Theorem 7 (Hierarchical coding scheme, $k\geq 2$ sources).

For any $(R_{1},R_{2},\ldots,R_{k})$ in the interior of the Slepian-Wolf rate
region, there exists a rate $(R_{1},R_{2},\ldots,R_{k})$ distributed
compression scheme such that for every $1>\eta>2^{-2^{O(\log n)}}$, the local
decoder achieves $d_{\mathrm{loc}}=\mathrm{poly}(\log(1/\eta))$ and
$P_{e}^{(\mathrm{loc})}\leq\eta$.

##  VII Concluding Remarks

In contrast with the single source set up, we showed that for multiple sources
lossless compression and strong locality can generally not be accommodated.
For the broad class of confusable sources, for strong locality to hold all
sources must be compressed at rates above their respective entropies. On the
other hand, if the distribution is not confusable, an arguably peculiar
situation, strong locality may hold even if compression rates are belo
individual entropies. For this case, the characterization of all rate pairs
for which strong locality can be achieved remains an open problem.

Our compression scheme is able to achieve
$d_{\mathrm{loc}}={\mathrm{poly}}(\log(1/\eta))$ for any target probability of
local decoding error $\eta$ specified at the decoder. Note that from our lower
bound, $d_{\mathrm{loc}}=\Omega(\log(1/\eta))$ and our scheme is suboptimal by
a polynomial factor. Designing an improved scheme that achieves this lower
bound is left as future work.

In this paper, we only considered the problem of local decodability in the
context of distributed compression. One may also require provisioning of local
substitutions/insertions/deletions of source symbols in the compressed domain.
This is an interesting problem that warrants more attention.

## References

  * [1] D. S. Pavlichin, T. Weissman, and G. Yona, “The human genome contracts again,” _Bioinformatics_ , vol. 29, no. 17, pp. 2199–2202, 2013.
  * [2] D. Pavlichin, T. Weissman, and G. Mably, “The quest to save genomics: Unless researchers solve the looming data compression problem, biomedical science could stagnate,” _IEEE Spectrum_ , vol. 55, no. 9, pp. 27–31, 2018.
  * [3] C. P. Chen and C.-Y. Zhang, “Data-intensive applications, challenges, techniques and technologies: A survey on big data,” _Information Sciences_ , vol. 275, pp. 314–347, 2014.
  * [4] I. A. T. Hashem, I. Yaqoob, N. B. Anuar, S. Mokhtar, A. Gani, and S. U. Khan, “The rise of “big data” on cloud computing: Review and open research issues,” _Information systems_ , vol. 47, pp. 98–115, 2015.
  * [5] M. P. Ball, J. V. Thakuria, A. W. Zaranek, T. Clegg, A. M. Rosenbaum, X. Wu, M. Angrist, J. Bhak, J. Bobe, M. J. Callow _et al._ , “A public resource facilitating clinical use of genomes,” _Proceedings of the National Academy of Sciences_ , vol. 109, no. 30, pp. 11 920–11 927, 2012.
  * [6] U. consortium _et al._ , “The uk10k project identifies rare variants in health and disease,” _Nature_ , vol. 526, no. 7571, p. 82, 2015.
  * [7] E. E. Schadt, M. D. Linderman, J. Sorenson, L. Lee, and G. P. Nolan, “Computational solutions to large-scale data management and analysis,” _Nature reviews genetics_ , vol. 11, no. 9, p. 647, 2010.
  * [8] J. Ziv and A. Lempel, “A universal algorithm for sequential data compression,” _IEEE Transactions on Information Theory_ , vol. 23, no. 3, pp. 337–343, 1977.
  * [9] ——, “Compression of individual sequences via variable-rate coding,” _IEEE Transactions on Information Theory_ , vol. 24, no. 5, pp. 530–536, 1978\.
  * [10] A. Mazumdar, V. Chandar, and G. W. Wornell, “Local recovery in data compression for general sources,” in _Proceedings of the 2015 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2015, pp. 2984–2988.
  * [11] K. Tatwawadi, S. Bidokhti, and T. Weissman, “On universal compression with constant random access,” in _Proceedings of the 2018 IEEE International Symposium on Information Theory_ , 2018, pp. 891–895.
  * [12] M. Patrascu, “Succincter,” in _2008 49th Annual IEEE Symposium on Foundations of Computer Science_. IEEE, 2008, pp. 305–313.
  * [13] Y. Dodis, M. Patrascu, and M. Thorup, “Changing base without losing space,” in _Proceedings of the forty-second ACM symposium on Theory of computing_ , 2010, pp. 593–602.
  * [14] J. I. Munro and Y. Nekrich, “Compressed data structures for dynamic sequences,” in _Algorithms-ESA 2015_. Springer, 2015, pp. 891–902.
  * [15] R. Raman and S. S. Rao, “Succinct dynamic dictionaries and trees,” in _International Colloquium on Automata, Languages, and Programming_. Springer, 2003, pp. 357–368.
  * [16] V. Chandar, D. Shah, and G. W. Wornell, “A locally encodable and decodable compressed data structure,” in _Proceedings of the 47th Annual Allerton Conference on Communication, Control, and Computing_. IEEE, 2009, pp. 613–619.
  * [17] V. B. Chandar, “Sparse graph codes for compression, sensing and secrecy,” Ph.D. dissertation, MIT, 2010.
  * [18] S. Kreft and G. Navarro, “LZ77-like compression with fast random access,” in _2010 Data Compression Conference_. IEEE, 2010, pp. 239–248.
  * [19] A. Dutta, R. Levi, D. Ron, and R. Rubinfeld, “A simple online competitive adaptation of lempel-ziv compression with efficient random access support,” in _Proceedings of the Data Compression Conference (DCC)_. IEEE, 2013, pp. 113–122.
  * [20] P. Bille, G. M. Landau, R. Raman, K. Sadakane, S. R. Satti, and O. Weimann, “Random access to grammar-compressed strings,” in _Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms_. Society for Industrial and Applied Mathematics, 2011, pp. 373–389.
  * [21] E. Viola, O. Weinstein, and H. Yu, “How to store a random walk,” _arXiv preprint arXiv:1907.1087_ , 2019.
  * [22] K. Sadakane and R. Grossi, “Squeezing succinct data structures into entropy bounds,” in _Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm_. Society for Industrial and Applied Mathematics, 2006, pp. 1230–1239.
  * [23] R. González and G. Navarro, “Statistical encoding of succinct data structures,” in _Annual Symposium on Combinatorial Pattern Matching_. Springer, 2006, pp. 294–305.
  * [24] P. Ferragina and R. Venturini, “A simple storage scheme for strings achieving entropy bounds,” in _Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms_. Society for Industrial and Applied Mathematics, 2007, pp. 690–696.
  * [25] A. Makhdoumi, S.-L. Huang, M. Medard, and Y. Polyanskiy, “On locally decodable source coding,” in _2015 IEEE International Conference on Communications (ICC)_. London: IEEE, Jun. 2015, pp. 4394–4399.
  * [26] P. K. Nicholson, V. Raman, and S. S. Rao, “A survey of data structures in the bitprobe model,” in _Space-Efficient Data Structures, Streams, and Algorithms_. Springer, 2013, pp. 303–318.
  * [27] A. Makhdoumi, S.-L. Huang, M. Medard, and Y. Polyanskiy, “On locally decodable source coding,” _arXiv preprint arXiv:1308.5239_ , 2013.
  * [28] H. Buhrman, P. B. Miltersen, J. Radhakrishnan, and S. Venkatesh, “Are bitvectors optimal?” _SIAM Journal on Computing_ , vol. 31, no. 6, pp. 1723–1744, 2002.
  * [29] A. Pananjady and T. A. Courtade, “The effect of local decodability constraints on variable-length compression,” _IEEE Transactions on Information Theory_ , vol. 64, no. 4, pp. 2593–2608, 2018.
  * [30] S. Vatedka and A. Tchamkerten, “Local Decode and Update for Big Data Compression,” _IEEE Transactions on Information Theory_ , vol. 66, no. 9, Sep. 2020.
  * [31] S. Vatedka, V. Chandar, and A. Tchamkerten, “O (log log n) worst-case local decoding and update efficiency for data compression,” in _2020 IEEE International Symposium on Information Theory (ISIT)_. IEEE, 2020, pp. 2371–2376.
  * [32] R. Vestergaard, Q. Zhang, and D. E. Lucani, “Enabling random access in universal compressors,” in _IEEE INFOCOM 2021-IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS)_. IEEE, 2021, pp. 1–6.
  * [33] D. Slepian and J. Wolf, “Noiseless coding of correlated information sources,” _IEEE Transactions on Information Theory_ , vol. 19, no. 4, pp. 471–480, 1973\.
  * [34] I. Csiszár and J. Körner, “Towards a general theory of source networks,” _IEEE Transactions on Information Theory_ , vol. 26, no. 2, pp. 155–165, 1980\.
  * [35] A. Mazumdar, V. Chandar, and G. W. Wornell, “Local recovery in data compression for general sources,” in _2015 IEEE International Symposium on Information Theory (ISIT)_. Hong Kong, Hong Kong: IEEE, Jun. 2015, pp. 2984–2988.
  * [36] K. Tatwawadi, S. S. Bidokhti, and T. Weissman, “On Universal Compression with Constant Random Access,” in _2018 IEEE International Symposium on Information Theory (ISIT)_. Vail, CO, USA: IEEE, Jun. 2018, pp. 891–895.
  * [37] S. Vatedka, V. Chandar, and A. Tchamkerten, “Locally decodable Slepian-Wolf compression,” _submitted, 2022 IEEE International Symposium on Information Theory_ , 2022.
  * [38] S. Kamath, “Reverse hypercontractivity using information measures,” in _2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton)_ , Sep. 2015, pp. 627–633.
  * [39] A. El Gamal and Y.-H. Kim, _Network Information Theory_. Cambridge University Press, 2011.