Search for dissertations about: "computational complexity"

Showing result 1 - 5 of 444 swedish dissertations containing the words computational complexity.

  1. 1. Space in Proof Complexity

    Author : Marc Vinyals; Jakob Nordström; Yehudayoff Amir; KTH; []
    Keywords : NATURAL SCIENCES; NATURVETENSKAP; NATURVETENSKAP; NATURAL SCIENCES; proof complexity; resolution; polynomial calculus; cutting planes; space complexity; computational complexity; pebble games; communication complexity; CDCL; Computer Science; Datalogi;

    Abstract : ropositional proof complexity is the study of the resources that are needed to prove formulas in propositional logic. In this thesis we are concerned with the size and space of proofs, and in particular with the latter.Different approaches to reasoning are captured by corresponding proof systems. READ MORE

  2. 2. Approximation and Online Algorithms with Applications in Computational Biology and Computational Geometry

    Author : Mia Persson; Data Vetenskap; []
    Keywords : NATURVETENSKAP; NATURAL SCIENCES; NATURVETENSKAP; NATURAL SCIENCES; numerisk analys; system; systems; control; Datalogi; numerical analysis; broadcasting; polygon exploration; robotics; Mathematics; Matematik; Computer science; clique partition; clustering; computational complexity; computational geometry; computational biology; online algorithm; kontroll; approximation algorithm;

    Abstract : The main contributions of this thesis are in the area of approximation and online algorithm design and derivation of lower bounds on the approximability for a number of combinatorial optimization problems with applications in computational biology and computational geometry. Approximation and online algorithms are fundamental tools used to deal with computationally hard problems and problems in which the input is gradually disclosed over time. READ MORE

  3. 3. Topological and geometrical methods in data analysis

    Author : Oliver Gäfvert; Sandra di Rocco; Henry Schenck; KTH; []
    Keywords : NATURAL SCIENCES; NATURVETENSKAP; NATURVETENSKAP; NATURAL SCIENCES; multiparameter persistent homology; computational algebraic geometry; algorithms; complexity; Matematik; Mathematics;

    Abstract : This thesis concerns two related data analysis pipelines, using topological and geometrical methods respectively, to extract relevant information. The first pipeline, referred to as the topological data analysis (TDA) pipeline, constructs a filtered simplicial complex on a given data set in order to describe its shape. READ MORE

  4. 4. On Some Combinatorial Optimization Problems : Algorithms and Complexity

    Author : Hannes Uppman; Peter Jonsson; Christer Bäckström; Ulf Nilsson; Stanislav Živný; Linköpings universitet; []
    Keywords : NATURAL SCIENCES; NATURVETENSKAP; NATURVETENSKAP; NATURAL SCIENCES; Computational complexity; optimization; constraint satisfaction problem;

    Abstract : This thesis is about the computational complexity of several classes of combinatorial optimization problems, all related to the constraint satisfaction problems.A constraint language consists of a domain and a set of relations on the domain. For each such language there is a constraint satisfaction problem (CSP). READ MORE

  5. 5. Computational methods for microfluidics

    Author : Ludvig af Klinteberg; Anna-Karin Tornberg; Peter Hansbo; KTH; []

    Abstract : This thesis is concerned with computational methods for fluid flows on the microscale, also known as microfluidics. This is motivated by current research in biological physics and miniaturization technology, where there is a need to understand complex flows involving microscale structures. Numerical simulations are an important tool for doing this. READ MORE