I know virtually noting about Fourier Analysis and I'd like to know whether it's worth to learn this topic for my problem.
My problem is: Given vectors $h_1,\cdots,h_k\in\{+1,-1\}^n$ where $k < n$, decide whether there exists another vector $x\in\{+1,-1\}^n$ that is orthogonal to all of $h_1,\cdots,h_k$.
I think I may formulate my problem with the help of a quadratic function $f(x) = x^T\left(\sum_{i=1}^k h_i h_i^T\right)x$ to have a condition that
$f(x) = 0$ if and only if $x$ is orthogonal to $h_1,\cdots,h_k$.
As the desired function is a boolean function that $f:\{+1,-1\}^n\to\mathbb{R}$, it may be uniquely represented by a certain Fourier expansion . Then my job is to check whether this function has zero Fourier coefficients or not.
I know there can be $2^n$ Fourier coefficients. And it may be impossible to check whether a function has a Fourier expansion with zero coefficients. Does this approach make sense? Is there any reference / related work on this kind of problem?