Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > VISHNU IYER:
All reports by Author Vishnu Iyer:

TR25-144 | 7th October 2025
Siddhartha Jain, Vishnu Iyer, Rolando Somma, Ning Bao, Stephen Jordan

Efficient Quantum Hermite Transform

We present a new primitive for quantum algorithms that implements a discrete Hermite transform efficiently, in time that depends logarithmically in both the dimension and the inverse of the allowable error. This transform, which maps basis states to states whose amplitudes are proportional to the Hermite functions, can be interpreted ... more >>>


TR23-154 | 12th October 2023
Vishnu Iyer, Siddhartha Jain, Matt Kovacs-Deak, Vinayak Kumar, Luke Schaeffer, Daochen Wang, Michael Whitmeyer

On the Rational Degree of Boolean Functions and Applications

We study a natural complexity measure of Boolean functions known as the (exact) rational degree. For total functions $f$, it is conjectured that $\mathrm{rdeg}(f)$ is polynomially related to $\mathrm{deg}(f)$, where $\mathrm{deg}(f)$ is the Fourier degree. Towards this conjecture, we show that symmetric functions have rational degree at least $\mathrm{deg}(f)/2$ and ... more >>>


TR21-004 | 10th January 2021
Vishnu Iyer, Avishay Tal, Michael Whitmeyer

Junta Distance Approximation with Sub-Exponential Queries

Leveraging tools of De, Mossel, and Neeman [FOCS, 2019], we show two different results pertaining to the tolerant testing of juntas. Given black-box access to a Boolean function $f:\{\pm1\}^{n} \to \{\pm1\}$ we give a poly$(k, \frac{1}{\varepsilon})$ query algorithm that distinguishes between functions that are $\gamma$-close to $k$-juntas and $(\gamma+\varepsilon)$-far from ... more >>>




ISSN 1433-8092 | Imprint