- Giovedì 12 Marzo 2020, ore 14:15, Aula XI
Giuseppe Melfi (Université de Neuchâtel)
Su alcuni problemi di Erdös
Abstract. Tba
- Mercoledì 13 Marzo 2019, ore 15.00, Aula VI
Alessandra Bernardi (Università degli studi di Trento)
Multiplication
Abstract. The use of "multiplication tables" arrives in Italy with Fibonacci in the schools of Abaco and resists Sputnik (USSR 1957) but not at the US landing on the Moon (1969): first the Karatsuba algorithm (1960) then the discovery of Cooley and Tukey of the Fast Fourier Transform (1965) completely change the history of global computer programming. The complexity of these algorithms goes from O(n^2), O (n log (3) / log (2)) to O (n log (n)) and can be measured with the rank of the associated tensors. The same type of measurement shows that the Strasser algorithm (1969) to multiply two 2x2 matrices with 7 multiplications instead of 8 is the most efficient method to multiply 2x2 matrices. What is the effective complexity of multiplying matrices nxn is still an open problem.
Its applications go beyond the multiplication of numbers and are present for example in the reproduction of each audio file or in the reconstruction of images ...
Google has announced that it is aiming for quantum supremacy and intends to do so before the 2027 year predicted by NASA for the first quantum computer with a considerable number of q-bits. If this happens the cybersecurity will have to completely change structure. The quantum version of the FFT could be the basis of this possible revolution.
