We stand with Ukraine

We stand with Ukraine

Marius Zimand

Orcid: 0000-0002-5938-6599

According to our database¹, Marius Zimand authored at least 66 papers between 1986 and 2024.

Collaborative distances:

Dijkstra number² of three.
Erdős number³ of three.

Timeline

Legend:

Book

In proceedings

Article

PhD thesis

Dataset

Other

Links

Online presence:

on orcid.org
on triton.towson.edu

On csauthors.net:

Bibliography

2024

On one-way functions and the average time complexity of almost-optimal compression.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2024

2023

Universal almost Optimal Compression and Slepian-wolf Coding in Probabilistic Polynomial Time.

[BibT_eX]

[DOI]

,

J. ACM, April, 2023

Frontiers of Computability, Randomness, and Complexity (dedicated to the 70th birthday of Professor Cristian Calude).

[BibT_eX]

[DOI]

Alastair A. Abbott

,

Cezar Câmpeanu

,

,

,

Theor. Comput. Sci., March, 2023

2022

Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity.

[BibT_eX]

[DOI]

,

Igor Carboni Oliveira

,

Electron. Colloquium Comput. Complex., 2022

Hall-type theorems for fast almost dynamic matching and applications.

[BibT_eX]

[DOI]

,

CoRR, 2022

2021

27 Open Problems in Kolmogorov Complexity.

[BibT_eX]

[DOI]

Andrei E. Romashchenko

,

,

SIGACT News, 2021

Online matching in lossless expanders.

[BibT_eX]

[DOI]

CoRR, 2021

List Approximation for Increasing Kolmogorov Complexity.

[BibT_eX]

[DOI]

Axioms, 2021

2020

Universal codes in the shared-randomness model for channels with general distortion capabilities.

[BibT_eX]

[DOI]

,

CoRR, 2020

Secret Key Agreement from Correlated Data, with No Prior Information.

[BibT_eX]

[DOI]

Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science, 2020

2019

On a conditional inequality in Kolmogorov complexity and its applications in communication complexity.

[BibT_eX]

[DOI]

Andrei E. Romashchenko

,

CoRR, 2019

2018

An operational characterization of mutual information in algorithmic information theory.

[BibT_eX]

[DOI]

Andrei E. Romashchenko

,

Electron. Colloquium Comput. Complex., 2018

Short lists with short programs in short time.

[BibT_eX]

[DOI]

,

,

Nikolai K. Vereshchagin

,

Comput. Complex., 2018

2017

Distributed compression through the lens of algorithmic information theory: a primer.

[BibT_eX]

[DOI]

CoRR, 2017

Kolmogorov complexity version of Slepian-Wolf coding.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

2016

A Brief on Short Descriptions.

[BibT_eX]

[DOI]

,

SIGACT News, 2016

2015

On Approximate Decidability of Minimal Programs.

[BibT_eX]

[DOI]

,

ACM Trans. Comput. Theory, 2015

On Optimal Language Compression for Sets in PSPACE/poly.

[BibT_eX]

[DOI]

N. V. Vinodchandran

,

Theory Comput. Syst., 2015

Linear list-approximation for short programs (or the power of a few random bits).

[BibT_eX]

[DOI]

,

Electron. Colloquium Comput. Complex., 2015

2014

Counting Dependent and Independent Strings.

[BibT_eX]

[DOI]

Fundam. Informaticae, 2014

Short Lists with Short Programs in Short Time - A Short Proof.

[BibT_eX]

[DOI]

Proceedings of the Language, Life, Limits - 10th Conference on Computability in Europe, 2014

2013

Review of Deterministic Extraction from weak random sources by Ariel Gabizon.

[BibT_eX]

[DOI]

SIGACT News, 2013

Generating Kolmogorov random strings from sources with limited independence.

[BibT_eX]

[DOI]

J. Log. Comput., 2013

On Efficient Constructions of Short Lists Containing Mostly Ramsey Graphs.

[BibT_eX]

[DOI]

Proceedings of the Theory and Applications of Models of Computation, 2013

2012

Nonuniform Kolmogorov extractors

[BibT_eX]

[DOI]

CoRR, 2012

Several Remarks on Index Generation Functions.

[BibT_eX]

[DOI]

Dan A. Simovici

,

,

Proceedings of the 42nd IEEE International Symposium on Multiple-Valued Logic, 2012

Symmetry of Information: A Closer Look.

[BibT_eX]

[DOI]

Proceedings of the Computation, Physics and Beyond, 2012

2011

On the optimal compression of sets in PSPACE.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

Possibilities and impossibilities in Kolmogorov complexity extraction

[BibT_eX]

[DOI]

CoRR, 2011

Symmetry of Information and Bounds on Nonuniform Randomness Extraction via Kolmogorov Extractors.

[BibT_eX]

[DOI]

Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011

2010

Simple extractors via constructions of cryptographic pseudo-random generators.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2010

Two Sources Are Better than One for Increasing the Kolmogorov Complexity of Infinite Sequences.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2010

Algorithmically independent sequences.

[BibT_eX]

[DOI]

Cristian S. Calude

,

Inf. Comput., 2010

Impossibility of Independence Amplification in Kolmogorov Complexity Theory.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2010, 2010

2009

Extracting the Kolmogorov Complexity of Strings and Sequences from Sources with Limited Independence.

[BibT_eX]

[DOI]

Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, 2009

On Generating Independent Random Strings.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Theory and Computational Practice, 2009

2008

Exposure-Resilient Extractors and the Derandomization of Probabilistic Sublinear Time.

[BibT_eX]

[DOI]

Comput. Complex., 2008

2007

Combinatorics and Related Areas A Collection of Papers in Honour of the 65th Birthday of Ioan Tomescu.

[BibT_eX]

[DOI]

Cristian S. Calude

,

Gheorghe Stefanescu

,

J. Univers. Comput. Sci., 2007

Selected Papers from the 1st ACIS International Workshop on Self-Assembling Wireless Networks.

[BibT_eX]

[DOI]

Gruia Calinescu

,

,

Alexander Zelikovsky

,

J. Univers. Comput. Sci., 2007

On Derandomizing Probabilistic Sublinear-Time Algorithms.

[BibT_eX]

[DOI]

Proceedings of the 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 2007

2006

The Complexity of Finding Top-Toda-Equivalence-Class Members.

[BibT_eX]

[DOI]

Lane A. Hemaspaandra

,

Mitsunori Ogihara

,

Mohammed J. Zaki

,

Theory Comput. Syst., 2006

Exposure-Resilient Extractors.

[BibT_eX]

[DOI]

Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006

2005

A List-Decodable Code with Local Encoding and Decoding.

[BibT_eX]

[DOI]

Proceedings of the 6th ACIS International Conference on Software Engineering, 2005

2003

An undergraduate track in computer security.

[BibT_eX]

[DOI]

,

,

Michael O'Leary

,

Alexander L. Wijesinha

,

Proceedings of the 8th Annual SIGCSE Conference on Innovation and Technology in Computer Science Education, 2003

A Dedicated Undergraduate Track in Computer Security Education.

[BibT_eX]

,

,

Michael O'Leary

,

Alexander L. Wijesinha

,

Proceedings of the Security Education and Critical Infrastructures, 2003

2002

Almost-Everywhere Superiority for Quantum Polynomial Time.

[BibT_eX]

[DOI]

Edith Hemaspaandra

,

Lane A. Hemaspaandra

,

Inf. Comput., 2002

2001

Probabilistically Checkable Proofs The Easy Way

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2001

2000

Extractors for the Real World.

[BibT_eX]

[DOI]

,

J. Univers. Comput. Sci., 2000

1999

Relative to a Random Oracle, P/Poly is not Measurable in EXP.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1999

Almost-Everywhere Superiority for Quantum Computing

[BibT_eX]

[DOI]

Edith Hemaspaandra

,

Lane A. Hemaspaandra

,

CoRR, 1999

1998

On the Size of Classes with Weak Membership Properties.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1998

Weighted NP Optimization Problems: Logical Definability and Approximation Properties.

[BibT_eX]

[DOI]

SIAM J. Comput., 1998

Power Balance and Apportionment Algorithms for the United States Congress.

[BibT_eX]

[DOI]

Lane A. Hemaspaandra

,

Kulathur S. Rajasethupathy

,

Prasanna Sethupathy

,

ACM J. Exp. Algorithmics, 1998

Sharing Random Bits with No Process Coordination.

[BibT_eX]

[DOI]

Proceedings of the 12th International Parallel Processing Symposium / 9th Symposium on Parallel and Distributed Processing (IPPS/SPDP '98), March 30, 1998

1997

Large Sets in AC<sup>0</sup> have Many Strings with Low Kolmogorov Complexity.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1997

1996

Effective Category and Measure in Abstract Complexity Theory.

[BibT_eX]

[DOI]

Cristian Calude

,

Theor. Comput. Sci., 1996

Strong Self-Reducibility Precludes Strong Immunity.

[BibT_eX]

[DOI]

Lane A. Hemaspaandra

,

Math. Syst. Theory, 1996

A High-Low Kolmogorov Complexity Law Equivalent to the 0-1 Law.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1996

1995

On the Topological Size of p-m-Complete Degrees.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1995

Worlds to die for.

[BibT_eX]

[DOI]

Lane A. Hemaspaandra

,

Ajit Ramachandran

,

SIGACT News, 1995

Effective Category and Measure in Abstract Complexity Theory (Extended Abstract).

[BibT_eX]

[DOI]

Cristian Calude

,

Proceedings of the Fundamentals of Computation Theory, 10th International Symposium, 1995

1994

Minimum Spanning Hypertrees.

[BibT_eX]

[DOI]

,

Discret. Appl. Math., 1994

1993

If not Empty, NP - P is Topologically Large.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1993

1992

Recursive Baire Classification and Speedable Functions.

[BibT_eX]

[DOI]

Cristian S. Calude

,

Gabriel Istrate

,

Math. Log. Q., 1992

1987

On Relativizations with Restricted Number of Accesses to the Oracle Set.

[BibT_eX]

[DOI]

Math. Syst. Theory, 1987

1986

On the Topological Size of Sets of Random Strings.

[BibT_eX]

[DOI]

Math. Log. Q., 1986

Loading...