Sökning: "Inapproximability"

Visar resultat 1 - 5 av 8 avhandlingar innehållade ordet Inapproximability.

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

    Författare :Sangxia Huang; Johan Håstad; Rishi Saket; KTH; []
    Nyckelord :NATURAL SCIENCES; NATURVETENSKAP; 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;

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

  2. 2. Conditional Inapproximability and Limited Independence

    Författare :Per Austrin; Johan Håstad; Ryan O'Donnell; KTH; []

    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. 3. Label Cover Reductions for Unconditional Approximation Hardness of Constraint Satisfaction

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

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

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

    Författare :Cenny Wenner; Johan Håstad; Viggo Kann; Irit Dinur; Stockholms universitet; []
    Nyckelord :NATURAL SCIENCES; NATURVETENSKAP; NATURVETENSKAP; NATURAL SCIENCES; Combinatorial Optimization; Complexity Theory; Approximation; Approximability; Inapproximability; Computational Hardness; NP; Optimization; Constraint Satisfaction; Kombinatorisk optimering; Komplexitetsteori; Beräkningsteori; Approximation; Approximerbarhet; Beräkningssvårighet; NP; Optimering; Vilkorssatisfiering; Vilkorsuppfyllning; Vilkorstillfredställand; datalogi; Computer Science;

    Sammanfattning : Combinatorial optimization include such tasks as finding the quickest route to work, scheduling jobs to specialists, and placing bus stops so as to minimize commuter times. We consider problems where one is given a collection of constraints with the objective of finding an assignment satisfying as many constraints as possible, also known as Constraint Satisfaction Problems (CSPs). LÄS MER

  5. 5. Applications of Gaussian Noise Stability in Inapproximability and Social Choice Theory

    Författare :Marcus Isaksson; Göteborgs universitet; Göteborgs universitet; Gothenburg University; []
    Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Gaussian noise stability; inapproximability theory; invariance principle; max-q-cut; condorcet voting; max-q-cut;

    Sammanfattning : Gaussian isoperimetric results have recently played an important role in proving fundamental results in hardness of approximation in computer science and in the study of voting schemes in social choice theory. In this thesis we prove a generalization of a Gaussian isoperimetric result by Borell and show that it implies that the majority function is optimal in Condorcet voting in the sense that it maximizes the probability that there is a single candidate which the society prefers over all other candidates. LÄS MER