Обчислювальна складність поліноміальної факторизації

Посилання на оригінальну статтю: https://aimath.org/ARCC/workshops/polyfactor.html

 

15 травня — 19 травня 2006 року

у

Американському Інституті Математики, Пало-Альто, Каліфорнія

організатори

Шухонг Гао, Марк ван Хьой, Еріх Калтофен і Віктор Шуп

 

Цей семінар, спонсорований AIM і NSF , буде присвячений алгоритмам для факторингу поліномів. Будуть розглянуті одноваріантні та багатовимірні поліноми з коефіцієнтами з кінцевих полів, раціональними і комплексними числами. Будуть розглянуті щільні поліноми, де присутні всі коефіцієнти, а також розріджені поліноми, які мають багато нульових коефіцієнтів.

Проблема факторингових поліномів — це класична задача алгебри з класичними алгоритмами, наприклад, Ньютона, Пуйссе, Ейзенштейна, Гаусса, Кронекера, Гільберта і Хензеля, а також сучасні алгоритми, що використовують рандомізацію, редукційне підставу, техніки малих та величезних кроків, суми кореневої потужності та логарифмічних похідних, а також чисельне наближення. Сучасні алгоритми використовують ефективні структури даних, такі як прямолінійні програми та чорні коробки для оцінки. Мета семінару — винайти значно швидші нові алгоритми, або, у свою чергу, встановити твердість задачі факторизації.

Основними темами семінару є:

  • Найбільш відомі асимптотичні часи роботи алгоритмів факторизації однофакторних і багатоваріантних поліномів над кінцевими полями, раціональні і комплексні числа в щільному і розрідженому поданні.
  • Орієнтовна факторизація багатовимірних поліномів над комплексними числами, коефіцієнти яких можуть бути задані приблизно за рахунок помилок, викликаних фізичними вимірами, або обчислення з плаваючою точкою.
  • NP-жорсткість незвідності і кореневий пошук поліномів в розрідженому і прямолінійному поданні над кінцевими полями і раціональними числами.
  • Алгоритми обчислення групи Галуа одновимірних поліномів над раціональними числами.

Семінар буде відрізнятися від типових конференцій. Учасники будуть запрошені запропонувати відкриті проблеми та питання до початку семінару, і вони будуть розміщені на сайті семінару. До них відносяться конкретні проблеми, на які є надія на досягнення певного прогресу під час семінару, а також більш амбітні проблеми, які можуть вплинути на майбутню діяльність галузі. Лекції на семінарі будуть орієнтовані на ознайомлення учасників з довідковим матеріалом, що веде до конкретних проблем, а графік буде включати обговорення та робочі сесії.

Термін подачі заявки на підтримку для участі в цьому семінарі пройшов.

Більш детальну інформацію можна отримати, написавши листа на workshops@aimath.org.