Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Nir Ailon:

TR07-070 | 11th June 2007
Nir Ailon, Edo Liberty

Fast Dimension Reduction Using Rademacher Series on Dual BCH Codes

The Fast Johnson-Lindenstrauss Transform was recently discovered by
Ailon and Chazelle as a technique for performing fast dimension
reduction from $\ell_2^d$ to $\ell_2^k$ in time $O(\max\{d\log d,
k^3\})$, where $k$ is the target lower dimension. This beats the
naive $O(dk)$ achieved by multiplying by random dense matrices, as
noticed ... more >>>

TR04-068 | 13th August 2004
Nir Ailon, Bernard Chazelle

Information Theory in Property Testing and Monotonicity Testing in Higher Dimension

In general property testing, we are given oracle access to a function $f$, and we wish to randomly test if the function satisfies a given property $P$, or it is $\epsilon$-far from having that property. In a more general setting, the domain on which the function is defined is equipped ... more >>>

ISSN 1433-8092 | Imprint