Search for dissertations about: "probabilistically checkable proofs"

Found 2 swedish dissertations containing the words probabilistically checkable proofs.

  2. 1. Hardness of Constraint Satisfaction and Hypergraph Coloring : Constructions of Probabilistically Checkable Proofs with Perfect Completeness

    Author : Sangxia Huang; Johan Håstad; Rishi Saket; KTH; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; Combinatorial optimization; approximation; inapproximability; hardness; probabilistically checkable proofs; pcp; perfect completeness; boolean constraint satisfaction problem; csp; graph coloring; hypergraph coloring; direct sum; superposition; label cover; Computer Science; Datalogi;

    Abstract : A Probabilistically Checkable Proof (PCP) of a mathematical statement is a proof written in a special manner that allows for efficient probabilistic verification. The celebrated PCP Theorem states that for every family of statements in NP, there is a probabilistic verification procedure that checks the validity of a PCP proof by reading only 3 bits from it. READ MORE

  4. 2. Label Cover Reductions for Unconditional Approximation Hardness of Constraint Satisfaction

    Author : Cenny Wenner; Johan Håstad; Irit Dinur; Numerical Analysis and Computer Science (NADA) Faculty of Science Stockholm University; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; Optimization; NP; Approximation; Approximability; Inapproximability; Constraint Satisfaction; CSP; Boolean Analysis; Satisfiability; SAT; Acyclic Subgraph; Betweenness; Unique Games; Computer Science; Datalogi;

    Abstract : Problem solving is an integral aspect of modern society and includes such tasks as picking the fastest route to work, optimizing a production line, scheduling computer tasks, placing new bus stops, or picking a meal from available ingredients.We study the hardness of solving Constraint Satisfaction Problems (CSPs). READ MORE