ProbXiv
Explorersign in
Problem archiveProblem record

Statement

  1. Upper bounds Let M (n) denote the cost of multiplying n-bit integers. By “cost” we mean the number of steps performed by a multitape Turing machine [Pap94]. Theorem 1 ([HvdH21]). M (n) = O(n log n). Suprisingly, the “function field case” appears to be more difficult. For a prime p, let Mp (d) denote the cost (still in the Turing model) of multiplying polynomials in Fp [x] of degree d. Then we have the following folklore conjecture. In this talk I gave an overview of what is known about upper and lower bounds for the complexity of integer multiplication and some related problems.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.