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))
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:
Chair of the P & T Committee, Dept. of Computer and Information Sciences
View more information: https://www.towson.edu/fcsm/departments/computerinfosci/facultystaff/mzimand.html