Half-SAT/ Half-Satisfiability Is the following satisfiability problem hard?
Given a set of clauses over boolean variables in conjunctive normal form, decide whether there is an assignment of truth values to the variables that satisfies at least half of the clauses.
I looked it up for a while and the only related research I could find is on approximating MAXSAT, which probably is not quite the same thing.
Results for any constant $c\in (0,1)$ instead of $\frac 1 2$ would be interesting as well.
 A: First note that your question is not quite right.  You asked:

Given … decide whether …

and of course the decision problem is straightforward: just try every possible assignment.  I assume that you meant to say “decide in polynomial time”.

The Karloff-Zwick algorithm shows that for any instance of 3SAT, there is an assignment that satisfies at least $\frac78$ of the clauses.
Karloff-Zwick says: assign the values at random.  Then each one of the $n$ causes is satisfied with probability $\frac 78$.
By linearity of expectation, the expected number of satisfied clauses $\frac78n$.
Since the expected number of satisfied clauses is $\frac78n$, then, by the pigeonhole principle, there must be an assignment that satisfies at least $\frac78n$ clauses.
So, when $c\le \frac78$, the problem is not only in $P$, but is trivial, because the answer is always “yes”.
Aaronson (reference below) says “A deterministic polynomial-time algorithm that's guaranteed to satisfy at least $\frac78$ of the clauses requires only a little more work.”

In contrast, for $c>\frac78$, there is probably not any corresponding algorithm, because of this theorem of Håstad:

Suppose there exists a polynomial-time algorithm that, given as input a satisfiable 3-SAT instance, outputs an assignment that satisfies at least a $\frac78 +\epsilon$ fraction of the clauses, for some positive constant $\epsilon$.  Then $P=NP$.

This is Håstad, J. 2001 “Some optimal inapproximability results” Journal of the ACM, 48 pp 798–859.
See also Aaronson, Scott “$P{\stackrel?=}NP$” p 25.
