Marius Zimand

Professional Service:

Member of the Editorial Board of Journal of Universal Computer Science, an international journal published by Springer Verlag.

Grant Reviewer for the National Science Foundation,  National Research Council Canada, National Research Agency of France, US-Israel Binational Science Foundation.

Selected Publications and Presentations:

Bruno Bauwens and Marius Zimand, ``Linear list-approximation for short programs (or the power of a few random bits),”  29-th IEEE Conference on Computational Complexity, pp. 241-247, June 2014, Vancouver, Canada.

Bruno Bauwens, Anton Makhlin, Nikolay Vereshchagin, and Marius Zimand, ``Short lists with short programs in short time, “ 28-th IEEE Conference on Computational Complexity, June 5-7, 2013, Stanford, California, US

Marius Zimand, ``Two sources are better than one for increasing the Kolmogorov complexity of infinite sequences,” Theory of Computing Systems, 46(4), pp. 707-722, 2010 (Best Paper Award at CSR'2008).

Marius Zimand, ``Simple extractors via cryptographic pseudo-random generators,” Theoretical Computer Science, vol. 411(10), pp. 1236--1250 (March 2010) (Best Paper Award at  ICALP 2005, Track C).

Marius Zimand,  ``Exposure-Resilient Extractors and the Derandomization of Probabilistic Sublinear Time,” Computational Complexity, vol. 17, no. 2 (May 2008), pp. 220--253. (Special issue with selected papers from 22nd Annual IEEE Conference on Computational Complexity (CCC 2007))

Research:

My research is in the area of randomness extraction, especially in the framework of algorithmic information theory (also known as Kolmogorov complexity). Recently my research has been supported by the grants NSF 0634830, 2006 -2009, and  NSF 1016158, 2010-2014. The main objectives are  on one hand to design efficient algorithms that transform objects with low-quality randomness into objects with high-quality randomness, or, on the other hand, to establish the impossibility of such constructions. The objects (usually called sources) can be finite probability distributions, finite binary strings, and infinite binary sequences and the randomness quality is measured, respectively, by min-entropy, Kolmogorov complexity, and constructive Hausdorff dimension.  Randomness extractors have direct applications in cryptography and they are also connected to other areas of great interest such as error-correcting codes and data structures. In addition, randomness extraction is an area that is of great mathematical interest.

Memberships / Affiliations:

ACM, SIGACT

Service:

Chair of the P & T Committee, Dept. of Computer and Information Sciences