Why is no one talking about the new fast polynomial composition algorithm? - Codeforces

→ Pay attention

Before contest
Codeforces Round (Div. 2)
6 days

→ Top rated

#	User	Rating
1	jiangly	3977
2	tourist	3815
3	jqdai0815	3682
4	ksun48	3614
5	orzdevinwang	3526
6	ecnerwala	3514
7	Benq	3483
8	hos.lyric	3381
9	gamegame	3374
10	heuristica	3358

Countries | Cities | Organizations

→ Top contributors

#	User	Contrib.
1	cry	170
2	-is-this-fft-	162
2	Um_nik	162
4	atcoder_official	160
5	djm03178	157
6	Dominater069	156
7	adamant	154
8	luogu_official	152
8	awoo	152
10	TheScrasse	147

View all →

→ Find user

→ Recent actions

Detailed →

Why is no one talking about the new fast polynomial composition algorithm?

Revision en1, by Kapt, 2024-04-08 17:01:02

So, about three weeks ago a fast ($$$\mathcal{O}(n\log^2(n))$$$) algorithm has been discovered by noshi91, here is the original blog.

Tags

advanced math

History

Revisions

	Rev.	Lang.	By	When	Δ	Comment
	en10		Kapt	2024-04-25 21:03:50	213
	en9		Kapt	2024-04-09 17:33:03	118
	en8		Kapt	2024-04-08 19:44:43	2	Tiny change: 'es a somewaht differen' -> 'es a somewhat differen'
	en7		Kapt	2024-04-08 19:41:56	214
	en6		Kapt	2024-04-08 18:45:33	34
	en5		Kapt	2024-04-08 18:44:36	0	(published)
	en4		Kapt	2024-04-08 18:39:47	164	Tiny change: 'log^2(n))$, so by [T' -> 'log^2(n))$ with Bostan-Mori algorithm, so by [T'
	en3		Kapt	2024-04-08 18:30:49	150	Tiny change: 'ginal blog. Previous' -> 'ginal blog (in Japanese). Previous'
	en2		Kapt	2024-04-08 18:16:45	3668	Tiny change: '(V)=deg(Q) and deg(U_i) \' -> '(V)=deg(Q)$ and $deg(U_i) \'
	en1		Kapt	2024-04-08 17:01:02	280	Initial revision (saved to drafts)