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

→ Pay attention

Before contest
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
27:45:23
Register now »

*has extra registration

→ Top rated

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Countries | Cities | Organizations

→ Top contributors

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

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)