Research is in progress that follows two paradigms for parallel computation: A reduction paradigm and a divide and conquer paradigm. The reduction paradigm proceeds as follows: given a problem instance of size n it employs a reducing procedure to produce a problem instance of size less than or equal to n/2, such that the solution to the original problem can be easily deduced from the solution to the reduced problem. Work on the reduction paradigm continues a previously successful avenue of research carried out by the PI. Work on the divide and conquer paradigm holds similar promise. Work done under each of these paradigms proceeds by obtaining exact solutions from approximate solutions. The PI is very knowledgeable and is an accomplished researcher in the area proposed. The work proposed is very significant for the future of parallel computation and has potential for substantial impact.
