Jin-Yi Cai

Augustus Anson Whitney Scholar
Computer Science
University of Wisconsin at Madison

The Theory of Holographic Algorithms

Photo by Tony Rinaldo

Jin-Yi Cai is a professor of computer science at the University of Wisconsin at Madison. His research area is computational complexity theory. It deals with foundational questions in computer science—what can or cannot be efficiently computed, and why.

Cai will investigate the theory of holographic algorithms. This theory uses a methodology based on perfect matchings, Pfaffians, and holographic representation in tensor spaces to give polynomial time algorithms to seemingly exponential time problems. The goal is to gain a substantially better understanding of the ultimate capabilities of these algorithms, especially in relation to the P-versus-NP question.

Cai has studied at Fudan University (1978–1981), Temple University (1981–1983), and Cornell University (1983–1986). His awards include National Science Foundation Presidential Young Investigator, Alfred P. Sloan, Association for Computing Machinery, and John Simon Guggenheim Memorial Foundation fellowships and the Humboldt Research Award.