CISC 876 Computational Complexity (T)
A systematic studyof the known relations between the most important resource bounded complexity classes. Reductions, separation results and translation techniques. Relativized computation. Topics may include also: Circuit complexity, Kolmogorov-Chaitin complexity, Communication complexity. Three term-hours; lectures and seminars. Kai Salomaa.
The School of Computing graduate facilities consist of network of Macs, PCs, SGI and Sun workstations with the main infrastructure supported by Sun servers. The School's network of 100 computers support the research laboratories in the fields of study described below. The laboratories contain specialized equipment such as audio and video equipment, robotic equipment, eye tracking equipment, ultra sound machine and tracking systems for surgical tools. Undergraduate teaching facilities include four laboratories with 175 PCs supporting a Win XP and Linux environment, 24 Sun workstations and Sun servers for the main infrastructure. There is a Human Media laboratory consisting of five Macs with tablets and digital video cameras.
The actual courses offered each term will be determined by student demand and the availability of faculty. All courses are half courses (3.0 credit units). In addition to the courses listed below, descriptions of other courses offered by the School are given in the undergraduate calendars. Graduate students in the School may include in their program relevant courses from other departments such as Electrical and Computer Engineering, Psychology, Mathematics, or the School of Business.