default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDMarius Zimand
Person information
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
[i39]Marius Zimand:
On one-way functions and the average time complexity of almost-optimal compression. Electron. Colloquium Comput. Complex. TR24 (2024)- 2023
- [j37]Bruno Bauwens
, Marius Zimand:
Universal almost Optimal Compression and Slepian-wolf Coding in Probabilistic Polynomial Time. J. ACM 70(2): 9:1-9:33 (2023) - [j36]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: 113819 (2023) - 2022
- [c30]Zhenjian Lu, Igor C. Oliveira, Marius Zimand:
Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity. ICALP 2022: 92:1-92:14 - [i38]Andrei E. Romashchenko, Alexander Shen, Marius Zimand:
27 Open Problems in Kolmogorov Complexity. CoRR abs/2203.15109 (2022) - [i37]Bruno Bauwens, Marius Zimand:
Hall-type theorems for fast almost dynamic matching and applications. CoRR abs/2204.01936 (2022) - [i36]Zhenjian Lu, Igor C. Oliveira, Marius Zimand:
Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity. CoRR abs/2204.08312 (2022) - [i35]Zhenjian Lu, Igor Carboni Oliveira, Marius Zimand:
Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity. Electron. Colloquium Comput. Complex. TR22 (2022) - 2021
- [j35]Marius Zimand:
List Approximation for Increasing Kolmogorov Complexity. Axioms 10(4): 334 (2021) - [j34]Andrei E. Romashchenko, Alexander Shen, Marius Zimand:
27 Open Problems in Kolmogorov Complexity. SIGACT News 52(4): 31-54 (2021) - [i34]Marius Zimand:
Online matching in lossless expanders. CoRR abs/2102.08243 (2021) - 2020
- [c29]Marius Zimand:
Secret Key Agreement from Correlated Data, with No Prior Information. STACS 2020: 21:1-21:12 - [i33]Bruno Bauwens, Marius Zimand:
Universal codes in the shared-randomness model for channels with general distortion capabilities. CoRR abs/2007.02330 (2020)
2010 – 2019
- 2019
- [j33]Andrei E. Romashchenko, Marius Zimand:
An Operational Characterization of Mutual Information in Algorithmic Information Theory. J. ACM 66(5): 38:1-38:42 (2019) - [i32]Andrei E. Romashchenko, Marius Zimand:
On a conditional inequality in Kolmogorov complexity and its applications in communication complexity. CoRR abs/1905.00164 (2019) - [i31]Marius Zimand:
Secret key agreement from correlated data, with no prior information. CoRR abs/1910.03757 (2019) - [i30]Bruno Bauwens, Marius Zimand:
Universal almost optimal compression and Slepian-Wolf coding in probabilistic polynomial time. CoRR abs/1911.04268 (2019) - 2018
- [j32]Bruno Bauwens, Anton Makhlin, Nikolai K. Vereshchagin, Marius Zimand:
Short lists with short programs in short time. Comput. Complex. 27(1): 31-61 (2018) - [c28]Andrei E. Romashchenko, Marius Zimand:
An Operational Characterization of Mutual Information in Algorithmic Information Theory. ICALP 2018: 95:1-95:14 - [i29]Andrei E. Romashchenko, Marius Zimand:
An operational characterization of mutual information in algorithmic information theory. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [c27]Marius Zimand:
List Approximation for Increasing Kolmogorov Complexity. STACS 2017: 58:1-58:12 - [c26]Marius Zimand:
Kolmogorov complexity version of Slepian-Wolf coding. STOC 2017: 22-32 - [i28]Marius Zimand:
Distributed compression through the lens of algorithmic information theory: a primer. CoRR abs/1706.08468 (2017) - [i27]Andrei E. Romashchenko, Marius Zimand:
An operational characterization of mutual information in algorithmic information theory. CoRR abs/1710.05984 (2017) - 2016
- [j31]Jason Teutsch, Marius Zimand:
A Brief on Short Descriptions. SIGACT News 47(1): 42-67 (2016) - [i26]Marius Zimand:
List approximation for increasing Kolmogorov complexity. CoRR abs/1609.05984 (2016) - 2015
- [j30]N. V. Vinodchandran, Marius Zimand:
On Optimal Language Compression for Sets in PSPACE/poly. Theory Comput. Syst. 56(3): 581-590 (2015) - [j29]Jason Teutsch, Marius Zimand:
On Approximate Decidability of Minimal Programs. ACM Trans. Comput. Theory 7(4): 17:1-17:16 (2015) - [i25]Marius Zimand:
Kolmogorov complexity version of Slepian-Wolf coding. CoRR abs/1511.03602 (2015) - [i24]Bruno Bauwens, Marius Zimand:
Linear list-approximation for short programs (or the power of a few random bits). Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [j28]Marius Zimand:
Counting Dependent and Independent Strings. Fundam. Informaticae 131(3-4): 485-497 (2014) - [c25]Marius Zimand:
Short Lists with Short Programs in Short Time - A Short Proof. CiE 2014: 403-408 - [c24]Bruno Bauwens, Marius Zimand:
Linear List-Approximation for Short Programs (or the Power of a Few Random Bits). CCC 2014: 241-247 - [i23]Jason Teutsch, Marius Zimand:
On approximate decidability of minimal programs. CoRR abs/1409.0496 (2014) - 2013
- [j27]Marius Zimand:
Generating Kolmogorov random strings from sources with limited independence. J. Log. Comput. 23(4): 909-924 (2013) - [j26]Marius Zimand:
Review of Deterministic Extraction from weak random sources by Ariel Gabizon. SIGACT News 44(1): 36-37 (2013) - [c23]Bruno Bauwens, Anton Makhlin, Nikolay K. Vereshchagin, Marius Zimand:
Short Lists with Short Programs in Short Time. CCC 2013: 98-108 - [c22]Marius Zimand:
On Efficient Constructions of Short Lists Containing Mostly Ramsey Graphs. TAMC 2013: 205-211 - [i22]Bruno Bauwens, Anton Makhlin, Nikolay K. Vereshchagin, Marius Zimand:
Short lists with short programs in short time. CoRR abs/1301.1547 (2013) - [i21]Marius Zimand:
Short lists with short programs in short time - a short proof. CoRR abs/1302.1109 (2013) - [i20]N. V. Vinodchandran, Marius Zimand:
On optimal language compression for sets in PSPACE/poly. CoRR abs/1304.1005 (2013) - [i19]Bruno Bauwens, Marius Zimand:
Linear list-approximation for short programs (or the power of a few random bits). CoRR abs/1311.7278 (2013) - [i18]Bruno Bauwens, Anton Makhlin, Nikolay K. Vereshchagin, Marius Zimand:
Short lists with short programs in short time. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [c21]Marius Zimand:
Symmetry of Information: A Closer Look. Computation, Physics and Beyond 2012: 241-246 - [c20]Dan A. Simovici, Marius Zimand, Dan Pletea:
Several Remarks on Index Generation Functions. ISMVL 2012: 179-184 - [i17]Marius Zimand:
Nonuniform Kolmogorov extractors. CoRR abs/1204.6696 (2012) - [i16]Marius Zimand:
Symmetry of Information: A Closer Look. CoRR abs/1206.5184 (2012) - [i15]Marius Zimand:
On efficient constructions of short lists containing mostly Ramsey graphs. CoRR abs/1210.4408 (2012) - 2011
- [c19]Marius Zimand:
Symmetry of Information and Bounds on Nonuniform Randomness Extraction via Kolmogorov Extractors. CCC 2011: 148-156 - [c18]Marius Zimand:
On the Optimal Compression of Sets in PSPACE. FCT 2011: 65-77 - [i14]Marius Zimand:
Symmetry of information and bounds on nonuniform randomness extraction via Kolmogorov extractors. CoRR abs/1103.5669 (2011) - [i13]Marius Zimand:
Possibilities and impossibilities in Kolmogorov complexity extraction. CoRR abs/1104.0872 (2011) - [i12]Marius Zimand:
On the optimal compression of sets in PSPACE. CoRR abs/1104.2816 (2011) - [i11]Marius Zimand:
On the optimal compression of sets in PSPACE. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [j25]Cristian S. Calude, Marius Zimand:
Algorithmically independent sequences. Inf. Comput. 208(3): 292-308 (2010) - [j24]Marius Zimand:
Two Sources Are Better than One for Increasing the Kolmogorov Complexity of Infinite Sequences. Theory Comput. Syst. 46(4): 707-722 (2010) - [j23]Marius Zimand:
Simple extractors via constructions of cryptographic pseudo-random generators. Theor. Comput. Sci. 411(10): 1236-1250 (2010) - [c17]Marius Zimand:
Counting Dependent and Independent Strings. MFCS 2010: 689-700 - [c16]Marius Zimand:
Impossibility of Independence Amplification in Kolmogorov Complexity Theory. MFCS 2010: 701-712 - [i10]Marius Zimand:
Impossibility of independence amplification in Kolmogorov complexity theory. CoRR abs/1006.0701 (2010) - [i9]Marius Zimand:
Counting dependent and independent strings. CoRR abs/1006.1315 (2010)
2000 – 2009
- 2009
- [c15]Marius Zimand:
On Generating Independent Random Strings. CiE 2009: 499-508 - [c14]Marius Zimand:
Extracting the Kolmogorov Complexity of Strings and Sequences from Sources with Limited Independence. STACS 2009: 697-708 - [i8]Marius Zimand:
Extracting the Kolmogorov Complexity of Strings and Sequences from Sources with Limited Independence. CoRR abs/0902.2141 (2009) - [i7]Marius Zimand:
On generating independent random strings. CoRR abs/0903.3889 (2009) - 2008
- [j22]Marius Zimand:
Exposure-Resilient Extractors and the Derandomization of Probabilistic Sublinear Time. Comput. Complex. 17(2): 220-253 (2008) - [c13]Marius Zimand:
Two Sources Are Better Than One for Increasing the Kolmogorov Complexity of Infinite Sequences. CSR 2008: 326-338 - [c12]Cristian S. Calude, Marius Zimand:
Algorithmically Independent Sequences. Developments in Language Theory 2008: 183-195 - [i6]Cristian S. Calude, Marius Zimand:
Algorithmically independent sequences. CoRR abs/0802.0487 (2008) - 2007
- [j21]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): 1-3 (2007) - [j20]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): 1498-1500 (2007) - [c11]Marius Zimand:
On Derandomizing Probabilistic Sublinear-Time Algorithms. CCC 2007: 1-9 - [i5]Marius Zimand:
Two sources are better than one for increasing the Kolmogorov complexity of infinite sequences. CoRR abs/0705.4658 (2007) - 2006
- [j19]Lane A. Hemaspaandra, Mitsunori Ogihara, Mohammed J. Zaki, Marius Zimand:
The Complexity of Finding Top-Toda-Equivalence-Class Members. Theory Comput. Syst. 39(5): 669-684 (2006) - [c10]Marius Zimand:
Exposure-Resilient Extractors. CCC 2006: 61-72 - 2005
- [c9]Marius Zimand:
Simple Extractors via Constructions of Cryptographic Pseudo-random Generators. ICALP 2005: 115-127 - [c8]Marius Zimand:
A List-Decodable Code with Local Encoding and Decoding. SNPD 2005: 232-237 - [i4]Marius Zimand:
Simple extractors via constructions of cryptographic pseudo-random generators. CoRR abs/cs/0501075 (2005) - [i3]Marius Zimand:
Simple extractors via constructions of cryptographic pseudo-random generators. Electron. Colloquium Comput. Complex. TR05 (2005) - 2004
- [c7]Lane A. Hemaspaandra, Mitsunori Ogihara, Mohammed Javeed Zaki, Marius Zimand:
The Complexity of Finding Top-Toda-Equivalence-Class Members. LATIN 2004: 90-99 - 2003
- [c6]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: 319-332 - [c5]Shiva Azadegan, M. Lavine, Michael O'Leary, Alexander L. Wijesinha, Marius Zimand:
An undergraduate track in computer security. ITiCSE 2003: 207-210 - 2002
- [j18]Edith Hemaspaandra, Lane A. Hemaspaandra, Marius Zimand:
Almost-Everywhere Superiority for Quantum Polynomial Time. Inf. Comput. 175(2): 171-181 (2002) - [c4]Marius Zimand:
Probabilistically Checkable Proofs the Easy Way. IFIP TCS 2002: 337-351 - 2001
- [i2]Marius Zimand:
Probabilistically Checkable Proofs The Easy Way. Electron. Colloquium Comput. Complex. TR01 (2001) - 2000
- [j17]Kundi Xue, Marius Zimand:
Extractors for the Real World. J. Univers. Comput. Sci. 6(1): 212-225 (2000)
1990 – 1999
- 1999
- [j16]Marius Zimand:
Relative to a Random Oracle, P/Poly is not Measurable in EXP. Inf. Process. Lett. 69(2): 83-86 (1999) - [i1]Edith Hemaspaandra, Lane A. Hemaspaandra, Marius Zimand:
Almost-Everywhere Superiority for Quantum Computing. CoRR quant-ph/9910033 (1999) - 1998
- [j15]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: 1 (1998) - [j14]Marius Zimand:
Weighted NP Optimization Problems: Logical Definability and Approximation Properties. SIAM J. Comput. 28(1): 36-56 (1998) - [j13]Marius Zimand:
On the Size of Classes with Weak Membership Properties. Theor. Comput. Sci. 209(1-2): 225-235 (1998) - [c3]Marius Zimand:
Sharing Random Bits with No Process Coordination. IPPS/SPDP 1998: 455-459 - 1997
- [j12]Marius Zimand:
Large Sets in AC0 have Many Strings with Low Kolmogorov Complexity. Inf. Process. Lett. 62(3): 165-170 (1997) - 1996
- [j11]Marius Zimand:
A High-Low Kolmogorov Complexity Law Equivalent to the 0-1 Law. Inf. Process. Lett. 57(2): 59-64 (1996) - [j10]Lane A. Hemaspaandra, Marius Zimand:
Strong Self-Reducibility Precludes Strong Immunity. Math. Syst. Theory 29(5): 535-548 (1996) - [j9]Cristian Calude, Marius Zimand:
Effective Category and Measure in Abstract Complexity Theory. Theor. Comput. Sci. 154(2): 307-327 (1996) - 1995
- [j8]Lane A. Hemaspaandra, Ajit Ramachandran, Marius Zimand:
Worlds to die for. SIGACT News 26(4): 5-15 (1995) - [j7]Marius Zimand:
On the Topological Size of p-m-Complete Degrees. Theor. Comput. Sci. 147(1&2): 137-147 (1995) - [c2]Marius Zimand:
Weighted NP Optimization Problems: Logical Definability and Approximation Properties. SCT 1995: 12-28 - [c1]Cristian Calude, Marius Zimand:
Effective Category and Measure in Abstract Complexity Theory (Extended Abstract). FCT 1995: 156-170 - 1994
- [j6]Marius Zimand:
On the Topological Size of p-m-Complete Degrees. Sci. Ann. Cuza Univ. 3: 107-116 (1994) - [j5]Ioan Tomescu, Marius Zimand:
Minimum Spanning Hypertrees. Discret. Appl. Math. 54(1): 67-76 (1994) - 1993
- [j4]Marius Zimand:
If not Empty, NP - P is Topologically Large. Theor. Comput. Sci. 119(2): 293-310 (1993) - 1992
- [j3]Cristian S. Calude, Gabriel Istrate, Marius Zimand:
Recursive Baire Classification and Speedable Functions. Math. Log. Q. 38(1): 169-178 (1992)
1980 – 1989
- 1987
- [j2]Marius Zimand:
On Relativizations with Restricted Number of Accesses to the Oracle Set. Math. Syst. Theory 20(1): 1-11 (1987) - 1986
- [j1]Marius Zimand:
On the Topological Size of Sets of Random Strings. Math. Log. Q. 32(6): 81-88 (1986)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-12-26 01:56 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
