Search for dissertations about: "probabilistically"

Showing result 1 - 5 of 8 swedish dissertations containing the word probabilistically.

  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. Contributions to the theory of unequal probability sampling

    Author : Anders Lundquist; Lennart Bondesson; Aleksandras Plikusas; Umeå universitet; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; balanced sampling; conditional Poisson sampling; inclusion probabilities; maximum entropy; Markov chain Monte Carlo; Pareto sampling; Sampford sampling; unequal probability sampling.; Mathematical statistics; Matematisk statistik; Mathematical Statistics; matematisk statistik;

    Abstract : This thesis consists of five papers related to the theory of unequal probability sampling from a finite population. Generally, it is assumed that we wish to make modelassisted inference, i.e. the inclusion probability for each unit in the population is prescribed before the sample is selected. READ MORE

  5. 3. Multidimensional Constellation Shaping for Coherent Optical Communication Systems

    Author : Ali Mirani; Chalmers tekniska högskola; []
    Keywords : TEKNIK OCH TEKNOLOGIER; ENGINEERING AND TECHNOLOGY; NATURVETENSKAP; NATURAL SCIENCES; TEKNIK OCH TEKNOLOGIER; ENGINEERING AND TECHNOLOGY; TEKNIK OCH TEKNOLOGIER; ENGINEERING AND TECHNOLOGY; lattice-based constellations; geometric shaping; probabilistic shaping; multidimensional modulation format; Voronoi constellation; constellation shaping; optical communications; coherent receiver;

    Abstract : To overcome the increasing demands for Internet traffic, exploiting the available degrees of freedom in optical communication systems is necessary. In this thesis, we study how constellation shaping can be achieved in various dimensions and how various shaping schemes affect the whole performance in real systems. READ MORE

  6. 4. Dominator-based Algorithms in Logic Synthesis and Verification

    Author : René Krenz-Bååth; Johnny Öberg; Joao Marques-Silva; KTH; []
    Keywords : TEKNIK OCH TEKNOLOGIER; ENGINEERING AND TECHNOLOGY; graph dominators; formal verification; logic synthesis; equivalence checking; decomposition; Electrical engineering; Elektroteknik;

    Abstract : Today's EDA (Electronic Design Automation) industry faces enormous challenges. Their primary cause is the tremendous increase of the complexity of modern digital designs. Graph algorithms are widely applied to solve various EDA problems. READ MORE

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