Since 2014
Lower Bounds for Dynamic Algebraic Problems
BRICS Report Series
View Archive Info| Field | Value | |
| Title |
Lower Bounds for Dynamic Algebraic Problems
|
|
| Creator |
Frandsen, Gudmund Skovbjerg
Hansen, Johan P. Miltersen, Peter Bro |
|
| Description |
We consider dynamic evaluation of algebraic functions (matrix multiplication, determinant, convolution, Fourier transform, etc.) in the model of Reif and Tate; i.e., if f(x1, . . . , xn) = (y1, . . . , ym) is an algebraic problem, we consider serving on-line requests of the form "change input xi to value v" or "what is the value of output yi?". We present techniques for showing lower bounds on the worst case time complexity per operation for such problems. The first gives lower bounds in a wide range of rather powerful models (for instance history dependentalgebraic computation trees over any infinite subset of a field, the integer RAM, and the generalized real RAM model of Ben-Amram and Galil). Using this technique, we show optimal Omega(n) bounds for dynamic matrix-vector product, dynamic matrix multiplication and dynamic discriminant and an Omega(sqrt(n)) lower bound for dynamic polynomial multiplication (convolution), providing a good match with Reif andTate's O(sqrt(n log n)) upper bound. We also show linear lower bounds for dynamic determinant, matrix adjoint and matrix inverse and an Omega(sqrt(n)) lower bound for the elementary symmetric functions. The second technique is the communication complexity technique of Miltersen, Nisan, Safra, and Wigderson which we apply to the settingof dynamic algebraic problems, obtaining similar lower bounds in the word RAM model. The third technique gives lower bounds in the weaker straight line program model. Using this technique, we show an ((log n)2= log log n) lower bound for dynamic discrete Fourier transform. Technical ingredients of our techniques are the incompressibility technique of Ben-Amram and Galil and the lower bound for depth-two superconcentrators of Radhakrishnan and Ta-Shma. The incompressibility technique is extended to arithmetic computation in arbitrary fields.
|
|
| Publisher |
Aarhus University
|
|
| Contributor |
—
|
|
| Date |
1998-01-11
|
|
| Type |
info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion — |
|
| Format |
application/pdf
|
|
| Identifier |
https://tidsskrift.dk/brics/article/view/19283
10.7146/brics.v5i11.19283 |
|
| Source |
BRICS Report Series; No 11 (1998): RS-11 Lower Bounds for Dynamic Algebraic Problems
BRICS Report Series; No 11 (1998): RS-11 Lower Bounds for Dynamic Algebraic Problems 1601-5355 0909-0878 |
|
| Language |
eng
|
|
| Relation |
https://tidsskrift.dk/brics/article/view/19283/16910
|
|
| Rights |
Copyright (c) 2014 BRICS Report Series
|
|