Цзинь-И Цай ( китайский :蔡进一; родился в 1961 году) — китайско-американский математик и компьютерный учёный . Он является профессором компьютерных наук, а также профессором математических наук Стенбока [1] в Университете Висконсин-Мэдисон . Его исследования находятся в области теоретической компьютерной науки , особенно теории вычислительной сложности . В последние годы он сосредоточился на классификации вычислительных задач подсчёта , особенно подсчёта гомоморфизмов графов , задач удовлетворения ограничений подсчёта и проблем Холанта, связанных с голографическими алгоритмами .
Цай родился в Шанхае, Китай . Он изучал математику в университете Фудань , который окончил в 1981 году. Он получил степень магистра в университете Темпл в 1983 году, вторую степень магистра в Корнеллском университете в 1985 году [2] и степень доктора философии в Корнеллском университете в 1986 году, с Юрисом Хартманисом в качестве его научного руководителя . [3]
Он стал преподавателем в Йельском университете (1986-1989), Принстонском университете (1989-1993) и Университете штата Нью-Йорк в Буффало (1993-2000), поднявшись с должности доцента до должности полного профессора в 1996 году. В 2000 году он стал профессором компьютерных наук в Университете Висконсин-Мэдисон. [2]
Цай был молодым исследователем , научным сотрудником Sloan [ 4] и стипендиатом Guggenheim [5] . Он получил серебряную медаль Morningside и исследовательскую премию Humboldt для старших ученых США [2 ]. В 2021 году он был совместно награжден премией Гёделя в области теоретической информатики за работу над статьей под названием « Сложность подсчета CSP с комплексными весами». [6] Он также был награжден премией Фулкерсона по дискретной математике, присуждаемой Американским математическим обществом и Обществом математического программирования [7] .
Он был избран членом Ассоциации вычислительной техники (2001), Американской ассоциации содействия развитию науки (2007) и иностранным членом Academia Europaea (2017). [2] Он был включен в число членов Американского математического общества 2023 года «за вклад в теорию сложности вычислений, особенно в области дихотомии сложности». [8]