Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks

We present a distributed algorithm that finds a maximal edge packing in O(Δ + log* W) synchronous communication rounds in a weighted graph, independent of the number of nodes in the network; here Δ is the maximum degree of the graph and W is the maximum weight. As a direct application, we have a distributed 2-approximation algorithm for minimum-weight vertex cover, with the same running time. We also show how to find an f-approximation of minimum-weight set cover in O(f2k2 + fk log* W) rounds; here k is the maximum size of a subset in the set cover instance, f is the maximum frequency of an element, and W is the maximum weight of a subset. The algorithms are deterministic, and they can be applied in anonymous networks.

A local 2-approximation algorithm for the vertex cover problem

We present a distributed 2-approximation algorithm for the minimum vertex cover problem. The algorithm is deterministic, and it runs in (Δ + 1)2 synchronous communication rounds, where Δ is the maximum degree of the graph. For Δ = 3, we give a 2-approximation algorithm also for the weighted version of the problem.

A simple local 3-approximation algorithm for vertex cover

We present a local algorithm (constant-time distributed algorithm) for finding a 3-approximate vertex cover in bounded-degree graphs. The algorithm is deterministic, and no auxiliary information besides port numbering is required. (c) 2009 Elsevier B.V. All rights reserved.

A local 2-approximation algorithm for the vertex cover problem

We present a distributed 2-approximation algorithm for the minimum vertex cover problem. The algorithm is deterministic, and it runs in (Δ + 1)2 synchronous communication rounds, where Δ is the maximum degree of the graph. For Δ = 3, we give a 2-approximation algorithm also for the weighted version of the problem.

Numerical computation of the module of a quadrilateral

The module of a quadrilateral is a positive real number which divides quadrilaterals into conformal equivalence classes. This is an introductory text to the module of a quadrilateral with some historical background and some numerical aspects. This work discusses the following topics: 1. Preliminaries 2. The module of a quadrilateral 3. The Schwarz-Christoffel Mapping 4. Symmetry properties of the module 5. Computational results 6. Other numerical methods Appendices include: Numerical evaluation of the elliptic integrals of the first kind. Matlab programs and scripts and possible topics for future research. Numerical results section covers additive quadrilaterals and the module of a quadrilateral under the movement of one of its vertex.

DNA Packaging and Host Cell Lysis: Late Events in Bacteriophage PRD1 Infection

The object of this study is a tailless internal membrane-containing bacteriophage PRD1. It has a dsDNA genome with covalently bound terminal proteins required for replication. The uniqueness of the structure makes this phage a desirable object of research. PRD1 has been studied for some 30 years during which time a lot of information has accumulated on its structure and life-cycle. The two least characterised steps of the PRD1 life-cycle, the genome packaging and virus release are investigated here. PRD1 shares the main principles of virion assembly (DNA packaging in particular) and host cell lysis with other dsDNA bacteriophages. However, this phage has some fascinating individual peculiarities, such as DNA packaging into a membrane vesicle inside the capsid, absence of apparent portal protein, holin inhibitor and procapsid expansion. In the course of this study we have identified the components of the DNA packaging vertex of the capsid, and determined the function of protein P6 in packaging. We managed to purify the procapsids for an in vitro packaging system, optimise the reaction and significantly increase its efficiency. We developed a new method to determine DNA translocation and were able to quantify the efficiency and the rate of packaging. A model for PRD1 DNA packaging was also proposed. Another part of this study covers the lysis of the host cell. As other dsDNA bacteriophages PRD1 has been proposed to utilise a two-component lysis system. The existence of this lysis system in PRD1 has been proven by experiments using recombinant proteins and the multi-step nature of the lysis process has been established.

The genome packaging machinery of dsDNA bacteriophage PRD1

Viral genomes are encapsidated within protective protein shells. This encapsidation can be achieved either by a co-condensation reaction of the nucleic acid and coat proteins, or by first forming empty viral particles which are subsequently packaged with nucleic acid, the latter mechanism being typical for many dsDNA bacteriophages. Bacteriophage PRD1 is an icosahedral, non-tailed dsDNA virus that has an internal lipid membrane, the hallmark of the Tectiviridae family. Although PRD1 has been known to assemble empty particles into which the genome is subsequently packaged, the mechanism for this has been unknown, and there has been no evidence for a separate packaging vertex, similar to the portal structures used for packaging in the tailed bacteriophages and herpesviruses. In this study, a unique DNA packaging vertex was identified for PRD1, containing the packaging ATPase P9, packaging factor P6 and two small membrane proteins, P20 and P22, extending the packaging vertex to the internal membrane. Lack of small membrane protein P20 was shown to totally abolish packaging, making it an essential part of the PRD1 packaging mechanism. The minor capsid proteins P6 was shown to be an important packaging factor, its absence leading to greatly reduced packaging efficiency. An in vitro DNA packaging mechanism consisting of recombinant packaging ATPase P9, empty procapsids and mutant PRD1 DNA with a LacZ-insert was developed for the analysis of PRD1 packaging, the first such system ever for a virus containing an internal membrane. A new tectiviral sequence, a linear plasmid called pBClin15, was identified in Bacillus cereus, providing material for sequence analysis of the tectiviruses. Analysis of PRD1 P9 and other putative tectiviral ATPase sequences revealed several conserved sequence motifs, among them a new tectiviral packaging ATPase motif. Mutagenesis studies on PRD1 P9 were used to confirm the significance of the motifs. P9-type putative ATPase sequences carrying a similar sequence motif were identified in several other membrane containing dsDNA viruses of bacterial, archaeal and eukaryotic hosts, suggesting that these viruses may have similar packaging mechanisms. Interestingly, almost the same set of viruses that were found to have similar putative packaging ATPases had earlier been found to share similar coat protein folds and capsid structures, and a common origin for these viruses had been suggested. The finding in this study of similar packaging proteins further supports the idea that these viruses are descendants of a common ancestor.

Gravitino phenomenology and cosmological implications of supergravity

In this thesis we consider the phenomenology of supergravity, and in particular the particle called "gravitino". We begin with an introductory part, where we discuss the theories of inflation, supersymmetry and supergravity. Gravitino production is then investigated into details, by considering the research papers here included. First we study the scattering of massive W bosons in the thermal bath of particles, during the period of reheating. We show that the process generates in the cross section non trivial contributions, which eventually lead to unitarity breaking above a certain scale. This happens because, in the annihilation diagram, the longitudinal degrees of freedom in the propagator of the gauge bosons disappear from the amplitude, by virtue of the supergravity vertex. Accordingly, the longitudinal polarizations of the on-shell W become strongly interacting in the high energy limit. By studying the process with both gauge and mass eigenstates, it is shown that the inclusion of diagrams with off-shell scalars of the MSSM does not cancel the divergences. Next, we approach cosmology more closely, and study the decay of a scalar field S into gravitinos at the end of inflation. Once its mass is comparable to the Hubble rate, the field starts coherent oscillations about the minimum of its potential and decays pertubatively. We embed S in a model of gauge mediation with metastable vacua, where the hidden sector is of the O'Raifeartaigh type. First we discuss the dynamics of the field in the expanding background, then radiative corrections to the scalar potential V(S) and to the Kähler potential are calculated. Constraints on the reheating temperature are accordingly obtained, by demanding that the gravitinos thus produced provide with the observed Dark Matter density. We modify consistently former results in the literature, and find that the gravitino number density and T_R are extremely sensitive to the parameters of the model. This means that it is easy to account for gravitino Dark Matter with an arbitrarily low reheating temperature.

Measurement of the top quark mass and pp̅ →tt̅ cross section in the all-hadronic mode with the CDF II detector

We present a measurement of the top quark mass and of the top-antitop pair production cross section using p-pbar data collected with the CDFII detector at the Tevatron Collider at the Fermi National Accelerator Laboratory and corresponding to an integrated luminosity of 2.9 fb-1. We select events with six or more jets satisfying a number of kinematical requirements imposed by means of a neural network algorithm. At least one of these jets must originate from a b quark, as identified by the reconstruction of a secondary vertex inside the jet. The mass measurement is based on a likelihood fit incorporating reconstructed mass distributions representative of signal and background, where the absolute jet energy scale (JES) is measured simultaneously with the top quark mass. The measurement yields a value of 174.8 +- 2.4(stat+JES) ^{+1.2}_{-1.0}(syst) GeV/c^2, where the uncertainty from the absolute jet energy scale is evaluated together with the statistical uncertainty. The procedure measures also the amount of signal from which we derive a cross section, sigma_{ttbar} = 7.2 +- 0.5(stat) +- 1.0 (syst) +- 0.4 (lum) pb, for the measured values of top quark mass and JES.

Top polarization as a probe of new physics

We investigate the effects of new physics scenarios containing a high mass vector resonance on top pair production at the LHC, using the polarization of the produced top. In particular we use kinematic distributions of the secondary lepton coming from top decay, which depends on top polarization, as it has been shown that the angular distribution of the decay lepton is insensitive to the anomalous tbW vertex and hence is a pure probe of new physics in top quark production. Spin sensitive variables involving the decay lepton are used to probe top polarization. Some sensitivity is found for the new couplings of the top.

Search for standard model Higgs boson production in association with a W boson using a neural network discriminant at CDF

We present a search for standard model Higgs boson production in association with a W boson in proton-antiproton collisions at a center of mass energy of 1.96 TeV. The search employs data collected with the CDF II detector that correspond to an integrated luminosity of approximately 1.9 inverse fb. We select events consistent with a signature of a single charged lepton, missing transverse energy, and two jets. Jets corresponding to bottom quarks are identified with a secondary vertex tagging method, a jet probability tagging method, and a neural network filter. We use kinematic information in an artificial neural network to improve discrimination between signal and background compared to previous analyses. The observed number of events and the neural network output distributions are consistent with the standard model background expectations, and we set 95% confidence level upper limits on the production cross section times branching fraction ranging from 1.2 to 1.1 pb or 7.5 to 102 times the standard model expectation for Higgs boson masses from 110 to $150 GeV/c^2, respectively.

Updated search for the flavor-changing neutral-current decay D0→μ+μ- in pp̅ collisions at √s=1.96 TeV

We report on a search for the flavor-changing neutral-current decay D0 \to {\mu}+ {\mu}- in pp collisions at \surd s = 1.96 TeV using 360 pb-1 of integrated luminosity collected by the CDF II detector at the Fermilab Tevatron collider. A displaced vertex trigger selects long-lived D0 candidates in the {\mu}+ {\mu}-, {\pi}+{\pi}-, and K-{\pi}+ decay modes. We use the Cabibbo-favored D0 \to K-{\pi}+ channel to optimize the selection criteria in an unbiased manner, and the kinematically similar D0 \to{\pi}+ {\pi}- channel for normalization. We set an upper limit on the branching fraction (D0 --> {\mu}+ {\mu}-)

Coherent quantum Boltzmann equations from cQPA

We reformulate and extend our recently introduced quantum kinetic theory for interacting fermion and scalar fields. Our formalism is based on the coherent quasiparticle approximation (cQPA) where nonlocal coherence information is encoded in new spectral solutions at off-shell momenta. We derive explicit forms for the cQPA propagators in the homogeneous background and show that the collision integrals involving the new coherence propagators need to be resummed to all orders in gradient expansion. We perform this resummation and derive generalized momentum space Feynman rules including coherent propagators and modified vertex rules for a Yukawa interaction. As a result we are able to set up self-consistent quantum Boltzmann equations for both fermion and scalar fields. We present several examples of diagrammatic calculations and numerical applications including a simple toy model for coherent baryogenesis.

Analysing local algorithms in location-aware quasi-unit-disk graphs

A local algorithm with local horizon r is a distributed algorithm that runs in r synchronous communication rounds; here r is a constant that does not depend on the size of the network. As a consequence, the output of a node in a local algorithm only depends on the input within r hops from the node. We give tight bounds on the local horizon for a class of local algorithms for combinatorial problems on unit-disk graphs (UDGs). Most of our bounds are due to a refined analysis of existing approaches, while others are obtained by suggesting new algorithms. The algorithms we consider are based on network decompositions guided by a rectangular tiling of the plane. The algorithms are applied to matching, independent set, graph colouring, vertex cover, and dominating set. We also study local algorithms on quasi-UDGs, which are a popular generalisation of UDGs, aimed at more realistic modelling of communication between the network nodes. Analysing the local algorithms on quasi-UDGs allows one to assume that the nodes know their coordinates only approximately, up to an additive error. Despite the localisation error, the quality of the solution to problems on quasi-UDGs remains the same as for the case of UDGs with perfect location awareness. We analyse the increase in the local horizon that comes along with moving from UDGs to quasi-UDGs.