Gleb Posobin

most citedComputing majority with low-fan-in majority queries

2 citations · 2 across the 1 of their papers we have counts for

collaborators

3 papers

cs.IT2018

Random noise increases Kolmogorov complexity and Hausdorff dimension

Gleb Posobin, Alexander Shen

Consider a binary string $x$ of length $n$ whose Kolmogorov complexity is $α n$ for some $α < 1$ . We want to increase the complexity of $x$ by changing a small fraction of bits in $x$ …

cs.CC2017★ 2 cited

Computing majority with low-fan-in majority queries

Gleb Posobin

In this paper we examine the problem of computing majority function $MAJ_{n}$ on $n$ bits by depth-two formula, where each gate is a majority function on at most $k$ inputs.…

cs.CC2017

Plain stopping time and conditional complexities revisited

Mikhail Andreev, Gleb Posobin, Alexander Shen

In this paper we analyze the notion of "stopping time complexity", informally defined as the amount of information needed to specify when to stop while reading an infinite sequence…