13 citations · 44 across the 22 of their papers we have counts for
31 papers
Explicit unbalanced 1-expanders with small degree and right size
Bruno Bauwens, Marius Zimand
An explicit graph is given with left size , left degree , right size and -expansion up to~, meaning that every left subset of size $K'…
Online matching games in bipartite expanders: applications to bitprobes and dictionaries with non-adaptive probing
Bruno Bauwens, Marius Zimand
A dictionary is a data structure which stores pairs (key, value). The operation query on input key returns value if the dictionary contains a pair (key, value) and nil otherwise. A…
Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity
Zhenjian Lu, Igor C. Oliveira, Marius Zimand
The classical coding theorem in Kolmogorov complexity states that if an -bit string is sampled with probability by an algorithm with prefix-free domain then K$(x) \leq \…
Online matching games in bipartite expanders: Hall-type results and applications to non-blocking connectors
Bruno Bauwens, Marius Zimand
The classical Hall Theorem shows the equivalence between \emph{offline} matching in bipartite graphs and a certain expansion property. We show that lossless expansion implies effic…
27 Open Problems in Kolmogorov Complexity
Andrei Romashchenko, Alexander Shen, Marius Zimand
The paper proposes open problems in classical Kolmogorov complexity. Each problem is presented with background information and thus the article also surveys some recent studies in…
Online matching in lossless expanders
Marius Zimand
Bauwens and Zimand [BZ 2019] have shown that lossless expanders have an interesting online matching property. The result appears in an implicit form in [BZ 2019]. We present an exp…