Igor Shinkar

activity

20112022

most citedGreedy Random Walk

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

collaborators

Showing 2015Show all

3 papers · 1 filter

cs.CC2015★ 1 cited

On Percolation and $N P$ -Hardness

Daniel Reichman, Igor Shinkar

We consider the robustness of computational hardness of problems whose input is obtained by applying independent random deletions to worst-case instances. For some classical $N P$ -h…

math.PR2015

A Counterexample to Monotonicity of Relative Mass in Random Walks

Oded Regev, Igor Shinkar

For a finite undirected graph $G = (V, E)$ , let $p_{u, v} (t)$ denote the probability that a continuous-time random walk starting at vertex $u$ is in $v$ at time $t$ . In this note we…

cs.DM2015

On Lipschitz Bijections between Boolean Functions

Shravas Rao, Igor Shinkar

For two functions $f, g : {0, 1}^{n} \to {0, 1}$ a mapping $ψ : {0, 1}^{n} \to {0, 1}^{n}$ is said to be a $\textit{mapping from $f $t o$ g$}$ if it is a bijection and $f (z) = g (ψ (z))$ for every…

On Percolation and NP-Hardness

A Counterexample to Monotonicity of Relative Mass in Random Walks

On Lipschitz Bijections between Boolean Functions

On Percolation and $N P$ -Hardness