LempelZiv Complexity and the IndividualSequence Approach to Information Theory

M. Feder, N. Merhav, and M. Gutman,
``Universal prediction of individual sequences,''
IEEE Trans. Inform. Theory,
vol. 38, no. 4, pp. 12581270, July 1992 (received the 1993 paper award
of the Information Theory Society).

N. Merhav and M. Feder,
``Universal schemes for sequential decision from individual data
sequences,''
IEEE Trans. Inform. Theory
vol. 39, no. 4, pp. 12801291, July 1993.

J. Ziv and N. Merhav,
``A measure of relative entropy between individual
sequences with application to universal classification,''
IEEE Trans. Inform. Theory,
vol. 39, no. 4, pp. 12701279, July 1993.

M. J. Weinberger, N. Merhav, and M. Feder,
``Optimal sequential probability
assignment for individual sequences,''
IEEE Trans. Inform. Theory
vol. 40, no. 2, pp. 384396, March 1994.

N. Merhav and M. Feder,
``On the cost of universality of block codes for individual sequences,''
Proc. 1994 IEEE Int. Symp. on Information Theory (ISIT `94), p. 263,
Trondheim, Norway, June 1994.

N. Merhav and M. Feder,
``Universal prediction,'' (invited paper)
IEEE Trans. Inform.
Theory, vol. 44, no. 6, pp. 21242147, October 1998.
(Commemorative issue for fifty years of Information Theory.)
Also, in Information Theory: 50 Years of Discovery,
pp. 80103, Eds.
S. Verdu and S. McLaughlin, IEEE Press, 1999.

A. Baruch and N. Merhav,
``Universal filtering and prediction of
individual sequences corrupted by noise
using the LempelZiv algorithm,''
Proc. 2000 IEEE Int. Symp. on Information Theory (ISIT 2000), p. 99,
Sorrento, Italy, June 2000.

T. Weissman and N. Merhav,
``Universal prediction of individual binary
sequences in the presence of arbitrarily varying, memoryless, additive
noise,'' Proc. 2000 IEEE Int. Symp. on Information Theory (ISIT
2000), p. 97, Sorrento, Italy, June 2000.

N. Merhav,
``Universal detection of messages via finitestate channels,''
IEEE Trans. Inform. Theory,
vol. 46, no. 6, pp. 22422246, September 2000.

T. Weissman, N. Merhav, and A. SomekhBaruch,
``Twofold universal prediction
schemes for achieving the finite state predictability of a noisy
individual binary sequence,''
IEEE Trans. Inform. Theory,
vol 47, no. 5, pp. 18491866, July 2001.

T. Weissman and N. Merhav,
``Universal prediction of binary individual
sequences in the presence of noise,''
IEEE Trans. Inform. Theory, vol. 47, no. 6, pp. 21512173,
September 2001.

T. Weissman and N. Merhav,
``On limiteddelay lossy coding and filtering of
individual sequences,''
IEEE Trans. Inform. Theory, vol. 48, no. 3, pp. 721733, March 2002.

N. Merhav, E. Ordentlich, G. Seroussi, and M. J. Weinberger,
``On sequential strategies for loss functions with memory,''
IEEE Trans. Inform. Theory, vol. 48, no. 7, pp. 19471958, July
2002.

E. Ordentlich, T. Weissman, M. J. Weinberger, A. SomekhBaruch, and
N. Merhav,
``Discrete universal filtering through incremental parsing,''
Proc. DCC 2004, Snowbird, Utah, March 2004.

N. Merhav and J. Ziv,
``On the WynerZiv problem for individual sequences,''
IEEE Trans. Inform. Theory, vol. 52, no. 3, pp. 867873, March 2006.

J. Ziv and N. Merhav,
``On contexttree prediction of individual sequences,''
IEEE Trans. Inform. Theory, vol. 53, no. 5, pp. 18601866, May 2007.

T. Weissman, E. Ordentlich, M. J. Weinberger, A. SomekhBaruch, and N.
Merhav,''
``Universal filtering via prediction,''
IEEE Trans. Inform. Theory, vol. 53, no. 4, pp. 12531264, April
2007.

N. Merhav and E. Sabbag,
``Optimal watermark embedding and detection
strategies under limited detection resources,''
IEEE Trans. Inform. Theory,
vol. 54, no. 1, pp. 255274, January 2008.

A. Reani and N. Merhav,
``Efficient online schemes for encoding
individual sequences with side information at the decoder,''
Proc. ISIT 2009, Seoul, Korea, JuneJuly 2009.
Full version:
IEEE Trans. Inform. Theory, vol. 57, no. 10, pp. 68606876,
October 2011.

A. Martin, N. Merhav, G. Seroussi, and M. J. Weinberger,
``Twiceuniversal
simulation of Markov sources and individual sequences,''
Proc. ISIT 2007, pp. 28762880, Nice, France, June 2007.
Full version, appears in IEEE Trans. on Inform. Theory
vol. 56, no. 9, pp. 42454255, Sept. 2010, and can be found
here.

N. Merhav,
``Perfectly secure encryption of individual sequences,''
IEEE Trans. Inform. Theory, vol. 59, no. 3, pp. 13021310, March
2013.

N. Merhav,
``Universal decoding for arbitrary channels relative to a given class of
decoding metrics,'' IEEE Trans. Inform. Theory,
vol. 59, no. 9, pp. 55665576, September 2013.

N. Merhav,
``On the data processing theorem in the semideterministic setting,''
IEEE Trans. Inform. Theory,
vol. 60, no. 10, pp. 60326040, October 2014.

N. Merhav,
``Sequence complexity and work extraction,''
Journal of Statistical Mechanics: Theory and Experiment,
P06037, June 2015. doi:10.1088/17425468/2015/06/P06037

N. Merhav,
``On empirical cumulant generating functions of code lengths for individual
sequences,''
IEEE Trans. Inform. Theory, vol. 63, no. 12, pp. 77297736, December
2017.

N. Merhav,
``Universal decoding using a noisy codebook,''
IEEE Trans. Inform. Theory, vol. 64, part 1, no. 4, pp. 22312239,
April 2018.

N. Merhav,
``Guessing individual sequences: generating randomized guesses using
finitestate machines,''
IEEE Trans. Inform. Theory, vol. 66, no. 5, pp. 29122920, May 2020.

N. Merhav,
``Finitestate sourcechannel coding for individual source sequences with
source side information at the decoder,''
IEEE Trans. Inform. Theory,
vol. 68, no. 3, pp. 15321544, March 2022.

N. Merhav,
``Encoding individual source sequences for the wiretap channel.''
Entropy, 23(12) 1694, December 17, 2021.

N. Merhav,
``A universal ensemble for samplewise lossy compression,''
Entropy, 2023, 25(8), 1199;
https://doi.org/10.3390/e25081199
August 2023.

N. Merhav,
``Lossy compression of individual sequences revisited: fundamental limits of
finitestate encoders,'' Entropy 2024, 26, 116.
https://doi.org/10.3390/e26020116 January 2024.

N. Merhav,
``Universal SlepianWolf coding for individual sequences,''
submitted for publication, March 2024.

N. Merhav,
``Refinements and extensions of Ziv's model of perfect secrecy for individual
sequences,'' submitted for publication, May 2024.

N. Merhav,
``On Jacob Ziv's individualsequence approach to information theory,''
submitted for publication.