Multi-Prover and parallel repetition in non-classical interactive games

Depuis l’introduction de la mécanique quantique, plusieurs mystères de la nature ont trouvé leurs explications. De plus en plus, les concepts de la mécanique quantique se sont entremêlés avec d’autres de la théorie de la complexité du calcul. De nouvelles idées et solutions ont été découvertes et élaborées dans le but de résoudre ces problèmes informatiques. En particulier, la mécanique quantique a secoué plusieurs preuves de sécurité de protocoles classiques. Dans ce m´emoire, nous faisons un étalage de résultats récents de l’implication de la mécanique quantique sur la complexité du calcul, et cela plus précisément dans le cas de classes avec interaction. Nous présentons ces travaux de recherches avec la nomenclature des jeux à information imparfaite avec coopération. Nous exposons les différences entre les théories classiques, quantiques et non-signalantes et les démontrons par l’exemple du jeu à cycle impair. Nous centralisons notre attention autour de deux grands thèmes : l’effet sur un jeu de l’ajout de joueurs et de la répétition parallèle. Nous observons que l’effet de ces modifications a des conséquences très différentes en fonction de la théorie physique considérée.

Improvement On Brooks Chromatic Bound For A Class Of Graphs

Brooks' Theorem says that if for a graph G,Δ(G)=n, then G is n-colourable, unless (1) n=2 and G has an odd cycle as a component, or (2) n>2 and Kn+1 is a component of G. In this paper we prove that if a graph G has none of some three graphs (K1,3;K5−e and H) as an induced subgraph and if Δ(G)greater-or-equal, slanted6 and d(G)<Δ(G), then χ(G)<Δ(G). Also we give examples to show that the hypothesis Δ(G)greater-or-equal, slanted6 can not be non-trivially relaxed and the graph K5−e can not be removed from the hypothesis. Moreover, for a graph G with none of K1,3;K5−e and H as an induced subgraph, we verify Borodin and Kostochka's conjecture that if for a graph G,Δ(G)greater-or-equal, slanted9 and d(G)<Δ(G), then χ(G)<Δ(G).

Estimating quantum chromatic numbers

We develop further the new versions of quantum chromatic numbers of graphs introduced by the first and fourth authors. We prove that the problem of computation of the commuting quantum chromatic number of a graph is solvable by an SDP algorithm and describe an hierarchy of variants of the commuting quantum chromatic number which converge to it. We introduce the tracial rank of a graph, a parameter that gives a lower bound for the commuting quantum chromatic number and parallels the projective rank, and prove that it is multiplicative. We describe the tracial rank, the projective rank and the fractional chromatic numbers in a unified manner that clarifies their connection with the commuting quantum chromatic number, the quantum chromatic number and the classical chromatic number, respectively. Finally, we present a new SDP algorithm that yields a parameter larger than the Lovász number and is yet a lower bound for the tracial rank of the graph. We determine the precise value of the tracial rank of an odd cycle.

The heliospheric Hale cycle over the last 300 years and its implications for a “lost” late 18th century solar cycle

A Hale cycle, one complete magnetic cycle of the Sun, spans two complete Schwabe cycles (also referred to as sunspot and, more generally, solar cycles). The approximately 22-year Hale cycle is seen in magnetic polarities of both sunspots and polar fields, as well as in the intensity of galactic cosmic rays reaching Earth, with odd- and even-numbered solar cycles displaying qualitatively different waveforms. Correct numbering of solar cycles also underpins empirical cycle-to-cycle relations which are used as first-order tests of stellar dynamo models. There has been much debate about whether the unusually long solar cycle 4 (SC4), spanning- 1784–1799, was actually two shorter solar cycles combined as a result of poor data coverage in the original Wolf sunspot number record. Indeed, the group sunspot number does show a small increase around 1794–1799 and there is evidence of an increase in the mean latitude of sunspots at this time, suggesting the existence of a cycle ‘‘4b’’. In this study, we use cosmogenic radionuclide data and associated reconstructions of the heliospheric magnetic field (HMF) to show that the Hale cycle has persisted over the last 300 years and that data prior to 1800 are more consistent with cycle 4 being a single long cycle (the ‘‘no SC4b’’ scenario). We also investigate the effect of cycle 4b on the HMF using an open solar flux (OSF) continuity model, in which the OSF source term is related to sunspot number and the OSF loss term is determined by the heliospheric current sheet tilt, assumed to be a simple function of solar cycle phase. The results are surprising; Without SC4b, the HMF shows two distinct peaks in the 1784–1799 interval, while the addition of SC4b removes the secondary peak, as the OSF loss term acts in opposition to the later rise in sunspot number. The timing and magnitude of the main SC4 HMF peak is also significantly changed by the addition of SC4b. These results are compared with the cosmogenic isotope reconstructions of HMF and historical aurora records. These data marginally favour the existence of SC4b (the ‘‘SC4b’’ scenario), though the result is less certain than that based on the persistence of the Hale cycle. Thus while the current uncertainties in the observations preclude any definitive conclusions, the data favour the ‘‘no SC4b’’ scenario. Future improvements to cosmogenic isotope reconstructions of the HMF, through either improved modelling or additional ice cores from well-separated geographic locations, may enable questions of the existence of SC4b and the phase of Hale cycle prior to the Maunder minimum to be settled conclusively.

The extended metamorphosis of a complete bipartite design into a cycle system

A K-t,K-t-design of order n is an edge-disjoint decomposition of K-n into copies of K-t,K-t. When t is odd, an extended metamorphosis of a K-t,K-t-design of order n into a 2t-cycle system of order n is obtained by taking (t - 1)/2 edge-disjoint cycles of length 2t from each K-t,K-t block, and rearranging all the remaining 1-factors in each K-t,K-t block into further 2t-cycles. The 'extended' refers to the fact that as many subgraphs isomorphic to a 2t-cycle as possible are removed from each K-t,K-t block, rather than merely one subgraph. In this paper an extended metamorphosis of a K-t,K-t-design of order congruent to 1 (mod 4t(2)) into a 2t-cycle system of the same order is given for all odd t > 3. A metamorphosis of a 2-fold K-t,K-t-design of any order congruent to 1 (mod 4t(2)) into a 2t-cycle system of the same order is also given, for all odd t > 3. (The case t = 3 appeared in Ars Combin. 64 (2002) 65-80.) When t is even, the graph K-t,K-t is easily seen to contain t/2 edge-disjoint cycles of length 2t, and so the metamorphosis in that case is straightforward. (C) 2004 Elsevier B.V. All rights reserved.

Data on the biogeochemical cycle of methane in the ocean

Geological, mineralogical and microbiological aspects of the methane cycle in water and sediments of different areas in the oceans are under consideration in the monograph. Original and published estimations of formation- and oxidation rates of methane with use of radioisotope and isotopic methods are given. The role of aerobic and anaerobic microbial oxidation of methane in production of organic matter and in formation of authigenic carbonates is considered. Particular attention is paid to processes of methane transformation in areas of its intensive input to the water column from deep-sea hydrothermal sources, mud volcanoes, and cold methane seeps.

Integrating health and sustainability in life cycle assessment

Until now health impact assessment and environmental impact assessment are two different issues, often not addressed together. Both issues have to be dealt with for sustainable building. The aim of this paper is to link healthy and sustainable housing in life cycle assessment. Two strategies are studied: clean air as a functional unity and health as a quality indicator. The strategies are illustrated with an example on the basis of Eco-Quantum, which is a Dutch whole-building assessment tool. It turns out that both strategies do not conflict with the LCA methodology. The LCA methodology has to be refined for this purpose.