We say that a polynomial $f(x_1,\ldots,x_n)$ is {\em indecomposable} if it cannot be written as a product of two polynomials that are defined over disjoint sets of variables. The {\em polynomial decomposition} problem is defined to be the task of finding the indecomposable factors of a given polynomial. Note that ... more >>>

We give new pseudorandom generators for \emph{regular} read-once branching programs of small width.
A branching program is regular if the in-degree of every vertex in it is (0 or) $2$.
For every width $d$ and length $n$,
our pseudorandom generator uses a seed of length $O((\log d + \log\log n ... more >>>

Three fundamental results of Levin involve algorithms or reductions
whose running time is exponential in the length of certain programs. We study the
question of whether such dependency can be made polynomial.

(1) Levin's ``optimal search algorithm'' performs at most a constant factor more slowly
than any other fixed ... more >>>