  Given a graph $G$ and a parameter $k$, the $k$-biclique problem asks whether
$G$ contains a complete bipartite subgraph $K_{k,k}$. This is the most easily
stated problem on graphs whose parameterized complexity is still unknown. We
provide an fpt-reduction from $k$-clique to $k$-biclique, thus solving this
longstanding open problem.
  Our reduction use a class of bipartite graphs with a threshold property of
independent interest. More specifically, for positive integers $n$, $s$ and
$t$, we consider a bipartite graph $G=(A\;\dot\cup\;B, E)$ such that $A$ can be
partitioned into $A=V_1\;\dot\cup \;V_2\;\dot\cup\cdots\dot\cup\; V_n$ and for
every $s$ distinct indices $i_1\cdots i_s$, there exist $v_{i_1}\in
V_{i_1}\cdots v_{i_s}\in V_{i_s}$ such that $v_{i_1}\cdots v_{i_s}$ have at
least $t+1$ common neighbors in $B$; on the other hand, every $s+1$ distinct
vertices in $A$ have at most $t$ common neighbors in $B$.
  Using the Paley-type graphs and Weil's character sum theorem, we show that
for $t=(s+1)!$ and $n$ large enough, such threshold bipartite graphs can be
computed in $n^{O(1)}$. One corollary of our reduction is that there is no
$f(k)\cdot n^{o(k)}$ time algorithm to decide whether a graph contains a
subgraph isomorphic to $K_{k!,k!}$ unless the ETH(Exponential Time Hypothesis)
fails. We also provide a probabilistic construction with better parameters
$t=\Theta(s^2)$, which indicates that $k$-biclique has no $f(k)\cdot
n^{o(\sqrt{k})}$-time algorithm unless 3-SAT with $m$ clauses can be solved in
$2^{o(m)}$-time with high probability. Our result also implies the dichotomy
classification of the parameterized complexity of cardinality constrain
satisfaction problem and the inapproximability of maximum $k$-intersection
problem.
