2 citations · 2 across the 1 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
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 on bits by depth-two formula, where each gate is a majority function on at most 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…