M.Sc Thesis

M.Sc StudentMagid Yonit
SubjectBSS Model of Computation over the Reals and Choice Operator
DepartmentDepartment of Computer Science
Supervisor PROFESSOR EMERITUS Johann Makowsky
Full Thesis textFull thesis text - English Version


B.C. Eaves and U.G. Rothblum studied the notion of linear algorithms and linear problems over the reals as an ordered field. They showed that by augmenting straight-line programs with random assignments from specified intervals one gets an exact correspondence between linear problems and algorithms. The class of the linear problems is huge, diverse, complex and important.

The class contains, for example, finding the rank of matrices, optimizing linear programming problems, optimizing bounded variable integer programs, solving linear complementary problems and determining satisfiability in sentential logic.

The notion of random assignments (i.e. arbitrarily picking a value to assign, no probability space involved) was introduced in order to achieve the complete solution set of a problem, which is useful in many cases.

The purpose of this research thesis is to place Eaves and Rothblum's result in a wider algorithmic context.

We extend this idea to algebraic problems and algorithms by introducing random assignments for roots of univariate polynomials. We also give an alternative proof of the Eaves-Rothblum characterization of the linear case. In both cases we give complexity estimates based on the complexity of cylindrical algebraic decomposition or, in the linear case, of the simplex algorithm. We also discuss the notion of choice operators as a more generalized form of random assignments.