Theoretical Aspects of VLSI (Very Large Scale Integration) Circuit Design.

During the period covered by the grant, two books and ten research papers were written under grant sponsorship. In addition nineteen of the research papers were written and published in conference proceeding. Ten other research manuscripts are now nearing completion. Titles of some of the completed work include EIGNENVALUES AND EXPANDERS, A FRAMEWORK OF SOLVING VLSI GRAPH LAYOUT PROBLEMS, TIGHT BOUNDS ON THE COMPLEXITY OF PARALLEL SORTING, WAFER-SCALE INTERGRATION OF SYSTOLIC ARRAYS, and THE AVERAGE CASE ANALYSIS OF SOME ON-LINE ALGORITHMS FOR BIN PACKING.