Sökning: "Uri Zwick"

Hittade 2 avhandlingar innehållade orden Uri Zwick.

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

   Författare :Gustav Hast; Johan Håstad; Uri Zwick; KTH; []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Datalogi; Computer science; Datalogi;

   Sammanfattning : 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. LÄS MER

3. 2. Conditional Inapproximability and Limited Independence

   Författare :Per Austrin; Johan Håstad; Ryan O'Donnell; KTH; []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Computer science; Datalogi;

   Sammanfattning : 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. LÄS MER