An instance Of MAx kCSP consists of weighted k-ary constraints acting over a set of Boolean variables. The objective is to find an assignment to the Boolean variables such that the total weight of satisfied constraints is maximized. In this paper we provide a probabilistical polynomial time approximation algorithm that c(0)k(log k)(-1)2(-k)- approximates MAx kCSP, for a constant c(0) > 0.

In this paper we study the approximability of the maximization version of constraint satisfaction problems. We provide two probabilistic approximation algorithms for MAX kCONJSAT which is the problem to satisfy as many conjunctions, each of size at most k, as possible. As observed by Trevisan, this leads to approximation algorithms with the same approximation ratio for the more general problem MAX kCSP, where instead of conjunctions arbitrary k-ary constraints are imposed. The first algorithm achieves an approximation ratio of 2(1.40-k). The second algorithm achieves a slightly better approximation ratio of 2(1.54-k), but the ratio is shown using computational evidence. These ratios should be compared with the previous best algorithm, due to Trevisan, that achieves an approximation ratio of 2(1-k). Both the new algorithms use a combination of random restrictions, a method which have been used in circuit complexity, and traditional semidefinite relaxation methods. A consequence of these algorithms is that some complexity classes described by probabilistical checkable proofs can be characterized as subsets of P. Our result in this paper implies that PCPc,s [log, k] subset of or equal to P for any c/s > 2(k-1.40), and we have computational evidence that if c/s > 2(k-1.54) this inclusion still holds.

MAX CSP(P) is the problem of maximizing the weight of satisfied constraints, where each constraint acts over a k-tuple of literals and is evaluated using the predicate P. The approximation ratio of a random assignment is equal to the fraction of satisfying inputs to P. If it is NP-hard to achieve a better approximation ratio for MAX CSP(P), then we say that P is approximation resistant. Our goal is to characterize which predicates that have this property. A general approximation algorithm for MAX CSP(P) is introduced. For a multitude of different P, it is shown that the algorithm beats the random assignment algorithm, thus implying that P is not approximation resistant. In particular, over 2/3 of the predicates on four binary inputs are proved not to be approximation resistant, as well as all predicates on 2s binary inputs, that have at most 2s + I accepting inputs. We also prove a large number of predicates to be approximation resistant. In particular, all predicates of arity 2s + s(2) with less than 2(s2) nonaccepting inputs axe proved to be approximation resistant, as well as almost 1/5 of the predicates on four binary inputs.

An instance of a Boolean constraint satisfaction problem, CSP, consists of a set of constraints acting over a set of Boolean variables. The objective is to find an assignment to the variables that satisfies all the constraints. In the maximization version, Max CSP, each constraint has a weight and the objective is to find an assignment such that the weight of satisfied constraints is maximized. By specifying which types of constraints that are allowed we create subproblems to Max CSP. For example, an instance of Max kCSP only contains constraints that act over at most k different variables. Another problem is Max CSP(P), where P is a predicate, i.e., a Boolean function. In such an instance P is used to determine if a constraint is satisfied or not.

Both Max kCSP and Max CSP(P) are NP-hard to solve optimally for k ≥ 2 and predicates P that depend on at least two input values. Therefore, we consider efficient approximation algorithms for these two problems. A trivial algorithm is to assign all variables a random value. Somewhat surprisingly, Håstad showed that using this random assignment approach is essentially optimal for approximating Max CSP(P), for some predicates P. We call such predicates approximation resistant. Goemans and Williamson introduced an approximation method that relaxes problems into semidefinite programs. Using this method they show that for predicates P of arity two, it is possible to outperform a random assignment in approximating Max CSP(P). By extending this technique Zwick characterized all predicates of arity three as either approximation resistant or not.

In this thesis we consider predicates of arity larger than three. We extend the work of Håstad and the work of Samorodnitsky and Trevisan in order to show predicates to be approximation resistant. We also use semidefinite relaxation algorithms in order to show that predicates are not approximation resistant. In particular we show that predicates with few non-accepting inputs are approximation resistant and that predicates with few accepting inputs are not approximation resistant. We study predicates of arity four more closely and characterize 354 out of 400 predicate types.

Max kCSP is 2^-k-approximated by a random assignment and previously no algorithms were known to outperform such an algorithm with more than a small constant factor. In this thesis a probabilistic

Ω (2^{k+log k-log log k})-approximation for Max kCSP is presented.

We study statistical tests with binary output that rarely outputs one, which we call nearly one-sided statistical tests. We provide an efficient reduction establishing improved security for the Goldreich-Levin hard-core bit against nearly one-sided tests. The analysis is extended to prove the security of the Blum-Micali pseudo-random generator combined with the Goldreich-Levin bit. Finally, some applications where nearly one-sided tests occur naturally are discussed.