2 citations · 3 across the 4 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2024
Nearest Neighbor Complexity and Boolean Circuits
Mason DiCicco, Vladimir Podolskii, Daniel Reichman
A nearest neighbor representation of a Boolean function is a set of vectors (anchors) labeled by or such that if and only if the closest anchor to $\ve…
cs.CC2023
Towards Simpler Sorting Networks and Monotone Circuits for Majority
Natalia Dobrokhotova-Maikova, Alexander Kozachinskiy, Vladimir Podolskii
In this paper, we study the problem of computing the majority function by low-depth monotone circuits and a related problem of constructing low-depth sorting networks. We consider…