Abstrakt. Vi visar tiden lägre gränser för både online heltal multiplikation och convolution i cell-probe modellen med ordstorlek w. För multiplikationsproblem, ett par siffror, var och en från ett av två n siffror som ska multipliceras, ges som ingång i steg i. Online-algoritmen ger en enda ny siffra från produkten av siffrorna innan steg i + 1. Vi ger en lägre gräns för tid ( δ w log n) i genomsnitt per utmatningssiffra för detta problem där 2 δ är det maximala värdet av en siffra. I konvolutionsproblemet får vi en fast vektor V av längd n och vi anser att en ström i vilken antalet anländer en i taget. Vi producerar den inre produkten av V och vektorn som består av de sista n nummer av strömmen. Vi visar en lägre gräns för den tid som krävs per nytt nummer i strömmen. Alla de gränser som presenteras håller under randomisering och amortering. Multiplikation och konvolution är centrala problem i studier av algoritmer som också har det bredaste utbudet av praktiska tillämpningar.
Clifford och Jalsenius REF övervägde en streaming variant av multiplikation, där ett nummer är fast och den andra avslöjas en siffra i taget.
Lower Bounds for Online Integer Multiplication and Convolution in the Cell-Probe Model
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}