Search for dissertations about: "Uri Zwick"

Found 2 swedish dissertations containing the words Uri Zwick.

  2. 1. Beating a Random Assignment : Approximating Constraint Satisfaction Problems

    Author : Gustav Hast; Johan Håstad; Uri Zwick; KTH; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; Datalogi; Computer science; Datalogi;

    Abstract : 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. READ MORE

  4. 2. Conditional Inapproximability and Limited Independence

    Author : Per Austrin; Johan Håstad; Ryan O'Donnell; KTH; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; Computer science; Datalogi;

    Abstract : Understanding the theoretical limitations of efficient computation is one of the most fundamental open problems of modern mathematics. This thesis studies the approximability of intractable optimization problems. In particular, we study so-called Max CSP problems. READ MORE