Valentine Kabanets is a computer scientist whose research concerns computational complexity theory, derandomization, pseudorandomness and circuit complexity. A recurring question in his research is when efficient randomized algorithms can be replaced by efficient deterministic algorithms.[ref]
Research interests by Valentine Kabanets. Computational Complexity; Role of randomness in efficient computation
His research description emphasizes a connection between designing fast algorithms and proving circuit lower bounds. An upper bound supplies an efficient method for a problem; a lower bound rules out methods within a specified model. In some settings, progress on one side can imply progress on the other, turning apparent obstacles into tools.[ref]
Identity source: www2.cs.sfu.ca/~kabanets/
Portrait of Valentine Kabanets
. Portrait identified on the cited institutional profile. New to topics? Read the docs here!