# zbMATH — the first resource for mathematics

## Zimand, Marius

Compute Distance To:
 Author ID: zimand.marius Published as: Zimand, M.; Zimand, Marius
 Documents Indexed: 51 Publications since 1983, including 1 Book Reviewing Activity: 181 Reviews
all top 5

#### Co-Authors

 35 single-authored 6 Calude, Cristian S. 4 Hemaspaandra, Lane A. 2 Ogihara, Mitsunori 2 Zaki, Mohammed Javeed 1 Bauwens, Bruno 1 Hemaspaandra, Edith 1 Istrate, Gabriel I. 1 Jürgensen, Helmut 1 Makhlin, Anton 1 Romashchenko, Andrei 1 Teutsch, Jason 1 Tomescu, Ioan 1 Vereshchagin, Nikolay K. 1 Vinodchandran, N. Variyam 1 Xue, Kundi
all top 5

#### Serials

 5 Theoretical Computer Science 3 Information Processing Letters 3 Theory of Computing Systems 2 Mathematical Systems Theory 2 Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 2 Information and Computation 2 Computational Complexity 1 Discrete Applied Mathematics 1 Analele Universităţii Bucureşti. Matematică 1 Applied Mathematics and Computation 1 Foundations of Control Engineering 1 SIAM Journal on Computing 1 Journal of Logic and Computation 1 International Journal of Computer Mathematics 1 Analele Ştiinţifice ale Universităţii Al. I. Cuza din Iaşi. Serie Nouă. Informatică 1 Journal of the ACM 1 Fundamenta Informaticae 1 Journal of Universal Computer Science 1 North-Holland Mathematics Studies 1 ACM Transactions on Computation Theory

#### Fields

 47 Computer science (68-XX) 11 Mathematical logic and foundations (03-XX) 3 Combinatorics (05-XX) 2 Quantum theory (81-XX) 1 Information and communication theory, circuits (94-XX)

#### Citations contained in zbMATH

30 Publications have been cited 84 times in 57 Documents Cited by Year
Short lists with short programs in short time. Zbl 1390.68356
Bauwens, Bruno; Makhlin, Anton; Vereshchagin, Nikolay; Zimand, Marius
2018
Is independence an exception? Zbl 0822.03024
Calude, C.; Jürgensen, H.; Zimand, M.
1994
Extracting the Kolmogorov complexity of strings and sequences from sources with limited independence. Zbl 1236.68113
Zimand, Marius
2009
Two sources are better than one for increasing the Kolmogorov complexity of infinite sequences. Zbl 1143.68020
Zimand, Marius
2008
Short lists with short programs in short time – a short proof. Zbl 1432.68201
Zimand, Marius
2014
Computational complexity: a quantitative perspective. Zbl 1106.68048
Zimand, Marius
2004
Strong self-reducibility precludes strong immunity. Zbl 0857.68046
Hemaspaandra, L. A.; Zimand, M.
1996
Exposure-resilient extractors and the derandomization of probabilistic sublinear time. Zbl 1149.68035
Zimand, Marius
2008
Almost-everywhere superiority for quantum polynomial time. Zbl 1012.68067
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Zimand, Marius
2002
On approximate decidability of minimal programs. Zbl 1347.68096
Teutsch, Jason; Zimand, Marius
2015
On the optimal compression of sets in PSPACE. Zbl 1342.68140
Zimand, Marius
2011
Impossibility of independence amplification in Kolmogorov complexity theory. Zbl 1287.68085
Zimand, Marius
2010
Two sources are better than one for increasing the Kolmogorov complexity of infinite sequences. Zbl 1205.68182
Zimand, Marius
2010
On generating independent random strings. Zbl 1268.68090
Zimand, Marius
2009
Algorithmically independent sequences. Zbl 1159.68012
Calude, Cristian S.; Zimand, Marius
2008
The complexity of finding top-Toda-equivalence-class members. Zbl 1100.68033
Hemaspaandra, Lane A.; Ogihara, Mitsunori; Zaki, Mohammed J.; Zimand, Marius
2006
Efficient privatization of random bits. Zbl 0922.68051
Zimand, Marius
1998
On the size of classes with weak membership properties. Zbl 0912.68048
Zimand, Marius
1998
Weighted NP optimization problems: logical definability and approximation properties. Zbl 0914.68074
Zimand, Marius
1998
Minimum spanning hypertrees. Zbl 0812.68105
Tomescu, Ioan; Zimand, Marius
1994
If not empty, NP-P is topologically large. Zbl 0781.68072
Zimand, Marius
1993
Recursive Baire classification and speedable functions. Zbl 0798.03042
Calude, Cristian; Istrate, Gabriel; Zimand, Marius
1992
Generating Kolmogorov random strings from sources with limited independence. Zbl 1271.68114
Zimand, Marius
2013
Counting dependent and independent strings. Zbl 1287.68084
Zimand, Marius
2010
Algorithmically independent sequences. Zbl 1187.68268
Calude, Cristian S.; Zimand, Marius
2010
Large sets in $$\mathrm{AC}^{0}$$ have many strings with low Kolmogorov complexity. Zbl 1337.68142
Zimand, Marius
1997
Effective category and measure in abstract complexity theory. Zbl 0872.03027
Calude, Cristian; Zimand, Marius
1996
On the topological size of p-m-complete degrees. Zbl 0873.68066
Zimand, Marius
1995
On the existence of complete sets for positive relativized classes. Zbl 0672.03027
Zimand, Marius
1988
On the topological size of sets of random strings. Zbl 0576.03031
Zimand, M.
1986
Short lists with short programs in short time. Zbl 1390.68356
Bauwens, Bruno; Makhlin, Anton; Vereshchagin, Nikolay; Zimand, Marius
2018
On approximate decidability of minimal programs. Zbl 1347.68096
Teutsch, Jason; Zimand, Marius
2015
Short lists with short programs in short time – a short proof. Zbl 1432.68201
Zimand, Marius
2014
Generating Kolmogorov random strings from sources with limited independence. Zbl 1271.68114
Zimand, Marius
2013
On the optimal compression of sets in PSPACE. Zbl 1342.68140
Zimand, Marius
2011
Impossibility of independence amplification in Kolmogorov complexity theory. Zbl 1287.68085
Zimand, Marius
2010
Two sources are better than one for increasing the Kolmogorov complexity of infinite sequences. Zbl 1205.68182
Zimand, Marius
2010
Counting dependent and independent strings. Zbl 1287.68084
Zimand, Marius
2010
Algorithmically independent sequences. Zbl 1187.68268
Calude, Cristian S.; Zimand, Marius
2010
Extracting the Kolmogorov complexity of strings and sequences from sources with limited independence. Zbl 1236.68113
Zimand, Marius
2009
On generating independent random strings. Zbl 1268.68090
Zimand, Marius
2009
Two sources are better than one for increasing the Kolmogorov complexity of infinite sequences. Zbl 1143.68020
Zimand, Marius
2008
Exposure-resilient extractors and the derandomization of probabilistic sublinear time. Zbl 1149.68035
Zimand, Marius
2008
Algorithmically independent sequences. Zbl 1159.68012
Calude, Cristian S.; Zimand, Marius
2008
The complexity of finding top-Toda-equivalence-class members. Zbl 1100.68033
Hemaspaandra, Lane A.; Ogihara, Mitsunori; Zaki, Mohammed J.; Zimand, Marius
2006
Computational complexity: a quantitative perspective. Zbl 1106.68048
Zimand, Marius
2004
Almost-everywhere superiority for quantum polynomial time. Zbl 1012.68067
Hemaspaandra, Edith; Hemaspaandra, Lane A.; Zimand, Marius
2002
Efficient privatization of random bits. Zbl 0922.68051
Zimand, Marius
1998
On the size of classes with weak membership properties. Zbl 0912.68048
Zimand, Marius
1998
Weighted NP optimization problems: logical definability and approximation properties. Zbl 0914.68074
Zimand, Marius
1998
Large sets in $$\mathrm{AC}^{0}$$ have many strings with low Kolmogorov complexity. Zbl 1337.68142
Zimand, Marius
1997
Strong self-reducibility precludes strong immunity. Zbl 0857.68046
Hemaspaandra, L. A.; Zimand, M.
1996
Effective category and measure in abstract complexity theory. Zbl 0872.03027
Calude, Cristian; Zimand, Marius
1996
On the topological size of p-m-complete degrees. Zbl 0873.68066
Zimand, Marius
1995
Is independence an exception? Zbl 0822.03024
Calude, C.; Jürgensen, H.; Zimand, M.
1994
Minimum spanning hypertrees. Zbl 0812.68105
Tomescu, Ioan; Zimand, Marius
1994
If not empty, NP-P is topologically large. Zbl 0781.68072
Zimand, Marius
1993
Recursive Baire classification and speedable functions. Zbl 0798.03042
Calude, Cristian; Istrate, Gabriel; Zimand, Marius
1992
On the existence of complete sets for positive relativized classes. Zbl 0672.03027
Zimand, Marius
1988
On the topological size of sets of random strings. Zbl 0576.03031
Zimand, M.
1986
all top 5

#### Cited by 69 Authors

 13 Zimand, Marius 8 Calude, Cristian S. 6 Hemaspaandra, Lane A. 3 Jürgensen, Helmut 3 Teutsch, Jason 3 Vereshchagin, Nikolay K. 2 Hemaspaandra, Edith 2 Jain, Sanjay 2 Musatov, Daniil 2 Rothe, Jörg-Matthias 2 Stephan, Frank 2 Vinodchandran, N. Variyam 2 Wang, Yongge 1 Ambegaokar, Vinay 1 Ambos-Spies, Klaus 1 Barland, Ian 1 Bauwens, Bruno 1 Becher, Verónica 1 Bienvenu, Laurent 1 Bridges, Douglas Suth 1 Calude, Elena 1 Câmpeanu, Cezar 1 Carton, Olivier 1 Crescenzi, Pierluigi 1 de Castro, Alexandre 1 Diacu, Florin Nicolae 1 Doty, David 1 Downey, Rodney Graham 1 Fortnow, Lance J. 1 Garcia, Gregori 1 Greenberg, Noam 1 Grossman, Ofer 1 Heiber, Pablo Ariel 1 Hempel, Harald 1 Hitchcock, John M. 1 Kinne, Jeff 1 Kolaitis, Phokion G. 1 Kräling, Thorsten 1 Lu, Chijen 1 Makhlin, Anton 1 Merkle, Wolfgang 1 Miles, Eric 1 Miller, Joseph S. 1 Milovanov, Alexey 1 Mora, Gaspar 1 Moshkovitz, Dana 1 Ohya, Masanori 1 Patarin, Jacques 1 Pavan, Aduri 1 Redtwitz, D. A. 1 Romashchenko, Andrei 1 Rubery, Daniel 1 Scozzari, Andrea 1 Shaltiel, Ronen 1 Shen, Alexander 1 Silvestri, Riccardo 1 Staiger, Ludwig 1 Suzuki, Toshio 1 Tantau, Till 1 Tardella, Fabio 1 Thakur, Madhukar N. 1 Tomescu, Ioan 1 Trevisan, Luca 1 van Melkebeek, Dieter 1 Viola, Emanuele 1 Volovich, Igor’ Vasil’evich 1 Wang, Fengming 1 Watanabe, Osamu 1 Yamakami, Tomoyuki
all top 5

#### Cited in 21 Serials

 13 Theoretical Computer Science 10 Theory of Computing Systems 4 Information and Computation 3 Information Processing Letters 3 Computational Complexity 2 Journal of Computer and System Sciences 1 Discrete Applied Mathematics 1 Discrete Mathematics 1 Reports on Mathematical Physics 1 The Mathematical Intelligencer 1 Advances in Mathematics 1 Mathematical Systems Theory 1 SIAM Journal on Computing 1 Advances in Applied Mathematics 1 Journal of Cryptology 1 MSCS. Mathematical Structures in Computer Science 1 Fractals 1 Annalen der Physik. 8th Series 1 RAIRO. Theoretical Informatics and Applications 1 Quantum Information Processing 1 ACM Transactions on Computation Theory
all top 5

#### Cited in 12 Fields

 45 Computer science (68-XX) 18 Mathematical logic and foundations (03-XX) 5 Quantum theory (81-XX) 4 Combinatorics (05-XX) 2 Operations research, mathematical programming (90-XX) 2 Information and communication theory, circuits (94-XX) 1 Order, lattices, ordered algebraic structures (06-XX) 1 Measure and integration (28-XX) 1 Probability theory and stochastic processes (60-XX) 1 Statistics (62-XX) 1 Mechanics of particles and systems (70-XX) 1 Statistical mechanics, structure of matter (82-XX)