= Somenath Biswas
{c}
<Somenath Biswas> coauthored the 2003 paper on <primality testing> and <polynomial identity testing> with <Manindra Agrawal>. Their <randomized algorithm> reduces a candidate <integer>'s primality to a univariate <polynomial> identity over the <integers> modulo that candidate.<Primality and Identity Testing via Chinese Remaindering by Manindra Agrawal and Somenath Biswas>[abstract]{ref}
A <polynomial> can have very high <polynomial degree> while being represented by a small <arithmetic circuit>. Expanding every <polynomial coefficient> can then be impractical. The paper also gives <randomized algorithms> for multivariate <polynomial identity testing> with <running time> <polynomial> in the circuit representation size and an error parameter. The <input> representation and <probability> of error are consequently essential parts of the algorithmic statement.
Back to article page
