| 1. |
- Johansson, Niklas, 1987-
(författare)
-
A Resource for Quantum Computation
- 2021
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- In this thesis we address the question, what is the resource, or property, that enables the advantage of quantum computers? The theory of quantum computers dates back to the eighties, so one would think there already is an answer to this question. There are several proposed solutions, but to this date, there is no consensus on an answer. Primarily, the advantage of quantum computers is characterized by a speedup for certain computational problems. This speedup is measured by comparing quantum algorithms with the best-known classical algorithms. For some algorithms we assume access to an object called oracle. The oracle computes a function, and the complexity of the oracle is of no concern. Instead, we count the number of queries to the oracle needed to solve the problem. Informally, the question we ask using an oracle is: if we can compute this function efficiently, what else could we then compute. However, using oracles while measuring a quantum speedup, we assume access to vastly different oracles residing in different models of computation.For our investigation of the speedup, we introduce a classical simulation framework that imitates quantum algorithms. The simulation suggests that the property enabling the potential quantum speedup is the ability to store, process, and retrieve information in an additional degree of freedom. We then theoretically verified that this is true for all problems that can be efficiently solved with a quantum computer.In parallel to this, we also see that quantum oracles sharply specify the information we can retrieve from the additional degree of freedom, while regular oracles do not. A regular oracle does not even allow for an extra degree of freedom. We conclude that comparing quantum with classical oracle query complexity bounds does not provide conclusive evidence for a quantum advantage.
|
|
| 2. |
- Hoff Rudhult, Maria
(författare)
-
SIDA VID SIDA? : Svenska företag i biståndsverksamheten, 1946–2013
- 2023
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- This thesis studies how the way private businesses were viewed came to affect their participation, and thus role, in Swedish development aid activities in the 1946-2013 period. The role is here viewed in terms of the relationship between “the public” and “the private”. The relationship between public and private activities, as well as the distinction between them, is mutable, and needs to be understood within the framework of a specific context. This, in turn, means that these relationships between the state, in the form of public activity, and the businesses, in the form of private activity, constitute the more comprehensive research problem of the thesis. The analytical strategy of the thesis is based on a discourse theoretical approach, discursive institutionalism, to study how development aid, based on the ideal of “solidarity”, was formulated, established and upheld as an area of policy, focusing especially on the role that was concurrently created for Swedish private businesses. The application of a genealogical approach in the reading of political texts as well as archival material, reports and evaluations, makes visible how the businesses have been part of the Swedish developmental aid activities during practically the entirety of the time period studied, and that this has not been openly accounted for in the public political material. The study shows that upholding the ideal of the “solidarity-based” politics regarding development aid was enabled by applying different logics of action to different parts of the development aid activity. This is made clear by the political ability to involve businesses in development aid activities without having to expressly renounce the position of solidarity. The result of the thesis also shows that the ideal of “solidarity” influenced both the preconditions for distinctions between public and private, and how views of businesses as illegitimate or legitimate actors in development aid activity changed over time.
|
|
| 3. |
- Johansson, Niklas, 1987-
(författare)
-
On the Power of Quantum Computation: Oracles
- 2018
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Quantum computation solve some computational problems faster than the best-known alternative in classical computation. The evidence for this consists of examples where a quantum algorithm outperforms the best-known classical algorithm. A large body of these examples relies on oracle query complexity, where the performance (complexity) of the algorithms is measured by the number of times they need to access an oracle. Here, an oracle is usually considered to be a black box that computes a specific function at unit cost.However, the quantum algorithm is given access to an oracle with more structure than the classical algorithm. This thesis argues that the two oracles are so vastly different that comparing quantum and classical query complexity should not be considered evidence, but merely hints for a quantum advantage.The approach used is based on a model that can be seen as an approximation of quantum theory, but can be efficiently simulated on a classical computer. This model solves several oracular problems with the same performance as their quantum counterparts, showing that there is no genuine quantum advantage for these problems. This approach also clarifies the assumptions made in quantum computation, and which properties that can be seen as resources in these algorithms.
|
|
| 4. |
- Osipov, George, 1994-
(författare)
-
On Infinite-Domain CSPs Parameterized by Solution Cost
- 2024
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- In this thesis we study the computational complexity of MinCSP - an optimization version of the Constraint Satisfaction Problem (CSP). The input to a MinCSP is a set of variables and constraints applied to these variables, and the goal is to assign values (from a fixed domain) to the variables while minimizing the solution cost, i.e. the number of unsatisfied constraints. We are specifically interested in MinCSP with infinite domains of values. Infinite-domain MinCSPs model fundamental optimization problems in computer science and are of particular relevance to artificial intelligence, especially temporal and spatial reasoning. The usual way to study computational complexity of CSPs is to restrict the types of constraints that can be used in the inputs, and either construct fast algorithms or prove lower bounds on the complexity of the resulting problems.The vast majority of interesting MinCSPs are NP-hard, so standard complexity-theoretic assumptions imply that we cannot find exact solutions to all inputs of these problems in polynomial time with respect to the input size. Hence, we need to relax at least one of the three requirements above, opting for either approximate solutions, solving some inputs, or using super-polynomial time. Parameterized algorithms exploits the latter two relaxations by identifying some common structure of the interesting inputs described by some parameter, and then allowing super-polynomial running times with respect to that parameter. Such algorithms are feasible for inputs of any size whenever the parameter value is small. For MinCSP, a natural parameter is optimal solution cost. We also study parameterized approximation algorithms, where the requirement for exact solutions is also relaxed.We present complete complexity classifications for several important classes of infinite-domain constraints. These are simple temporal constraints and interval constraints, which have notable applications in temporal reasoning in AI, linear equations over finite and infinite fields as well as some commutative rings (e.g., the rationals and the integers), which are of fundamental theoretical importance, and equality constraints, which are closely related to connectivity problems in undirected graphs and form the basis of studying first-order definable constraints over infinite domains. In all cases, we prove results as follows: we fix a (possibly infinite) set of allowed constraint types C, and for every finite subset of C, determine whether MinCSP(), i.e., MinCSP restricted to the constraint types in , is fixed-parameter tractable, i.e. solvable in f(k) · poly(n) time, where k is the parameter, n is the input size, and f is any function that depends solely on k. To rule out such algorithms, we prove lower bounds under standard assumptions of parameterized complexity. In all cases except simple temporal constraints, we also provide complete classifications for fixed-parameter time constant-factor approximation.
|
|
| 5. |
- Roy, Biman, 1989-
(författare)
-
Applications of Partial Polymorphisms in (Fine-Grained) Complexity of Constraint Satisfaction Problems
- 2020
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- In this thesis we study the worst-case complexity ofconstraint satisfaction problems and some of its variants. We use methods from universal algebra: in particular, algebras of total functions and partial functions that are respectively known as clones and strong partial clones. The constraint satisfactionproblem parameterized by a set of relations Γ (CSP(Γ)) is the following problem: given a set of variables restricted by a set of constraints based on the relations Γ, is there an assignment to thevariables that satisfies all constraints? We refer to the set Γ as aconstraint language. The inverse CSPproblem over Γ (Inv-CSP(Γ)) asks the opposite: given a relation R, does there exist a CSP(Γ) instance with R as its set of models? When Γ is a Boolean language, then we use the term SAT(Γ) instead of CSP(Γ) and Inv-SAT(Γ) instead of Inv-CSP(Γ).Fine-grained complexity is an approach in which we zoom inside a complexity class and classify theproblems in it based on their worst-case time complexities. We start by investigating the fine-grained complexity of NP-complete CSP(Γ) problems. An NP-complete CSP(Γ) problem is said to be easier than an NP-complete CSP(∆) problem if the worst-case time complexity of CSP(Γ) is not higher thanthe worst-case time complexity of CSP(∆). We first analyze the NP-complete SAT problems that are easier than monotone 1-in-3-SAT (which can be represented by SAT(R) for a certain relation R), and find out that there exists a continuum of such problems. For this, we use the connection between constraint languages and strong partial clones and exploit the fact that CSP(Γ) is easier than CSP(∆) when the strong partial clone corresponding to Γ contains the strong partial clone of ∆. An NP-complete CSP(Γ) problem is said to be the easiest with respect to a variable domain D if it is easier than any other NP-complete CSP(∆) problem of that domain. We show that for every finite domain there exists an easiest NP-complete problem for the ultraconservative CSP(Γ) problems. An ultraconservative CSP(Γ) is a special class of CSP problems where the constraint language containsall unary relations. We additionally show that no NP-complete CSP(Γ) problem can be solved insub-exponential time (i.e. in2^o(n) time where n is the number of variables) given that theexponentialtime hypothesisis true.Moving to classical complexity, we show that for any Boolean constraint language Γ, Inv-SAT(Γ) is either in P or it is coNP-complete. This is a generalization of an earlier dichotomy result, which was only known to be true for ultraconservative constraint languages. We show that Inv-SAT(Γ) is coNP-complete if and only if the clone corresponding to Γ contains essentially unary functions only. For arbitrary finite domains our results are not conclusive, but we manage to prove that theinversek-coloring problem is coNP-complete for each k>2. We exploit weak bases to prove many of theseresults. A weak base of a clone C is a constraint language that corresponds to the largest strong partia clone that contains C. It is known that for many decision problems X(Γ) that are parameterized bya constraint language Γ(such as Inv-SAT), there are strong connections between the complexity of X(Γ) and weak bases. This fact can be exploited to achieve general complexity results. The Boolean domain is well-suited for this approach since we have a fairly good understanding of Boolean weak bases. In the final result of this thesis, we investigate the relationships between the weak bases in the Boolean domain based on their strong partial clones and completely classify them according to the setinclusion. To avoid a tedious case analysis, we introduce a technique that allows us to discard a largenumber of cases from further investigation.
|
|
| 6. |
- Arora-Jonsson, Stefan, Professor, 1969-, et al.
(författare)
-
Teaching schools to compete : the case of Swedish upper secondary education
- 2024
-
Ingår i: Socio-Economic Review. - : Oxford University Press. - 1475-1461 .- 1475-147X.
-
Tidskriftsartikel (refereegranskat)abstract
- Significant efforts have been made to promote competition in public service sectors, expanding the reach of competition into non-economic fields. Surprisingly little is, however, known about the process by which competition is introduced into such settings. We examine this process, focusing on a Swedish municipality’s efforts to implement competition for students among its schools. By incorporating recent theoretical advancements regarding competition as an organized relationship, and utilizing a combination of qualitative and quantitative data, we shed light on the organizational efforts undertaken by politicians and bureaucrats to teach their schools to compete. We find that introducing competition can be complex, time-consuming and that it requires substantial organizational commitment. We highlight the existence of varying perceptions of competition among different stakeholders following its introduction. These findings suggest the need for future research that addresses questions about the costs of, and interests behind, introducing competition, as well as questions about responsibility for the subsequent effects of competition.
|
|
| 7. |
- Arora-Jonsson, Stefan, Professor, 1969-, et al.
(författare)
-
The Construction of Competition in Public Research Funding Systems
- 2023
-
Ingår i: Handbook of Public Funding of Research. - Cheltenham : Edward Elgar Publishing. - 9781800883079 ; , s. 172-184
-
Bokkapitel (övrigt vetenskapligt/konstnärligt)abstract
- Competition is a core feature of public research systems. Previous literature has mainly focused on the consequences of competition for research funding in such systems. These consequences are important, but the literature has largely assumed that competition for funding is inevitable in public research systems. This assumption masks the extent to which competition is a constructed phenomenon requiring explanation. When and why is there competition for research funding in public systems? In this chapter, our aim is to develop new knowledge about the ways that various allocations of funding are or are not constructed as competition for funding. We utilise recent theorising to analyse competition for research funding as a phenomenon that eventually comes about through organising efforts. Our chapter revitalises previous literature, and offers policy implications and future inquiry avenues that highlight the importance of understanding how competition for funding is constructed, and potentially revoked, in public research systems.
|
|
| 8. |
- Bomark, Niklas, 1984-, et al.
(författare)
-
Convincing Others That They are Competing : The Case of Schools
- 2021
-
Ingår i: Competition. - Oxford : Oxford University Press. - 9780192898012 - 9780191924460
-
Bokkapitel (refereegranskat)abstract
- The past decades have seen numerous attempts to introduce competition into new sectors of society, but we still know little about the processes by which competition is realized in a new setting. We study three decades of organizational efforts of a Swedish municipality that sought to introduce competition for students among its upper secondary schools following a national reform in the early 1990s. Our study shows that declaring competition was far from sufficient for its realization; the path to competition was lined with hesitation, uncertainty, and a rich variety of organizational challenges to be overcome. One particularly vexing challenge was to convince the principals of the schools that they should view each other as competitors for students. Our findings contribute to previous literature by demonstrating that competition need not be a prerequisite for choice; that several organizers of competition may operate at once; and, more generally, that competition is introduced through stepwise, piecemeal processes.
|
|
| 9. |
- Dabrowski, Konrad K., et al.
(författare)
-
Almost Consistent Systems of Linear Equations
- 2023
-
Ingår i: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). - Philadelphia, PA : Society for Industrial and Applied Mathematics. - 9781611977554 ; , s. 3179-3217
-
Konferensbidrag (refereegranskat)abstract
- Checking whether a system of linear equations is consistent is a basic computational problem with ubiquitous applications. When dealing with inconsistent systems, one may seek an assignment that minimizes the number of unsatisfied equations. This problem is NP-hard and UGC-hard to approximate within any constant even for two-variable equations over the two-element field. We study this problem from the point of view of parameterized complexity, with the parameter being the number of unsatisfied equations. We consider equations defined over Euclidean domains—a family of commutative rings that generalize finite and infinite fields including the rationals, the ring of integers and many other structures. We show that if every equation contains at most two variables, the problem is fixed-parameter tractable. This generalizes many eminent graph separation problems such as Bipartization, Multiway Cut and Multicut parameterized by the size of the cutset. To complement this, we show that the problem is W[1]-hard when three or more variables are allowed in an equation, as well as for many commutative rings that are not Euclidean domains. On the technical side, we introduce the notion of important balanced subgraphs, generalizing important separators of Marx [Theor. Comput. Sci. 2006] to the setting of biased graphs. Furthermore, we use recent results on parameterized MinCSP [Kim et al., SODA 2021] to efficiently solve a generalization of Multicut with disjunctive cut requests.
|
|
| 10. |
- Dabrowski, Konrad K., et al.
(författare)
-
Parameterized Complexity Classification for Interval Constraints
- 2023
-
Ingår i: 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). - Saarbrücken/Wadern : Schloss Dagstuhl – Leibniz-Zentrum für Informatik. - 9783959773058 ; , s. 11:1-11:19
-
Konferensbidrag (refereegranskat)abstract
- Constraint satisfaction problems form a nicely behaved class of problems that lends itself to complexity classification results. From the point of view of parameterized complexity, a natural task is to classify the parameterized complexity of MinCSP problems parameterized by the number of unsatisfied constraints. In other words, we ask whether we can delete at most k constraints, where k is the parameter, to get a satisfiable instance. In this work, we take a step towards classifying the parameterized complexity for an important infinite-domain CSP: Allen’s interval algebra (IA). This CSP has closed intervals with rational endpoints as domain values and employs a set A of 13 basic comparison relations such as "precedes" or "during" for relating intervals. IA is a highly influential and well-studied formalism within AI and qualitative reasoning that has numerous applications in, for instance, planning, natural language processing and molecular biology. We provide an FPT vs. W[1]-hard dichotomy for MinCSP(Γ) for all Γ ⊆ A. IA is sometimes extended with unions of the relations in A or first-order definable relations over A, but extending our results to these cases would require first solving the parameterized complexity of Directed Symmetric Multicut, which is a notorious open problem. Already in this limited setting, we uncover connections to new variants of graph cut and separation problems. This includes hardness proofs for simultaneous cuts or feedback arc set problems in directed graphs, as well as new tractable cases with algorithms based on the recently introduced flow augmentation technique. Given the intractability of MinCSP(A) in general, we then consider (parameterized) approximation algorithms. We first show that MinCSP(A) cannot be polynomial-time approximated within any constant factor and continue by presenting a factor-2 fpt-approximation algorithm. Once again, this algorithm has its roots in flow augmentation.
|
|
