В. Николаенко (Академический университет)

Нижние оценки на схемную сложность

Доклад будет посвящен нижним оценкам на схемную сложность. Будет
рассказан результат 2010 года (J. Kinne, D. van Melkebeek, R.
Shaltiel), который является улучшением и упрощением результата 2004
года (V. Kabanets, R. Impagliazzo). В первой части доклада будет
показана нижняя оценка на схемы в предположении существования
алгоритма для распознавания ACZ (язык арифметических схем, вычисляющих
нулевые многочлены) с ограниченной ошибкой. Во второй части доклада
будет показана параметризация результата Kabanets и Impagliazzo.