| 1. |
- Angelsmark, Ola, 1972-, et al.
(författare)
-
Determining the Number of Solutions to Binary CSP Instances
- 2002
-
Ingår i: Principles and Practice of Constraint Programming, 8th International Conference CP-2002,2002. - Heidelberg : Springer Verlag. ; , s. 327-
-
Konferensbidrag (refereegranskat)abstract
- Counting the number of solutions to CSP instances has applications in several areas, ranging from statistical physics to artificial intelligence. We give an algorithm for counting the number of solutions to binary CSPs, which works by transforming the problem into a number of 2-SAT instances, where the total number of solutions to these instances is the same as those of the original problem. The algorithm consists of two main cases, depending on whether the domain size d is even, in which case the algorithm runs in O(1.3247^n*(d/2)^n) time, or odd, in which case it runs in O(1.3247^n*((d^2+d+2)/4)^(n/2)) if d=4*k+1, and O(1.3247^n*((d^2+d)/4)^(n/2)) if d=4*k+3. We also give an algorithm for counting the number of possible 3-colourings of a given graph, which runs in O(1.8171^n), an improvement over our general algorithm gained by using problem specific knowledge.
|
|
| 2. |
- 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.
|
|
| 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. |
- Krokhin, Andrei, et al.
(författare)
-
Constraint satisfaction problems on intervals and lengths
- 2004
-
Ingår i: SIAM Journal on Discrete Mathematics. - 0895-4801 .- 1095-7146. ; 17:3, s. 453-477
-
Tidskriftsartikel (refereegranskat)abstract
- We study interval-valued constraint satisfaction problems (CSPs), in which the aim is to find an assignment of intervals to a given set of variables subject to constraints on the relative positions of intervals. Many well-known problems such as INTERVAL GRAPH RECOGNITION and INTERVAL SATISFIABILITY can be considered as examples of such CSPs. One interesting question concerning such problems is to determine exactly how the complexity of an interval-valued CSP depends on the set of constraints allowed in instances. For the framework known as Allen's interval algebra this question was completely answered earlier by the authors, by giving a complete description of the tractable cases and showing that all remaining cases are NP-complete. Here we extend the qualitative framework of Allen's algebra with additional constraints on the lengths of intervals. We allow these length constraints to be expressed as Horn disjunctive linear relations, a well-known tractable and sufficiently expressive form of constraints. The class of problems we consider contains, in particular, problems that are very closely related to the previously studied UNIT INTERVAL GRAPH SANDWICH problem. We completely characterize sets of qualitative relations for which the CSP augmented with arbitrary length constraints of the above form is tractable. We also show that, again, all the remaining cases are NP-complete.
|
|
| 5. |
- Angelsmark, Ola, 1972-, et al.
(författare)
-
Finite Domain Constraint Satisfaction Using Quantum Computation
- 2002
-
Ingår i: Mathematical Foundations of Computer Science, 27th International Symposium MFCS-2002,2002. - Heidelberg : Springer Verlag. ; , s. 93-
-
Konferensbidrag (refereegranskat)abstract
- We present a quantum algorithm for finite domain constraint solving, where the constraints have arity 2. It is complete and runs in time, where d is size of the domain of the variables and n the number of variables. For the case of d=3 we provide a method to obtain an upper time bound of . Also for d=5 the upper bound has been improved. Using this method in a slightly different way we can decide 3-colourability in O(1.2185^n) time.
|
|
| 6. |
|
|
| 7. |
- Arora-Jonsson, Stefan, 1969-, et al.
(författare)
-
Konkurrens som organisation
- 2019
-
Ingår i: Organisation & Samhälle. - Stockholm : Föreningen Företagsekonomi i Sverige (FEKIS). - 2001-9114 .- 2002-0287. ; :1, s. 22-27
-
Tidskriftsartikel (övrigt vetenskapligt/konstnärligt)
|
|
| 8. |
- Arora-Jonsson, Stefan, 1969-, et al.
(författare)
-
Organizing a Competitive Logic in the Swedish School Market
- 2019
-
Ingår i: Academy of Management Proceedings. - : Academy of Management. - 1543-8643. ; :1
-
Tidskriftsartikel (övrigt vetenskapligt/konstnärligt)abstract
- A common assumption in organizational literature is that the “rules” by which organizations compete in a market emerge from processes of mutual adjustment among competitors to the constraints posed by market structures and institutions. While this may often be the case, we point the analytical gaze to the arguably prevalent but understudied case where the rules for competing are decided, i.e. result from an attempt at organizing by an organizer, rather than by mutual adjustment among competitors. We explore the formation and change of a competitive logic among Swedish upper secondary schools, using archival and interview data from two municipalities. We find how a broad-sweeping reform initially failed to shape a competitive logic, i.e. schools did not think they were competing. Over time, however, the idea of competing for students took hold, resulting in the organization of two very different competitive logics. Our findings speak to literatures that deal with institutional, geographical, and structural perspectives on competition, adding the notion of organizers as central actors in processes where competition forms and changes.
|
|
| 9. |
- 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.
|
|
| 10. |
- 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.
|
|
