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,''
submitted to IEEE Trans. Inform. Theory, May 2016.

N. Merhav,
``Universal decoding using a noisy codebook,''
submitted to IEEE Trans. Inform. Theory, September 2016.