Sökning: "Per Austrin"

Hittade 3 avhandlingar innehållade orden Per Austrin.

  1. 1. 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

  3. 2. On Long Proofs of Simple Truths

    Författare :Kilian Risse; Per Austrin; Johan Håstad; Jakob Nordström; Benjamin Rossman; KTH; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Computational Complexity; Lower Bounds; Proof Complexity; Datalogi; Computer Science;

    Sammanfattning : Propositional proof complexity is the study of certificates of infeasibility. In this thesis we consider several proof systems with limited deductive ability and unconditionally show that they require long refutations of the feasibility of certain Boolean formulas. LÄS MER

  4. 3. Hardness of Approximating Constraint Satisfaction Problems and Their Variants in Presence of Additional Structural Assumptions

    Författare :Aleksa Stankovic; Johan Håstad; Per Austrin; Luca Trevisan; KTH; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Hardness of Approximation; Approximation Algorithms; Label Cover; Vertex Cover; Unique Games Conjecture; Max-3-Lin; Universal Factor Graphs; Regular Constraint Satisfaction Problems; Inapproximerbarhet; Approximationsalgoritm; Label Cover; Vertex Cover; Unique Games Conjecture; Max-3-Lin; Universell Faktorgraf; Regelbundna Begränsningsproblem; Datalogi; Computer Science;

    Sammanfattning : This thesis studies how the approximability of some fundamental computational problems is affected by some additional requirements on the structure of the inputs. The problems studied in this thesis belong or are closely related to constraint satisfaction problems (CSPs), which are considered to be one of the most fundamental problems in theoretical computer science. LÄS MER