Previous Conferences & Workshops

Polynomial Identity Testing is the following problem: given an arithmetic circuit C, determine if the polynomial computed by it is the identically zero polynomial. This problem admits a randomized polynomial-time algorithm but no efficient...

Let $M$ be an arbitrary $n$ by $n$ matrix. We study the condition number a random perturbation $M+N_n$ of $M$, where $N_n$ is a random matrix, motivated by a problem raised by Spielman and Teng. It is shown that, under very general conditions on $M$...