Exact bounds for distributed graph colouring

A distributed system is a collection of networked autonomous processing units which must work in a cooperative manner. Currently, large-scale distributed systems, such as various telecommunication and computer networks, are abundant and used in a multitude of tasks. The field of distributed computing studies what can be computed efficiently in such systems. Distributed systems are usually modelled as graphs where nodes represent the processors and edges denote communication links between processors. This thesis concentrates on the computational complexity of the distributed graph colouring problem. The objective of the graph colouring problem is to assign a colour to each node in such a way that no two nodes connected by an edge share the same colour. In particular, it is often desirable to use only a small number of colours. This task is a fundamental symmetry-breaking primitive in various distributed algorithms. A graph that has been coloured in this manner using at most k different colours is said to be k-coloured. This work examines the synchronous message-passing model of distributed computation: every node runs the same algorithm, and the system operates in discrete synchronous communication rounds. During each round, a node can communicate with its neighbours and perform local computation. In this model, the time complexity of a problem is the number of synchronous communication rounds required to solve the problem. It is known that 3-colouring any k-coloured directed cycle requires at least ½(log* k - 3) communication rounds and is possible in ½(log* k + 7) communication rounds for all k ≥ 3. This work shows that for any k ≥ 3, colouring a k-coloured directed cycle with at most three colours is possible in ½(log* k + 3) rounds. In contrast, it is also shown that for some values of k, colouring a directed cycle with at most three colours requires at least ½(log* k + 1) communication rounds. Furthermore, in the case of directed rooted trees, reducing a k-colouring into a 3-colouring requires at least log* k + 1 rounds for some k and possible in log* k + 3 rounds for all k ≥ 3. The new positive and negative results are derived using computational methods, as the existence of distributed colouring algorithms corresponds to the colourability of so-called neighbourhood graphs. The colourability of these graphs is analysed using Boolean satisfiability (SAT) solvers. Finally, this thesis shows that similar methods are applicable in capturing the existence of distributed algorithms for other graph problems, such as the maximal matching problem.

Simulation and graph mining tools for improving gene mapping efficiency

Gene mapping is a systematic search for genes that affect observable characteristics of an organism. In this thesis we offer computational tools to improve the efficiency of (disease) gene-mapping efforts. In the first part of the thesis we propose an efficient simulation procedure for generating realistic genetical data from isolated populations. Simulated data is useful for evaluating hypothesised gene-mapping study designs and computational analysis tools. As an example of such evaluation, we demonstrate how a population-based study design can be a powerful alternative to traditional family-based designs in association-based gene-mapping projects. In the second part of the thesis we consider a prioritisation of a (typically large) set of putative disease-associated genes acquired from an initial gene-mapping analysis. Prioritisation is necessary to be able to focus on the most promising candidates. We show how to harness the current biomedical knowledge for the prioritisation task by integrating various publicly available biological databases into a weighted biological graph. We then demonstrate how to find and evaluate connections between entities, such as genes and diseases, from this unified schema by graph mining techniques. Finally, in the last part of the thesis, we define the concept of reliable subgraph and the corresponding subgraph extraction problem. Reliable subgraphs concisely describe strong and independent connections between two given vertices in a random graph, and hence they are especially useful for visualising such connections. We propose novel algorithms for extracting reliable subgraphs from large random graphs. The efficiency and scalability of the proposed graph mining methods are backed by extensive experiments on real data. While our application focus is in genetics, the concepts and algorithms can be applied to other domains as well. We demonstrate this generality by considering coauthor graphs in addition to biological graphs in the experiments.

Nuori konservatiivi : Tuure Junnila ja hänen poliittinen toimintansa vuoteen 1956

Tuure Junnila, PhD (1910-1999) was one of Finland's most renowned conservative politicians of the post-war period. Junnila is remembered primarily as a persistent opponent of Urho Kekkonen, a long-term Member of Parliament, a conspicuous opposition member and a prolific political writer. Junnila's ideologies and political views were conservative, and he is one of the most outstanding figures in the history of the National Coalition Party. Junnila also made an extensive career outside of politics, first as an economist and then as an executive of Finland's leading commercial bank Kansallis-Osake-Pankki. The Young Conservative is a partial biography written using traditional historical research methods, which examines Junnila's personal history and his activity in public life up to 1956. The study begins by investigating Junnila's background through his childhood, school years, university studies and early professional career. It also looks at Junnila's work as an economist and practical banker. Particular attention is paid to Junnila's political work, constantly focusing on the following five often overlapping areas: (1) economic policy, (2) domestic policy, (3) foreign and security policy, (4) Junnila and Urho Kekkonen, (5) Junnila, the Coalition Party and Finnish conservatism. In his economic policy, Junnila emphasised the importance of economic stability, opposed socialisation and the growth of public expenditure, defended the free market system and private entrepreneurship, and demanded tax cuts. This policy was very popular within the Coalition Party during the early 1950s, making Junnila the leading conservative economic politician of the time. In terms of domestic policy, Junnila demanded as early as the 1940s that a "third force" should be established in Finland to counterbalance the agrarian and labour parties by uniting conservative and liberal ideologies under the same roof. Foreign and security policy is the area of Junnila's political activity which is most clearly situated after the mid-1950s. However, Junnila's early speeches and writings already show a striving towards the unconditional neutrality modelled by Switzerland and Sweden and a strong emphasis on Finland's right to internal self-determination. Junnila, as did the Coalition Party as a whole, adopted a consistently critical approach towards Urho Kekkonen between 1951 and 1956, but this attitude was not as bluntly negative and all-round antagonistic as many previous studies have implied. Junnila was one of the leading Finnish conservatives of the early 1950s and in all essence his views were analogous to the general alignment of the Coalition Party at the time: conservative in ideology and general policy, and liberal in economic policy.

Järjestö jäänmurtajana : Suomen merimiesunioni työmarkkinaosapuolena ja suomalaisten laivatyöntekijöiden turvallisuuden vankentajana 1944-1980

Like an Icebreaker: The Finnish Seamen s Union as collective bargaining maverick and champion of sailors social safety 1944-1980. The Finnish Seamen's Union (FSU), which was established on a national basis in 1920, was one of the first Finnish trade unions to succeed in collective bargaining. In the early 1930s, the gains made in the late 1920s were lost, due to politically based internal rivalries, the Great Depression, and a disastrous strike. Unexpectedly the FSU survived and went on promoting the well-being of its members even during World War II. After the war the FSU was in an exceptionally favorable position to exploit the introduction of coordinated capitalism, which was based on social partnership between unions, employers and government. Torpedoes, mines and confiscations had caused severe losses to the Finnish merchant marine. Both ship-owners and government alike understood the crucial importance of using the remaining national shipping capacity effectively. The FSU could no longer be crushed, and so, in 1945, the union was allowed to turn all ocean-going Finnish ships into closed shops. The FSU also had another source of power. After the sailors of the Finnish icebreaker fleet also joined its ranks, the FSU could, in effect, block Finnish foreign trade in wintertime. From the late 1940s to the 1960s the union started and won numerous icebreaker strikes. Finnish seamen were thus granted special pension rights, reductions on income taxes and import duties, and other social privileges. The FSU could neither be controlled by union federations nor intimidated by employers or governments. The successful union and its tactically clever chairperson, Niilo Välläri, were continuously but erroneously accused of syndicalism. Välläri did not aim for socialism but wanted the Finnish seamen to get all the social benefits that capitalism could possibly offer. Välläri s policy was successfully followed by the FSU until the late 1980s when Finnish ship-owners were allowed to flag their vessels outside the national registry. Since then the FSU has been on the defensive and has yielded to pay cuts. The FSU members have not lost their social benefits, but they are under constant fear of losing their jobs to cheap foreign labor.

Fuel conditions and fire behavior characteristics of managed Picea abies and Pinus sylvestris forests in Finland

The objectives of this study were to analyze the impact of structural stand characteristics on ignition potential, surface fuel moisture, and fire behavior in Pinus sylvestris L. and Picea abies (L.) Karst stands in Finland and to explain stand-specific fire danger using the Canadian Fire Weather Index System and the Finnish Fire Risk Index. Additionally, the study analyzes the relationship between observed fire activity and fire weather indices at different stages of growing season. Field experiments were carried out in Pinus sylvestris or Picea abies dominated stands during fire seasons 2001 and 2002. Observations on ignition potential, fuel moisture, and fire behavior were analyzed in relation to stand structure and the outputs of the Finnish and Canadian fire weather indices. Seasonal patterns of fire activity were examined based on national fire statistics 1996 2003, effective temperature sum, and the fire weather indices. Point fire ignition potential was highest in Pinus clear-cuts and lowest in closed Picea stands. Moss-dominated surface fuels were driest in clear-cut and sapling stage stands and presented the highest moisture content under closed Picea canopy. Pinus sylvestris stands carried fire under a wide range of fire weather conditions under which Picea abies stands failed to sustain fire. In the national fire records, the daily number of reported ignitions presented its highest value during late fire season whereas the daily area burned peaked most substantially during early season. The fire weather indices correlated significantly with ignition potential and fuel moisture but were unable to explain fire behavior in the experimental fires. During the initial and final stages of the growing season, fire activity was disconnected from weather-based fire danger ratings. Information on stand structure and season stage would benefit the assessment of fire danger in Finnish forest landscape for fire suppression and controlled burning purposes.

Traditionally Protected Forests and Sacred Forests of Zigua and Gweno Ethnic Groups in Tanzania

In Tanzania, indigenous forests can still be found whose existence is based on the management systems of precolonial society. This study covers material from over 900 forests. There are similar types of forests elsewhere in Africa, and similar forests can also be found in indigenous cultures on every continent. In this study they are called traditionally protected forests (TPFs). They have a high level of endemism and a rich biodiversity. The field study was carried out during the years 1997-2003 using participatory methods. An active debate is going on concerning the capacity of local communities to manage their environment. The role of indigenous people and their institutions in the development of the physical environment is a central issue in the debate. This study discusses the opportunities that the local people have had to decide on how to conserve, maintain, utilise, and manage their environment during different political periods. The study explains what kinds of changes have taken place in these forests and institutions in northeastern Tanzania among the matrilinear Zigua and patrilinear Gweno ethnic groups. About 2% of the land area of the communities was still protected by the precolonial structures. The communities have established their protection systems for different reasons, not only because of their beliefs but also because of different secular and clearly environmentally motivated reasons. There are different TPF types. Less than half of them are directly related to spirituality, and more than half are not. In earlier research elsewhere, it has been commonly understood that spiritual reasons played the main role in the protection of these environments. This study is also part of the postcolonial geographical discussion on the precolonial landscape and environmental management which was started by Carl Sauer. In the Zigua case study villages, only two out of five first comer clans have performed rain rituals in the past 30 years. Many of the most respected sacred sites do not have a ritual maker or even a person who knows how to perform rituals any longer. The same is happening with male initiation rites. In all case study villages there have been illegal cuts in the TPFs, but variations can be seen between the communities. The number of those who neither respect indigenous regulations nor accept indigenous penalties is growing. Positive developments have also taken place. Nowadays, the Forest Act of 2002 is in effect, which works as a cornerstone of community-based land ownership and also allows elders to protect TPFs, and by-laws are created with the support of different projects. Moreover, during the field study it was found that many young people are ignorant about their village's TPF sites, but interested in learning about their history and values.

Boundedness and convergence of singular integrals on fractal type sets

The topic of this dissertation lies in the intersection of harmonic analysis and fractal geometry. We particulary consider singular integrals in Euclidean spaces with respect to general measures, and we study how the geometric structure of the measures affects certain analytic properties of the operators. The thesis consists of three research articles and an overview. In the first article we construct singular integral operators on lower dimensional Sierpinski gaskets associated with homogeneous Calderón-Zygmund kernels. While these operators are bounded their principal values fail to exist almost everywhere. Conformal iterated function systems generate a broad range of fractal sets. In the second article we prove that many of these limit sets are porous in a very strong sense, by showing that they contain holes spread in every direction. In the following we connect these results with singular integrals. We exploit the fractal structure of these limit sets, in order to establish that singular integrals associated with very general kernels converge weakly. Boundedness questions consist a central topic of investigation in the theory of singular integrals. In the third article we study singular integrals of different measures. We prove a very general boundedness result in the case where the two underlying measures are separated by a Lipshitz graph. As a consequence we show that a certain weak convergence holds for a large class of singular integrals.

Computational Methods for Reconstruction and Analysis of Genome-Scale Metabolic Networks

Metabolism is the cellular subsystem responsible for generation of energy from nutrients and production of building blocks for larger macromolecules. Computational and statistical modeling of metabolism is vital to many disciplines including bioengineering, the study of diseases, drug target identification, and understanding the evolution of metabolism. In this thesis, we propose efficient computational methods for metabolic modeling. The techniques presented are targeted particularly at the analysis of large metabolic models encompassing the whole metabolism of one or several organisms. We concentrate on three major themes of metabolic modeling: metabolic pathway analysis, metabolic reconstruction and the study of evolution of metabolism. In the first part of this thesis, we study metabolic pathway analysis. We propose a novel modeling framework called gapless modeling to study biochemically viable metabolic networks and pathways. In addition, we investigate the utilization of atom-level information on metabolism to improve the quality of pathway analyses. We describe efficient algorithms for discovering both gapless and atom-level metabolic pathways, and conduct experiments with large-scale metabolic networks. The presented gapless approach offers a compromise in terms of complexity and feasibility between the previous graph-theoretic and stoichiometric approaches to metabolic modeling. Gapless pathway analysis shows that microbial metabolic networks are not as robust to random damage as suggested by previous studies. Furthermore the amino acid biosynthesis pathways of the fungal species Trichoderma reesei discovered from atom-level data are shown to closely correspond to those of Saccharomyces cerevisiae. In the second part, we propose computational methods for metabolic reconstruction in the gapless modeling framework. We study the task of reconstructing a metabolic network that does not suffer from connectivity problems. Such problems often limit the usability of reconstructed models, and typically require a significant amount of manual postprocessing. We formulate gapless metabolic reconstruction as an optimization problem and propose an efficient divide-and-conquer strategy to solve it with real-world instances. We also describe computational techniques for solving problems stemming from ambiguities in metabolite naming. These techniques have been implemented in a web-based sofware ReMatch intended for reconstruction of models for 13C metabolic flux analysis. In the third part, we extend our scope from single to multiple metabolic networks and propose an algorithm for inferring gapless metabolic networks of ancestral species from phylogenetic data. Experimenting with 16 fungal species, we show that the method is able to generate results that are easily interpretable and that provide hypotheses about the evolution of metabolism.

Optimisation Problems in Wireless Sensor Networks : Local Algorithms and Local Graphs

This thesis studies optimisation problems related to modern large-scale distributed systems, such as wireless sensor networks and wireless ad-hoc networks. The concrete tasks that we use as motivating examples are the following: (i) maximising the lifetime of a battery-powered wireless sensor network, (ii) maximising the capacity of a wireless communication network, and (iii) minimising the number of sensors in a surveillance application. A sensor node consumes energy both when it is transmitting or forwarding data, and when it is performing measurements. Hence task (i), lifetime maximisation, can be approached from two different perspectives. First, we can seek for optimal data flows that make the most out of the energy resources available in the network; such optimisation problems are examples of so-called max-min linear programs. Second, we can conserve energy by putting redundant sensors into sleep mode; we arrive at the sleep scheduling problem, in which the objective is to find an optimal schedule that determines when each sensor node is asleep and when it is awake. In a wireless network simultaneous radio transmissions may interfere with each other. Task (ii), capacity maximisation, therefore gives rise to another scheduling problem, the activity scheduling problem, in which the objective is to find a minimum-length conflict-free schedule that satisfies the data transmission requirements of all wireless communication links. Task (iii), minimising the number of sensors, is related to the classical graph problem of finding a minimum dominating set. However, if we are not only interested in detecting an intruder but also locating the intruder, it is not sufficient to solve the dominating set problem; formulations such as minimum-size identifying codes and locating dominating codes are more appropriate. This thesis presents approximation algorithms for each of these optimisation problems, i.e., for max-min linear programs, sleep scheduling, activity scheduling, identifying codes, and locating dominating codes. Two complementary approaches are taken. The main focus is on local algorithms, which are constant-time distributed algorithms. The contributions include local approximation algorithms for max-min linear programs, sleep scheduling, and activity scheduling. In the case of max-min linear programs, tight upper and lower bounds are proved for the best possible approximation ratio that can be achieved by any local algorithm. The second approach is the study of centralised polynomial-time algorithms in local graphs these are geometric graphs whose structure exhibits spatial locality. Among other contributions, it is shown that while identifying codes and locating dominating codes are hard to approximate in general graphs, they admit a polynomial-time approximation scheme in local graphs.

Socialist Realism instead of Formalism : the Formation and Development of the Soviet Music Control System 1932-1950

Whereas it has been widely assumed in the public that the Soviet music policy system had a “top-down” structure of control and command that directly affected musical creativity, in fact my research shows that the relations between the different levels of the music policy system were vague, and the viewpoints of its representatives differed from each other. Because the representatives of the party and government organs controlling operas could not define which kind of music represented Socialist Realism, the system as it developed during the 1930s and 1940s did not function effectively enough in order to create such a centralised control of Soviet music, still less could Soviet operas fulfil the highly ambiguous aesthetics of Socialist Realism. I show that musical discussions developed as bureaucratic ritualistic arenas, where it became more important to reveal the heretical composers, making scapegoats of them, and requiring them to perform self-criticism, than to give directions on how to reach the artistic goals of Socialist Realism. When one opera was found to be unacceptable, this lead to a strengthening of control by the party leadership, which lead to more operas, one after the other, to be revealed as failures. I have studied the control of the composition, staging and reception of the opera case-studies, which remain obscure in the West despite a growing scholarly interest in them, and have created a detailed picture of the foundation and development of the Soviet music control system in 1932-1950. My detailed discussion of such case-studies as Ivan Dzerzhinskii’s The Quiet Don, Dmitrii Shostakovich’s Lady Macbeth of Mtsensk District, Vano Muradeli’s The Great Friendship, Sergei Prokofiev’s Story of a Real Man, Tikhon Khrennikov’s Frol Skobeev and Evgenii Zhukovskii’s From All One’s Heart backs with documentary precision the historically revisionist model of the development of Soviet music. In February 1948, composers belonging to the elite of the Union of Soviet Composers, e.g. Dmitri Shostakovich and Sergei Prokofiev, were accused in a Central Committee Resolution of formalism, as been under the influence of western modernism. Accusations of formalism were connected to the criticism of the conciderable financial, material and social privileges these composers enjoyed in the leadership of the Union. With my new archival findings I give a more detailed picture of the financial background for the 1948 campaign. The independent position of the music funding organization of the Union of Soviet Composers (Muzfond) to decide on its finances was an exceptional phenomenon in the Soviet Union and contradicted the strivings to strengthen the control of Soviet music. The financial audits of the Union of Soviet Composers did not, however, change the elite status of some of its composers, except for maybe a short duration in some cases. At the same time the independence of the significal financial authorities of Soviet theatres was restricted. The cuts in the governmental funding allocated to Soviet theatres contradicted the intensified ideological demands for Soviet operas.

Short-term effects of variable retention on epigaeic spiders and carabid beetles in Finland

Forestry has influenced forest dwelling organisms for centuries in Fennoscandia. For example, in Finland ca. 30% of the threatened species are threatened because of forestry. Nowadays forest management recommendations include practices aimed at maintaining biodiversity in harvesting, such as green-tree retention. However, the effects of these practices have been little studied. In variable retention, different numbers of trees are retained, varying from green-tree retention (at least a few live standing trees in clear-cuts) to thinning (only individual trees removed). I examined the responses of ground-dwelling spiders and carabid beetles to green-tree retention (with small and large tree groups), gap felling and thinning aimed at an uneven age structure of trees. The impacts of these harvesting methods were compared to those of clear-cutting and uncut controls. I aimed to test the hypothesis that retaining more trees positively affects populations of those species of spiders and carabids that were present before harvesting. The data come from two studies. First, spiders were collected with pitfall traps in south-central Finland in 1995 (pre-treatment) and 1998 (after-treatment) in order to examine the effects of clear-cutting, green-tree retention (with 0.01-0.02-ha sized tree groups), gap felling (with three 0.16-ha sized openings in a 1-ha stand), thinning aiming at an uneven age structure of trees and uncut control. Second, spiders and carabids were caught with pitfall traps in eastern Finland in 1998-2001 (pre-treatment and three post-treatment years) in eleven 0.09-0.55-ha sized retention-tree groups and clear-cuts adjacent to them. Original spider and carabid assemblages were better maintained after harvests that retained more trees. Thinning maintained forest spiders well. However, gap felling and large retention-tree groups maintained some forest spider and carabid species in the short-term, but negatively affected some species over time. However, use of small retention-tree groups was associated with negative effects on forest spider populations. Studies are needed on the long-term effects of variable retention on terrestrial invertebrates; especially those directed at defining appropriate retention patch size and on the importance of structural diversity provided by variable retention for invertebrate populations. However, the aims of variable retention should be specified first. For example, are retention-tree groups planned to constitute life-boats , stepping-stones or to create structural diversity? Does it suffice that some species are maintained, or do we want to preserve the most sensitive ones, and how are these best defined? Moreover, the ecological benefits and economic costs of modified logging methods should be compared to other approaches aimed at maintaining biodiversity.

Communities of wood-inhabiting fungi : Ecological requirements and responses to forest management and fragmentation

Despite much research on forest biodiversity in Fennoscandia, the exact mechanisms of species declines in dead-wood dependent fungi are still poorly understood. In particular, there is only limited information on why certain fungal species have responded negatively to habitat loss and fragmentation, while others have not. Understanding the mechanisms behind species declines would be essential for the design and development of ecologically effective and scientifically informed conservation measures, and management practices that would promote biodiversity in production forests. In this thesis I study the ecology of polypores and their responses to forest management, with a particular focus on why some species have declined more than others. The data considered in the thesis comprise altogether 98,318 dead-wood objects, with 43,085 observations of 174 fungal species. Out of these, 1,964 observations represent 58 red-listed species. The data were collected from 496 sites, including woodland key habitats, clear-cuts with retention trees, mature managed forests, and natural or natural-like forests in southern Finland and Russian Karelia. I show that the most relevant way of measuring resource availability can differ to a great extent between species seemingly sharing the same resources. It is thus critical to measure the availability of resources in a way that takes into account the ecological requirements of the species. The results show that connectivity at the local, landscape and regional scales is important especially for the highly specialized species, many of which are also red-listed. Habitat loss and fragmentation affect not only species diversity but also the relative abundances of the species and, consequently, species interactions and fungal successional pathways. Changes in species distributions and abundances are likely to affect the food chains in which wood-inhabiting fungi are involved, and thus the functioning of the whole forest ecosystem. The findings of my thesis highlight the importance of protecting well-connected, large and high-quality forest areas to maintain forest biodiversity. Small habitat patches distributed across the landscape are likely to contribute only marginally to protection of red-listed species, especially if habitat quality is not substantially higher than in ordinary managed forest, as is the case with woodland key habitats. Key habitats might supplement the forest protection network if they were delineated larger and if harvesting of individual trees was prohibited in them. Taking the landscape perspective into account in the design and development of conservation measures is critical while striving to halt the decline of forest biodiversity in an ecologically effective manner.

Search for WW and WZ production in lepton plus jets final state at CDF

We present a search for WW and WZ production in final states that contain a charged lepton (electron or muon) and at least two jets, produced in sqrt(s) = 1.96 TeV ppbar collisions at the Fermilab Tevatron, using data corresponding to 1.2 fb-1 of integrated luminosity collected with the CDF II detector. Diboson production in this decay channel has yet to be observed at hadron colliders due to the large single W plus jets background. An artificial neural network has been developed to increase signal sensitivity, as compared with an event selection based on conventional cuts. We set a 95% confidence level upper limit of sigma_{WW}* BR(W->lnu,W->jets)+ sigma_{WZ}*BR(W->lnu,Z->jets)

Search for Long-Lived Massive Charged Particles in 1.96 TeV pp̅ Collisions

We performed a signature-based search for long-lived charged massive particles (CHAMPs) produced in 1.0 $\rm{fb}^{-1}$ of $\bar{p}p$ collisions at $\sqrt{s}=1.96$ TeV, collected with the CDF II detector using a high transverse-momentum ($p_T$) muon trigger. The search used time-of-flight to isolate slowly moving, high-$p_T$ particles. One event passed our selection cuts with an expected background of $1.9 \pm 0.2$ events. We set an upper bound on the production cross section, and, interpreting this result within the context of a stable scalar top quark model, set a lower limit on the particle mass of 249 GeV/$c^2$ at 95% C.L.