Standard

On a Polytime Factorization Algorithm for Multilinear Polynomials over F2. / Emelyanov, Pavel; Ponomaryov, Denis.

Computer Algebra in Scientific Computing - 20th International Workshop, CASC 2018, Proceedings. ed. / VP Gerdt; W Koepf; WM Seiler; EV Vorozhtsov. Springer-Verlag GmbH and Co. KG, 2018. p. 164-176 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11077 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Emelyanov, P & Ponomaryov, D 2018, On a Polytime Factorization Algorithm for Multilinear Polynomials over F2. in VP Gerdt, W Koepf, WM Seiler & EV Vorozhtsov (eds), Computer Algebra in Scientific Computing - 20th International Workshop, CASC 2018, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11077 LNCS, Springer-Verlag GmbH and Co. KG, pp. 164-176, 20th International Workshop on Computer Algebra in Scientific Computing, CASC 2018, Lille, France, 17.09.2018. https://doi.org/10.1007/978-3-319-99639-4_11

APA

Emelyanov, P., & Ponomaryov, D. (2018). On a Polytime Factorization Algorithm for Multilinear Polynomials over F2. In VP. Gerdt, W. Koepf, WM. Seiler, & EV. Vorozhtsov (Eds.), Computer Algebra in Scientific Computing - 20th International Workshop, CASC 2018, Proceedings (pp. 164-176). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11077 LNCS). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-319-99639-4_11

Vancouver

Emelyanov P, Ponomaryov D. On a Polytime Factorization Algorithm for Multilinear Polynomials over F2. In Gerdt VP, Koepf W, Seiler WM, Vorozhtsov EV, editors, Computer Algebra in Scientific Computing - 20th International Workshop, CASC 2018, Proceedings. Springer-Verlag GmbH and Co. KG. 2018. p. 164-176. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-99639-4_11

Author

Emelyanov, Pavel ; Ponomaryov, Denis. / On a Polytime Factorization Algorithm for Multilinear Polynomials over F2. Computer Algebra in Scientific Computing - 20th International Workshop, CASC 2018, Proceedings. editor / VP Gerdt ; W Koepf ; WM Seiler ; EV Vorozhtsov. Springer-Verlag GmbH and Co. KG, 2018. pp. 164-176 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{17ab6269443f4b689620c7ca176a349e,
title = "On a Polytime Factorization Algorithm for Multilinear Polynomials over F2",
abstract = "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.",
author = "Pavel Emelyanov and Denis Ponomaryov",
note = "Publisher Copyright: {\textcopyright} 2018, Springer Nature Switzerland AG.; 20th International Workshop on Computer Algebra in Scientific Computing, CASC 2018 ; Conference date: 17-09-2018 Through 21-09-2018",
year = "2018",
month = jan,
day = "1",
doi = "10.1007/978-3-319-99639-4_11",
language = "English",
isbn = "9783319996387",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag GmbH and Co. KG",
pages = "164--176",
editor = "VP Gerdt and W Koepf and WM Seiler and EV Vorozhtsov",
booktitle = "Computer Algebra in Scientific Computing - 20th International Workshop, CASC 2018, Proceedings",
address = "Germany",

}

RIS

TY - GEN

T1 - On a Polytime Factorization Algorithm for Multilinear Polynomials over F2

AU - Emelyanov, Pavel

AU - Ponomaryov, Denis

N1 - Publisher Copyright: © 2018, Springer Nature Switzerland AG.

PY - 2018/1/1

Y1 - 2018/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85053994940&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-99639-4_11

DO - 10.1007/978-3-319-99639-4_11

M3 - Conference contribution

AN - SCOPUS:85053994940

SN - 9783319996387

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 164

EP - 176

BT - Computer Algebra in Scientific Computing - 20th International Workshop, CASC 2018, Proceedings

A2 - Gerdt, VP

A2 - Koepf, W

A2 - Seiler, WM

A2 - Vorozhtsov, EV

PB - Springer-Verlag GmbH and Co. KG

T2 - 20th International Workshop on Computer Algebra in Scientific Computing, CASC 2018

Y2 - 17 September 2018 through 21 September 2018

ER -

ID: 16758176