| 1. |
- Angel, O., et al.
(författare)
-
THE PHASE TRANSITION FOR DYADIC TILINGS
- 2014
-
Ingår i: Transactions of the American Mathematical Society. - 0002-9947 .- 1088-6850. ; 366:2, s. 1029-1046
-
Tidskriftsartikel (refereegranskat)abstract
- A dyadic tile of order n is any rectangle obtained from the unit square by n successive bisections by horizontal or vertical cuts. Let each dyadic tile of order n be available with probability p, independent of the others. We prove that for p sufficiently close to 1, there exists a set of pairwise disjoint available tiles whose union is the unit square, with probability tending to 1 as n -> infinity, as conjectured by Joel Spencer in 1999. In particular, we prove that if p = 7/8, such a tiling exists with probability at least 1 - (3/4)(n). The proof involves a surprisingly delicate counting argument for sets of unavailable tiles that prevent tiling.
|
|
| 2. |
- Angulo, Julio, 1980-, et al.
(författare)
-
What Would It Take for You to Tell Your Secrets to a Cloud? : Studying decision factors when disclosing information to cloud services
- 2014
-
Ingår i: Secure IT Systems. - Cham : Springer. - 9783319115993 ; , s. 129-145
-
Konferensbidrag (refereegranskat)abstract
- We investigate the end users’ behaviours and attitudes with regards to the control they place in the personal information that they disclose to cloud storage services. Three controlled experiments were carried out to study the influence in users’ decisions to retain or surrender control over their personal information depending on different factors. The results of these experiments reveal, among other things, the users’ willingness to surrender control over personal information that is perceived as non-sensitive in exchange for valuable rewards, and that users would value the possibility of knowing and controlling the parties who are granted access to their data in the cloud. Based on the results from the experiments we provide implications for the design of end-user tools that can promote transparency and accountability in cloud computing environments.
|
|
| 3. |
- Freij, Ragnar, 1984, et al.
(författare)
-
Partially ordered secretaries
- 2010
-
Ingår i: Electronic Communications in Probability. - 1083-589X. ; 15, s. 504-507
-
Tidskriftsartikel (refereegranskat)abstract
- The elements of a finite nonempty partially ordered set are exposed at independent uniform times in [0, 1] to a selector who, at any given time, can see the structure of the induced partial order on the exposed elements. The selector’s task is to choose online a maximal element. This generalizes the classical linear order secretary problem, for which it is known that the selector can succeed with probability 1=e and that this is best possible. We describe a strategy for the general problem that achieves success probability at least 1=e for an arbitrary partial order.
|
|
| 4. |
- Hessler, Martin, et al.
(författare)
-
Edge cover and polymatroid flow problems
- 2010
-
Ingår i: Electronic Journal of Probability. - : Institute of Mathematical Statistics. - 1083-6489. ; 15, s. 2200-2219
-
Tidskriftsartikel (refereegranskat)abstract
- In an n by n complete bipartite graph with independent exponentially distributed edge costs, we ask for the minimum total cost of a set of edges of which each vertex is incident to at least one. This so-called minimum edge cover problem is a relaxation of perfect matching. We show that the large n limit cost of the minimum edge cover is W(1)(2) + 2W(1) approximate to 1.456, where W is the Lambert W-function. In particular this means that the minimum edge cover is essentially cheaper than the minimum perfect matching, whose limit cost is pi(2)/6 approximate to 1.645. We obtain this result through a generalization of the perfect matching problem to a setting where we impose a (poly-)matroid structure on the two vertex-sets of the graph, and ask for an edge set of prescribed size connecting independent sets.
|
|
| 5. |
|
|
| 6. |
- Larsson, Urban, 1965, et al.
(författare)
-
From heaps of matches to the limits of computability
- 2013
-
Ingår i: Electronic Journal of Combinatorics. - : The Electronic Journal of Combinatorics. - 1077-8926 .- 1097-1440. ; 20:3
-
Tidskriftsartikel (refereegranskat)abstract
- We study so-called invariant games played with a fixed number d of heaps of matches. A game is described by a finite list M of integer vectors of length d specifying the legal moves. A move consists in changing the current game-state by adding one of the vectors in M, provided all elements of the resulting vector are nonnegative. For instance, in a two-heap game, the vector (1, -2) would mean adding one match to the first heap and removing two matches from the second heap. If (1, -2) is an element of M, such a move would be permitted provided there are at least two matches in the second heap. Two players take turns, and a player unable to make a move loses. We show that these games embrace computational universality, and that therefore a number of basic questions about them are algorithmically undecidable. In particular, we prove that there is no algorithm that takes two games M and M' (with the same number of heaps) as input, and determines whether or not they are equivalent in the sense that every starting-position which is a first player win in one of the games is a first player win in the other.
|
|
| 7. |
- Larsson, Urban, 1965, et al.
(författare)
-
Maharaja Nim : Wythoff's Queen meets the Knight
- 2013
-
Annan publikation (övrigt vetenskapligt/konstnärligt)abstract
- We relax the hypothesis of a recent result of A. S. Fraenkel and U. Peled on certain complementary sequences of positive integers. The motivation is to understand to asymptotic behavior of the impartial game of \emph{Maharaja Nim}, an extension of the classical game of Wythoff Nim. In the latter game, two players take turn in moving a single Queen of Chess on a large board, attempting to be the first to put her in the lower left corner, position $(0,0)$. Here, in addition to the classical rules, a player may also move the Queen as the Knight of Chess moves, still taking into consideration that, by moving no coordinate increases. We prove that the second player's winning positions are close to those of Wythoff Nim, namely they are within a bounded distance to the half-lines, starting at the origin, of slope $\frac{\sqrt{5}+1}{2}$ and $\frac{\sqrt{5}-1}{2}$ respectively. We encode the patterns of the P-positions by means of a certain \emph{dictionary process}, thus introducing a new method for analyzing games related to Wythoff Nim. Via Post's Tag productions, we also prove that, in general, such dictionary processes are algorithmically undecidable.
|
|
| 8. |
- Larsson, Urban, 1965, et al.
(författare)
-
Maharaja Nim
- 2013
-
Tidskriftsartikel (övrigt vetenskapligt/konstnärligt)abstract
- We relax the hypothesis of a recent result of A. S. Fraenkel and U. Peled on certain complementary sequences of positive integers. The motivation is to understand to asymptotic behavior of the impartial game of \emph{Maharaja Nim}, an extension of the classical game of Wythoff Nim. In the latter game, two players take turn in moving a single Queen of Chess on a large board, attempting to be the first to put her in the lower left corner, position $(0,0)$. Here, in addition to the classical rules, a player may also move the Queen as the Knight of Chess moves, still taking into consideration that, by moving no coordinate increases. We prove that the second player's winning positions are close to those of Wythoff Nim, namely they are within a bounded distance to the half-lines, starting at the origin, of slope $\frac{\sqrt{5}+1}{2}$ and $\frac{\sqrt{5}-1}{2}$ respectively. We encode the patterns of the P-positions by means of a certain \emph{dictionary process}, thus introducing a new method for analyzing games related to Wythoff Nim. Via Post's Tag productions, we also prove that, in general, such dictionary processes are algorithmically undecidable.
|
|
| 9. |
|
|
| 10. |
|
|
