Marius Zimand

ORCID

Publication Activity (10 Years)

Years Active: 1986-2023
Publications (10 Years): 25

Top Venues

CoRR

Electron. Colloquium Comput. Complex.

SIGACT News

ICALP

Publications

Bruno Bauwens, Marius Zimand
Universal almost Optimal Compression and Slepian-wolf Coding in Probabilistic Polynomial Time. J. ACM 70 (2) (2023)
Alastair A. Abbott, Cezar Câmpeanu, Ludwig Staiger, Marius Zimand, Arto Salomaa
Frontiers of Computability, Randomness, and Complexity (dedicated to the 70th birthday of Professor Cristian Calude). Theor. Comput. Sci. 952 (2023)
Zhenjian Lu, Igor Carboni Oliveira, Marius Zimand
Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity. Electron. Colloquium Comput. Complex. (2022)
Bruno Bauwens, Marius Zimand
Hall-type theorems for fast almost dynamic matching and applications. CoRR (2022)
Zhenjian Lu, Igor Carboni Oliveira, Marius Zimand
Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity. CoRR (2022)
Andrei E. Romashchenko, Alexander Shen, Marius Zimand
27 Open Problems in Kolmogorov Complexity. CoRR (2022)
Zhenjian Lu, Igor Carboni Oliveira, Marius Zimand
Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity. ICALP (2022)
Marius Zimand
List Approximation for Increasing Kolmogorov Complexity. Axioms 10 (4) (2021)
Marius Zimand
Online matching in lossless expanders. CoRR (2021)
Andrei E. Romashchenko, Alexander Shen, Marius Zimand
27 Open Problems in Kolmogorov Complexity. SIGACT News 52 (4) (2021)
Bruno Bauwens, Marius Zimand
Universal codes in the shared-randomness model for channels with general distortion capabilities. CoRR (2020)
Marius Zimand
Secret Key Agreement from Correlated Data, with No Prior Information. STACS (2020)
Andrei E. Romashchenko, Marius Zimand
On a conditional inequality in Kolmogorov complexity and its applications in communication complexity. CoRR (2019)
Marius Zimand
Secret key agreement from correlated data, with no prior information. CoRR (2019)
Bruno Bauwens, Marius Zimand
Universal almost optimal compression and Slepian-Wolf coding in probabilistic polynomial time. CoRR (2019)
Andrei E. Romashchenko, Marius Zimand
An Operational Characterization of Mutual Information in Algorithmic Information Theory. J. ACM 66 (5) (2019)
Bruno Bauwens, Anton Makhlin, Nikolai K. Vereshchagin, Marius Zimand
Short lists with short programs in short time. Comput. Complex. 27 (1) (2018)
Andrei E. Romashchenko, Marius Zimand
An operational characterization of mutual information in algorithmic information theory. Electron. Colloquium Comput. Complex. 25 (2018)
Andrei E. Romashchenko, Marius Zimand
An Operational Characterization of Mutual Information in Algorithmic Information Theory. ICALP (2018)
Marius Zimand
Distributed compression through the lens of algorithmic information theory: a primer. CoRR (2017)
Marius Zimand
List Approximation for Increasing Kolmogorov Complexity. STACS (2017)
Andrei E. Romashchenko, Marius Zimand
An operational characterization of mutual information in algorithmic information theory. CoRR (2017)
Marius Zimand
Kolmogorov complexity version of Slepian-Wolf coding. STOC (2017)
Marius Zimand
List approximation for increasing Kolmogorov complexity. CoRR (2016)
Jason Teutsch, Marius Zimand
A Brief on Short Descriptions. SIGACT News 47 (1) (2016)
Marius Zimand
Kolmogorov complexity version of Slepian-Wolf coding. CoRR (2015)
Bruno Bauwens, Marius Zimand
Linear list-approximation for short programs (or the power of a few random bits). Electron. Colloquium Comput. Complex. 22 (2015)
N. V. Vinodchandran, Marius Zimand
On Optimal Language Compression for Sets in PSPACE/poly. Theory Comput. Syst. 56 (3) (2015)
Jason Teutsch, Marius Zimand
On Approximate Decidability of Minimal Programs. ACM Trans. Comput. Theory 7 (4) (2015)
Bruno Bauwens, Marius Zimand
Linear List-Approximation for Short Programs (or the Power of a Few Random Bits). Computational Complexity Conference (2014)
Marius Zimand
Counting Dependent and Independent Strings. Fundam. Informaticae 131 (3-4) (2014)
Jason Teutsch, Marius Zimand
On approximate decidability of minimal programs. CoRR (2014)
Marius Zimand
Short Lists with Short Programs in Short Time - A Short Proof. CiE (2014)
Marius Zimand
Short lists with short programs in short time - a short proof CoRR (2013)
Bruno Bauwens, Anton Makhlin, Nikolay K. Vereshchagin, Marius Zimand
Short lists with short programs in short time CoRR (2013)
N. V. Vinodchandran, Marius Zimand
On optimal language compression for sets in PSPACE/poly CoRR (2013)
Marius Zimand
Generating Kolmogorov random strings from sources with limited independence. J. Log. Comput. 23 (4) (2013)
Marius Zimand
Review of Deterministic Extraction from weak random sources by Ariel Gabizon. SIGACT News 44 (1) (2013)
Marius Zimand
On Efficient Constructions of Short Lists Containing Mostly Ramsey Graphs. TAMC (2013)
Bruno Bauwens, Anton Makhlin, Nikolay K. Vereshchagin, Marius Zimand
Short lists with short programs in short time. Electron. Colloquium Comput. Complex. 20 (2013)
Bruno Bauwens, Anton Makhlin, Nikolay K. Vereshchagin, Marius Zimand
Short Lists with Short Programs in Short Time. Computational Complexity Conference (2013)
Bruno Bauwens, Marius Zimand
Linear list-approximation for short programs (or the power of a few random bits). CoRR (2013)
Marius Zimand
Symmetry of Information: A Closer Look CoRR (2012)
Marius Zimand
Symmetry of Information: A Closer Look. Computation, Physics and Beyond (2012)
Dan A. Simovici, Marius Zimand, Dan Pletea
Several Remarks on Index Generation Functions. ISMVL (2012)
Marius Zimand
On efficient constructions of short lists containing mostly Ramsey graphs CoRR (2012)
Marius Zimand
Nonuniform Kolmogorov extractors CoRR (2012)
Marius Zimand
Possibilities and impossibilities in Kolmogorov complexity extraction CoRR (2011)
Marius Zimand
On the optimal compression of sets in PSPACE. Electron. Colloquium Comput. Complex. 18 (2011)
Marius Zimand
Symmetry of information and bounds on nonuniform randomness extraction via Kolmogorov extractors CoRR (2011)
Marius Zimand
On the Optimal Compression of Sets in PSPACE. FCT (2011)
Marius Zimand
On the optimal compression of sets in PSPACE CoRR (2011)
Marius Zimand
Symmetry of Information and Bounds on Nonuniform Randomness Extraction via Kolmogorov Extractors. Computational Complexity Conference (2011)
Marius Zimand
Two Sources Are Better than One for Increasing the Kolmogorov Complexity of Infinite Sequences. Theory Comput. Syst. 46 (4) (2010)
Marius Zimand
Impossibility of Independence Amplification in Kolmogorov Complexity Theory. MFCS (2010)
Marius Zimand
Counting Dependent and Independent Strings. MFCS (2010)
Marius Zimand
Impossibility of independence amplification in Kolmogorov complexity theory CoRR (2010)
Cristian S. Calude, Marius Zimand
Algorithmically independent sequences. Inf. Comput. 208 (3) (2010)
Marius Zimand
Counting dependent and independent strings CoRR (2010)
Marius Zimand
Simple extractors via constructions of cryptographic pseudo-random generators. Theor. Comput. Sci. 411 (10) (2010)
Marius Zimand
Extracting the Kolmogorov Complexity of Strings and Sequences from Sources with Limited Independence. STACS (2009)
Marius Zimand
Extracting the Kolmogorov Complexity of Strings and Sequences from Sources with Limited Independence CoRR (2009)
Marius Zimand
On generating independent random strings CoRR (2009)
Marius Zimand
On Generating Independent Random Strings. CiE (2009)
Cristian S. Calude, Marius Zimand
Algorithmically independent sequences CoRR (2008)
Cristian S. Calude, Marius Zimand
Algorithmically Independent Sequences. Developments in Language Theory (2008)
Marius Zimand
Two Sources Are Better Than One for Increasing the Kolmogorov Complexity of Infinite Sequences. CSR (2008)
Marius Zimand
Exposure-Resilient Extractors and the Derandomization of Probabilistic Sublinear Time. Comput. Complex. 17 (2) (2008)
Gruia Calinescu, Ion I. Mandoiu, Alexander Zelikovsky, Marius Zimand
Selected Papers from the 1st ACIS International Workshop on Self-Assembling Wireless Networks. J. Univers. Comput. Sci. 13 (1) (2007)
Marius Zimand
Two sources are better than one for increasing the Kolmogorov complexity of infinite sequences CoRR (2007)
Marius Zimand
On Derandomizing Probabilistic Sublinear-Time Algorithms. Computational Complexity Conference (2007)
Cristian S. Calude, Gheorghe Stefanescu, Marius Zimand
Combinatorics and Related Areas A Collection of Papers in Honour of the 65th Birthday of Ioan Tomescu. J. Univers. Comput. Sci. 13 (11) (2007)
Marius Zimand
Exposure-Resilient Extractors. Computational Complexity Conference (2006)
Lane A. Hemaspaandra, Mitsunori Ogihara, Mohammed J. Zaki, Marius Zimand
The Complexity of Finding Top-Toda-Equivalence-Class Members. Theory Comput. Syst. 39 (5) (2006)
Marius Zimand
A List-Decodable Code with Local Encoding and Decoding. SNPD (2005)
Marius Zimand
Simple extractors via constructions of cryptographic pseudo-random generators Electron. Colloquium Comput. Complex. (071) (2005)
Marius Zimand
Simple Extractors via Constructions of Cryptographic Pseudo-random Generators. ICALP (2005)
Marius Zimand
Simple extractors via constructions of cryptographic pseudo-random generators CoRR (2005)
Lane A. Hemaspaandra, Mitsunori Ogihara, Mohammed Javeed Zaki, Marius Zimand
The Complexity of Finding Top-Toda-Equivalence-Class Members. LATIN (2004)
Shiva Azadegan, M. Lavine, Michael O'Leary, Alexander L. Wijesinha, Marius Zimand
An undergraduate track in computer security. ITiCSE (2003)
Shiva Azadegan, M. Lavine, Michael O'Leary, Alexander L. Wijesinha, Marius Zimand
A Dedicated Undergraduate Track in Computer Security Education. World Conference on Information Security Education (2003)
Marius Zimand
Probabilistically Checkable Proofs the Easy Way. IFIP TCS (2002)
Edith Hemaspaandra, Lane A. Hemaspaandra, Marius Zimand
Almost-Everywhere Superiority for Quantum Polynomial Time. Inf. Comput. 175 (2) (2002)
Marius Zimand
Probabilistically Checkable Proofs The Easy Way Electron. Colloquium Comput. Complex. 8 (27) (2001)
Kundi Xue, Marius Zimand
Extractors for the Real World. J. Univers. Comput. Sci. 6 (1) (2000)
Marius Zimand
Relative to a Random Oracle, P/Poly is not Measurable in EXP. Inf. Process. Lett. 69 (2) (1999)
Edith Hemaspaandra, Lane A. Hemaspaandra, Marius Zimand
Almost-Everywhere Superiority for Quantum Computing CoRR (1999)
Lane A. Hemaspaandra, Kulathur S. Rajasethupathy, Prasanna Sethupathy, Marius Zimand
Power Balance and Apportionment Algorithms for the United States Congress. ACM J. Exp. Algorithmics 3 (1998)
Marius Zimand
Weighted NP Optimization Problems: Logical Definability and Approximation Properties. SIAM J. Comput. 28 (1) (1998)
Marius Zimand
On the Size of Classes with Weak Membership Properties. Theor. Comput. Sci. 209 (1-2) (1998)
Marius Zimand
Sharing Random Bits with No Process Coordination. IPPS/SPDP (1998)
Marius Zimand
have Many Strings with Low Kolmogorov Complexity. Inf. Process. Lett. 62 (3) (1997)
Lane A. Hemaspaandra, Marius Zimand
Strong Self-Reducibility Precludes Strong Immunity. Math. Syst. Theory 29 (5) (1996)
Cristian Calude, Marius Zimand
Effective Category and Measure in Abstract Complexity Theory. Theor. Comput. Sci. 154 (2) (1996)
Marius Zimand
A High-Low Kolmogorov Complexity Law Equivalent to the 0-1 Law. Inf. Process. Lett. 57 (2) (1996)
Marius Zimand
On the Topological Size of p-m-Complete Degrees. Theor. Comput. Sci. 147 (1&2) (1995)
Cristian Calude, Marius Zimand
Effective Category and Measure in Abstract Complexity Theory (Extended Abstract). FCT (1995)
Lane A. Hemaspaandra, Ajit Ramachandran, Marius Zimand
Worlds to die for. SIGACT News 26 (4) (1995)
Marius Zimand
Weighted NP Optimization Problems: Logical Definability and Approximation Properties. Computational Complexity Conference (1995)
Marius Zimand
On the Topological Size of p-m-Complete Degrees. Sci. Ann. Cuza Univ. 3 (1994)

Marius Zimand.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Marius Zimand