Пятница 19.10. Александр Куликов (ПОМИ РАН): "Сложность линейных операторов"

[PDMI seminars]

Семинар по дискретной математике

Тема: Сложность линейных операторов
Место: ауд. 106
Время: 19.10.2018, 14:00
Докладчик: Александр Куликов (ПОМИ РАН)

Abstract:
Пусть A — булева матрица размера n на n, в которой O(n) нулей, и мы хотим вычислить Ax, где x — вектор переменных размерности n над некоторой полугруппой. Сколько полугрупповых операций для этого требуется? Мы покажем, что для коммутативных полугрупп можно построить схемы линейного размера для вычисления Ax. После этого мы покажем, что для некоммутативного случая схем линейного размера не существует.

Доклад по совместной статье с А. Моховым, И. Михайлиным и В. Подольским.