🚀 go-pugleaf

	UofT Department of Computer Science Seminar Schedule for
		   the week of October 10th, 1983

Thursday, October 13th, 2:00 P.M., GB248:  Professor Susan Landau,
   Department of Mathematics, Wesleyan University, Middleton, Conn.,
   "Solvability by radicals is in polynomial time".

   ABSTRACT:  Determining if a polynomial has roots expressible in
   radicals is a question whose history goes back to the Babylonians.
   Galois provided a constructive (through exponential time) criterion
   for determining which polynomials have roots expressible in radicals.
   We provide a polynomial time algorithm to answer the question.
   (This talk represents joint work with Gary Miller.)

Thursday, October 13th, 3:00 P.M., GB248:  Margaret Solowiej, Department
   of Computer Science, University of Toronto, "N-dimensional Newton
   method with precision control for determining roots of complex 
   polynomials".

   ABSTRACT:  Difficulties with deflation, stopping criteria and limited
   precision in conventional root-finding algorithms lead to their
   failure to return roots to within a prescribed accuracy.  An algorithm
   is presented which uses the n-dimensional Newton method with dynamic
   precision control for determining all the roots of a complex polynomial
   simultaneously, to within a user-specified tolerance.  Control of
   precision is accomplished by using a running error analysis to
   monitor the errors in the approximation updates at each iterative step.

Friday, October 14th, 11:10 A.M., GB220:  Professor Neil Immerman,
   Departments of Math and Computer Science, Yale University, New Haven,
   Conn., "Languages which capture complexity classes".

   ABSTRACT:  We present a series of languages adequate for expressing
   exactly those properties checkable in a series of computational
   complexity classes.  For example, we show that a graph property is
   in polynomial time if and only if it is expressible in the language
   of first order graph theory together with a least fixed point operator.
   As another example, a group theoretic property is in the logspace
   hierarchy if and only if it is expressible in the language of first
   order group theory together with a transitive closure operator.
   Thus questions of complexity can be translated to expressibility issues.
   Separating complexity classes is equivalent to showing that certain
   of the above operators are more powerful than others.  Efficient
   algorithms may be obtained simply by describing a problem in one of
   our languages.
-- 
		Phyllis Eve Bregman
		CSRG, Univ. of Toronto
		{decvax,linus,ihnp4,uw-beaver,floyd,utzoo}!utcsrgv!phyllis