  Given an $n*n$ sparse symmetric matrix with $m$ nonzero entries, performing
Gaussian elimination may turn some zeroes into nonzero values. To maintain the
matrix sparse, we would like to minimize the number $k$ of these changes, hence
called the minimum fill-in problem. Agrawal et al.~[FOCS'90] developed the
first approximation algorithm, based on early heuristics by George [SIAM J
Numer Anal 10] and by Lipton et al.~[SIAM J Numer Anal 16]. The objective
function they used is $m+k$, the number of nonzero elements after elimination.
An approximation algorithm using $k$ as the objective function was presented by
Natanzon et al.~[STOC'98]. These two versions are incomparable in terms of
approximation.
  Parameterized algorithms for the problem was first studied by Kaplan et
al.~[FOCS'94]. Fomin & Villanger [SODA'12] recently gave an algorithm running
in time $2^{O(\sqrt{k} \log k)}+n^{O(1)}$.
  Hardness results of this problem are surprisingly scarce, and the few known
ones are either weak or have to use nonstandard complexity conjectures. The
only inapproximability result by Wu et al.~[IJCAI'15] applies to only the
objective function $m+k$, and is grounded on the Small Set Expansion
Conjecture. The only nontrivial parameterized lower bounds, by Bliznets et
al.~[SODA'16], include a very weak one based on ETH, and a strong one based on
hardness of subexponential-time approximation of the minimum bisection problem
on regular graphs. For both versions of the problem, we exclude the existence
of PTASs, assuming P$\ne$NP, and the existence of $2^{O(n^{1-\delta})}$-time
approximation schemes for any positive $\delta$, assuming ETH. It also implies
a $2^{O(k^{1/2-\delta})} n^{O(1)}$ parameterized lower bound. Behind these
results is a new reduction from vertex cover, which might be of its own
interest: All previous reductions for similar problems are from some kind of
graph layout problems.
