Periodic Reporting for period 4 - SpeedInfTradeoff (Speed-Information Tradeoffs: Beyond Quasi-Entropy Analysis)

The main problems being addressed by the project is to obtain lower bounds for computation of the Fourier Transform, using a reasonably solid model of computation. It is widely conjectured that the n log(n) running time of the FFT (Fast Fourier Transform) algorithm is...