On a Polytime Factorization Algorithm for Multilinear Polynomials over F2

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

2 Цитирования (Scopus)

Аннотация

In 2010, Shpilka and Volkovich established a prominent result on the equivalence of polynomial factorization and identity testing. It follows from their result that a multilinear polynomial over the finite field of order 2 can be factored in time cubic in the size of the polynomial given as a string. Later, we have rediscovered this result and provided a simple factorization algorithm based on computations over derivatives of multilinear polynomials. The algorithm has been applied to solve problems of compact representation of various combinatorial structures, including Boolean functions and relational data tables. In this paper, we describe an improvement of this factorization algorithm and report on preliminary experimental analysis.

Язык оригиналаанглийский
Название основной публикацииComputer Algebra in Scientific Computing - 20th International Workshop, CASC 2018, Proceedings
РедакторыVP Gerdt, W Koepf, WM Seiler, EV Vorozhtsov
ИздательSpringer-Verlag GmbH and Co. KG
Страницы164-176
Число страниц13
ISBN (печатное издание)9783319996387
DOI
СостояниеОпубликовано - 1 янв 2018
Событие20th International Workshop on Computer Algebra in Scientific Computing, CASC 2018 - Lille, Франция
Продолжительность: 17 сен 201821 сен 2018

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том11077 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

Конференция

Конференция20th International Workshop on Computer Algebra in Scientific Computing, CASC 2018
СтранаФранция
ГородLille
Период17.09.201821.09.2018

Fingerprint Подробные сведения о темах исследования «On a Polytime Factorization Algorithm for Multilinear Polynomials over F<sub>2</sub>». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать