New Complexity Results for MAP in Bayesian Networks

This paper presents new results for the (partial) maximum a posteriori (MAP) problem in Bayesian networks, which is the problem of querying the most probable state configuration of some of the network variables given evidence. It is demonstrated that the problem remains hard even in networks with very simple topology, such as binary polytrees and simple trees (including the Naive Bayes structure), which extends previous complexity results. Furthermore, a Fully Polynomial Time Approximation Scheme for MAP in networks with bounded treewidth and bounded number of states per variable is developed. Approximation schemes were thought to be impossible, but here it is shown otherwise under the assumptions just mentioned, which are adopted in most applications.

Solving Limited Memory Influence Diagrams

We present a new algorithm for exactly solving decision making problems represented as influence diagrams. We do not require the usual assumptions of no forgetting and regularity; this allows us to solve problems with simultaneous decisions and limited information. The algorithm is empirically shown to outperform a state-of-the-art algorithm on randomly generated problems of up to 150 variables and 10^64 solutions. We show that the problem is NP-hard even if the underlying graph structure of the problem has small treewidth and the variables take on a bounded number of states, but that a fully polynomial time approximation scheme exists for these cases. Moreover, we show that the bound on the number of states is a necessary condition for any efficient approximation scheme.

The Complexity of Approximately Solving Influence Diagrams

Influence diagrams allow for intuitive and yet precise description of complex situations involving decision making under uncertainty. Unfortunately, most of the problems described by influence diagrams are hard to solve. In this paper we discuss the complexity of approximately solving influence diagrams. We do not assume no-forgetting or regularity, which makes the class of problems we address very broad. Remarkably, we show that when both the treewidth and the cardinality of the variables are bounded the problem admits a fully polynomial-time approximation scheme.

New Results for the MAP Problem in Bayesian Networks

This paper presents new results for the (partial) maximum a posteriori (MAP) problem in Bayesian networks, which is the problem of querying the most probable state configuration of some of the network variables given evidence. First, it is demonstrated that the problem remains hard even in networks with very simple topology, such as binary polytrees and simple trees (including the Naive Bayes structure). Such proofs extend previous complexity results for the problem. Inapproximability results are also derived in the case of trees if the number of states per variable is not bounded. Although the problem is shown to be hard and inapproximable even in very simple scenarios, a new exact algorithm is described that is empirically fast in networks of bounded treewidth and bounded number of states per variable. The same algorithm is used as basis of a Fully Polynomial Time Approximation Scheme for MAP under such assumptions. Approximation schemes were generally thought to be impossible for this problem, but we show otherwise for classes of networks that are important in practice. The algorithms are extensively tested using some well-known networks as well as random generated cases to show their effectiveness.

Anytime Marginal MAP Inference

This paper presents a new anytime algorithm for the marginal MAP problem in graphical models of bounded treewidth. We show asymptotic convergence and theoretical error bounds for any fixed step. Experiments show that it compares well to a state-of-the-art systematic search algorithm.

The Inferential Complexity of Bayesian and Credal Networks

This paper presents new results on the complexity of graph-theoretical models that represent probabilities (Bayesian networks) and that represent interval and set valued probabilities (credal networks). We define a new class of networks with bounded width, and introduce a new decision problem for Bayesian networks, the maximin a posteriori. We present new links between the Bayesian and credal networks, and present new results both for Bayesian networks (most probable explanation with observations, maximin a posteriori) and for credal networks (bounds on probabilities a posteriori, most probable explanation with and without observations, maximum a posteriori).

A Syntactic Approach to Revising Epistemic States with Uncertain Inputs

Revising its beliefs when receiving new information is an important ability of any intelligent system. However, in realistic settings the new input is not always certain. A compelling way of dealing with uncertain input in an agent-based setting is to treat it as unreliable input, which may strengthen or weaken the beliefs of the agent. Recent work focused on the postulates associated with this form of belief change and on finding semantical operators that satisfy these postulates. In this paper we propose a new syntactic approach for this form of belief change and show that it agrees with the semantical definition. This makes it feasible to develop complex agent systems capable of efficiently dealing with unreliable input in a semantically meaningful way. Additionally, we show that imposing restrictions on the input and the beliefs that are entailed allows us to devise a tractable approach suitable for resource-bounded agents or agents where reactiveness is of paramount importance.

A metapopulation model of species boundaries

The majority, if not all, species have a limited geographic range bounded by a distribution edge. Violent ecotones such as sea coasts clearly produce edges for many species; however such ecotones, while sufficient for the formation of an edge, are not always necessary. We demonstrate this by simulation in discrete time of a spatially structured finite size metapopulation subjected to a spatial gradient in per-unit-time population extinction probability together with spatially structured dispersal and recolonisation. We find that relatively sharp edges separating a homeland or main geographical range from an outland or zone of relatively sparse and ephemeral colonisation can form in gradual environmental gradients. The form and placing of the edge is an emergent property of the metapopulation dynamics. The sharpness of the edge declines with increasing dispersal distance, and is dependent on the relative scales of dispersal distance and gradient length. The space over which the edge develops is short relative to the potential species range. The edge is robust against changes in both the shape of the environmental gradient and to a lesser extent to alterations in the kind of dispersal operating. Persistence times in the absence of environmental gradients are virtually independent of the shape of the dispersal function describing migration. The common finding of bell shaped population density distributions across geographic ranges may occur without the strict necessity of a niche mediated response to a spatially autocorrelated environment.

Density functional theory study of mixed-phase TiO2: heterostructures and electronic properties

In this work, density functional theory calculations have been performed to study the geometric, electronic, and energetic properties of two-phase TiO2 composites built by joining two single-phase TiO2 slabs, aiming at verifying possible improvement of the photo-activities of the composites through phase separation of excitons. We find that such desired electronic properties can be determined by several factors. When both the HOMO and LUMO levels of one of the two single-phase TiO2 slabs are higher than the corresponding ones of the other, the composite may have native electronic structures with phase-separated HOMO-LUMO states, especially when the two slabs exhibit highly matched surface lattices. For those pairs of TiO2 slabs with the HOMO and LUMO levels of one phase being within the range of those of the other, though the energetically favored composite give HOMO-LUMO states within one phase, one may still be able to separate them and move the HOMO state to the interface region by destabilizing the interactions between the two slabs.

Facet-Dependent Catalytic Activity of Platinum Nanocrystals for Triiodide Reduction in Dye-Sensitized Solar Cells

Platinum (Pt) nanocrystals have demonstrated to be an effective catalyst in many heterogeneous catalytic processes. However, pioneer facets with highest activity have been reported differently for various reaction systems. Although Pt has been the most important counter electrode material for dye-sensitized solar cells (DSCs), suitable atomic arrangement on the exposed crystal facet of Pt for triiodide reduction is still inexplicable. Using density functional theory, we have investigated the catalytic reaction processes of triiodide reduction over {100}, {111} and {411} facets, indicating that the activity follows the order of Pt(111) > Pt(411) > Pt(100). Further, Pt nanocrystals mainly bounded by {100}, {111} and {411} facets were synthesized and used as counter electrode materials for DSCs. The highest photovoltaic conversion efficiency of Pt(111) in DSCs confirms the predictions of the theoretical study. These findings have deepened the understanding of the mechanism of triiodide reduction at Pt surfaces and further screened the best facet for DSCs successfully.

Testing preference formation in learning design contingent valuation (LDCV) using advanced information and repetitive treatments

Policymakers have largely replaced Single Bounded Discrete Choice (SBDC) valuation by the more statistically efficient repetitive methods; Double Bounded Discrete Choice (DBDC) and Discrete Choice Experiments (DCE) . Repetitive valuation permits classification into rational preferences: (i) a priori well-formed; (ii) consistent non-arbitrary values “discovered” through repetition and experience; (Plott, 1996; List 2003) and irrational preferences; (iii) consistent but arbitrary values as “shaped” by preceding bid level (Tufano, 2010; Ariely et al., 2003) and (iv) inconsistent and arbitrary values. Policy valuations should demonstrate behaviorally rational preferences. We outline novel methods for testing this in DBDC applied to renewable energy premiums in Chile.

Norms of basic elementary operators on algebras of regular operators

We show that if E is an atomic Banach lattice with an ordercontinuous norm, A, B ∈ L^r(E) and M_A,_B is the operator on L^r(E) defined by M_A,_B(T) = AT B then ||M_A,_B||r = ||A||_r||B||_r but that there is no real α > 0 such that ||MA,B || ≥ α ||A||r||B ||r.

Representing Irishness in Belfast’s Gaeltacht Quarter

This paper examines a place-making project in post-conflict Belfast, analyzing efforts to transform an area which has often been used as a byword for militant Irish nationalism and social deprivation into an inclusive, vibrant tourist destination and cultural hub themed around the Irish language (called the "Gaeltacht Quarter‟). The antagonistic and territorial assumptions about place that characterize divided cities now co-exist with global trends towards the commodification of difference as recreation or spectacle, and longstanding struggles over the representation of contested identities are intertwined with the struggle to compete for international tourism and investment. The proliferation of officially themed quarters in many cities across the world reflects the enthusiasm with which planning authorities have embraced the vision of difference as a benign resource for the creation of tourist revenue. Yet, analysis of „quartering‟ processes reveals that such commodification does not neutralise or evade the political potency of naming, representing and delimiting cultural difference. Indeed, this paper argues that such projects offer a valuable insight into the inseparable roles of physical and representational space as both loci and catalysts of contestation in urban conflicts. Bringing together a wide range of public and private interest groups, projects redefining parts of Belfast as distinctive quarters have been explicitly linked with efforts to deterritorialize the city. The creation of bounded, themed spaces as an attempt to leave behind the ethno-sectarian geographical segregation that parts of Belfast still experience has its particular ironies, but is in many ways typical of contemporary trends in urban planning. The Gaeltacht Quarter exemplifies both the importance and the challenge of representation within cities where culturally distinguishing features have acted as markers of violent division, and where negotiations about how to successfully encompass difference necessarily address multiple local and international audiences simultaneously.

From the Right to Life to the Right to Livability: Radically Re-approaching ‘Life’ in Human Rights Politics

This article critically reflects on current mainstream debate on abortion in international human rights discourse and the conception of life underpinning it. The public health focus on access to safe abortion which has dominated this discourse can be detected as committed to a fundamentally liberal idea of bounded and individual subjecthood which mirrors the commitments of the liberal right to life more generally. However, feminist challenges to this frame seeking to advance wider access to reproductive freedoms appear equally underpinned by a liberal conception of life. It is asserted that feminists may offer a more radical challenge to the current impasse in international debate on abortion by engaging with the concept of livability which foregrounds life as an interdependent and conditioned process. The trope of the ‘right to livability’ developed in this article presents a means to reposition the relation between rights and life and facilitate such radical engagement which better attends to the socio-political conditions shaping our interdependent living and being.

Enabling Robust and Efficient Distributed Computation in Dynamic Peer-to-Peer Networks

Motivated by the need for designing efficient and robust fully-distributed computation in highly dynamic networks such as Peer-to-Peer (P2P) networks, we study distributed protocols for constructing and maintaining dynamic network topologies with good expansion properties. Our goal is to maintain a sparse (bounded degree) expander topology despite heavy {\em churn} (i.e., nodes joining and leaving the network continuously over time). We assume that the churn is controlled by an adversary that has complete knowledge and control of what nodes join and leave and at what time and has unlimited computational power, but is oblivious to the random choices made by the algorithm. Our main contribution is a randomized distributed protocol that guarantees with high probability the maintenance of a {\em constant} degree graph with {\em high expansion} even under {\em continuous high adversarial} churn. Our protocol can tolerate a churn rate of up to $O(n/\poly\log(n))$ per round (where $n$ is the stable network size). Our protocol is efficient, lightweight, and scalable, and it incurs only $O(\poly\log(n))$ overhead for topology maintenance: only polylogarithmic (in $n$) bits needs to be processed and sent by each node per round and any node's computation cost per round is also polylogarithmic. The given protocol is a fundamental ingredient that is needed for the design of efficient fully-distributed algorithms for solving fundamental distributed computing problems such as agreement, leader election, search, and storage in highly dynamic P2P networks and enables fast and scalable algorithms for these problems that can tolerate a large amount of churn.