* [174] D. Pearson and J. Robinson, “Visual communication at very low data rates,” _Proceedings of the IEEE_ , vol. 73, no. 4, pp. 795–812, 1985.
  * [175] R. Lopez and T. Huang, “Head pose computation for very low bit-rate video coding,” in _International Conference on Computer Analysis of Images and Patterns_ , 1995.
  * [176] Y. Nakaya, Y. Chuah, and H. Harashima, “Model-based/waveform hybrid coding for videotelephone images,” in _International Conference on Acoustics, Speech, and Signal Processing_ , 1991, pp. 2741–2744 vol.4.
  * [177] M. Oquab _et al._ , “Low bandwidth video-chat compression using deep generative models,” in _Proc. IEEE Conf. Comput. Vis. Pattern Recognit. Workshop_ , 2021.
  * [178] G. Konuko _et al._ , “Ultra-low bitrate video conferencing using deep image animation,” in _IEEE Int. Conf. Acoust. Speech Signal Process._ , 06 2021, pp. 4210–4214.
  * [179] A. Tang _et al._ , “Generative compression for face video: A hybrid scheme,” in _Proc. IEEE Int. Conf. Multimedia Expo._ , jul 2022, pp. 1–6.
  * [180] B. Chen _et al._ , “Beyond keypoint coding: Temporal evolution inference with compact feature representation for talking face video compression,” in _Data Compression Conference_ , 2022, pp. 13–22.
  * [181] Z. Wang _et al._ , “Dynamic multi-reference generative prediction for face video compression,” in _Proc. IEEE Int. Conf. Image Process._ , 2022, pp. 896–900.
  * [182] B. Chen _et al._ , “Compact temporal trajectory representation for talking face video compression,” _IEEE Trans. Circuits Syst. Video Technol._ , 2023.
  * [183] B. Chen, Z. Wang, B. Li, S. Wang, S. Wang, and Y. Ye, “Interactive face video coding: A generative compression framework,” _arXiv preprint arXiv:2302.09919_ , 2023.
  * [184] S. Yin _et al._ , “Enabling translatability of generative face video coding: A unified face feature transcoding framework,” in _Data Compression Conference_ , 2024.
  * [185] P. Dhariwal and A. Nichol, “Diffusion models beat gans on image synthesis,” in _Adv. Neural Inf. Process. Syst._ , vol. 34, 2021, pp. 8780–8794.
  * [186] B. Chen _et al._ , “AHG9: Common SEI message of generative face video,” _The Joint Video Experts Team of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29, doc. no. JVET-AD0051_ , April 2023.
  * [187] H.-B. Teo _et al._ , “AHG9: A study on generative face video SEI message,” _The Joint Video Experts Team of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29, doc. no. JVET-AE0088_ , July 2023.
  * [188] M. M. Hannuksela _et al._ , “Ahg9: On the generative face video sei message,” _The Joint Video Experts Team of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29, doc. no. JVET-AG0087_ , January 2024.
  * [189] B. Chen _et al._ , “AHG9: Common text for proposed generative face video SEI message,” _The Joint Video Experts Team of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29, doc. no. JVET-AE0280_ , July 2023.
  * [190] M. M. Hannuksela _et al._ , “Ahg9: Usage of the neural-network post-filter characteristics sei message to define the generator nn of the generative face video sei message,” _The Joint Video Experts Team of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29, doc. no. JVET-AG0088_ , January 2024.
  * [191] Y. Ye _et al._ , “On VVC-assisted ultra-low rate generative face video coding,” _MPEG ISO/IEC JTC 1/SC 29/WG 2 doc. no. m64987_ , October 2023.
  * [192] B. Chen _et al._ , “AHG16: Proposed common software tools and testing conditions for generative face video compression,” _The Joint Video Experts Team of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29, doc. no. JVET-AG0042_ , January 2024.
  * [193] S. McCarthy and B. Chen, “Test conditions and evaluation procedures for generative face video coding,” _The Joint Video Experts Team of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29, doc. no. JVET-AG2035_ , January 2024.
  * [194] S. Yin _et al._ , “AHG16: Interoperability study on parameter translator of generative face video coding,” _The Joint Video Experts Team of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29, doc. no. JVET-AG0048_ , January 2024.
  * [195] R. Zou _et al._ , “Ahg16: Depthwise separable convolution for generative face video compression,” _The Joint Video Experts Team of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29, doc. no. JVET-AG0139_ , January 2024.
  * [196] N. Anantrasirichai and D. Bull, “Artificial intelligence in the creative industries: a review,” _Artificial intelligence review_ , pp. 1–68, 2022.
  * [197] C. Rota, M. Buzzelli, S. Bianco, and R. Schettini, “Video restoration based on deep learning: a comprehensive survey,” _Artificial Intelligence Review_ , vol. 56, no. 6, pp. 5317–5364, 2023.
  * [198] L. Zhai, Y. Wang, S. Cui, and Y. Zhou, “A comprehensive review of deep learning-based real-world image restoration,” _IEEE Access_ , 2023.
  * [199] K. Chauhan, S. Patel, M. Kumhar, J. Bhatia, S. Tanwar, I. E. Davidson, T. F. Mazibuko, and R. Sharma, “Deep learning-based single-image super-resolution: A comprehensive review,” _IEEE Access_ , 2023.
  * [200] X. Li, Y. Ren, X. Jin, C. Lan, X. Wang, W. Zeng, X. Wang, and Z. Chen, “Diffusion models for image restoration and enhancement–a comprehensive survey,” _arXiv preprint arXiv:2308.09388_ , 2023.
  * [201] D. J. Rezende, S. Mohamed, and D. Wierstra, “Stochastic backpropagation and approximate inference in deep generative models,” in _International Conference on Machine Learning_. PMLR, 2014, pp. 1278–1286.
  * [202] D. Im, S. Ahn, R. Memisevic, and Y. Bengio, “Denoising criterion for variational auto-encoding framework,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 31, no. 1, 2017.
  * [203] A. Creswell and A. A. Bharath, “Denoising adversarial autoencoders,” _IEEE Transactions on Neural Networks and Learning Systems_ , vol. 30, no. 4, pp. 968–984, 2018.
  * [204] M. Prakash, A. Krull, and F. Jug, “Fully unsupervised diversity denoising with convolutional variational autoencoders,” _arXiv preprint arXiv:2006.06072_ , 2020.
  * [205] T. M. Nimisha, A. Kumar Singh, and A. N. Rajagopalan, “Blur-invariant deep learning for blind-deblurring,” in _Proceedings of the IEEE International Conference on Computer Vision_ , 2017, pp. 4752–4760.
  * [206] M. Asim, F. Shamshad, and A. Ahmed, “Blind image deconvolution using deep generative priors,” _IEEE Transactions on Computational Imaging_ , vol. 6, pp. 1493–1506, 2020.
  * [207] Y. Du, J. Xu, Q. Qiu, X. Zhen, and L. Zhang, “Variational image deraining,” in _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision_ , 2020, pp. 2406–2415.
  * [208] G. Kim, S. W. Park, and J. Kwon, “Pixel-wise wasserstein autoencoder for highly generative dehazing,” _IEEE Transactions on Image Processing_ , vol. 30, pp. 5452–5462, 2021.
  * [209] Z.-S. Liu, W.-C. Siu, and Y.-L. Chan, “Photo-realistic image super-resolution via variational autoencoders,” _IEEE Transactions on Circuits and Systems for video Technology_ , vol. 31, no. 4, pp. 1351–1365, 2020.
  * [210] D. Chira, I. Haralampiev, O. Winther, A. Dittadi, and V. Liévin, “Image super-resolution with deep variational autoencoders,” in _European Conference on Computer Vision_. Springer, 2022, pp. 395–411.
  * [211] J. Chen, J. Chen, H. Chao, and M. Yang, “Image blind denoising with generative adversarial network based noise modeling,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2018, pp. 3155–3164.
  * [212] N. Anantrasirichai and D. Bull, “Contextual colorization and denoising for low-light ultra high resolution sequences,” in _2021 IEEE International Conference on Image Processing (ICIP)_. IEEE, 2021, pp. 1614–1618.
  * [213] Y. Poirier-Ginter and J.-F. Lalonde, “Robust unsupervised stylegan image restoration,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2023, pp. 22 292–22 301.
  * [214] S. Cha, T. Park, B. Kim, J. Baek, and T. Moon, “Gan2gan: Generative noise learning for blind denoising with single noisy images,” in _International Conference on Learning Representations_ , 2021.
  * [215] R. Li, J. Pan, Z. Li, and J. Tang, “Single image dehazing via conditional generative adversarial network,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2018, pp. 8202–8211.
  * [216] H. Zhang, V. Sindagi, and V. M. Patel, “Image de-raining using a conditional generative adversarial network,” _IEEE Transactions on Circuits and Systems for Video Technology_ , vol. 30, no. 11, pp. 3943–3956, 2019.
  * [217] M. Fu, H. Liu, Y. Yu, J. Chen, and K. Wang, “Dw-gan: A discrete wavelet transform gan for nonhomogeneous dehazing,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2021, pp. 203–212.
  * [218] K. Lin, T. H. Li, S. Liu, and G. Li, “Real photographs denoising with noise domain adaptation and attentive generative adversarial network,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops_ , 2019, pp. 0–0.
  * [219] Y. Xie, E. Franz, M. Chu, and N. Thuerey, “tempogan: A temporally coherent, volumetric gan for super-resolution fluid flow,” _ACM Transactions on Graphics (TOG)_ , vol. 37, no. 4, pp. 1–15, 2018.
  * [220] A. Kudo, Y. Kitamura, Y. Li, S. Iizuka, and E. Simo-Serra, “Virtual thin slice: 3D conditional gan-based super-resolution for ct slice interval,” in _Machine Learning for Medical Image Reconstruction: Second International Workshop, MLMIR 2019, Held in Conjunction with MICCAI 2019, Shenzhen, China, October 17, 2019, Proceedings 2_. Springer, 2019, pp. 91–100.
  * [221] S. Maeda, “Unpaired image super-resolution using pseudo-supervision,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2020, pp. 291–300.
  * [222] J. Wang, Y. Chen, Y. Wu, J. Shi, and J. Gee, “Enhanced generative adversarial network for 3D brain mri super-resolution,” in _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision_ , 2020, pp. 3627–3636.
  * [223] X. Wang, K. Yu, S. Wu, J. Gu, Y. Liu, C. Dong, Y. Qiao, and C. Change Loy, “Esrgan: Enhanced super-resolution generative adversarial networks,” in _Proceedings of the European Conference on Computer Vision (ECCV) workshops_ , 2018, pp. 0–0.
  * [224] D. Ma, M. Afonso, F. Zhang, and D. R. Bull, “Perceptually-inspired super-resolution of compressed videos,” in _Applications of Digital Image Processing XLII_ , vol. 11137. SPIE, 2019, pp. 310–318.
  * [225] T. Shang, Q. Dai, S. Zhu, T. Yang, and Y. Guo, “Perceptual extreme super-resolution network with receptive field block,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition workshops_ , 2020, pp. 440–441.
  * [226] C. You, G. Li, Y. Zhang, X. Zhang, H. Shan, M. Li, S. Ju, Z. Zhao, Z. Zhang, W. Cong _et al._ , “Ct super-resolution gan constrained by the identical, residual, and cycle learning ensemble (gan-circle),” _IEEE Transactions on Medical Imaging_ , vol. 39, no. 1, pp. 188–203, 2019.
  * [227] J. Park, S. Son, and K. M. Lee, “Content-aware local gan for photo-realistic super-resolution,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2023, pp. 10 585–10 594.
  * [228] J. He, W. Shi, K. Chen, L. Fu, and C. Dong, “Gcfsr: a generative and controllable face super resolution method without facial and gan priors,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2022, pp. 1889–1898.
  * [229] F.-A. Croitoru, V. Hondru, R. T. Ionescu, and M. Shah, “Diffusion models in vision: A survey,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 2023.
  * [230] O. Özdenizci and R. Legenstein, “Restoring vision in adverse weather conditions with patch-based denoising diffusion models,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 2023.
  * [231] C. Saharia, J. Ho, W. Chan, T. Salimans, D. J. Fleet, and M. Norouzi, “Image super-resolution via iterative refinement,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 45, no. 4, pp. 4713–4726, 2023.
  * [232] H. Li, Y. Yang, M. Chang, S. Chen, H. Feng, Z. Xu, Q. Li, and Y. Chen, “Srdiff: Single image super-resolution with diffusion probabilistic models,” _Neurocomputing_ , vol. 479, pp. 47–59, 2022.
  * [233] B. Kawar, M. Elad, S. Ermon, and J. Song, “Denoising diffusion restoration models,” _Advances in Neural Information Processing Systems_ , vol. 35, pp. 23 593–23 606, 2022.
  * [234] S. Gao, X. Liu, B. Zeng, S. Xu, Y. Li, X. Luo, J. Liu, X. Zhen, and B. Zhang, “Implicit diffusion models for continuous super-resolution,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2023, pp. 10 021–10 030.
  * [235] B. Xia, Y. Zhang, S. Wang, Y. Wang, X. Wu, Y. Tian, W. Yang, and L. Van Gool, “Diffir: Efficient diffusion model for image restoration,” _arXiv preprint arXiv:2303.09472_ , 2023.
  * [236] F. Zhan, Y. Yu, R. Wu, J. Zhang, S. Lu, L. Liu, A. Kortylewski, C. Theobalt, and E. Xing, “Multimodal image synthesis and editing: A survey and taxonomy,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 2023.
  * [237] T.-C. Wang, M.-Y. Liu, J.-Y. Zhu, A. Tao, J. Kautz, and B. Catanzaro, “High-resolution image synthesis and semantic manipulation with conditional gans,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2018, pp. 8798–8807.
  * [238] T. Park, M.-Y. Liu, T.-C. Wang, and J.-Y. Zhu, “Semantic image synthesis with spatially-adaptive normalization,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2019, pp. 2337–2346.
  * [239] W. Wang, J. Bao, W. Zhou, D. Chen, D. Chen, L. Yuan, and H. Li, “Semantic image synthesis via diffusion models,” _arXiv preprint arXiv:2207.00050_ , 2022.
  * [240] C. H. Wu and F. De la Torre, “A latent space of stochastic diffusion models for zero-shot image editing and guidance,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2023, pp. 7378–7387.
  * [241] H.-Y. Lee, H.-Y. Tseng, J.-B. Huang, M. Singh, and M.-H. Yang, “Diverse image-to-image translation via disentangled representations,” in _Proceedings of the European Conference on Computer Vision (ECCV)_ , 2018, pp. 35–51.
  * [242] V. Sushko, E. Schönfeld, D. Zhang, J. Gall, B. Schiele, and A. Khoreva, “You only need adversarial supervision for semantic image synthesis,” _arXiv preprint arXiv:2012.04781_ , 2020.
  * [243] M. Chen, A. Radford, R. Child, J. Wu, H. Jun, D. Luan, and I. Sutskever, “Generative pretraining from pixels,” in _International Conference on Machine Learning_. PMLR, 2020, pp. 1691–1703.
  * [244] P. Esser, R. Rombach, and B. Ommer, “Taming transformers for high-resolution image synthesis,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2021, pp. 12 873–12 883.
  * [245] C. Wu, J. Liang, L. Ji, F. Yang, Y. Fang, D. Jiang, and N. Duan, “Nüwa: Visual synthesis pre-training for neural visual world creation,” in _European Conference on Computer Vision_. Springer, 2022, pp. 720–736.
  * [246] S. Sun, L. Wei, J. Xing, J. Jia, and Q. Tian, “Sddm: score-decomposed diffusion models on manifolds for unpaired image-to-image translation,” in _International Conference on Machine Learning_. PMLR, 2023, pp. 33 115–33 134.
  * [247] N. Tumanyan, M. Geyer, S. Bagon, and T. Dekel, “Plug-and-play diffusion features for text-driven image-to-image translation,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2023, pp. 1921–1930.
  * [248] S. Niklaus and F. Liu, “Context-aware synthesis for video frame interpolation,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , 2018, pp. 1701–1710.
  * [249] H. Sim, J. Oh, and M. Kim, “XVFI: extreme video frame interpolation,” in _Proceedings of the IEEE International Conference on Computer Vision (ICCV)_ , 2021.
  * [250] Z. Liu, R. A. Yeh, X. Tang, Y. Liu, and A. Agarwala, “Video frame synthesis using deep voxel flow,” in _Proceedings of the IEEE International Conference on Computer Vision_ , 2017, pp. 4463–4471.
  * [251] L. Kong, B. Jiang, D. Luo, W. Chu, X. Huang, Y. Tai, C. Wang, and J. Yang, “Ifrnet: Intermediate feature refine network for efficient frame interpolation,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2022, pp. 1969–1978.
  * [252] M. Koren, K. Menda, and A. Sharma, “Frame interpolation using generative adversarial networks,” 2017.
  * [253] J. van Amersfoort, W. Shi, A. Acosta, F. Massa, J. Totz, Z. Wang, and J. Caballero, “Frame interpolation with multi-scale deep loss functions and generative adversarial networks,” _arXiv preprint arXiv:1711.06045_ , 2017.
  * [254] S. Wen, W. Liu, Y. Yang, T. Huang, and Z. Zeng, “Generating realistic videos from keyframes with concatenated gans,” _IEEE Transactions on Circuits and Systems for Video Technology_ , vol. 29, no. 8, pp. 2337–2348, 2019.
  * [255] I. Gulrajani, F. Ahmed, M. Arjovsky, V. Dumoulin, and A. C. Courville, “Improved training of wasserstein gans,” _Advances in neural information processing systems_ , vol. 30, 2017.
  * [256] V. Voleti, A. Jolicoeur-Martineau, and C. Pal, “Mcvd-masked conditional video diffusion for prediction, generation, and interpolation,” _Advances in Neural Information Processing Systems_ , vol. 35, pp. 23 371–23 385, 2022.
  * [257] Z. Deng, X. He, Y. Peng, X. Zhu, and L. Cheng, “Mv-diffusion: Motion-aware video diffusion model,” in _Proceedings of the 31st ACM International Conference on Multimedia_ , 2023, pp. 7255–7263.
  * [258] D. Danier, F. Zhang, and D. Bull, “Ldmvfi: Video frame interpolation with latent diffusion models,” _arXiv preprint arXiv:2303.09508_ , 2023.
  * [259] J. Park, K. Ko, C. Lee, and C.-S. Kim, “BMBC: Bilateral motion estimation with bilateral cost volume for video interpolation,” in _Computer Vision–ECCV 2020: 16th European Conference, Glasgow, UK, August 23–28, 2020, Proceedings, Part XIV 16_. Springer, 2020, pp. 109–125.
  * [260] D. Danier, F. Zhang, and D. Bull, “St-mfnet: A spatio-temporal multi-flow network for frame interpolation,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2022, pp. 3521–3531.
  * [261] H. Yang, P. Shi, D. Zhong, D. Pan, and Z. Ying, “Blind image quality assessment of natural distorted image based on generative adversarial networks,” _IEEE Access_ , vol. 7, pp. 179 290–179 303, 2019.
  * [262] J. Ma, J. Wu, L. Li, W. Dong, and X. Xie, “Active inference of gan for no-reference image quality assessment,” in _2020 IEEE International Conference on Multimedia and Expo (ICME)_. IEEE, 2020, pp. 1–6.
  * [263] Y. Zhu, H. Ma, J. Peng, D. Liu, and Z. Xiong, “Recycling discriminator: Towards opinion-unaware image quality assessment using wasserstein gan,” in _Proceedings of the 29th ACM International Conference on Multimedia_ , 2021, pp. 116–125.
  * [264] P. P. ˇZiga Babnik and V. Štruc, “Diffiqa: Face image quality assessment using denoising diffusion probabilistic models,” 2023.
  * [265] J. Zhang, Z. Fang, and L. Yu, “A no-reference perceptual image quality assessment database for learned image codecs,” _Journal of Visual Communication and Image Representation_ , vol. 88, p. 103617, 2022.
  * [266] E. Betzalel, C. Penso, A. Navon, and E. Fetaya, “A study on the evaluation of generative models,” _arXiv preprint arXiv:2206.10935_ , 2022.
  * [267] T. Salimans, I. Goodfellow, W. Zaremba, V. Cheung, A. Radford, and X. Chen, “Improved techniques for training gans,” _Advances in neural information processing systems_ , vol. 29, 2016.
  * [268] M. Heusel, H. Ramsauer, T. Unterthiner, B. Nessler, and S. Hochreiter, “Gans trained by a two time-scale update rule converge to a local nash equilibrium,” _Advances in neural information processing systems_ , vol. 30, 2017.
  * [269] E. J. Nunn, P. Khadivi, and S. Samavi, “Compound frechet inception distance for quality assessment of gan created images,” _arXiv preprint arXiv:2106.08575_ , 2021.
  * [270] H. Ko, D. Y. Lee, S. Cho, and A. C. Bovik, “Quality prediction on deep generative images,” _IEEE Transactions on Image Processing_ , vol. 29, pp. 5964–5979, 2020.
  * [271] H. Zheng, H. Yang, J. Fu, Z.-J. Zha, and J. Luo, “Learning conditional knowledge distillation for degraded-reference image quality assessment,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2021, pp. 10 242–10 251.
  * [272] G. Zhao, V. Magoulianitis, S. You, and C.-C. J. Kuo, “A lightweight generalizable evaluation and enhancement framework for generative models and generated samples,” in _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision_ , 2024, pp. 450–459.
  * [273] M. Horowitz, “1.1 computing’s energy problem (and what we can do about it),” in _2014 IEEE International Solid-State Circuits Conference Digest of Technical Papers (ISSCC)_. IEEE, 2014, pp. 10–14.
  * [274] J. Ballé, N. Johnston, and D. Minnen, “Integer networks for data compression with latent-variable models,” in _International Conference on Learning Representations_ , 2019.
  * [275] H. Sun, L. Yu, and J. Katto, “Learned image compression with fixed-point arithmetic,” in _2021 Picture Coding Symposium (PCS)_. IEEE, 2021, pp. 1–5.
  * [276] D. He, Z. Yang, Y. Chen, Q. Zhang, H. Qin, and Y. Wang, “Post-training quantization for cross-platform learned image compression,” _arXiv preprint arXiv:2202.07513_ , 2022.
  * [277] E. Koyuncu, T. Solovyev, E. Alshina, and A. Kaup, “Device interoperability for learned image compression with weights and activations quantization,” in _2022 Picture Coding Symposium (PCS)_. IEEE, 2022, pp. 151–155.
  * [278] G.-W. Jeon, S. Yu, and J.-S. Lee, “Integer quantized learned image compression,” in _2023 IEEE International Conference on Image Processing (ICIP)_. IEEE, 2023, pp. 2755–2759.
  * [279] E. Koyuncu, T. Solovyev, J. Sauer, E. Alshina, and A. Kaup, “Quantized decoder in learned image compression for deterministic reconstruction,” _arXiv preprint arXiv:2312.11209_ , 2023.
  * [280] A. Gholami, S. Kim, Z. Dong, Z. Yao, M. W. Mahoney, and K. Keutzer, “A survey of quantization methods for efficient neural network inference,” in _Low-Power Computer Vision_. Chapman and Hall/CRC, 2022, pp. 291–326.
  * [281] C. Jia, X. Hang, W. Liu, S. Wang, and S. Ma, “Fpx-nvc: An fpga-accelerated p-frame based neural video coding system,” in _2022 IEEE International Conference on Visual Communications and Image Processing (VCIP)_. IEEE, 2022, pp. 1–1.
  * [282] H. Sun, L. Yu, and J. Katto, “Q-lic: Quantizing learned image compression with channel splitting,” _IEEE Transactions on Circuits and Systems for Video Technology_ , 2022.
  * [283] J. Shi, M. Lu, and Z. Ma, “Rate-distortion optimized post-training quantization for learned image compression,” _IEEE Transactions on Circuits and Systems for Video Technology_ , 2023.
  * [284] A. Luo, H. Sun, J. Liu, and J. Katto, “Memory-efficient learned image compression with pruned hyperprior module,” in _2022 IEEE International Conference on Image Processing (ICIP)_. IEEE, 2022, pp. 3061–3065.
  * [285] X. Ding, T. Hao, J. Tan, J. Liu, J. Han, Y. Guo, and G. Ding, “Resrep: Lossless cnn pruning via decoupling remembering and forgetting,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2021, pp. 4510–4520.
  * [286] J.-H. Kim, J.-H. Choi, J. Chang, and J.-S. Lee, “Efficient deep learning-based lossy image compression via asymmetric autoencoder and pruning,” in _ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2020, pp. 2063–2067.
  * [287] W. Guo-Hua, J. Li, B. Li, and Y. Lu, “Evc: Towards real-time neural image compression with mask decay,” in _The Eleventh International Conference on Learning Representations_ , 2022.
  * [288] Z. Zheng, X. Wang, X. Lin, and S. Lv, “Get the best of the three worlds: Real-time neural image compression in a non-gpu environment,” in _Proceedings of the 29th ACM International Conference on Multimedia_ , 2021, pp. 5400–5409.
  * [289] S. Yin, T. Xu, Y. Liang, Y. Wang, Y. Li, Y. Wang, and J. Liu, “Bandwidth-efficient inference for neural image compression,” _arXiv preprint arXiv:2309.02855_ , 2023.
  * [290] S. Yu and J.-S. Lee, “Lut-lic: Look-up table-assisted learned image compression,” in _International Conference on Neural Information Processing_. Springer, 2023, pp. 430–441.
  * [291] C. Jia, X. Hang, S. Wang, Y. Wu, S. Ma, and W. Gao, “Fpx-nic: An fpga-accelerated 4k ultra-high-definition neural video coding system,” _IEEE Transactions on Circuits and Systems for Video Technology_ , vol. 32, no. 9, pp. 6385–6399, 2022.
  * [292] Z. Zhao, C. Jia, S. Wang, S. Ma, and J. Yang, “Learned image compression using adaptive block-wise encoding and reconstruction network,” in _2021 IEEE International Symposium on Circuits and Systems (ISCAS)_ , 2021, pp. 1–5.
  * [293] H. Shao, B. Liu, Z. Li, C. Yan, Y. Sun, and T. Wang, “A high-throughput processor for gdn-based deep learning image compression,” _Electronics_ , vol. 12, no. 10, p. 2289, 2023.
  * [294] H. Sun, Q. Yi, F. Lin, L. Yu, J. Katto, and M. Fujita, “F-lic: Fpga-based learned image compression with a fine-grained pipeline,” in _2022 IEEE Asian Solid-State Circuits Conference (A-SSCC)_. IEEE, 2022, pp. 1–3.
  * [295] Z. Cheng, H. Sun, M. Takeuchi, and J. Katto, “Deep residual learning for image compression,” in _CVPR Workshops_ , 2019, pp. 1–5.
  * [296] H. Sun, Q. Yi, F. Lin, L. Yu, J. Katto, and M. Fujita, “Real-time learned image codec on fpga,” in _2022 IEEE International Conference on Visual Communications and Image Processing (VCIP)_. IEEE, 2022, pp. 1–1.
  * [297] S.-F. Tsai, C.-T. Li, H.-H. Chen, P.-K. Tsung, K.-Y. Chen, and L.-G. Chen, “A 1062mpixels/s 8192$\times$ 4320p high efficiency video coding (h. 265) encoder chip,” in _2013 Symposium on VLSI Circuits_. IEEE, 2013, pp. C188–C189.
  * [298] C.-T. Huang, M. Tikekar, C. Juvekar, V. Sze, and A. Chandrakasan, “A 249Mpixel/s HEVC video-decoder chip for Quad Full HD applications,” in _2013 IEEE International Solid-State Circuits Conference Digest of Technical Papers_. IEEE, 2013, pp. 162–163.
  * [299] D. Zhou, S. Wang, H. Sun, J. Zhou, J. Zhu, Y. Zhao, J. Zhou, S. Zhang, S. Kimura, T. Yoshimura _et al._ , “A 4Gpixel/s 8/10b H.265/HEVC video decoder chip for 8K Ultra HD applications,” in _2016 IEEE International Solid-State Circuits Conference (ISSCC)_. IEEE, 2016, pp. 266–268.
  * [300] J. Liu, H. Sun, and J. Katto, “Learned image compression with mixed transformer-cnn architectures,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2023, pp. 14 388–14 397.
  * [301] K. Tian, Y. Guan, J. Xiang, J. Zhang, X. Han, and W. Yang, “Towards real-time neural video codec for cross-platform application using calibration information,” in _Proceedings of the 31st ACM International Conference on Multimedia_ , 2023, pp. 7961–7970.
  * [302] T. Peng, G. Gao, H. Sun, F. Zhang, and D. Bull, “Accelerating learnt video codecs with gradient decay and layer-wise distillation,” _arXiv preprint arXiv:2312.02605_ , 2023.
  * [303] S. Zhang, W. Mao, H. Shi, and Z. Wang, “A computationally efficient neural video compression accelerator based on a sparse cnn-transformer hybrid network,” _arXiv preprint arXiv:2312.10716_ , 2023.
  * [304] H. Le, L. Zhang, A. Said, G. Sautiere, Y. Yang, P. Shrestha, F. Yin, R. Pourreza, and A. Wiggers, “MobileCodec: Neural inter-frame video compression on mobile devices,” in _Proceedings of the 13th ACM Multimedia Systems Conference_ , 2022, pp. 324–330.
  * [305] T. van Rozendaal, T. Singhal, H. Le, G. Sautiere, A. Said, K. Buska, A. Raha, D. Kalatzis, H. Mehta, F. Mayer _et al._ , “Mobilenvc: Real-time 1080p neural video compression on a mobile device,” in _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision_ , 2024, pp. 4323–4333.
  * [306] E. Dupont, A. Golinski, M. Alizadeh, Y. W. Teh, and A. Doucet, “COIN: Compression with implicit neural representations,” in _Neural Compression: From Information Theory to Applications–Workshop@ ICLR 2021_ , 2021.
  * [307] Y. Strümpler, J. Postels, R. Yang, L. V. Gool, and F. Tombari, “Implicit neural representations for image compression,” in _European Conference on Computer Vision_. Springer, 2022, pp. 74–91.
  * [308] H. Kim, M. Bauer, L. Theis, J. R. Schwarz, and E. Dupont, “C3: High-performance and low-complexity neural compression from a single image or video,” _arXiv preprint arXiv:2312.02753_ , 2023.
  * [309] Y. Zhang, T. van Rozendaal, J. Brehmer, M. Nagel, and T. S. Cohen, “Implicit neural video compression,” in _ICLR Workshop on Deep Generative Models for Highly Structured Data_ , 2022.
  * [310] T. Ladune, P. Philippe, F. Henry, G. Clare, and T. Leguay, “COOL-CHIC: Coordinate-based low complexity hierarchical image codec,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2023, pp. 13 515–13 522.
  * [311] T. Van Rozendaal, J. Brehmer, Y. Zhang, R. Pourreza, A. Wiggers, and T. S. Cohen, “Instance-adaptive video compression: Improving neural codecs by training on the test set,” _arXiv preprint arXiv:2111.10302_ , 2021.
  * [312] E. Dupont, H. Loya, M. Alizadeh, A. Golinski, Y. W. Teh, and A. Doucet, “COIN++: Neural compression across modalities,” _Transactions on Machine Learning Research_ , 2022.
  * [313] C. Gomes, R. Azevedo, and C. Schroers, “Video compression with entropy-constrained neural representations,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2023, pp. 18 497–18 506.
  * [314] B. B. Damodaran, M. Balcilar, F. Galpin, and P. Hellier, “RQAT-INR: Improved implicit neural image compression,” in _2023 Data Compression Conference (DCC)_. IEEE, 2023, pp. 208–217.
  * [315] Z. Guo, G. Flamich, J. He, Z. Chen, and J. M. Hernández-Lobato, “Compression with bayesian implicit neural representations,” in _Thirty-seventh Conference on Neural Information Processing Systems_ , 2023.
  * [316] G. Zhang, X. Zhang, and L. Tang, “Enhanced quantified local implicit neural representation for image compression,” _IEEE Signal Processing Letters_ , vol. 30, pp. 1742–1746, 2023.
  * [317] C. Cremer, X. Li, and D. Duvenaud, “Inference suboptimality in variational autoencoders,” in _International Conference on Machine Learning_. PMLR, 2018, pp. 1078–1086.
  * [318] T. van Rozendaal, I. A. Huijben, and T. S. Cohen, “Overfitting for fun and profit: Instance-adaptive data compression,” _arXiv preprint arXiv:2101.08687_ , 2021.
  * [319] M. Balcilar, B. Damodaran, and P. Hellier, “Reducing the amortization gap of entropy bottleneck in end-to-end image compression,” in _2022 Picture Coding Symposium (PCS)_. IEEE, 2022, pp. 115–119.
  * [320] O. Jourairi, M. Balcilar, A. Lambert, and F. Schnitzler, “Improving the reconstruction quality by overfitted decoder bias in neural image compression,” in _2022 Picture Coding Symposium (PCS)_. IEEE, 2022, pp. 61–65.
  * [321] H. Zhang, F. Cricri, H. R. Tavakoli, M. Santamaria, Y.-H. Lam, and M. M. Hannuksela, “Learn to overfit better: finding the important parameters for learned image compression,” in _2021 International Conference on Visual Communications and Image Processing (VCIP)_ , 2021, pp. 1–5.
  * [322] M. Balcilar, B. B. Damodaran, and P. Hellier, “Reducing the mismatch between marginal and learned distributions in neural video compression,” in _2022 IEEE International Conference on Visual Communications and Image Processing (VCIP)_. IEEE, 2022, pp. 1–5.
  * [323] K. Liu, D. Wu, Y. Wu, Y. Wang, D. Feng, B. Tan, and S. Garg, “Manipulation attacks on learned image compression,” _IEEE Transactions on Artificial Intelligence_ , 2023.
  * [324] M. Song, J. Choi, and B. Han, “A training-free defense framework for robust learned image compression,” _arXiv preprint arXiv:2401.11902_ , 2024.
  * [325] T. Zhu, H. Sun, X. Xiong, X. Zhu, Y. Gong, Y. Fan _et al._ , “Attack and defense analysis of learned image compression,” _arXiv preprint arXiv:2401.10345_ , 2024.
  * [326] T. Chen and Z. Ma, “Towards robust neural image compression: Adversarial attack and model finetuning,” _IEEE Transactions on Circuits and Systems for Video Technology_ , 2023.
  * [327] Y. Choi, M. El-Khamy, and J. Lee, “Variable rate deep image compression with a conditional autoencoder,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2019, pp. 3146–3154.
  * [328] Z. Cui, J. Wang, S. Gao, T. Guo, Y. Feng, and B. Bai, “Asymmetric gained deep image compression with continuous rate adaptation,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2021, pp. 10 532–10 541.
  * [329] M. Song, J. Choi, and B. Han, “Variable-rate deep image compression through spatially-adaptive feature transform,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2021, pp. 2380–2389.


$\displaystyle\leq\frac{\log\left(\frac{n}{\log
n}\right)+\left(\log\left(\frac{n}{\log
n}\right)+\log(1+C_{\mathrm{grow}})+1\right)^{2/3}}{\left(1-\left(1-\xi\right)\cdot(\log
n)^{-\xi}\right)^{2}}\leq\sum^{t_{2}-1}_{t=t_{1}}\log\left(1+q(t)\cdot\phi_{n/\log
n}\right)\leq t_{3}\cdot\log(1+1\cdot 1).$

Hence, rearranging implies that $t_{3}\geq\frac{1}{2\cdot\log 2}\cdot\log n$.
If we let $t_{0}:=0$ then we can define Phase $i$ to be the interval
$(t_{i-1},t_{i}]$ for $i\in[4]$. Since $t_{1}\leq t_{2}\leq t_{3}\leq
t_{4}<\infty$, the preconditions of Corollary 4.3 are satisfied in Phases
$1-3$, and the preconditions of Corollary 4.4 are satisfied in Phase $4$.

For Phase $1$, we let $A=1,B=\log n$ and $\nu_{t}^{[A,B]}=q(t)\cdot\phi_{\log
n}$. We note that by Lemma 2.3 (ii), $\delta_{t}=q(t)\cdot\varphi(I_{t})$.
Therefore, our choice of $\nu_{t}^{[A,B]}$ satisfies the requirement of
Corollary 4.3. Thus,

$\mathbf{P}\left[\,|I_{t_{2}}|\geq\log n\,\right]\geq 1-o(1).$

Similarly, in Phase 2 we let $A=\log n,B=\frac{n}{\log n}$ and
$\nu_{t}^{[A,B]}=q(t)\cdot\phi_{\frac{n}{\log n}}$ to get that

$\mathbf{P}_{t_{1}}\left[\,|I_{t_{2}}|\geq\frac{n}{\log
n}~{}\Big{|}~{}|I_{t_{1}}|\geq\log n\,\right]\geq 1-o(1),$

and in Phase 3, $A=\frac{n}{\log n},B=n/2$ and
$\nu_{t}^{[A,B]}=q(t)\cdot\phi_{t}$, resulting in

$\mathbf{P}_{t_{2}}\left[\,|I_{t_{3}}|\geq\frac{n}{2}~{}\Big{|}~{}|I_{t_{2}}|\geq\frac{n}{\log
n}\,\right]\geq 1-o(1).$

Lastly, in Phase 4, we apply Corollary 4.4 with $C=n/2$,
$D=n\cdot\exp(-\sqrt{\log n})$ and $\nu_{t}^{[C,D]}=q(t)\cdot\phi_{n/2}$
(where again $\nu_{t}^{[C,D]}$ satisfies the requirement of Corollary 4.4 by
Lemma 2.3 (ii)). Therefore,

$\mathbf{P}_{t_{3}}\left[\,|U_{t_{4}}|\leq n\cdot\exp(-\sqrt{\log
n})~{}\Big{|}~{}|I_{t_{3}}|\geq n/2\,\right]\geq 1-o(1).$

By taking the union bound we obtain,

$\mathbf{P}\left[\,|U_{t_{4}}|\geq n\cdot\left(1-\exp(-\sqrt{\log
n})\right)\,\right]\geq 1-o(1).$

Since $t_{1}\leq t_{2}\leq t_{3}\leq t_{4}$ by definition, it remains to show
that if the main precondition of the theorem (Eq. 4.10) is satisfied, then
$t_{4}\leq T_{{\rm{\texttt{PULL}}}}$ holds. Then, since $I_{t_{4}}\subseteq
I_{T_{{\rm{\texttt{PULL}}}}}$, the proof would be complete. In the remainder
of the proof for PULL, we will thus establish that $t_{4}\leq
T_{{\rm{\texttt{PULL}}}}$ indeed holds. First, since $t_{1}$ and $t_{2}$ are
chosen minimally, we know that for large $n$,

$\displaystyle\sum^{t_{1}-2}_{t=0}\log\left(1+q(t)\cdot\phi_{\log
n}\right)<\frac{\log\log n+\left(\log\log
n+\log\left(1+C_{\mathrm{grow}}\right)+1\right)^{2/3}}{\xi^{2}}\leq(\log
n)^{2/3},$ (4.11)

and, since $C_{\mathrm{grow}}\leq 1$, we have

$\displaystyle\sum^{t_{2}-2}_{t=t_{1}}\log\left(1+q(t)\cdot\phi_{n/\log
n}\right)$ $\displaystyle<\frac{\log\left(\frac{n}{\left(\log
n\right)^{2}}\right)+\left(\log\left(\frac{n}{\left(\log
n\right)^{2}}\right)+\log(1+C_{\mathrm{grow}})+1\right)^{2/3}}{\left(1-(1-\xi)\cdot(\log
n)^{-\xi}\right)^{2}}$ $\displaystyle\leq\frac{\log n+\left(\log
n\right)^{2/3}}{\left(1-(1-\xi)\cdot(\log n)^{-\xi}\right)^{2}}.$ (4.12)

Therefore, since $\phi_{\log n}\geq\phi_{n/\log n}$ and
$\log\left(1+q(t_{1}-1)\cdot\phi_{\log
n}\right),\log\left(1+q(t_{2}-1)\cdot\phi_{n/\log n}\right)\leq\log 2$,

$\sum^{t_{2}-1}_{t=0}\log\left(1+q(t)\cdot\phi_{n/\log
n}\right)\leq\sum^{t_{1}-2}_{t=0}\log\left(1+q(t)\cdot\phi_{\log
n}\right)+\sum^{t_{2}-2}_{t=t_{1}}\log\left(1+q(t)\cdot\phi_{n/\log
n}\right)+2\log\left(2\right).$

Now inserting the bounds on these sums from Eq. 4.11 and Eq. 4.12 gives

$\sum^{t_{2}-1}_{t=0}\log\left(1+q(t)\cdot\phi_{n/\log n}\right)\leq\frac{\log
n+3\left(\log n\right)^{2/3}}{\left(1-(1-\xi)\cdot(\log
n)^{-\xi}\right)^{2}}:=M,$

Now, since $\phi_{n/\log n}\geq\left(1-\lambda\right)\left(1-\frac{1}{\log
n}\right)$ (by Lemma A.12) and using A.14, we obtain,

$(1-\lambda)\left(1-\frac{1}{\log
n}\right)\cdot\sum^{t_{2}-1}_{t=0}\log(1+q(t))\leq M$

Now by rearranging and exponentiating both sides, we have

$\displaystyle\prod^{t_{2}-1}_{t=0}(1+q(t))\leq\exp\left(\left((1-\lambda)\left(1-\frac{1}{\log
n}\right)\right)^{-1}M\right)\leq\exp\left(\frac{1}{1-\lambda}\cdot\frac{\log
n+4\left(\log n\right)^{2/3}}{\left(1-(1-\xi)\cdot(\log
n)^{-\xi}\right)^{2}}\right).$ (4.13)

Similarly to the above, as $t_{3}$ is also chosen minimally,

$\displaystyle\sum_{t=t_{2}}^{t_{3}-1}\log\left(1+q(t)\cdot\phi_{n/2}\right)\leq\frac{\log\log
n+\left(\log\log
n+\log\left(1+C_{\mathrm{grow}}\right)+1\right)^{2/3}}{\left(1-(1-\xi)\cdot(n/\log
n)^{-\xi}\right)^{2}}+\log 2\leq(\log n)^{2/3}.$ (4.14)

We can now lower bound the right-hand side as follows,

$\sum^{t_{3}-1}_{t=t_{2}}\log\left(1+q(t)\cdot\phi_{n/2}\right)\stackrel{{\scriptstyle(a)}}{{\geq}}\sum^{t_{3}-1}_{t=t_{2}}\log\left(1+q(t)\cdot\frac{1-\lambda}{2}\right)\stackrel{{\scriptstyle(b)}}{{\geq}}\frac{1-\lambda}{2}\cdot\sum^{t_{3}-1}_{t=t_{2}}\log\left(1+q(t)\right),$
(4.15)

where $(a)$ uses $\phi_{n/2}\geq\frac{1}{2}(1-\lambda)$ from Lemma A.12, and
$(b)$ follows by A.14. Combining Eq. 4.14 and Eq. 4.15 gives us
$\sum^{t_{3}-1}_{t=t_{2}}\log\left(1+q(t)\right)\leq\frac{2}{1-\lambda}\cdot(\log
n)^{2/3}$. Exponentiating, we get

$\prod^{t_{3}-1}_{t=t_{2}}(1+q(t))\leq\exp\left(\frac{2}{1-\lambda}\cdot(\log
n)^{2/3}\right).$ (4.16)

Now, combining Eq. 4.13 and Eq. 4.16,

$\displaystyle\prod_{t=0}^{t_{3}-1}(1+q(t))$
$\displaystyle\leq\exp\left(\frac{1}{1-\lambda}\cdot\frac{\log n+4\left(\log
n\right)^{2/3}}{\left(1-(1-\xi)\cdot(\log
n)^{-\xi}\right)^{2}}\right)\cdot\exp\left(\frac{2}{1-\lambda}\cdot(\log
n)^{2/3}\right)$
$\displaystyle\leq\exp\left(\frac{1}{1-\lambda}\cdot\frac{\log n+6\left(\log
n\right)^{2/3}}{\left(1-(1-\xi)\cdot(\log n)^{-\xi}\right)^{2}}\right).$
(4.17)

Lastly, we consider Phase $4$. In this phase, since $t_{3}\geq\frac{1}{2\log
2}\cdot\log n$ and $\varepsilon\geq\frac{1}{\log n}$, we have
$C_{\mathrm{shrink}}\leq 1-\frac{1}{\log n}$. Recall that
$D:=n\cdot\exp\left(-\sqrt{\log n}\right)$, hence
$1-\min\left(\frac{1}{2\left(1-C_{\mathrm{shrink}}\right)\cdot
D},1/2\right)\geq 1-1/\sqrt{n}$. Thus, similarly to as we did for
$t_{1}$-$t_{3}$, by minimality of $t_{4}$,

$\sum^{t_{4}-2}_{t=t_{3}}\log\left(1-q(t)\cdot\phi_{n/2}\right)\geq-\frac{\log\left(\frac{n}{2\cdot
D}\right)+\left(\log\left(\frac{n}{2\cdot
D}\right)-\log\left(1-C_{\mathrm{shrink}}\right)+1\right)^{2/3}}{1-\min\left(\frac{1}{2\left(1-C_{\mathrm{shrink}}\right)\cdot
D},1/2\right)}\geq-\frac{(\log n)^{2/3}}{5}.$ (4.18)

Thus we have, since $1-q(t)\geq\varepsilon\geq 1/\log n$ we have

$\sum^{t_{4}-1}_{t=t_{3}}\log\left(1-q(t)\cdot\phi_{n/2}\right)\geq-\frac{(\log
n)^{2/3}}{5}+\log\left(1-q(t_{4}-1)\cdot\phi_{n/2}\right)\geq-\frac{(\log
n)^{2/3}}{4}.$ (4.19)

Using Lemma A.12 to give
$\phi_{n/2}\geq\frac{1}{2}\cdot\left(1-\lambda\right)$ in $(a)$, and then
using the fact that $-2x\leq\log(1-x)\leq-x$ when $x\in[0,1/2]$, noting that
$q(t)(1-\lambda)/2\in[0,1/2]$, we get

$\sum_{t=t_{3}}^{t_{4}-1}\log(1-q(t)\cdot\phi_{n/2})\overset{(a)}{\leq}\sum_{t=t_{3}}^{t_{4}-1}\log\left(1-q(t)\cdot\frac{1-\lambda}{2}\right)\leq\sum_{t=t_{3}}^{t_{4}-1}\frac{1-\lambda}{2}\cdot
q(t)\leq\frac{1-\lambda}{4}\sum_{t=t_{3}}^{t_{4}-1}\log(1-q(t)).$ (4.20)

Combining Eq. 4.19 and Eq. 4.20 gives
$\sum_{t=t_{3}}^{t_{4}-1}-\log(1-q(t))\leq\frac{(\log n)^{2/3}}{1-\lambda}$.
Exponentiating, we obtain
$\prod^{t_{4}-1}_{t=t_{3}}\left(1-q(t)\right)^{-1}\leq\exp\left(\frac{(\log
n)^{2/3}}{1-\lambda}\right).$ Then, since $1+z\leq\frac{1}{1-z}$ for
$z\in[0,1)$, we conclude that

$\displaystyle\prod_{t=t_{3}}^{t_{4}-1}\left(1+q(t)\right)\leq\prod^{t_{4}-1}_{t=t_{3}}\left(1-q(t)\right)^{-1}\leq\exp\left(\frac{(\log
n)^{2/3}}{1-\lambda}\right).$ (4.21)

Combining Eq. 4.17 and Eq. 4.21, we obtain,

$\displaystyle\prod_{t=0}^{t_{4}-1}\left(1+q(t)\right)$
$\displaystyle\leq\exp\left(\frac{1}{1-\lambda}\cdot\frac{\log n+7\left(\log
n\right)^{2/3}}{\left(1-(1-\xi)\cdot(\log n)^{-\xi}\right)^{2}}\right).$

If we define $\gamma_{{\rm{\texttt{PULL}}}}:=(1-\lambda)$, then this implies
that $t_{4}\leq T_{{\rm{\texttt{PULL}}}}$ by the theorem statement, concluding
the proof.

The proof for PUSH is very similar, however the constant
$\gamma_{{\rm{\texttt{PULL}}}}$ is slightly different. This is since in Phase
$2$ we have to use the bound $\delta_{t}\geq
q(t)\cdot\left(1-7\sqrt{\lambda+\frac{1}{\log n}}\right)$ from Lemma 2.4 (i)
for PUSH, rather than the bound $\delta_{t}=q(t)\cdot\varphi(I_{t})$ from
Lemma 2.3 (ii) for PULL. Other than that, very little changes in the proof.∎

###  4.2 Power-Law Credibility

In this part we consider a natural credibility function with a polynomial
decay.

######  Definition 4.8 (Power-law credibility).

Let $\alpha\in(0,\infty)$ be any constant . Then, the power-law credibility
function is defined for any round $t\geq 0$ as

$q_{\alpha}(t):=(t+1)^{-\alpha}.$

In particular, in the first round the credibility function is $1$.

We first observe that if $\alpha>1$, we only inform a constant number of
vertices in expectation.

######  Proposition 4.9.

Let $(G_{t})_{t\geq 0}$ be any sequence of regular graphs, and consider a
Growing Process such that
$\mathbf{E}_{t}\left[\,\frac{|\Delta_{t+1}|}{|I_{t}|}\,\right]\leq
C_{\mathrm{grow}}\cdot q(t)$ for all $t\geq 0$ . Then, for any constant
$\alpha>1$, there is a constant $\kappa=\kappa(\alpha)>0$, such that for any
$T\geq 0$,

$\mathbf{E}[\,|I_{T}|\,]\leq\kappa.$

The condition
$\mathbf{E}_{t}\left[\,\frac{|\Delta_{t+1}|}{|I_{t}|}\,\right]\leq
C_{\mathrm{grow}}\cdot q(t)$ is a refinement of $\mathcal{P}_{2}$ in
Definition 2.1, and is satisfied by the PULL, PUSH, PUSH-PULL processes as
shown in Lemma 2.3 by choosing $C_{\mathrm{grow}}$ as 1, 1, and 2,
respectively.

###### Proof.

Recall that
$|I_{t+1}|=\left(1+\frac{|\Delta_{t+1}|}{|I_{t}|}\right)\cdot|I_{t}|$. Then,

$\displaystyle\mathbf{E}_{t}\left[\,|I_{t+1}|\,\right]\leq(1+C_{\mathrm{grow}}\cdot
q(t))\cdot|I_{t}|\leq e^{C_{\mathrm{grow}}\cdot q(t)}\cdot|I_{t}|$

and recursively we have $\mathbf{E}[\,|I_{T}|\,]\leq
e^{C_{\mathrm{grow}}\sum_{t=0}^{T-1}q(t)}$. Since $q(t)=(t+1)^{-\alpha}$ with
$\alpha>1$, it holds that $\sum_{t=0}^{\infty}q(t)<\infty$. By choosing
$\kappa=e^{C_{\mathrm{grow}}\sum_{t=0}^{\infty}q(t)}$ we obtain the desired
result. ∎

The next result considers the regime $\alpha\leq 1$, and proves that after a
sufficiently long time, the rumor reaches all $n$ vertices. In particular,
when $\alpha=1$, the spreading time becomes polynomial in $n$ (even if
$(G_{t})_{t\geq 0}$ was a sequence of expander graphs).

######  Theorem 4.10.

Let $(G_{t})_{t\geq 0}$ be any sequence of regular $n$-vertex graphs, and
consider a process $\mathcal{P}$ that is both a $C_{\mathrm{grow}}$-growing
process and a $C_{\mathrm{shrink}}$-shrinking process, where
$C_{\mathrm{shrink}}<1$ is constant, with a power law credibility function.
Then, for any constant $\alpha<1$, there are constants
$0<\kappa_{1}:=\kappa_{1}(\alpha)<\kappa_{2}:=\kappa_{2}(\alpha)$ such that
for any $T_{1}\leq\kappa_{1}\cdot(\frac{1}{\Psi}\cdot\log n)^{1/(1-\alpha)}$,
$T_{2}\geq\kappa_{2}\cdot(\frac{1}{\Phi}\cdot\log n)^{1/(1-\alpha)}$ and any
$\eta>0$ we have,

  * $(i)$

$\mathbf{P}\left[\,|I_{T_{1}}|<n^{1/2+\eta}\,\right]\geq 1-n^{-\eta}$,

  * $(ii)$

$\mathbf{P}\left[\,|I_{T_{2}}|=n\,\right]\geq 1-o(1)$.

Further, if $\alpha=1$, then there are constants $0<\kappa_{1}<\kappa_{2}$,
such that for any $T_{1}\leq\left(\frac{1}{\Psi}\cdot n\right)^{\kappa_{1}}$
and $T_{2}\geq\left(\frac{1}{\Phi}\cdot n\right)^{\kappa_{2}}$,

  * $(iii)$

$\mathbf{P}\left[\,|I_{T_{1}}|<n^{1/2+\eta}\,\right]\geq 1-n^{-\eta}$,

  * $(iv)$

$\mathbf{P}\left[\,|I_{T_{2}}|=n\,\right]\geq 1-o(1)$.

###### Proof.

We begin with the proof of $(i)$. Observe that

$\prod_{t=0}^{T_{1}-1}\left(1+\Psi(t)\cdot
q(t)\right)\leq\exp\left(\Psi\cdot\sum_{t=1}^{T_{1}}t^{-\alpha}\right)\stackrel{{\scriptstyle(a)}}{{\leq}}\exp\left(\frac{1}{1-\alpha}\cdot\Psi\cdot
T_{1}^{1-\alpha}\right)\stackrel{{\scriptstyle(b)}}{{=}}\exp\left(\frac{1}{1-\alpha}\cdot\kappa_{1}\log
n\right)\stackrel{{\scriptstyle(c)}}{{\leq}}\sqrt{n},$

where $(a)$ holds by A.16 $(b)$ holds by the definition of $T_{1}$ and $(c)$
holds if $\kappa_{1}\leq(\frac{1-\alpha}{2})^{\frac{1}{1-\alpha}}$. The result
then follows from Theorem 4.5, where we take $\rho=1/\sqrt{n}$.

Proof of $(ii)$: We seek to apply Theorem 4.6. Since $1+x\geq e^{x/4}$ for
$0\leq x\leq 1$, and by A.16, we have

$\prod_{t=0}^{T_{2}-1}\left(1+\Phi(t)\cdot
q(t)\right)\geq\exp\left(\frac{1}{4}\cdot\Phi\cdot\sum_{t=1}^{T_{2}}t^{-\alpha}\right)\geq\exp\left(\frac{1}{4}\cdot\frac{1}{1-\alpha}\cdot\Phi\cdot\left(T_{2}^{1-\alpha}-1\right)\right).$

Now, by the definition of $T_{2}$ and if
$\kappa_{2}\geq(\tfrac{16(1-\alpha)}{\Phi\xi})^{\frac{1}{1-\alpha}}$, where
$\xi=10^{-30}$, then we have

$\prod_{t=0}^{T_{2}-1}\left(1+\Phi(t)\cdot
q(t)\right)\geq\exp\left(\frac{1}{4}\cdot\frac{1}{1-\alpha}\cdot\Phi\cdot\left(\tfrac{16(1-\alpha)}{\Phi\xi}\log
n-1\right)\right)\geq\exp\left(\left(\frac{2}{\xi}+1\right)\cdot\log
n\right),$

Hence, taking logarithms, we satisfy the precondition of Theorem 4.6.

The proofs of statements $(iii)$ and $(iv)$ for $\alpha=1$ are analogous,
noting that $\sum_{t=1}^{T}t^{-1}=\ln(T)+\Theta(1)$.∎

###  4.3 Additive Credibility

######  Definition 4.11 (Additive credibility).

Let $\alpha\in(0,1)$ . Then, the additive credibility function is defined for
any round $t\geq 0$ as

$q_{\alpha}(t)=q(t):=(1-t\cdot\alpha)^{+},$

where $z^{+}=\max(z,0)$. In particular, in the first round (when $t=0$) the
credibility function is $1$.

In comparison to the power-law credibility function, the additive credibility
function has a time-independent decrease. As we will see below, the
interesting regime (for expanders) is when $\alpha=\Theta(1/\log n)$. That
means, unlike the power-law-credibility, the additive credibility function
remains close to $1$ for a significant number of rounds. However, after
$O(\log^{2}n)$ steps, the credibility becomes polynomially small; much smaller
than any power-law credibility at this point.

Let us consider the additive credibility function in the PUSH and PULL model
for regular graphs. We also observe that if we let $T=1/\alpha$, $I_{T}$ is
the maximal set of informed vertices in every execution, as $q(t)=0$ for
$t\geq T$. We start by proving an upper bound on $I_{T}$ for $T=1/\alpha$,
followed by a lower bound. We remark that, due to the specific nature of
$q(t)$, we can use Stirling’s approximation to determine a rather precise
threshold for the parameter $\alpha$.

######  Theorem 4.12.

Let $(G_{t})_{t\geq 0}$ be a sequence of regular $n$-vertex strong expander
graphs, and consider the PUSH or PULL protocol with an additive credibility
function. Let $\mathcal{P}\in\\{{\rm{\texttt{PUSH}}},{\rm{\texttt{PULL}}}\\}$.

  * $(i)$

Let $\alpha\geq\frac{\log\left(\frac{4}{e}\right)}{\log n+\log\zeta}$, where
$\frac{1}{n}<\zeta<\frac{1}{\sqrt{2}\cdot 2}$ . Then, for any $T:=1/\alpha$
and for any $\eta>0$ (not necessarily constant),

$\mathbf{P}\left[\,|I_{T}|\leq\sqrt{2}\cdot\zeta\cdot n^{1+\eta}\,\right]\geq
1-n^{-\eta}.$

  * $(ii)$

Further, let
$\alpha\leq\frac{\log\left(\frac{4}{e}\right)}{\log\left(2\sqrt{2}\cdot\exp\left(\frac{1}{\gamma_{\mathcal{P}}}\cdot\frac{\log
n+7(\log n)^{2/3}}{\left(1-(1-\xi)\cdot(\log
n)^{-\xi}\right)^{2}}\right)\right)}$, for $\gamma_{\mathcal{P}}$ as in
Theorem 4.7. Then, for $T:=1/\alpha$,

$\mathbf{P}\left[\,|I_{T}|\geq n\cdot\left(1-\exp(-\sqrt{\log
n})\right)\,\right]\geq 1-o(1).$

###### Proof.

We begin with Item $(i)$, where we seek to apply Theorem 4.5. We note that by
Lemma 2.3 (i) and Lemma 2.3 (ii), for both PUSH and PULL, $\delta_{t}\leq
q(t)\cdot\varphi(I_{t})$. Thus, for PUSH and PULL,

$\Psi(t):=\max_{\begin{subarray}{c}I\subseteq V\colon\\\ 1\leq|I|\leq
n-1\end{subarray}}\frac{\delta_{t}(I)}{q(t)}\leq\max_{\begin{subarray}{c}I\subseteq
V\colon\\\ 1\leq|I|\leq n-1\end{subarray}}\frac{q(t)\cdot\varphi(I)}{q(t)}\leq
1.$ (4.22)

Hence, by using Eq. 4.22 in $(a)$, A.18 in $(b)$, and the definition of
$\alpha$ in $(c)$, we have

$\displaystyle\prod^{T-1}_{t=0}\left(1+\Psi(t)\cdot q(t)\right)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\prod^{T-1}_{t=0}(1+q(t))\leq\prod^{1/\alpha-1}_{t=0}(1+(1-t\cdot\alpha))=\prod_{t=0}^{1/\alpha-1}\left(2-t\cdot\alpha\right)\stackrel{{\scriptstyle(b)}}{{\leq}}\sqrt{2}\cdot\left(\frac{4}{e}\right)^{1/\alpha}\stackrel{{\scriptstyle(c)}}{{\leq}}\sqrt{2}\cdot\zeta
n.$

Taking logarithms yields,

$\sum^{T-1}_{t=0}\log(1+\Psi(t)\cdot
q(t))\leq\log\left(\sqrt{2}\cdot\zeta\cdot n\right).$

By Theorem 4.5, we obtain
$\mathbf{E}\left[\,|I_{T}|\,\right]\leq\sqrt{2}\cdot\zeta\cdot n$ as well as
the tail bound by Markov’s inequality.

Proof of Item $(ii)$: For the second statement, we seek to apply Theorem 4.7.
By a simple coupling argument, we may assume that
$\alpha=\log\left(\frac{4}{e}\right)/\log\left(2\sqrt{2}\cdot\exp\left(\frac{1}{\gamma_{\mathcal{P}}}\cdot\frac{\log
n+7(\log n)^{2/3}}{\left(1-(1-\xi)\cdot(\log
n)^{-\xi}\right)^{2}}\right)\right)$, since by making $\alpha$ smaller, $q(t)$
increases and therefore only more vertices get informed. Recall that as in
Theorem 4.7,

$\varepsilon:=1-\max_{t\geq\frac{1}{2\log(2)}\cdot\log(n)}q(t).$

To satisfy the precondition on $q(t)$ of Theorem 4.7, we need that
$\varepsilon\geq\frac{1}{\log n}$ for all $t\geq\frac{1}{2\log 2}$. By
definition of the additive credibility function (and the fact it is non-
increasing in $t\geq 0$), it holds for any $t\geq\frac{1}{2\log 2}\cdot\log n$
that

$\varepsilon=1-q\left(\frac{1}{2\log 2}\cdot\log n\right)\geq
1-(1-\frac{1}{2\log 2}\cdot\log n\cdot\alpha).$

Since the choice of $\alpha$ implies that
$\alpha\geq\frac{\log(4/e)}{\frac{1}{2}\cdot\log n}$, it follows that

$\varepsilon\geq\frac{\log(4/e)}{4\log 2}>\frac{1}{10}.$

Therefore the precondition on $q(t)$ of Theorem 4.7 holds. Furthermore, by
using A.19 in $(a)$,

$\prod_{t=0}^{T-1}(1+q(t))=\prod^{1/\alpha-1}_{t=0}(1+q(t))=\prod^{1/\alpha-1}_{t=0}\left(2-t\cdot\alpha\right)\stackrel{{\scriptstyle(a)}}{{\geq}}\frac{1}{\sqrt{2}}\left(\frac{4}{e}\right)^{1/\alpha}\cdot
e^{-1/2\cdot\alpha}$

Now, using in $(b)$ that $e^{-1/2\cdot\alpha}\geq\frac{1}{2}$ for our choice
of $\alpha=O(\frac{1}{\log n})$, and in $(c)$ again our specific choice of
$\alpha$ gives

$\prod_{t=0}^{T-1}(1+q(t))\stackrel{{\scriptstyle(b)}}{{\geq}}\frac{1}{\sqrt{2}}\left(\frac{4}{e}\right)^{1/\alpha}\cdot\frac{1}{2}\stackrel{{\scriptstyle(c)}}{{\geq}}\exp\left(\frac{1}{\gamma_{\mathcal{P}}}\cdot\frac{\log
n+7\left(\log
n\right)^{2/3}}{\left(1-(1-\xi)\cdot(\log)^{-\xi}\right)^{2}}\right),$

Taking logarithms yields,

$\sum_{t=0}^{T-1}\log(1+q(t))\geq\frac{1}{\gamma_{\mathcal{P}}}\cdot\frac{\log
n+7\left(\log n\right)^{2/3}}{\left(1-(1-\xi)\cdot(\log)^{-\xi}\right)^{2}},$

and hence also the precondition Eq. 4.10 in Theorem 4.7 holds. Therefore,
statement $(ii)$ follows by Theorem 4.7. ∎

###  4.4 Multiplicative Credibility

######  Definition 4.13 (Multiplicative credibility).

Let $\alpha\in(0,1)$ . Then, the multiplicative credibility function is
defined for any round $t\geq 0$ as

$q_{\alpha}(t):=(1-\alpha)^{t}.$

In particular, in the first round the credibility function is $1$.

The next result is the multiplicative analogue of Theorem 4.12.

######  Theorem 4.14.

Let $(G_{t})_{t\geq 0}$ be any sequence of regular $n$-vertex strong expander
graphs, and consider the PUSH or PULL protocol with a multiplicative
credibility function . Then, there are constants $\kappa_{1}\leq\frac{1}{2}$
and $\kappa_{2}\geq\frac{1}{8}$, such that the following holds.

  * $(i)$

If $\alpha\geq\frac{\kappa_{1}}{\log n}$, then for any $T\geq 1$,
$\mathbf{E}_{t}\left[\,|I_{T}|\,\right]\leq\sqrt{n}$, and hence for any
$\eta>0$ (not necessarily constant),

$\mathbf{P}\left[\,|I_{T}|\leq n^{1/2+\eta}\,\right]\geq 1-n^{-\eta}.$

  * $(ii)$

Further, if $\alpha\leq\frac{\kappa_{2}}{\log n}$, then, for any $T\geq 4\log
n$,

$\mathbf{P}\left[\,|I_{T}|\geq n\cdot\left(1-\exp(-(\log
n)^{1/2})\right)\,\right]\geq 1-o(1).$

######  Remark 4.15.

We believe that with a more refined analysis it would be also possible to show
that $\kappa_{2}\geq(1-o(1))\cdot\kappa_{1}$, but for the sake of simplicity
and space we only prove this weaker dichotomy here.

###### Proof.

We note again that by Lemma 2.3, $\delta_{t}\leq q(t)\cdot\varphi(I_{t})$.
Hence, similarly as in the proof of Theorem 4.12

$\Psi(t):=\max_{\begin{subarray}{c}I\subseteq V\colon\\\ 1\leq|I|\leq
n-1\end{subarray}}\frac{\delta_{t}(I)}{q(t)}\leq\max_{\begin{subarray}{c}I\subseteq
V\colon\\\ 1\leq|I|\leq n-1\end{subarray}}\frac{q(t)\cdot\varphi(I)}{q(t)}\leq
1.$ (4.23)

Proof of $(i)$: Moreover, we set $\kappa_{1}:=\frac{1}{2}$, then for any
$T\geq 0$,

$\displaystyle\prod_{t=0}^{T-1}\left(1+\Psi(t)\cdot q(t)\right)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\prod_{t=0}^{T-1}\left(1+q(t)\right)\leq\prod_{t=0}^{\infty}\left(1+\left(1-\alpha\right)^{t}\right)\stackrel{{\scriptstyle(b)}}{{\leq}}\prod_{t=0}^{\infty}\left(1+\left(1-\frac{1/2}{\log
n}\right)^{t}\right)\stackrel{{\scriptstyle(c)}}{{\leq}}\sqrt{n},$

where $(a)$ holds by Eq. 4.23, $(b)$ by our bound on $\alpha$, and $(c)$ by
A.20$(i)$. Taking logarithms, the statement holds by Theorem 4.5.

Proof of $(ii)$: For the second statement, we set $\kappa_{2}:=\frac{1}{8}$,
and then for $T:=4\log n$,

$\prod_{t=0}^{4\log n-1}(1+q(t))=\prod_{t=0}^{4\log
n-1}\left(1+(1-\alpha)^{t}\right)\stackrel{{\scriptstyle(a)}}{{\geq}}\prod_{t=0}^{4\log
n-1}\left(1+\left(1-\frac{1/8}{\log
n}\right)^{t}\right)\stackrel{{\scriptstyle(b)}}{{\geq}}n^{3/2},$ (4.24)

where $(a)$ follows for our value of $\alpha$ and $(b)$ by A.20 $(ii)$.

Taking the logarithm of (4.24), we see that the first precondition of Theorem
4.7 is met for $T=4\log n$. Also, by definition of the multiplicative
credibility function, we have for any constant $c_{2}>0$ another constant
$\varepsilon=\varepsilon(c_{2})>0$ such that for any $t\geq c_{2}\log n$,
$q(t)\leq 1-\varepsilon$, which is the second precondition . Therefore,
Theorem 4.7 applies, completing the proof. ∎

###  4.5 Fixed Credibility

Here, we consider $q(t)=q$ to be constant over time (however, $q(t)$ may
depend on $n$). This model was studied in previous works [12, 17] on complete
graphs and strong expanders (2.1), respectively (under the guise of
“robustness”). Here we provide upper bounds for the spreading time of the
PUSH, PULL and PUSH-PULL model on regular strong expander graphs, using our
framework. As the analysis between the protocols are very similar, we will
only give details in the case of PUSH here.

######  Theorem 4.16 (cf. [12]).

Let $(G_{t})_{t\geq 0}$ be any sequence of regular $n$-vertex strong expander
graphs. Let the credibility function $q(t)=q$ be constant in
$(0,1-\varepsilon]$ for some constant $\varepsilon>0$ and define the following
times

  * •

$T_{{\rm{\texttt{PUSH}}}}:=(1+o(1))\cdot\left(\frac{1}{\log(1+q)}+\frac{1}{q}\right)\cdot\log
n$,

  * •

$T_{{\rm{\texttt{PULL}}}}:=(1+o(1))\cdot\left(\frac{1}{\log(1+q)}-\frac{1}{\log(1-q)}\right)\cdot\log
n$,

  * •

$T_{{\rm{\texttt{PUSH-
PULL}}}}:=(1+o(1))\cdot\left(\frac{1}{\log(1+2q)}+\frac{1}{q-\log(1-q)}\right)\cdot\log
n$.

Then for each
$\mathcal{P}\in\\{{\rm{\texttt{PUSH}}},{\rm{\texttt{PULL}}},{\rm{\texttt{PUSH-
PULL}}}\\}$ we have

$\mathbf{P}\left[\,|I_{T_{\mathcal{P}}}|=n\,\right]\geq 1-o(1).$

We note that the corresponding result [12, Theorem 1.2] in the original paper
is stated only for static graphs, however it is likely that the methods in
that paper would also extend to dynamic graphs.

###### Proof.

Here, we only provide a proof of the PUSH model. We note that if $q\leq
1-\varepsilon$, by Lemma 2.8 (i) PUSH is a $C_{\mathrm{shrink}}$-shrinking
process for $C_{\mathrm{shrink}}=1-\varepsilon$. We will again follow the
approach outlined at the beginning of this section, where we break up the
analysis into phases. An overview of the running times of these phases is
given in Table 3, also for the PULL and PUSH-PULL processes.

Phase | Start/finish sizes | PUSH | PULL | PUSH-PULL
---|---|---|---|---
1 | $A=1,B=\log n$ | $\frac{\log\log n}{\log\left(1+q\right)}$ | $\frac{\log\log n}{\log(1+q)}$ | $\frac{\log\log n}{\log\left(1+2q\right)}$
2 | $A=\log n,B=\frac{n}{\log n}$ | $\frac{\log n}{\log(1+q)}$ | $\frac{\log n}{\log\left(1+q\right)}$ | $\frac{\log n}{\log(1+2q)}$
3 | $A=\frac{n}{\log n},B=\frac{n}{2}$ | $\frac{\log\log n}{\log(1+q)}$ | $\frac{\log\log n}{\log(1+q)}$ | $\frac{\log\log n}{\log(1+2q)}$
4 |  $C=n/2$, $D=\frac{n}{\log n}$ | $\frac{1}{q}\log\log n$ | $\frac{\log\log n}{-\log\left(1-q\right)}$ | $\frac{\log\log n}{q-\log\left(1-q\right)}$
5 | $C=\frac{n}{\log n},D=\log n$ | $\frac{1}{q}\log n$ | $\frac{\log n}{-\log\left(1-q\right)}$ | $\frac{\log n}{q-\log\left(1-q\right)}$
6 | $C=\log n,D=\frac{3}{4}$ | $\frac{1}{q}\log\log n$ | $\frac{\log\log n}{-\log\left(1-q\right)}$ | $\frac{\log\log n}{q-\log\left(1-q\right)}$
Table 3: Runtimes for PUSH, PULL and PUSH-PULL for different phases obtained
by Theorem 3.1 (row 1,2,3) and Theorem 3.5 (row 4,5,6), all bounds hold
w.h.p.. The upper bounds contained within cells shaded in  Green  hold up to a
multiplicative $(1+o(1))$ factor and it is these bound which contribute to the
to total run time, all other bounds hold up to a multiplicative constant and
are negligible. Our result for PULL holds only when $q$ is bounded away from
$1$, the remaining cases where $q$ is equal (or tending to) $1$ are covered in
[17, 12].

#### Phase 1:

Recall that $\xi=10^{-30}$, as defined in Corollary 4.3, and define the time

$t_{1}:=\min\left\\{s\geq
0\colon\sum^{s-1}_{t=0}\log\left(1+q\cdot\left(1-\frac{q}{2}\right)\cdot\frac{1}{2}\right)\geq\frac{\log\log
n+o(\log\log n)}{\xi^{2}}\right\\}.$

We aim to apply Corollary 4.3 with $A=1$ and $B=\log n$. We note that by Lemma
2.3 (i)

$\delta_{t}\geq\delta_{t}^{[1,\log n]}\geq
q\cdot\left(1-\frac{q}{2}\right)\cdot\phi_{\log n}.$

Moreover, since $(G_{t})_{t\geq 0}$ is a strong expander and we can assume $n$
is large, by Lemma A.12

$\phi_{\log n}\geq(1-\lambda)\cdot\left(1-\frac{\log
n}{n}\right)\geq\frac{1}{2}.$ (4.25)

Hence, setting
$\nu_{t}^{[A,B]}=q\cdot\left(1-\frac{q}{2}\right)\cdot\frac{1}{2}$, by
Corollary 4.3 we get that,

$\mathbf{P}\left[\,|I_{t_{1}}|\geq\log n~{}\Big{|}~{}|I_{0}|\geq
1\,\right]\geq 1-o(1).$

Let us now solve for $t_{1}$ to get an upper bound on how long Phase 1 takes.
We note that by minimality of $t_{1}$,

$\displaystyle(t_{1}-1)\cdot\log\left(1+q\cdot\left(1-\frac{q}{2}\right)\cdot\frac{1}{2}\right)$
$\displaystyle=\sum_{t=0}^{t_{1}-1}\log\left(1+q\cdot\left(1-\frac{q}{2}\right)\cdot\frac{1}{2}\right)$
$\displaystyle\leq\frac{\log\log n+o(\log\log
n)}{\xi^{2}}+\log\left(1+q\cdot\left(1-\frac{q}{2}\right)\cdot\frac{1}{2}\right).$

Rearranging, we get that,

$\displaystyle t_{1}$ $\displaystyle\leq 2+\frac{\log\log n+o(\log\log
n)}{\xi^{2}\cdot\log\left(1+q\cdot\left(1-\frac{q}{2}\right)\cdot\frac{1}{2}\right)}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}2+\frac{\log\log
n+o(\log\log
n)}{\xi^{2}\cdot\left(1-\frac{q}{2}\right)\cdot\frac{1}{2}\cdot\log\left(1+q\right)}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}O\left(\frac{\log\log
n}{\log\left(1+q\right)}\right),$

where $(a)$ follows from A.14 and $(b)$ holds since we assume $G_{t}$ to be a
(strong) expander.

#### Phase 2:

Let

$t_{2}:=\min\left\\{s\geq
t_{1}\colon\sum^{s-1}_{t=t_{1}}\log\left(1+q\cdot\left(1-7\sqrt{\lambda+\frac{1}{\log
n}}\right)\right)\geq\frac{\log n-2\log\log n+o(\log
n)}{\left(1-(1-\xi)\cdot\log n^{-\xi}\right)^{2}}\right\\}.$

Again, we aim to apply Corollary 4.3, this time with $A=\log n$ and
$B=\frac{n}{\log n}$. By Lemma 2.4

$\displaystyle\delta_{t}\geq\delta^{[\log n,\frac{\log n}{n}]}_{t}\geq
q\cdot\left(1-7\sqrt{\lambda+\frac{1}{\log n}}\right).$

Thus by Corollary 4.3 for
$\nu^{[A,B]}_{t}=q\cdot\left(1-7\sqrt{\lambda+\frac{1}{\log n}}\right)$,

$\mathbf{P}_{t_{1}}\left[\,|I_{t_{2}}|\geq\frac{n}{\log
n}~{}\Big{|}~{}|I_{t_{1}}|\geq\log n\,\right]\geq 1-o(1).$

Similarly as in Phase 1, solving for $t_{2}-t_{1}$, we obtain,

$\displaystyle t_{2}-t_{1}$ $\displaystyle\leq 2+\frac{\log n-2\log\log
n+o(\log n)}{\left(1-(1-\xi)\cdot\log
n^{-\xi}\right)^{2}\cdot\log\left(1+q\cdot\left(1-7\sqrt{\lambda+\frac{1}{\log
n}}\right)\right)}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}2+\frac{\log n-2\log\log
n+o(\log n)}{\left(1-(1-\xi)\cdot\log
n^{-\xi}\right)^{2}\cdot\left(1-7\sqrt{\lambda+\frac{1}{\log
n}}\right)\log(1+q)}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}(1+o(1))\cdot\frac{\log
n}{\log(1+q)},$

where again $(a)$ follows from A.14 and $(b)$ follows from $G_{t}$ being a
strong expander (note that here, unlike as in Phase $1$ and $3$, we do need
that $G_{t}$ is a _strong_ expander (Eq. 2.1)).

#### Phase 3:

Let

$t_{3}:=\min\left\\{s\geq
t_{2}\colon\sum^{s-1}_{t=t_{2}}\log\left(1+q\cdot\left(1-\frac{q}{2}\right)\cdot\frac{1}{2}\cdot(1-\lambda)\right)\geq\frac{\log\log
n-\log\log 2+o(\log\log n)}{\left(1-(1-\xi)\cdot\left(\frac{n}{\log
n}\right)^{-\xi}\right)^{2}}\right\\}.$

We want to apply Corollary 4.3 with $A=\frac{n}{\log n},B=n/2$. For
$\frac{n}{\log n}\leq|I_{t}|\leq\frac{n}{2}$ it holds that,

$\delta_{t}\geq\delta_{t}^{[\frac{n}{\log
n},n/2]}\stackrel{{\scriptstyle(a)}}{{\geq}}q\cdot\left(1-\frac{q}{2}\right)\cdot\varphi(I_{t})\stackrel{{\scriptstyle(b)}}{{\geq}}q\cdot\left(1-\frac{q}{2}\right)\cdot\frac{1}{2}\left(1-\lambda\right),$

where $(a)$ holds by Lemma 2.3 (i) and $(b)$ by Lemma A.12. Thus, by Corollary
4.3 with
$\nu^{[A,B]}_{t}=q\cdot\left(1-\frac{q}{2}\right)\cdot\frac{1}{2}\left(1-\lambda\right)$,
we get that

$\mathbf{P}_{t_{2}}\left[\,|I_{t_{3}}|\geq\frac{n}{2}~{}\Big{|}~{}|I_{t_{2}}|\geq\frac{n}{\log
n}\,\right]\geq 1-o(1).$

Solving for $t_{3}-t_{2}$ results in,

$\displaystyle t_{3}-t_{2}$ $\displaystyle\leq 2+\frac{\log\log n-\log\log
2+o(\log\log n)}{\left(1-(1-\xi)\cdot\left(\frac{n}{\log
n}\right)^{-\xi}\right)^{2}\cdot\log\left(1+q\cdot\left(1-\frac{q}{2}\right)\cdot\frac{1}{2}\cdot\left(1-\lambda\right)\right)}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}2+\frac{\log\log n-\log\log
2+o(\log\log n)}{\left(1-(1-\xi)\cdot\left(\frac{n}{\log
n}\right)^{-\xi}\right)^{2}\cdot\frac{1}{2}\cdot\left(1-\lambda\right)\cdot\left(1-\frac{q}{2}\right)\cdot\log\left(1+q\right)}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}O\left(\frac{\log\log
n}{\log(1+q)}\right),$

where again $(a)$ follows form A.14 and $(b)$ follows from $G_{t}$ being a
(strong) expander.

#### Phase 4:

Let

$t_{4}:=\min\left\\{s\geq
t_{3}\colon\sum^{s-1}_{t=t_{3}}\log\left(1-\left(1-e^{-q}\right)\cdot\frac{1}{2}\cdot\left(1-\lambda\right)\right)\leq-\frac{\log\log
n-\log\log 2+o(\log\log n)}{\left(1-\frac{\log
n}{2\cdot\left(1-C_{\mathrm{shrink}}\right)\cdot n}\right)}\right\\}.$

For this Phase we aim to apply Corollary 4.4 with $C=n/2$ and $D=\frac{n}{\log
n}$. Note that $t_{4}$ is a deterministic upper bound on the stopping time
$\tau$ from Corollary 4.4, and that for $D=\frac{n}{\log
n}$,$\gamma=1-\min\left(\frac{1}{2\left(1-C_{\mathrm{shrink}}\right)\cdot\frac{n}{\log
n}},\frac{1}{2}\right)=1-\frac{\log
n}{2\left(1-C_{\mathrm{shrink}}\right)\cdot n}$. By Lemma 2.5 and Lemma A.12

$\displaystyle\delta_{t}\geq\delta_{t}^{[\frac{n}{\log
n},n/2]}\geq\Bigl{(}1-e^{-q(t)}\Bigr{)}\cdot\varphi(I_{t})\geq\Bigl{(}1-e^{-q(t)}\Bigr{)}\cdot\frac{1}{2}\cdot\left(1-\lambda\right).$

Thus, letting
$\nu^{[C,D]}_{t}=\Bigl{(}1-e^{-q(t)}\Bigr{)}\cdot\frac{1}{2}\cdot\left(1-\lambda\right)$,
by Corollary 4.4

$\mathbf{P}_{t_{3}}\left[\,|U_{t_{4}}|\leq\frac{n}{\log
n}~{}\Big{|}~{}|U_{t_{3}}|\leq\frac{n}{2}\,\right]\geq 1-o(1).$

We note that by minimality of $t_{4}$,

$\displaystyle\sum_{t=t_{3}}^{t_{4}-1}\log\left(1-\left(1-e^{-q}\right)\cdot\frac{1}{2}\cdot\left(1-\lambda\right)\right)$
$\displaystyle=\left(t_{4}-t_{3}-1\right)\cdot\log\left(1-\left(1-e^{-q}\right)\cdot\frac{1}{2}\cdot\left(1-\lambda\right)\right)$
$\displaystyle\geq-\frac{\log\log n-\log\log 2+o(\log\log
n)}{\left(1-\frac{\log n}{2\cdot\left(1-C_{\mathrm{shrink}}\right)\cdot
n}\right)}+\log\left(1-\left(1-e^{-q}\right)\cdot\frac{1}{2}\cdot\left(1-\lambda\right)\right)$

Solving for $t_{4}-t_{3}$, we get that,

$\displaystyle t_{4}-t_{3}$ $\displaystyle\leq 2-\frac{\log\log n-\log\log
2+o(\log\log n)}{\left(1-\frac{\log
n}{2\cdot\left(1-C_{\mathrm{shrink}}\right)\cdot
n}\right)\cdot\log\left(1-\left(1-e^{-q}\right)\cdot\frac{1}{2}\cdot\left(1-\lambda\right)\right)}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}2+\frac{\log\log n-\log\log
2+o(\log\log n)}{\left(1-\frac{\log
n}{2\cdot\left(1-C_{\mathrm{shrink}}\right)\cdot
n}\right)\cdot\left(1-e^{-q}\right)\cdot\frac{1}{2}\cdot\left(1-\lambda\right)}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}2+\frac{\log\log n-\log\log
2+o(\log\log n)}{\left(1-\frac{\log
n}{2\cdot\left(1-C_{\mathrm{shrink}}\right)\cdot n}\right)\cdot
q\cdot\left(1-\lambda\right)}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}O\left(\frac{\log\log
n}{q}\right),$

where in $(a)$ we used the bound $-\log(1-x)\geq x$ for any $x\in(0,1)$, in
$(b)$ we have used $e^{-x}\leq 1-x/2$ which holds for all $x\in[0,1.59]$ and
finally in $(c)$ the fact that $1-C_{\mathrm{shrink}}=\varepsilon>0$ for
$\varepsilon$ constant, and that $G_{t}$ is a strong expander.

#### Phase 5:

Let

$t_{5}:=\left\\{s\geq
t_{4}\colon\sum^{s-1}_{t=t_{4}}\log\left(1-\left(1-e^{-q}\right)\cdot(1-\lambda)\cdot\left(1-\frac{1}{\log
n}\right)\right)\leq-\frac{\log n-2\log\log n+o(\log
n)}{1-\frac{1}{2\left(1-C_{\mathrm{shrink}}\right)\log n}}\right\\}.$

By Lemma 2.5 and Lemma A.12

$\delta_{t}\geq\delta_{t}^{[\log
n,\frac{n}{\log}]}\geq\left(1-e^{-q}\right)\cdot\left(1-\lambda\right)\cdot\left(1-\frac{1}{\log
n}\right)$

By Corollary 4.4 with $C=\frac{n}{\log n},D=\log n$ and
$\nu_{t}^{[C,D]}=\left(1-e^{-q(t)}\right)\cdot\left(1-\lambda\right)\cdot\left(1-\frac{1}{\log
n}\right)$, we get that

$\mathbf{P}_{t_{4}}\left[\,|U_{t_{5}}|\leq\log
n~{}\Big{|}~{}|U_{t_{4}}|\leq\frac{n}{\log n}\,\right]\geq 1-o(1).$

Again, solving for $t_{5}-t_{4}$ we obtain that,

$t_{5}-t_{4}\leq 2-\frac{\log n-2\log\log n+o(\log
n)}{(1-\frac{1}{2\left(1-C_{\mathrm{shrink}}\right)\log
n})\cdot\log\left(1-\left(1-e^{-q(t)}\right)\cdot(1-\lambda)\cdot\left(1-\frac{1}{\log
n}\right)\right)}.$ (4.26)

Now, using A.15 in $(a)$, and in $(b)$ using the fact that $G_{t}$ is a strong
expander, we have

$\displaystyle\log\left(1-(1-e^{-q})\cdot(1-\lambda)\cdot\left(1-\frac{1}{\log
n}\right)\right)$
$\displaystyle=\log\left(1-\left(1-\left(\lambda+\frac{1}{\log
n}-\frac{\lambda}{\log n}\right)\right)\cdot(1-e^{-q})\right)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\left(1-\frac{\lambda+\frac{1}{\log
n}-\frac{\lambda}{\log n}}{e^{-q}}\right)\log\left(1-(1-e^{-q})\right)$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}-(1-o(1))\cdot q.$

Inserting this into Eq. 4.26 gives us

$t_{5}-t_{4}\leq 2+\frac{\log n-2\log\log n+o(\log
n)}{(1-\frac{1}{2\left(1-C_{\mathrm{shrink}}\right)\log n})\cdot
q}\stackrel{{\scriptstyle(a)}}{{=}}(1+o(1))\cdot\frac{\log n}{q},$

where in $(a)$ we have used $1-C_{\mathrm{shrink}}=\varepsilon>0$ for
$\varepsilon$ constant.

#### Phase 6:

Let

$\displaystyle t_{6}:=\min\biggl{\\{}s\geq t_{5}\colon$
$\displaystyle\sum^{s-1}_{t=t_{5}}\log\left(1-\left(1-e^{-q}\right)\cdot\frac{1}{2}\right)\leq-2\left({\log\log
n-\log\left(\frac{3}{4}\right)+o(\log\log n)}\right)\biggr{\\}}.$

By Lemma 2.5 and Lemma A.12, and as $(G_{t})_{t\geq 0}$ is a strong expander,
we have

$\delta_{t}\geq\delta_{t}^{[3/4,\log
n]}\geq\left(1-e^{-q(t)}\right)\cdot(1-\lambda)\cdot\left(1-\frac{\log
n}{n}\right)\geq\left(1-e^{-q(t)}\right)\cdot\frac{1}{2}.$

By Corollary 4.4 with $C=\log n,D=3/4$ and
$\nu_{t}^{[C,D]}=\left(1-e^{-q}\right)\cdot\frac{1}{2}$,

$\mathbf{P}_{t_{5}}\left[\,|U_{t_{6}}|\leq 3/4~{}\Big{|}~{}|U_{t_{5}}|\leq\log
n\,\right]\geq 1-o(1).$

Solving for $t_{6}-t_{5}$, we get that

$\displaystyle t_{6}-t_{5}$ $\displaystyle\leq 2-2\cdot\frac{\log\log
n-\log\left(\frac{3}{4}\right)+o(\log\log
n)}{\log\left(1-\left(1-e^{-q}\right)\cdot\frac{1}{2}\right)}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}2+4\cdot\frac{\log\log
n+o(\log\log n)}{\left(1-e^{-q}\right)}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}2+8\cdot\frac{\log\log
n+o(\log\log n)}{q}$ $\displaystyle=O\left(\frac{\log\log n}{q}\right),$

where, similarly to Phase 4, in $(a)$ we used $-\log(1-x)\geq x$ for any
$x<1$, and in $(b)$ we have used $e^{-x}\leq 1-x/2$ which holds for all
$x\in[0,1.59]$.

To conclude, we see that the dominant contributions to the running time come
from Phases $2$ and $5$, thus, the total running time is bounded from above by
$(1+o(1))\cdot\left(\frac{1}{\log(1+q)}+\frac{1}{q}\right)\cdot\log n$. ∎

##  5 Conclusions

In this work, we presented a general framework for analyzing spreading
processes with a time-dependent credibility function. The key idea is to link
the spreading progress to an aggregate sum of growth (or shrinking) factors
over consecutive rounds. In that way, our approach generalizes various
previous works that were based on estimating the worst-case growth across all
sets via the conductance of the graph. We also obtained several dichotomy
results in terms of the number of vertices that get informed, both for general
and more concrete credibility functions (see Section 4).

In terms of open problems, a natural direction is to generalize our main
technical results from regular graphs to arbitrary graphs, which we believe to
be doable. Another avenue for future research is to allow more complex
interactions between the credibility function $q(t)$ and the evolving set of
informed vertices $I_{t}$, which could more accurately model an external
influence on the network (e.g., fact-checkers). Lastly, one could consider
more general spreading processes including other epidemic models (e.g., SIR
model or independent cascade model), majority dynamics or variants of the
voter model, in which informed vertices may also become uninformed in future
steps.

## References

  * [1] Noga Alon and Joel H Spencer.  The probabilistic method.  John Wiley & Sons, 2016.
  * [2] Ruben Becker, Arnaud Casteigts, Pierluigi Crescenzi, Bojana Kodric, Malte Renken, Michael Raskin, and Viktor Zamaraev.  Giant components in random temporal graphs.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2023, volume 275 of LIPIcs, pages 29:1–29:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023\.
  * [3] Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah.  Randomized gossip algorithms.  IEEE transactions on information theory, 52(6):2508–2530, 2006\.
  * [4] Andrei Z. Broder, Alan M. Frieze, Stephen Suen, and Eli Upfal.  Optimal construction of edge-disjoint paths in random graphs.  SIAM J. Comput., 28(2):541–573, 1998.
  * [5] H. Bruns, F.J. Dessart, and M. Pantazi.  Covid-19 misinformation: Preparing for future crises.  Technical report, EUR 31139 EN, Publications Office of the European Union, Luxembourg, JRC130111., 2022.
  * [6] Arnaud Casteigts, Michael Raskin, Malte Renken, and Viktor Zamaraev.  Sharp thresholds in random simple temporal graphs.  In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, pages 319–326. IEEE, 2021.
  * [7] Flavio Chierichetti, George Giakkoupis, Silvio Lattanzi, and Alessandro Panconesi.  Rumor spreading and conductance.  J. ACM, 65(4), apr 2018.
  * [8] Fan RK Chung.  Spectral graph theory, volume 92.  American Mathematical Soc., 1997.
  * [9] F.K. Chung and L. Lu.  Concentration inequalities and martingale inequalities: A survey.  Internet Mathematics, 3(1):79–127, 2007.
  * [10] Andrea Clementi, Riccardo Silvestri, and Luca Trevisan.  Information spreading in dynamic graphs.  In Proceedings of the 2012 ACM symposium on Principles of distributed computing, pages 37–46, 2012.
  * [11] Andrea E. F. Clementi, Pierluigi Crescenzi, Carola Doerr, Pierre Fraigniaud, Francesco Pasquale, and Riccardo Silvestri.  Rumor spreading in random evolving graphs.  Random Struct. Algorithms, 48(2):290–312, 2016.
  * [12] Rami Daknama, Konstantinos Panagiotou, and Simon Reisser.  Robustness of randomized rumour spreading.  Combinatorics, Probability and Computing, 30(1):37–78, 2021.
  * [13] Sebastian Daum, Fabian Kuhn, and Yannic Maus.  Rumor spreading with bounded in-degree.  Theor. Comput. Sci., 810:43–57, 2020.
  * [14] Michela Del Vicario, Alessandro Bessi, Fabiana Zollo, Fabio Petroni, Antonio Scala, Guido Caldarelli, H Eugene Stanley, and Walter Quattrociocchi.  The spreading of misinformation online.  Proceedings of the national academy of Sciences, 113(3):554–559, 2016.
  * [15] Alan Demers, Dan Greene, Carl Hauser, Wes Irish, John Larson, Scott Shenker, Howard Sturgis, Dan Swinehart, and Doug Terry.  Epidemic algorithms for replicated database maintenance.  In Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, pages 1–12, 1987.
  * [16] Benjamin Doerr, Mahmoud Fouz, and Tobias Friedrich.  Why rumors spread so quickly in social networks.  Communications of the ACM, 55(6):70–75, 2012.
  * [17] Benjamin Doerr and Anatolii Kostrygin.  Randomized rumor spreading revisited.  In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017\.
  * [18] Devdatt P Dubhashi and Alessandro Panconesi.  Concentration of measure for the analysis of randomized algorithms.  Cambridge University Press, 2009.
  * [19] Nikolaos Fountoulakis, Anna Huber, and Konstantinos Panagiotou.  Reliable broadcasting in random networks and the effect of density.  In 2010 Proceedings IEEE INFOCOM, pages 1–9. IEEE, 2010.
  * [20] Nikolaos Fountoulakis and Konstantinos Panagiotou.  Rumor spreading on random regular graphs and expanders.  Random Struct. Algorithms, 43(2):201–220, 2013.
  * [21] Alan M Frieze and Geoffrey R Grimmett.  The shortest-path problem for graphs with random arc-lengths.  Discrete Applied Mathematics, 10(1):57–77, 1985.
  * [22] George Giakkoupis.  Tight bounds for rumor spreading with vertex expansion.  In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, pages 801–815. SIAM, 2014.
  * [23] George Giakkoupis, Thomas Sauerwald, and Alexandre Stauffer.  Randomized rumor spreading in dynamic graphs.  In Automata, Languages, and Programming: 41st International Colloquium, ICALP 2014, Proceedings, Part II 41, pages 495–507. Springer, 2014\.
  * [24] Lee Howell.  Digital wildfires in a hyperconnected world.  World Economic Forum report, 3(2013):15–94, 2013.
  * [25] Mark Jerrum and Alistair Sinclair.  Approximating the permanent.  SIAM journal on computing, 18(6):1149–1178, 1989.
  * [26] Richard Karp, Christian Schindelhauer, Scott Shenker, and Berthold Vocking.  Randomized rumor spreading.  In Proceedings 41st Annual Symposium on Foundations of Computer Science, pages 565–574. IEEE, 2000.
  * [27] David Kempe, Jon Kleinberg, and Éva Tardos.  Maximizing the spread of influence through a social network.  In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 137–146, 2003.
  * [28] William Ogilvy Kermack and Anderson G McKendrick.  A contribution to the mathematical theory of epidemics.  Proceedings of the royal society of london. Series A, Containing papers of a mathematical and physical character, 115(772):700–721, 1927.
  * [29] Taichi Murayama, Shoko Wakamiya, Eiji Aramaki, and Ryota Kobayashi.  Modeling the spread of fake news on twitter.  PLOS ONE, 16(4):1–16, 04 2021.
  * [30] Konstantinos Panagiotou, Xavier Perez-Gimenez, Thomas Sauerwald, and He Sun.  Randomized rumour spreading: The effect of the network topology.  Combinatorics, Probability and Computing, 24(2):457–479, 2015.
  * [31] Konstantinos Panagiotou, Ali Pourmiri, and Thomas Sauerwald.  Faster rumor spreading with multiple calls.  Electron. J. Comb., 22(1):1, 2015.
  * [32] Alessandro Panconesi and Aravind Srinivasan.  Randomized distributed edge coloring via an extension of the chernoff-hoeffding bounds.  SIAM J. Comput., 26(2):350–368, 1997.
  * [33] F Peter.  ‘bogus’ AP tweet about explosion at the white house wipes billions off us markets.  The Telegraph, 2013.
  * [34] José R.C. Piqueira, Mauro Zilbovicius, and Cristiane M. Batistela.  Daley–kendal models in fake-news scenario.  Physica A: Statistical Mechanics and its Applications, 548:123406, 2020.
  * [35] Boris Pittel.  On spreading a rumor.  SIAM Journal on Applied Mathematics, 47(1):213–223, 1987.
  * [36] Ali Pourmiri and Bernard Mans.  Tight analysis of asynchronous rumor spreading in dynamic networks.  In Proceedings of the 39th Symposium on Principles of Distributed Computing, pages 263–272, 2020.
  * [37] Amir Sarid.  The spectral gap of random regular graphs.  arXiv:2201.02015, 2022.
  * [38] David Williams.  Probability with martingales.  Cambridge university press, 1991.
  * [39] Savvas Zannettou, Michael Sirivianos, Jeremy Blackburn, and Nicolas Kourtellis.  The web of false information: Rumors, fake news, hoaxes, clickbait, and various other shenanigans.  ACM J. Data Inf. Qual., 11(3):10:1–10:37, 2019.
  * [40] Ahad N. Zehmakan, Charlotte Out, and Sajjad Hesamipour Khelejan.  Why rumors spread fast in social networks, and how to stop it.  In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI 2023, pages 234–242. ijcai.org, 2023.
  * [41] Laijun Zhao, Wanlin Xie, H Oliver Gao, Xiaoyan Qiu, Xiaoli Wang, and Shuhai Zhang.  A rumor spreading model with variable forgetting rate.  Physica A: Statistical Mechanics and its Applications, 392(23):6146–6154, 2013.

##  Appendix A Tools

###  A.1 Auxiliary Probabilistic Tools

For convenience, we add several well known claims.

######  Lemma A.1.

Let $Y$ be any random variable, and $Y_{1},Y_{2}$ be two independent copies
with the same distribution as $Y$. Then,

$\mathbf{Var}\left[\,Y\,\right]=\frac{1}{2}\cdot\mathbf{E}\left[\,(Y_{1}-Y_{2})^{2}\,\right].$

###### Proof.

If $Y_{1},Y_{2}\sim Y$ are independent samples from the same distribution $Y$,
then

$\displaystyle\mathbf{E}\left[\,(Y_{1}-Y_{2})^{2}\,\right]$
$\displaystyle=\mathbf{E}\left[\,(Y_{1}-\mathbf{E}\left[\,Y\,\right]+\mathbf{E}\left[\,Y\,\right]-Y_{2})^{2}\,\right]$
$\displaystyle=\mathbf{E}\left[\,(Y_{1}-\mathbf{E}\left[\,Y\,\right])^{2}\,\right]+2\cdot\mathbf{E}\left[\,(Y_{1}-\mathbf{E}\left[\,Y\,\right])\cdot(\mathbf{E}\left[\,Y\,\right]-Y_{2})\,\right]+\mathbf{E}\left[\,(Y_{2}-\mathbf{E}\left[\,Y\,\right])^{2}\,\right]$
$\displaystyle=2\cdot\mathbf{Var}\left[\,Y\,\right].\qed$

######  Lemma A.2.

Let $Z$ be a non-negative random variable. Then,

$\mathbf{Var}\left[\,\log(1+Z)\,\right]\leq\mathbf{Var}\left[\,Z\,\right].$

###### Proof.

Let $Y$ be any random variable, and $Y_{1},Y_{2}$ be two independent copies
with the same distribution as $Y$. Then, by Lemma A.1,
$2\cdot\mathbf{Var}\left[\,Y\,\right]=\mathbf{E}\left[\,(Y_{1}-Y_{2})^{2}\,\right]$.
If $x,y\geq 0$ then $|\log(1+x)-\log(1+y)|\leq|x-y|$. To see the previous
inequality, assuming that $x>y$, the mean value theorem yields
$\log(1+x)-\log(1+y)=\frac{1}{1+z}(x-y)$, where $z$ lies between $y$ and $x$,
then clearly $z\geq 0$, so $0<\frac{1}{1+z}\leq 1$, proving the inequality.
Now

$\displaystyle 2\cdot\mathbf{Var}\left[\,\log(1+Z)\,\right]$
$\displaystyle=\mathbf{E}\left[\,\left(\log(1+Z_{1})-(\log(1+Z_{2})\right)^{2}\,\right]\leq\mathbf{E}\left[\,\left(Z_{1}-Z_{2}\right)^{2}\,\right]=2\cdot\mathbf{Var}\left[\,Z\,\right].\qed$

######  Lemma A.3.

Let $Z$ be a non-negative random variable . Then, for any $a\in\mathbb{R}$,

$\mathbf{Var}\left[\,\max\\{Z,a\\}\,\right]\leq\mathbf{Var}\left[\,Z\,\right],\qquad\text{as
well
as}\qquad\mathbf{Var}\left[\,\min(Z,a)\,\right]\leq\mathbf{Var}\left[\,Z\,\right].$

###### Proof.

This is identical to the proof of Lemma A.2 by noting that
$|\max\\{Z,a\\}-\max\\{Z^{\prime},a\\}|\leq|Z-Z^{\prime}|$ and
$|\min(Z,a)-\min(Z^{\prime},a)|\leq|Z-Z^{\prime}|$. ∎

######  Lemma A.4 (Jensen’s Inequality).

If $f$ is a convex function, then

$\mathbf{E}\left[\,f(X)\,\right]\geq
f\left(\mathbf{E}\left[\,X\,\right]\right).$

If $f$ is a concave function, then

$\mathbf{E}\left[\,f(X)\,\right]\leq
f\left(\mathbf{E}\left[\,X\,\right]\right).$

######  Theorem A.5 (Optional Stopping Theorem [38, Theorem 10.10]).

Let $(X_{t})_{t\geq 0}$ be a discrete-time supermartingale and
$\tau\in\mathbb{N}_{0}\cup\\{\infty\\}$ be a stopping time, both with respect
to the same filtration $(\mathcal{F}_{t})_{t\geq 0}$ . Assume that one of the
following three conditions holds:

  * •

There exists a constant $c$ such that almost surely $\tau\leq c$.

  * •

$\mathbf{E}[\,\tau\,]<\infty$ and there exists a constant $c$ such that
$\mathbb{E}\bigl{[}|X_{t+1}-X_{t}|\,\big{|}\,{\mathcal{F}}_{t}\bigr{]}\leq c$
almost surely on the event $\\{\tau>t\\}$ for all $t\in\mathbb{N}$.

  * •

There exists a constant $c$ such that $|X_{t\wedge\tau}|\leq c$ almost surely
for all $t\in\mathbb{N}_{0}$.

Then $X_{\tau}$ is an almost surely well defined random variable and
$\mathbb{E}[X_{\tau}]\leq\mathbb{E}[X_{0}]$.

###  A.2 Concentration Inequalities

Here, we provide several concentration inequalities; stating with several
versions of the Chernoff bound.

######  Lemma A.6 (Chernoff bound, cf. [18]).

Suppose that $X_{1},\ldots,X_{n}$ are independent Bernoulli random variables
and let $X:=\sum_{i=1}^{n}X_{i}$ . Then, for any $0\leq\eta\leq 1$,

  * (i)

$\mathbf{P}\left[\,X\leq\left(1-\eta\right)\mathbf{E}\left[\,X\,\right]\,\right]\leq\exp\left({-\frac{\eta^{2}\mathbf{E}\left[\,X\,\right]}{2}}\right)$,

  * (ii)

$\mathbf{P}\left[\,X\geq\left(1+\eta\right)\mathbf{E}\left[\,X\,\right]\,\right]\leq\exp\left({-\frac{\eta^{2}\mathbf{E}\left[\,X\,\right]}{3}}\right)$.

More generally, for any $\eta>0$,

  * (iii)

$\mathbf{P}\left[\,X\geq(1+\eta)\mathbf{E}\left[\,X\,\right]\,\right]\leq\exp\left(-\frac{\eta^{2}\mathbf{E}\left[\,X\,\right]}{2+\eta}\right).$

  * (iv)

$\mathbf{P}\left[\,X\geq(1+\eta)\mathbf{E}\left[\,X\,\right]\,\right]\leq\left(\frac{e^{\eta}}{(1+\eta)^{1+\eta}}\right)^{\mathbf{E}\left[\,X\,\right]}\leq\left(\frac{e}{1+\eta}\right)^{(1+\eta)\cdot\mathbf{E}\left[\,X\,\right]}$

Not that these Chernoff bounds are valid as long as for all subsets
$S\subseteq\\{1,\ldots,n\\}$, $\mathbf{P}\left[\,\cap_{i\in
S}X_{i}=1\,\right]\leq\prod_{i\in S}\mathbf{P}\left[\,X_{i}=1\,\right]$, as
shown by Panconesi and Srinivasan [32].

######  Lemma A.7 ([9, Theorem 6.5]).

Let $(Z_{i})_{i\geq 0}$ be a discrete-time martingale associated with a filter
$\mathcal{F}$ satisfying

  1. 1.

$\mathbf{Var}\left[\,Z_{i}~{}\Big{|}~{}\mathcal{F}_{i-1}\,\right]\leq\sigma_{i}^{2}$
for all $1\leq i\leq n$;

  2. 2.

$Z_{i-1}-Z_{i}\leq M$ for $1\leq i\leq n$.

Then for any $h\geq 0$,

$\displaystyle\mathbf{P}\left[\,Z_{n}-\mathbf{E}\left[\,Z_{n}\,\right]\leq-h\,\right]\leq\exp\left(-\frac{h^{2}}{2\cdot\left(\sum_{i=1}^{n}\sigma_{i}^{2}+Mh/3\right)}\right).$

######  Lemma A.8 ([9, Theorem 6.3]).

Let $(Z_{i})_{i\geq 0}$ be a discrete-time martingale associated with a filter
$\mathcal{F}$ satisfying

  1. 1.

$\mathbf{Var}\left[\,Z_{i}~{}\Big{|}~{}\mathcal{F}_{i-1}\,\right]\leq\sigma_{i}^{2}$
for all $1\leq i\leq n$;

  2. 2.

$Z_{i}-Z_{i-1}\leq M$ for $1\leq i\leq n$.

Then for any $h\geq 0$,

$\displaystyle\mathbf{P}\left[\,Z_{n}-\mathbf{E}\left[\,Z_{n}\,\right]\geq
h\,\right]\leq\exp\left(-\frac{h^{2}}{2\cdot\left(\sum_{i=1}^{n}\left(\sigma_{i}^{2}\right)+Mh/3\right)}\right).$

###  A.3 Variations of the expander mixing lemma

######  Lemma A.9 (Expander mixing lemma - weak version [1] Corollary 9.2.5).

Let $G=(V,E)$ be a $d$-regular graph and let $S,T\subseteq V$ be sets of
vertices. For $M:=D^{-1/2}AD^{-1/2}$ the normalized adjacency matrix of $G$
and $1=\lambda_{1}\geq\lambda_{2}\geq\dots\geq\lambda_{n}\geq-1$ the
eigenvalues of $M$ and
$\lambda:=\max\\{|\lambda_{2}|,\lambda_{3}|,\dots,|\lambda_{n}|\\}$. Then,

$\left|e(S,T)-\frac{|S||T|d}{n}\right|\leq\lambda\cdot d\sqrt{|S|\cdot|T|}.$

######  Lemma A.10 (Expander mixing lemma - strong version [8]).

Let $G=(V,E)$ be a $d$-regular graph and let $S,T\subseteq V$ be sets of
vertices. For $M:=D^{-1/2}AD^{-1/2}$ the normalized adjacency matrix of $G$
and $1=\lambda_{1}\geq\lambda_{2}\geq\dots\geq\lambda_{n}\geq-1$ the
eigenvalues of $M$ and
$\lambda:=\max\\{|\lambda_{2}|,\lambda_{3}|,\dots,|\lambda_{n}|\\}$. Then, it
holds that,

$\left|e(S,T)-\frac{d}{n}\cdot|S|\cdot|T|\right|\leq\lambda\cdot\frac{d}{n}\sqrt{|S|\cdot|V\setminus
S|\cdot|T|\cdot|V\setminus T|}.$

######  Corollary A.11.

Let $G=(V,E)$ be a $d$-regular graph. Then, for any subset $S\subseteq V$,

$(1-\lambda)\cdot\frac{d}{n}\cdot|S|\cdot|V\setminus S|\leq e(S,V\setminus
S)\leq(1+\lambda)\frac{d}{n}\cdot|S|\cdot|V\setminus S|.$

###### Proof.

By choosing $T=V\setminus S$ in Lemma A.10, we obtain

$\displaystyle\left|e(S,V\setminus S)-\frac{d}{n}\cdot|S|\cdot|V\setminus
S|\right|$ $\displaystyle\leq\lambda\cdot\frac{d}{n}\cdot|S|\cdot|V\setminus
S|,$

which gives the claimed bounds. ∎

######  Lemma A.12.

Let $M:=D^{-1/2}AD^{-1/2}$ be the normalized adjacency matrix of $G$,
$1=\lambda_{1}\geq\lambda_{2}\geq\dots\geq\lambda_{n}\geq-1$ the eigenvalues
of $M$ and
$\lambda:=\max\\{|\lambda_{2}|,\lambda_{3}|,\dots,|\lambda_{n}|\\}$. Let
$S\subseteq V$ such that $1\leq|S|\leq n/2$. Then, the following holds,

$\varphi(S)\geq(1-\lambda)\cdot\left(1-\frac{|S|}{n}\right).$

###### Proof.

By Lemma A.10, we note that,

$\displaystyle e(S,V\setminus S)$
$\displaystyle\geq(1-\lambda)\cdot\frac{d}{n}\cdot|S|\cdot|V\setminus
S|\geq(1-\lambda)\cdot
d\cdot|S|\cdot\left(1-\frac{|S|}{n}\right)=(1-\lambda)\cdot\operatorname{vol}(S)\cdot\left(1-\frac{|S|}{n}\right).$

Therefore, since $|S|\leq n/2$ and thus
$\operatorname{vol}(S)\leq\operatorname{vol}(V\setminus S)$,

$\varphi(S)=\frac{e(S,V\setminus
S)}{\min\left(\operatorname{vol}(S),\operatorname{vol}(V\setminus
S)\right)}=\frac{e(S,V\setminus
S)}{\operatorname{vol}(S)}\geq(1-\lambda)\cdot\left(1-\frac{|S|}{n}\right).\qed$

###  A.4 Simple Technical Claims

######  Claim A.13.

For all $x\geq 1$ and $\kappa\in(0,1/1000)$ we have,

$\min\left(64\cdot x^{-1/4},1-\kappa\right)\leq(1-\kappa^{2})\cdot
x^{-\kappa^{2}}.$

###### Proof.

Observe that for any $x<\left(\frac{64}{1-\kappa}\right)^{4}$ we have
$1-\kappa<64\cdot x^{-1/4}$, and

$(1-\kappa^{2})\cdot
x^{-\frac{\log(1+\kappa)}{4\log(\frac{64}{1-\kappa})}}>(1-\kappa^{2})\cdot\left(\left(\frac{64}{1-\kappa}\right)^{4}\right)^{-\frac{\log(1+\kappa)}{4\log(\frac{64}{1-\kappa})}}=(1-\kappa^{2})\cdot\frac{1}{1+\kappa}=1-\kappa.$

Conversely, for any $x\geq\left(\frac{64}{1-\kappa}\right)^{4}$ we have
$64\cdot x^{-1/4}\leq 1-\kappa$, and so we clam that also

$64\cdot x^{-1/4}\leq(1-\kappa^{2})\cdot
x^{-\frac{\log(1+\kappa)}{4\log(\frac{64}{1-\kappa})}}.$

To see this, note that any such $x$ can be expressed as
$c\cdot\left(\frac{64}{1-\kappa}\right)^{4}$ for some $c\geq 1$. After this
change of variables the inequality above reads

$(1-\kappa)\cdot c^{-1/4}\leq(1-\kappa)\cdot
c^{-\frac{\log(1+\kappa)}{4\log(\frac{64}{1-\kappa})}},$

which holds since $1/4\geq\frac{\log(1+\kappa)}{4\log(\frac{64}{1-\kappa})}$.
The result follows by using the inequalities $\frac{x}{1+x}\leq\log(1+x)\leq
x$ since

$\frac{\log(1+\kappa)}{4\log(\frac{64}{1-\kappa})}\geq\frac{\frac{\kappa}{1+\kappa}}{\frac{4\cdot
64}{1-\kappa}}\geq\kappa^{2},$

as $\kappa\in(0,1/1000)$. ∎

######  Claim A.14.

For any $z\geq 0$ and any $a\in[0,1]$, the following holds:

$\log\left(1+(1-a)\cdot z\right)\geq(1-a)\cdot\log\left(1+z\right).$

###### Proof.

To begin observe that if $z=0$ then the statement holds, for any $a\in[0,1]$.
So from now on we can assume $z>0$. For any fixed $z>0$, we consider the
function

$f_{z}(a):=\log\left(1+(1-a)\cdot z\right)-(1-a)\cdot\log\left(1+z\right).$

Note that for $a=0$, we have

$f_{z}(0)=\log(1+z)-\log(1+z)=0,$

and for $a=1$, we have

$f_{z}(1)=\log(1)-0\cdot\log(1+z)=0.$

Taking the derivatives,

$\frac{\partial f_{z}(a)}{\partial a}=\frac{z}{(a-1)z-1}+\log(z+1),$

and

$\frac{\partial^{2}f_{z}(a)}{\partial^{2}a}=\frac{-z^{2}}{((a-1)z-1)^{2}}.$

Thus we see that $\frac{\partial^{2}f_{z}(a)}{\partial a}<0$ always, since
$z>0$. Therefore, all stationary points must be local maxima and so
$f_{z}(a)\geq 0$ for all $a\in[0,1]$, which yields the claim. ∎

######  Claim A.15.

For any $x<1$ and $a<1$,

$\log\left(1-(1-a)\cdot
x\right)\leq\left(1-\frac{a}{1-x}\right)\cdot\log\left(1-x\right).$

###### Proof.

The derivative of $f(x)=\log(x)$ at point $1-x$ is $\frac{1}{1-x}$. Therefore,
as $\log(.)$ is concave,

$\log\left(1-x+a\cdot x\right)\leq\log\left(1-x\right)+\frac{a\cdot x}{1-x}.$

Further, since $\log(1-x)\leq-x$, we have $x\leq-\log(1-x)$ and thus

$\log\left(1-x+a\cdot
x\right)\leq\log(1-x)\cdot\left(1-\frac{a}{1-x}\right).\qed$

######  Claim A.16.

For any $0<\alpha<1$ and $T\geq 1$,

$\frac{T^{1-\alpha}-1}{1-\alpha}\leq\sum_{k=1}^{T}k^{-\alpha}\leq\frac{T^{1-\alpha}}{1-\alpha}.$

###### Proof.

Since the function $x^{1-\alpha}$ is decreasing on $[1,\infty)$ and
$0<1-\alpha<1$ we have

$\sum_{k=1}^{T}k^{-\alpha}\leq
1+\int_{1}^{T}x^{-\alpha}\,\mathrm{d}x=1+\left[\frac{x^{1-\alpha}}{1-\alpha}\right]_{x=1}^{T}=1+\frac{T^{1-\alpha}}{1-\alpha}-\frac{1}{1-\alpha}\leq\frac{T^{1-\alpha}}{1-\alpha}.$

The lower bound follows similarly as
$\sum_{k=1}^{T}k^{-\alpha}\geq\int_{1}^{T}x^{-\alpha}\,\mathrm{d}x$. ∎

######  Lemma A.17 (Stirling’s approximation upper and lower bound).

For every integer $n\geq 1$,

$\sqrt{2\pi n}\left(\frac{n}{e}\right)^{n}e^{\frac{1}{12n+1}}<n!<\sqrt{2\pi
n}\left(\frac{n}{e}\right)^{n}e^{\frac{1}{12n}}.$

######  Claim A.18.

For any $\alpha>0$,

$\prod_{i=0}^{1/\alpha-1}(2-i\cdot\alpha)\leq\sqrt{2}\left(\frac{4}{e}\right)^{1/\alpha}.$

###### Proof.

We have

$\prod^{1/\alpha}_{i=1}(2-(i-1)\cdot\alpha)=\frac{\prod_{i=1}^{1/\alpha}(2/\alpha-(i-1))}{(1/\alpha)^{1/\alpha}}=\frac{(2/\alpha)!}{(1/\alpha)!(1/\alpha)^{1/\alpha}}\stackrel{{\scriptstyle(a)}}{{\leq}}\frac{\sqrt{2\pi\cdot
2/\alpha}\left(\frac{2/\alpha}{e}\right)^{2/\alpha}e^{\frac{1}{12\cdot
2/\alpha}}}{\sqrt{2\pi\cdot
1/\alpha}\left(\frac{1/\alpha}{e}\right)^{1/\alpha}e^{\frac{1}{12\cdot
1/\alpha+1}}(1/\alpha)^{1/\alpha}},$

where $(a)$ holds by applying the upper bound in Lemma A.17 to the factorial
in the numerator and the lower bound in Lemma A.17 to the factorial in the
denominator. With some factoring and cancelling we now have

$\prod^{1/\alpha}_{i=1}(2-(i-1)\cdot\alpha)\leq\frac{\sqrt{2/\alpha}\cdot
2^{2/\alpha}\left(1/\alpha\right)^{2/\alpha}\left(1/e\right)^{2/\alpha}e^{\frac{1}{24/\alpha}}}{\sqrt{1/\alpha}\cdot(1/\alpha)^{1/\alpha}(1/\alpha)^{1/\alpha}\left(1/e\right)^{1/\alpha}e^{\frac{1}{12/\alpha+1}}}=\sqrt{2}\left(\frac{4}{e}\right)^{1/\alpha}\cdot\frac{e^{1/(24/\alpha)}}{e^{1/(12/\alpha)+1}}\leq\sqrt{2}\left(\frac{4}{e}\right)^{1/\alpha},$

as claimed. ∎

The next result is the lower bound version of the previous claim.

######  Claim A.19.

For any $\alpha>0$,

$\prod^{1/\alpha-1}_{i=0}(2-i\cdot\alpha)\geq\frac{1}{\sqrt{2}}\left(\frac{4}{e}\right)^{1/\alpha}\cdot
e^{-\frac{1}{2}\alpha}.$

###### Proof.

Shifting the indices by one gives us

$\prod^{1/\alpha-1}_{i=0}(2-i\cdot\alpha)=\prod^{1/\alpha}_{i=1}(2-i\cdot\alpha)=\frac{\prod_{i=1}^{1/\alpha}(2/\alpha-i)}{(1/\alpha)^{1/\alpha}}=\frac{(2/\alpha-1)!}{(1/\alpha-1)!(1/\alpha)^{1/\alpha}}=\frac{(2/\alpha)!(1/\alpha)}{(1/\alpha)!(2/\alpha)(1/\alpha)^{1/\alpha}}.$

By applying the Stirling’s inequalities Lemma A.17 to the factorials in the
numerator denominator we have

$\prod^{1/\alpha-1}_{i=0}(2-i\cdot\alpha)\geq\frac{\sqrt{2\pi\cdot
2/\alpha}\left(\frac{2/\alpha}{e}\right)^{2/\alpha}e^{\frac{1}{12\cdot
2/\alpha+1}}(1/\alpha)}{\sqrt{2\pi\cdot
1/\alpha}\left(\frac{1/\alpha}{e}\right)^{1/\alpha}e^{\frac{1}{12\cdot
1/\alpha}}(1/\alpha)^{1/\alpha}(2/\alpha)}=\frac{\sqrt{2/\alpha}(1/\alpha)2^{2/\alpha}\left(1/\alpha\right)^{2/\alpha}\left(1/e\right)^{2/\alpha}e^{\frac{1}{24/\alpha+1}}}{\sqrt{1/\alpha}(2/\alpha)(1/\alpha)^{1/\alpha}(1/\alpha)^{1/\alpha}\left(1/e\right)^{1/\alpha}e^{\frac{1}{12/\alpha}}}.$

We can then cancel many of the terms to give

$\displaystyle\prod^{1/\alpha-1}_{i=0}(2-i\cdot\alpha)\geq\frac{1}{\sqrt{2}}\left(\frac{4}{e}\right)^{1/\alpha}\cdot
e^{\frac{1}{24/\alpha+1}-\frac{1}{12/\alpha}}\geq\frac{1}{\sqrt{2}}\left(\frac{4}{e}\right)^{1/\alpha}\cdot
e^{\frac{1}{25}\alpha-\frac{1}{12}\alpha}\geq\frac{1}{\sqrt{2}}\left(\frac{4}{e}\right)^{1/\alpha}\cdot
e^{-\frac{1}{2}\alpha},$

as claimed. ∎

######  Claim A.20.

For the constants $c_{1}:=\frac{1}{2}$ and $c_{2}:=\frac{1}{8}$ we have,

$\prod_{i=0}^{\infty}\left(1+\left(1-\frac{c_{1}}{\log
n}\right)^{i}\right)\leq\sqrt{n},\qquad and\qquad\prod_{i=0}^{4\log
n-1}\left(1+\left(1-\frac{c_{2}}{\log n}\right)^{i}\right)\geq n^{3/2}.$

###### Proof.

For the first statement,

$\prod_{i=0}^{\infty}\left(1+\left(1-\frac{c_{1}}{\log
n}\right)^{i}\right)\leq\exp\left(\sum_{i=0}^{\infty}\left(1-\frac{c_{1}}{\log
n}\right)^{i}\right)\leq\exp\left(\frac{\log n}{c_{1}}\right)=\sqrt{n},$

since $c_{1}=\frac{1}{2}$. For the second statement, recall
$c_{2}:=\frac{1}{8}$, and note that for any $i\leq 4\log n$,

$1+\left(1-\frac{c_{2}}{\log n}\right)^{i}\geq 2-4c_{2}\geq\frac{3}{2},$

where we have used Bernoulli’s inequality. Therefore,

$\prod_{i=0}^{4\log n-1}\left(1+\left(1-\frac{c_{2}}{\log
n}\right)^{i}\right)\geq\left(\frac{3}{2}\right)^{4\log n-1}\geq n^{3/2},$

as $(3/2)^{4}>e^{3/2}$. ∎