Тонианн Питасси
Тонианн Питасси | |
|---|---|
 Питасси на МФО семинаре Proof Complexity and Beyond , 2017 | |
| Национальность |
|
| Образование | |
| Супруг | Richard Zemel |
| Научная карьера | |
| Поля | Математика, информатика |
| Учреждения |
|
| Докторантура | Стивен Кук |
Тонианн Питасси — канадско-американский математик и ученый-компьютерщик, специализирующийся на теории сложности вычислений . В настоящее время она является профессором инженерных наук Джеффри Л. и Бренды Блюстейн в Колумбийском университете и возглавляла исследовательский центр Bell в Университете Торонто . [1] [2]
Академическая карьера [ править ]
Уроженка Питтсбурга , Питасси получила степени бакалавра и магистра в Университете штата Пенсильвания , а затем переехала в Университет Торонто для учебы в докторантуре; она получила докторскую степень в 1992 году в Торонто под руководством Стивена Кука . После постдокторантуры в Калифорнийском университете в Сан-Диего и преподавательских должностей в Университетах Питтсбурга и Университета Аризоны она вернулась в Торонто в 2001 году и стала профессором кафедры компьютерных наук Университета Торонто и кафедры компьютерных наук Университета Торонто. Математики до 2021 года, когда она поступила на факультет Колумбийского университета . [3] [4]
Она была приглашенным докладчиком на Международном конгрессе математиков в Берлине в 1998 году. [5] [6] Она была программным руководителем Симпозиума по теории вычислений 2012 года . [7] С сентября по декабрь 2017 года она была приглашенным профессором в Институте перспективных исследований . [8]
Исследования [ править ]
Исследования Питасси в основном сосредоточены на сложности доказательства — разделе теории сложности вычислений , который ищет верхние и нижние границы длины математических доказательств логических утверждений в различных формализованных системах доказательств. Целью данного исследования является использование этих границ для понимания как временной сложности процедур поиска доказательств, так и относительной силы различных систем доказательства.
Вклады исследований, которые она внесла в эту область, включают экспоненциальные нижние границы для доказательств Фреге принципа « ячейки» ; [9] экспоненциальные нижние оценки метода секущей плоскости, применяемого к утверждениям, полученным из задачи максимальной клики , [10] экспоненциальные нижние оценки для доказательств разрешения плотных случайных случаев 3-выполнимости , [11] и субэкспоненциальные верхние границы для тех же самых плотных случайных случаев с использованием алгоритма Дэвиса-Патнэма . [12] Вместе с Полом Бимом она также написала обзор сложности доказательств. [13]
Признание [ править ]
Питасси был избран научным сотрудником ACM в 2018 году за «вклад в исследования и образование в области сложности вычислений и доказательств». [14]
Питасси также была лауреатом премии EATCS (Европейской ассоциации теоретической информатики) в 2021 году за «фундаментальный и широкомасштабный вклад в повышение сложности вычислений». [15]
В 2022 году она была включена в состав Национальной академии наук . [2] [16]
Избранные публикации [ править ]
- Питасси, Тонианн; Бим, Пол; Импальяццо, Рассел (1993), «Экспоненциальные нижние границы принципа группировки», Computational Complexity , 3 (2): 97–140, doi : 10.1007/BF01200117 , MR 1233662 , S2CID 1046674 .
- Бим, Пол; Питасси, Тонианн (1996), «Нижние границы упрощенного и улучшенного разрешения», Труды 37-го ежегодного симпозиума по основам информатики , стр. 274–282, doi : 10.1109/SFCS.1996.548486 , MR 1450625 , S2CID 14341656 .
- Боне, Мария ; Питасси, Тонианн; Раз, Ран (1997), «Нижние оценки доказательств секущих плоскостей с малыми коэффициентами», Journal of Символическая логика , 62 (3): 708–728, doi : 10.2307/2275569 , JSTOR 2275569 , MR 1472120 .
- Бим, Пол; Питасси, Тонианн (1998), «Сложность доказательства утверждений: прошлое, настоящее и будущее», Бюллетень Европейской ассоциации теоретической информатики (65): 66–89, MR 1650939 . Перепечатано в журнале «Текущие тенденции в теоретической информатике» , World Scientific, 2001, MR. 1886033 .
- Бим, Пол; Карп, Ричард ; Питасси, Тонианн; Сакс, Майкл (1998), «О сложности доказательства невыполнимости случайных формул k-CNF», Труды 30-го симпозиума ACM по теории вычислений , стр. 561–571, CiteSeerX 10.1.1.39.213 , doi : 10.1145/ 276698.276870 , МР 1715604 , S2CID 10262912 .
- Бим, Пол; Карп, Ричард ; Питасси, Тонианн; Сакс, Майкл (2002), «Эффективность разрешения и процедуры Дэвиса-Патнэма», SIAM Journal on Computing , 31 (4): 1048–1075, doi : 10.1137/S0097539700369156 , MR 1919956 .
- Дворк, Синтия; Наор, Мони; Питасси, Тонианн; Ротблюм, Гай Н. (2010). «Дифференциальная конфиденциальность под постоянным наблюдением». Труды сорок второго симпозиума ACM по теории вычислений . стр. 715–724. дои : 10.1145/1806689.1806787 . ISBN 9781450300506 . S2CID 1522154 .
- Дворк, Синтия; Хардт, Мориц; Питасси, Тонианн; Рейнгольд, Омер; Земель, Ричард (2012). «Справедливость через осознанность». Материалы 3-й конференции «Инновации в теоретической информатике» . ИТКС '12. Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 214–226. arXiv : 1104.3913 . дои : 10.1145/2090236.2090255 . ISBN 9781450311151 . S2CID 13496699 .
- Дворк, Синтия; Фельдман, Виталий; Хардт, Мориц; Питасси, Тонианн; Рейнгольд, Омер; Рот, Аарон (7 августа 2015 г.). «Многоразовое использование: сохранение достоверности в адаптивном анализе данных» . Наука . 349 (6248): 636–638. Бибкод : 2015Sci...349..636D . дои : 10.1126/science.aaa9375 . ISSN 0036-8075 . ПМИД 26250683 .
Ссылки [ править ]
- ^ "Тонианн Питасси | Факультет компьютерных наук Колумбийского университета" . www.cs.columbia.edu . Проверено 4 мая 2022 г.
- ↑ Перейти обратно: Перейти обратно: а б «Четыре колумбийца избраны в Национальную академию наук» . Новости Колумбии . Проверено 4 мая 2022 г.
- ^ «Тонианн Питасси» . Университет Торонто . Проверено 31 декабря 2017 г.
- ^ Тонианн Питасси в проекте «Математическая генеалогия»
- ^ «Пленарное заседание ICM и приглашенные докладчики» . Международный математический союз . Проверено 31 декабря 2017 г.
- ^ Питасси, Тонианн (1998). «Неразрешимые системы уравнений и сложность доказательства» . Док. Математика. (Билефельд) Extra Vol. ICM Берлин, 1998, вып. III . стр. 451–458.
- ^ «STOC 2012 — 44-й симпозиум ACM по теории вычислений» . Нью-Йоркский университет , факультет компьютерных наук . Проверено 31 декабря 2017 г.
- ^ «Тонианн Питасси» . Институт перспективных исследований . Проверено 31 декабря 2017 г.
- ^ Питасси, Бим и Импаглиаццо (1993) .
- ^ Bonet, Pitassi & Raz (1997) .
- ^ Бим и Питасси (1996) ; Бим и др. (2002) .
- ^ Бим и др. (1998) ; Бим и др. (2002) .
- ^ Бим и Питасси (1998) .
- ^ Стипендиаты ACM 2018 удостоены награды за важнейшие достижения, лежащие в основе цифровой эпохи , Ассоциация вычислительной техники , 5 декабря 2018 г.
- ^ Премия EATCS 2021 — Laudatio для Тонианна (Тони) Питасси , Европейская ассоциация теоретической информатики, 4 июня 2021 г.
- ^ «Выборы НАН 2022» . nasonline.org . Проверено 4 мая 2022 г.
- Живые люди
- Канадские женщины-математики
- Канадские женщины-компьютерщики
- Канадские ученые-компьютерщики
- Выпускники Университета Торонто
- Преподаватели Пенсильванского государственного университета
- факультет Питтсбургского университета
- факультет Университета Аризоны
- Академический состав Университета Торонто
- Теоретики-компьютерщики
- Члены Ассоциации вычислительной техники 2018 г.
- факультет Колумбийского университета