Marius Zimand

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