Igor Shinkar

activity

20112022

most citedGreedy Random Walk

8 citations · 35 across the 17 of their papers we have counts for

collaborators

Showing 2016 · cs.DSShow all

2 papers · 2 filters

cs.DS2016

Sorting Networks On Restricted Topologies

Indranil Banerjee, Dana Richards, Igor Shinkar

The sorting number of a graph with $n$ vertices is the minimum depth of a sorting network with $n$ inputs and outputs that uses only the edges of the graph to perform comparisons.…

cs.DS2016★ 2 cited

An $O (n)$ Queries Adaptive Tester for Unateness

Subhash Khot, Igor Shinkar

We present an adaptive tester for the unateness property of Boolean functions. Given a function $f : {0, 1}^{n} \to {0, 1}$ the tester makes $O (n lo g (n) / ε)$ adaptive queries to the…

Sorting Networks On Restricted Topologies

An O(n) Queries Adaptive Tester for Unateness

An $O (n)$ Queries Adaptive Tester for Unateness