All reports by Author Adi Akavia:

__
TR14-033
| 10th March 2014
__

Adi Akavia, Andrej Bogdanov, Siyao Guo, Akshay Kamath, Alon Rosen#### Candidate Weak Pseudorandom Functions in $\mathrm{AC}0 \circ \mathrm{MOD}2$

Revisions: 1

__
TR08-102
| 9th November 2008
__

Adi Akavia#### Finding Significant Fourier Transform Coefficients Deterministically and Locally

Adi Akavia, Andrej Bogdanov, Siyao Guo, Akshay Kamath, Alon Rosen

Pseudorandom functions (PRFs) play a fundamental role in symmetric-key cryptography. However, they are inherently complex and cannot be implemented in the class $\mathrm{AC}^0( \mathrm{MOD}_2)$. Weak pseudorandom functions (weak PRFs) do not suffer from this complexity limitation, yet they suffice for many cryptographic applications. We study the minimal complexity requirements for ... more >>>

Adi Akavia

Computing the Fourier transform is a basic building block used in numerous applications. For data intensive applications, even the $O(N\log N)$ running time of the Fast Fourier Transform (FFT) algorithm may be too slow, and {\em sub-linear} running time is necessary. Clearly, outputting the entire Fourier transform in sub-linear ... more >>>