Влияние программы Гротендика на TCS

Гротендик скончался . Он оказал огромное влияние на математику 20-го века, продолжая в 21-м веке. Этот вопрос задается в некотором стиле / духе, например, «Вкладов Алана Тьюринга в информатику» .

Каковы основные влияния Гротендика на теоретическую информатику?

Неравенство Гротендика , начиная с его дней в функциональном анализе, было первоначально доказано, чтобы связать фундаментальные нормы на пространствах тензорных произведений. Гротендик назвал неравенство «фундаментальной теоремой метрической теории тензорных пространств произведений» и опубликовал ее в известной ныне статье в 1958 году на французском языке в ограниченном тираже бразильского журнала. Документ в основном игнорировался в течение 15 лет, пока он не был вновь открыт Линденштрауссом и Пельчинским (после того, как Гротендик оставил функциональный анализ). Они дали много переформулировок основных результатов работы, связали их с исследованиями абсолютно суммирующих операторов и норм факторизации и отметили, что Гротендик решил «открытые» проблемы, возникшие послестатья была опубликована. Пизье в своем обзоре очень подробно описывает неравенство, его варианты и его огромное влияние на функциональный анализ .

Неравенство Гротендика очень естественно выражается на языке комбинаторных алгоритмов оптимизации и аппроксимации. Это говорит о том, что невыпуклая, NP-трудная оптимизационная задача аппроксимируется с точностью до фиксированной постоянной своей полуопределенной релаксации макс { Σ я , J v J ⟩ : U 1

$$\max\{x^TAy: x \in \{-1, 1\}^m, y \in \{-1, 1\}^n\}$$ где S n + m - $$\max\{\sum_{i,j}{a_{ij}\langle u_i, v_j\rangle}: u_1, \ldots, u_m, v_1, \ldots, v_n \in \mathbb{S}^{n+m-1}\},$$ $\mathbb{S}^{n+m-1}$ единичный шар в $\mathbb{R}^{n+m}$, Доказательства неравенства дают «алгоритмы округления», а фактически случайное гиперплоскость Геманса-Уильямсона выполняет свою работу (но дает субоптимальную константу). Однако неравенство Гротендика интересно, потому что анализ алгоритма округления должен быть «глобальным», то есть рассматривать все члены целевой функции вместе.

Сказав это, не должно быть удивительно, что неравенство Гротендикса нашло вторую (третью? Четвертую) жизнь в информатике. Хот и Naor обозреть свои многочисленные приложения и подключения к комбинаторной оптимизации.

На этом история не заканчивается. Неравенство связано с нарушениями неравенства Белла в квантовой механике (см. Статью Пизье), использовалось Линиалом и Шрайбманом в работе над сложностью коммуникации и даже оказалось полезным в работе по анализу частных данных (бесстыдная пробка).

$X$$X\subseteq \{ \text{simple},$ $\text{dependent},$ $\text{polymorphic},$ $\text{higher-order}\}$ , также благодаря Гротендику, играет важную роль в предоставлении категориальной семантики логикам и теориям типов, что представляет интерес как для логиков, так и для теоретических компьютерных ученых.

$p$ -адических когомологий, этальных когомологий в формулах подсчета точек для алгебраических многообразий имеет корни в его работе.

Я предполагаю, что видение Малмулей обобщения гипотезы Римана над конечными полями, исходящими из гипотез Вейля, можно рассматривать как вопрос о том, что изначально имело плодотворные результаты из этальных когомологий Гротендика.