title: Hecke-Kiselman Monoids of Small Cardinality

abstract: In this paper, we give a characterization of digraphs $Q, |Q|\leq 4$ such that the associated Hecke-Kiselman monoid $H_Q$ is finite. In general, a necessary condition for $H_Q$ to be a finite monoid is that $Q$ is acyclic and its Coxeter components are Dynkin diagram. We show, by constructing examples, that such conditions are not sufficient.


title: 3-D modelling of the collimated bipolar outflows of compact planetary nebulae with WR-type central stars

abstract: We present high-resolution, long-slit spectroscopic observations of five compact ($\leq$ 10 arcsec) planetary nebulae located close to the galactic bulge region and for which no high spatial resolution images are available. The data have been drawn from the San Pedro M\'artir kinematic catalogue of galactic planetary nebulae (L\'opez et al. 2012). The central star in four of these objects (M 1-32, M 2-20, M 2-31 and M 3-15) is of WR-type and the fifth object (M 2-42) has a wels type nucleus. These observations reveal the presence in all of them of a dense and thick equatorial torus-like component and high-speed, collimated, bipolar outflows. The code SHAPE is used to investigate the main morpho-kinematic characteristics and reproduce the 3-D structure of these objects assuming a cylindrical velocity field for the bipolar outflows and a homologous expansion law for the torus/ring component. The deprojected expansion velocities of the bipolar outflows are found to be in the range of 65 to 200 km $\rm{s^{-1}}$, whereas the torus/ring component shows much slower expansion velocities, in the range of 15 to 25 km $\rm{s^{-1}}$. It is found that these planetary nebulae have very similar structural components and the differences in their emission line spectra derive mostly from their different projections on the sky. The relation of their morpho-kinematic characteristics with the WR-type nuclei deserves further investigation.


title: Outer Billiards, Digital Filters and Kicked Hamiltonians

abstract: In 1978 Jurgen Moser suggested the outer billiards map (Tangent map) as a discontinuous model of Hamiltonian dynamics. A decade earlier, J.B. Jackson and his colleagues at Bell Labs were trying to understand the source of self-sustaining oscillations in digital filters. Some of the discrete mappings used to describe these filters show a remarkable ability to 'shadow' the Tangent map when the polygon in question is regular. In this paper we describe a specific digital filter map (Df) that appears to have dynamics which are conjugate to the Tangent map for a regular N-gon with N even. When N is odd, there is evidence of another conjugacy between the Tangent map dynamics of N and the matching 2N-gon, so a case like N = 7 can be studied with the Df map in the context of N = 14. This provides a many-fold increase in efficiency, and also allows us to generalize the Tangent map to obtain 'step-k' versions - which have dynamics that are unexplored. We also present some related maps, including Chua and Lin's 3-dimensional version of Df, an Analog to Digital Converter from Orla Feely, a sawtooth version of the Standard Map by Peter Ashwin and various kicked harmonic oscillators. All of these seem to shadow the Tangent map in some form. Mathematica code is provided for all mappings both here and at DynamicsOfPolygons.org.


title: Stock prices assessment: proposal of a new index based on volume weighted historical prices through the use of computer modeling

abstract: The importance of considering the volumes to analyze stock prices movements can be considered as a well-accepted practice in the financial area. However, when we look at the scientific production in this field, we still cannot find a unified model that includes volume and price variations for stock assessment purposes. In this paper we present a computer model that could fulfill this gap, proposing a new index to evaluate stock prices based on their historical prices and volumes traded. Besides the model can be considered mathematically very simple, it was able to improve significantly the performance of agents operating with real financial data. Based on the results obtained, and also on the very intuitive logic of our model, we believe that the index proposed here can be very useful to help investors on the activity of determining ideal price ranges for buying and selling stocks in the financial market.


title: Entanglement Entropy for Singular Surfaces

abstract: We study entanglement entropy for regions with a singular boundary in higher dimensions using the AdS/CFT correspondence and find that various singularities make new universal contributions. When the boundary CFT has an even spacetime dimension, we find that the entanglement entropy of a conical surface contains a term quadratic in the logarithm of the UV cut-off. In four dimensions, the coefficient of this contribution is proportional to the central charge 'c'. A conical singularity in an odd number of spacetime dimensions contributes a term proportional to the logarithm of the UV cut-off. We also study the entanglement entropy for various boundary surfaces with extended singularities. In these cases, similar universal terms may appear depending on the dimension and curvature of the singular locus.

categories: hep-th cond-mat.stat-mech math-ph math.MP


title: Defect formation dynamics during CdTe overlayer growth

abstract: The presence of atomic-scale defects at multilayer interfaces significantly degrades performance in CdTe-based photovoltaic technologies. The ability to accurately predict and understand defect formation mechanisms during overlayer growth is, therefore, a rational approach for improving the efficiencies of CdTe materials. In this work, we utilize a recently developed CdTe bond-order potential (BOP) to enable accurate molecular dynamics (MD) simulations for predicting defect formation during multilayer growth. A detailed comparison of our MD simulations to high-resolution transmission electron microscopy experiments verifies the accuracy and predictive power of our approach. Our simulations further indicate that island growth can reduce the lattice mismatch induced defects. These results highlight the use of predictive MD simulations to gain new insight on defect reduction in CdTe overlayers, which directly addresses efforts to improve these materials.


title: Optically induced nuclear spin polarization in a single GaAs/AlGaAs quantum well probed by a resistance detection method in the fractional quantum Hall regime

abstract: We study the optically pumped nuclear spin polarization in a single GaAs/AlGaAs quantum well in the quantum Hall system. We apply resistive detection via the contact hyperfine interaction, which provides high sensitivity and selectivity, to probe a small amount of polarized nuclear spins in a single well. The properties of the optical nuclear spin polarization are clearly observed. We theoretically discuss the nuclear spin dynamics accompanied with doped electrons to analyze the experimental data. The optical nuclear polarization spectra exhibit electron-spin-resolved lowest Landau level interband transitions. We find that the phonon emission process, which normally assists the optical pumping process, influences the optical nuclear spin polarization. We also discuss that the electron-electron interaction can play an important role in the optical nuclear spin polarization.


title: Boundary diffraction wave integrals for diffraction modeling of external occulters

abstract: An occulter is a large diffracting screen which may be flown in conjunction with a telescope to image extrasolar planets. The edge is shaped to minimize the diffracted light in a region beyond the occulter, and a telescope may be placed in this dark shadow to view an extrasolar system with the starlight removed. Errors in position, orientation, and shape of the occulter will diffract additional light into this region, and a challenge of modeling an occulter system is to accurately and quickly model these effects. We present a fast method for the calculation of electric fields following an occulter, based on the concept of the boundary diffraction wave: the 2D structure of the occulter is reduced to a 1D edge integral which directly incorporates the occulter shape, and which can be easily adjusted to include changes in occulter position and shape, as well as the effects of sources---such as exoplanets---which arrive off-axis to the occulter. The structure of a typical implementation of the algorithm is included.


title: Specialized Orthonormal Frames and Embedding

abstract: We discuss some specializations of the frames of flat orthonormal frame bundles over geometries of indefinite signature, and the resulting symmetries of families of embedded Riemannian or pseudo-Riemannian geometries. The specializations are closed sets of linear constraints on the connection 1-forms of the framing. The embeddings can be isometric, as in minimal surfaces or Regge-Teitelboim gravity, or torsion-free, as in Einstein vacuum gravity. Involutive exterior differential systems are given, and their Cartan character tables calculated to express the well-posedness of the underlying partial differential embedding and specialization equations.


title: Non-homogeneous systems of hydrodynamic type possessing Lax representations

abstract: We consider 1+1 - dimensional non-homogeneous systems of hydrodynamic type that possess Lax representations with movable singularities. We present a construction, which provides a wide class of examples of such systems with arbitrary number of components. In the two-component case a classification is given.


title: Nonlinear Dynamics of Parity-Even Tricritical Gravity in Three and Four Dimensions

abstract: Recently proposed "multicritical" higher-derivative gravities in Anti de Sitter space carry logarithmic representations of the Anti de Sitter isometry group. While generically non-unitary already at the quadratic, free-theory level, in special cases these theories admit a unitary subspace. The simplest example of such behavior is "tricritical" gravity. In this paper, we extend the study of parity-even tricritical gravity in d = 3, 4 to the first nonlinear order. We show that the would-be unitary subspace suffers from a linearization instability and is absent in the full non-linear theory.


title: Extending Monte Carlo Methods to Factor Graphs with Negative and Complex Factors

abstract: The partition function of a factor graph can sometimes be accurately estimated by Monte Carlo methods. In this paper, such methods are extended to factor graphs with negative and complex factors.


title: Inter-subband resistance oscillations in crossed electric and magnetic fields

abstract: Quantum oscillations of nonlinear resistance are investigated in response to electric current and magnetic field applied perpendicular to single GaAs quantum wells with two populated subbands. At small magnetic fields current-induced oscillations appear as Landau-Zener transitions between Landau levels inside the lowest subband. Period of these oscillations is proportional to the magnetic field. At high magnetic fields different kind of quantum oscillations emerges with a period,which is independent of the magnetic field. At a fixed current the oscillations are periodic in inverse magnetic field with a period that is independent of the dc bias. The proposed model considers these oscillations as a result of spatial variations of the energy separation between two subbands induced by the electric current.


title: A classification of right-angled Coxeter groups with no 3-flats and locally connected boundary

abstract: If $(W,S)$ is a right-angled Coxeter system and $W$ has no $\mathbb Z^3$ subgroups, then it is shown that the absence of an elementary separation property in the presentation diagram for $(W,S)$ implies all CAT(0) spaces acted on geometrically by $W$ have locally connected CAT(0) boundary. It was previously known that if the presentation diagram of a general right-angled Coxeter system satisfied the separation property then all CAT(0) spaces acted on geometrically by $W$ have non-locally connected boundary. In particular, this gives a complete classification of the right-angled Coxeter groups with no 3-flats and with locally connected boundary.


title: Evolution of the neutron resonances in AFe2Se2

abstract: Recent experiments on the alkali-intercalated iron selenides have raised questions about the symmetry of the superconducting phase. Random phase approximation calculations of the leading pairing eigenstate for a tight- binding 5-orbital Hubbard-Hund model of AFe2Se2 find that a d-wave (B1g) state evolves into an extended s{\pm} (A1g) state as the system is hole-doped. However, over a range of doping these two states are nearly degenerate. Here, we calculate the imaginary part of the magnetic spin susceptibility \chi"(q,{\omega}) for these gaps and discuss how the evolution of neutron scattering resonances can distinguish between them.


title: Fast and efficient exact synthesis of single qubit unitaries generated by Clifford and T gates

abstract: In this paper, we show the equivalence of the set of unitaries computable by the circuits over the Clifford and T library and the set of unitaries over the ring $\mathbb{Z}[\frac{1}{\sqrt{2}},i]$, in the single-qubit case. We report an efficient synthesis algorithm, with an exact optimality guarantee on the number of Hadamard and T gates used. We conjecture that the equivalence of the sets of unitaries implementable by circuits over the Clifford and T library and unitaries over the ring $\mathbb{Z}[\frac{1}{\sqrt{2}},i]$ holds in the $n$-qubit case.


title: D-Branes at del Pezzo Singularities: Global Embedding and Moduli Stabilisation

abstract: In the context of type IIB string theory we combine moduli stabilisation and model building on branes at del Pezzo singularities in a fully consistent global compactification. By means of toric geometry, we classify all the CY manifolds with 3 < h11 < 6 which admit two identical del Pezzo singularities mapped into each other under the orientifold involution. This effective singularity hosts the visible sector containing the Standard Model while the Kaehler moduli are stabilised via a combination of D-terms, perturbative and non-perturbative effects supported on hidden sectors. We present concrete models where the visible sector, containing the Standard Model, gauge and matter content, is built via fractional D3-branes at del Pezzo singularities and all the Kaehler moduli are fixed providing an explicit realisation of both KKLT and LARGE volume scenarios, the latter with D-term uplifting to de Sitter minima. We perform the consistency checks for global embedding such as tadpole, K-theory charges and Freed-Witten anomaly cancellation. We briefly discuss phenomenological and cosmological implications of our models.


title: Can we predict the global magnetic topology of a pre-main sequence star from its position in the Hertzsprung-Russell diagram?

abstract: ZDI studies have shown that the magnetic fields of T Tauri stars can be significantly more complex than a simple dipole and can vary markedly between sources. We collect and summarize the magnetic field topology information obtained to date and present Hertzsprung-Russell (HR) diagrams for the stars in the sample. Intriguingly, the large scale field topology of a given pre-main sequence (PMS) star is strongly dependent upon the stellar internal structure, with the strength of the dipole component of its multipolar magnetic field decaying rapidly with the development of a radiative core. Using the observational data as a basis, we argue that the general characteristics of the global magnetic field of a PMS star can be determined from its position in the HR diagram. Moving from hotter and more luminous to cooler and less luminous stars across the PMS of the HR diagram, we present evidence for four distinct magnetic topology regimes. Stars with large radiative cores, empirically estimated to be those with a core mass in excess of ~40 per cent of the stellar mass, host highly complex and dominantly non-axisymmetric magnetic fields, while those with smaller radiative cores host axisymmetric fields with field modes of higher order than the dipole dominant (typically, but not always, the octupole). Fully convective stars stars above ~0.5 MSun appear to host dominantly axisymmetric fields with strong (kilo-Gauss) dipole components. Based on similarities between the magnetic properties of PMS stars and main sequence M-dwarfs with similar internal structures, we speculate that a bistable dynamo process operates for lower mass stars (<~0.5 MSun at an age of a few Myr) and that they will be found to host a variety of magnetic field topologies. If the magnetic topology trends across the HR diagram are confirmed they may provide a new method of constraining PMS stellar evolution models.


title: Large-Flip Importance Sampling

abstract: We propose a new Monte Carlo algorithm for complex discrete distributions. The algorithm is motivated by the N-Fold Way, which is an ingenious event-driven MCMC sampler that avoids rejection moves at any specific state. The N-Fold Way can however get "trapped" in cycles. We surmount this problem by modifying the sampling process. This correction does introduce bias, but the bias is subsequently corrected with a carefully engineered importance sampler.


title: Analysis of Semi-Supervised Learning with the Yarowsky Algorithm

abstract: The Yarowsky algorithm is a rule-based semi-supervised learning algorithm that has been successfully applied to some problems in computational linguistics. The algorithm was not mathematically well understood until (Abney 2004) which analyzed some specific variants of the algorithm, and also proposed some new algorithms for bootstrapping. In this paper, we extend Abney's work and show that some of his proposed algorithms actually optimize (an upper-bound on) an objective function based on a new definition of cross-entropy which is based on a particular instantiation of the Bregman distance between probability distributions. Moreover, we suggest some new algorithms for rule-based semi-supervised learning and show connections with harmonic functions and minimum multi-way cuts in graph-based semi-supervised learning.


title: Shift-Invariance Sparse Coding for Audio Classification

abstract: Sparse coding is an unsupervised learning algorithm that learns a succinct high-level representation of the inputs given only unlabeled data; it represents each input as a sparse linear combination of a set of basis functions. Originally applied to modeling the human visual cortex, sparse coding has also been shown to be useful for self-taught learning, in which the goal is to solve a supervised classification task given access to additional unlabeled data drawn from different classes than that in the supervised learning problem. Shift-invariant sparse coding (SISC) is an extension of sparse coding which reconstructs a (usually time-series) input using all of the basis functions in all possible shifts. In this paper, we present an efficient algorithm for learning SISC bases. Our method is based on iteratively solving two large convex optimization problems: The first, which computes the linear coefficients, is an L1-regularized linear least squares problem with potentially hundreds of thousands of variables. Existing methods typically use a heuristic to select a small subset of the variables to optimize, but we present a way to efficiently compute the exact solution. The second, which solves for bases, is a constrained linear least squares problem. By optimizing over complex-valued variables in the Fourier domain, we reduce the coupling between the different variables, allowing the problem to be solved efficiently. We show that SISC's learned high-level representations of speech and music provide useful features for classification tasks within those domains. When applied to classification, under certain conditions the learned features outperform state of the art spectral and cepstral features.


title: Studies in Lower Bounding Probabilities of Evidence using the Markov Inequality

abstract: Computing the probability of evidence even with known error bounds is NP-hard. In this paper we address this hard problem by settling on an easier problem. We propose an approximation which provides high confidence lower bounds on probability of evidence but does not have any guarantees in terms of relative or absolute error. Our proposed approximation is a randomized importance sampling scheme that uses the Markov inequality. However, a straight-forward application of the Markov inequality may lead to poor lower bounds. We therefore propose several heuristic measures to improve its performance in practice. Empirical evaluation of our scheme with state-of- the-art lower bounding schemes reveals the promise of our approach.


title: Convergent Propagation Algorithms via Oriented Trees

abstract: Inference problems in graphical models are often approximated by casting them as constrained optimization problems. Message passing algorithms, such as belief propagation, have previously been suggested as methods for solving these optimization problems. However, there are few convergence guarantees for such algorithms, and the algorithms are therefore not guaranteed to solve the corresponding optimization problem. Here we present an oriented tree decomposition algorithm that is guaranteed to converge to the global optimum of the Tree-Reweighted (TRW) variational problem. Our algorithm performs local updates in the convex dual of the TRW problem - an unconstrained generalized geometric program. Primal updates, also local, correspond to oriented reparametrization operations that leave the distribution intact.


title: Search for Choquet-optimal paths under uncertainty

abstract: Choquet expected utility (CEU) is one of the most sophisticated decision criteria used in decision theory under uncertainty. It provides a generalisation of expected utility enhancing both descriptive and prescriptive possibilities. In this paper, we investigate the use of CEU for path-planning under uncertainty with a special focus on robust solutions. We first recall the main features of the CEU model and introduce some examples showing its descriptive potential. Then we focus on the search for Choquet-optimal paths in multivalued implicit graphs where costs depend on different scenarios. After discussing complexity issues, we propose two different heuristic search algorithms to solve the problem. Finally, numerical experiments are reported, showing the practical efficiency of the proposed algorithms.


title: A new parameter Learning Method for Bayesian Networks with Qualitative Influences

abstract: We propose a new method for parameter learning in Bayesian networks with qualitative influences. This method extends our previous work from networks of binary variables to networks of discrete variables with ordered values. The specified qualitative influences correspond to certain order restrictions on the parameters in the network. These parameters may therefore be estimated using constrained maximum likelihood estimation. We propose an alternative method, based on the isotonic regression. The constrained maximum likelihood estimates are fairly complicated to compute, whereas computation of the isotonic regression estimates only requires the repeated application of the Pool Adjacent Violators algorithm for linear orders. Therefore, the isotonic regression estimator is to be preferred from the viewpoint of computational complexity. Through experiments on simulated and real data, we show that the new learning method is competitive in performance to the constrained maximum likelihood estimator, and that both estimators improve on the standard estimator.


title: Causal Reasoning in Graphical Time Series Models

abstract: We propose a definition of causality for time series in terms of the effect of an intervention in one component of a multivariate time series on another component at some later point in time. Conditions for identifiability, comparable to the back-door and front-door criteria, are presented and can also be verified graphically. Computation of the causal effect is derived and illustrated for the linear case.


title: Bayesian structure learning using dynamic programming and MCMC

abstract: MCMC methods for sampling from the space of DAGs can mix poorly due to the local nature of the proposals that are commonly used. It has been shown that sampling from the space of node orders yields better results [FK03, EW06]. Recently, Koivisto and Sood showed how one can analytically marginalize over orders using dynamic programming (DP) [KS04, Koi06]. Their method computes the exact marginal posterior edge probabilities, thus avoiding the need for MCMC. Unfortunately, there are four drawbacks to the DP technique: it can only use modular priors, it can only compute posteriors over modular features, it is difficult to compute a predictive density, and it takes exponential time and space. We show how to overcome the first three of these problems by using the DP algorithm as a proposal distribution for MCMC in DAG space. We show that this hybrid technique converges to the posterior faster than other methods, resulting in more accurate structure learning and higher predictive likelihoods on test data.


title: Statistical Translation, Heat Kernels and Expected Distances

abstract: High dimensional structured data such as text and images is often poorly understood and misrepresented in statistical modeling. The standard histogram representation suffers from high variance and performs poorly in general. We explore novel connections between statistical translation, heat kernels on manifolds and graphs, and expected distances. These connections provide a new framework for unsupervised metric learning for text documents. Experiments indicate that the resulting distances are generally superior to their more standard counterparts.


title: Learning Probabilistic Relational Dynamics for Multiple Tasks

abstract: The ways in which an agent's actions affect the world can often be modeled compactly using a set of relational probabilistic planning rules. This paper addresses the problem of learning such rule sets for multiple related tasks. We take a hierarchical Bayesian approach, in which the system learns a prior distribution over rule sets. We present a class of prior distributions parameterized by a rule set prototype that is stochastically modified to produce a task-specific rule set. We also describe a coordinate ascent algorithm that iteratively optimizes the task-specific rule sets and the prior distribution. Experiments using this algorithm show that transferring information from related tasks significantly reduces the amount of training data required to predict action effects in blocks-world domains.


title: Probabilistic Models for Anomaly Detection in Remote Sensor Data Streams

abstract: Remote sensors are becoming the standard for observing and recording ecological data in the field. Such sensors can record data at fine temporal resolutions, and they can operate under extreme conditions prohibitive to human access. Unfortunately, sensor data streams exhibit many kinds of errors ranging from corrupt communications to partial or total sensor failures. This means that the raw data stream must be cleaned before it can be used by domain scientists. In our application environment|the H.J. Andrews Experimental Forest|this data cleaning is performed manually. This paper introduces a Dynamic Bayesian Network model for analyzing sensor observations and distinguishing sensor failures from valid data for the case of air temperature measured at 15 minute time resolution. The model combines an accurate distribution of long-term and short-term temperature variations with a single generalized fault model. Experiments with historical data show that the precision and recall of the method is comparable to that of the domain expert. The system is currently being deployed to perform real-time automated data cleaning.


title: Node Splitting: A Scheme for Generating Upper Bounds in Bayesian Networks

abstract: We formulate in this paper the mini-bucket algorithm for approximate inference in terms of exact inference on an approximate model produced by splitting nodes in a Bayesian network. The new formulation leads to a number of theoretical and practical implications. First, we show that branchand- bound search algorithms that use minibucket bounds may operate in a drastically reduced search space. Second, we show that the proposed formulation inspires new minibucket heuristics and allows us to analyze existing heuristics from a new perspective. Finally, we show that this new formulation allows mini-bucket approximations to benefit from recent advances in exact inference, allowing one to significantly increase the reach of these approximations.


title: A Utility Framework for Bounded-Loss Market Makers

abstract: We introduce a class of utility-based market makers that always accept orders at their risk-neutral prices. We derive necessary and sufficient conditions for such market makers to have bounded loss. We prove that hyperbolic absolute risk aversion utility market makers are equivalent to weighted pseudospherical scoring rule market makers. In particular, Hanson's logarithmic scoring rule market maker corresponds to a negative exponential utility market maker in our framework. We describe a third equivalent formulation based on maintaining a cost function that seems most natural for implementation purposes, and we illustrate how to translate among the three equivalent formulations. We examine the tradeoff between the market's liquidity and the market maker's worst-case loss. For a fixed bound on worst-case loss, some market makers exhibit greater liquidity near uniform prices and some exhibit greater liquidity near extreme prices, but no market maker can exhibit uniformly greater liquidity in all regimes. For a fixed minimum liquidity level, we give the lower bound of market maker's worst-case loss under some regularity conditions.


title: Reachability Under Uncertainty

abstract: In this paper we introduce a new network reachability problem where the goal is to find the most reliable path between two nodes in a network, represented as a directed acyclic graph. Individual edges within this network may fail according to certain probabilities, and these failure probabilities may depend on the values of one or more hidden variables. This problem may be viewed as a generalization of shortest-path problems for finding minimum cost paths or Viterbi-type problems for finding highest-probability sequences of states, where the addition of the hidden variables introduces correlations that are not handled by previous algorithms. We give theoretical results characterizing this problem including an NP-hardness proof. We also give an exact algorithm and a more efficient approximation algorithm for this problem.


title: Generalized Polya Urn for Time-varying Dirichlet Process Mixtures

abstract: Dirichlet Process Mixtures (DPMs) are a popular class of statistical models to perform density estimation and clustering. However, when the data available have a distribution evolving over time, such models are inadequate. We introduce here a class of time-varying DPMs which ensures that at each time step the random distribution follows a DPM model. Our model relies on an intuitive and simple generalized Polya urn scheme. Inference is performed using Markov chain Monte Carlo and Sequential Monte Carlo. We demonstrate our model on various applications.


title: Minimax regret based elicitation of generalized additive utilities

abstract: We describe the semantic foundations for elicitation of generalized additively independent (GAI) utilities using the minimax regret criterion, and propose several new query types and strategies for this purpose. Computational feasibility is obtained by exploiting the local GAI structure in the model. Our results provide a practical approach for implementing preference-based constrained configuration optimization as well as effective search in multiattribute product databases.


title: Discovering Patterns in Biological Sequences by Optimal Segmentation

abstract: Computational methods for discovering patterns of local correlations in sequences are important in computational biology. Here we show how to determine the optimal partitioning of aligned sequences into non-overlapping segments such that positions in the same segment are strongly correlated while positions in different segments are not. Our approach involves discovering the hidden variables of a Bayesian network that interact with observed sequences so as to form a set of independent mixture models. We introduce a dynamic program to efficiently discover the optimal segmentation, or equivalently the optimal set of hidden variables. We evaluate our approach on two computational biology tasks. One task is related to the design of vaccines against polymorphic pathogens and the other task involves analysis of single nucleotide polymorphisms (SNPs) in human DNA. We show how common tasks in these problems naturally correspond to inference procedures in the learned models. Error rates of our learned models for the prediction of missing SNPs are up to 1/3 less than the error rates of a state-of-the-art SNP prediction method. Source code is available at www.uwm.edu/~joebock/segmentation.


title: Evaluating influence diagrams with decision circuits

abstract: Although a number of related algorithms have been developed to evaluate influence diagrams, exploiting the conditional independence in the diagram, the exact solution has remained intractable for many important problems. In this paper we introduce decision circuits as a means to exploit the local structure usually found in decision problems and to improve the performance of influence diagram analysis. This work builds on the probabilistic inference algorithms using arithmetic circuits to represent Bayesian belief networks [Darwiche, 2003]. Once compiled, these arithmetic circuits efficiently evaluate probabilistic queries on the belief network, and methods have been developed to exploit both the global and local structure of the network. We show that decision circuits can be constructed in a similar fashion and promise similar benefits.


title: Optimizing Memory-Bounded Controllers for Decentralized POMDPs

abstract: We present a memory-bounded optimization approach for solving infinite-horizon decentralized POMDPs. Policies for each agent are represented by stochastic finite state controllers. We formulate the problem of optimizing these policies as a nonlinear program, leveraging powerful existing nonlinear optimization techniques for solving the problem. While existing solvers only guarantee locally optimal solutions, we show that our formulation produces higher quality controllers than the state-of-the-art approach. We also incorporate a shared source of randomness in the form of a correlation device to further increase solution quality with only a limited increase in space and time. Our experimental results show that nonlinear optimization can be used to provide high quality, concise solutions to decentralized decision problems under uncertainty.


title: A Tractable Approach to Finding Closest Truncated-commute-time Neighbors in Large Graphs

abstract: Recently there has been much interest in graph-based learning, with applications in collaborative filtering for recommender networks, link prediction for social networks and fraud detection. These networks can consist of millions of entities, and so it is very important to develop highly efficient techniques. We are especially interested in accelerating random walk approaches to compute some very interesting proximity measures of these kinds of graphs. These measures have been shown to do well empirically (Liben-Nowell & Kleinberg, 2003; Brand, 2005). We introduce a truncated variation on a well-known measure, namely commute times arising from random walks on graphs. We present a very novel algorithm to compute all interesting pairs of approximate nearest neighbors in truncated commute times, without computing it between all pairs. We show results on both simulated and real graphs of size up to 100; 000 entities, which indicate near-linear scaling in computation time.


title: Reasoning at the Right Time Granularity

abstract: Most real-world dynamic systems are composed of different components that often evolve at very different rates. In traditional temporal graphical models, such as dynamic Bayesian networks, time is modeled at a fixed granularity, generally selected based on the rate at which the fastest component evolves. Inference must then be performed at this fastest granularity, potentially at significant computational cost. Continuous Time Bayesian Networks (CTBNs) avoid time-slicing in the representation by modeling the system as evolving continuously over time. The expectation-propagation (EP) inference algorithm of Nodelman et al. (2005) can then vary the inference granularity over time, but the granularity is uniform across all parts of the system, and must be selected in advance. In this paper, we provide a new EP algorithm that utilizes a general cluster graph architecture where clusters contain distributions that can overlap in both space (set of variables) and time. This architecture allows different parts of the system to be modeled at very different time granularities, according to their current rate of evolution. We also provide an information-theoretic criterion for dynamically re-partitioning the clusters during inference to tune the level of approximation to the current rate of evolution. This avoids the need to hand-select the appropriate granularity, and allows the granularity to adapt as information is transmitted across the network. We present experiments demonstrating that this approach can result in significant computational savings.


title: Mixture-of-Parents Maximum Entropy Markov Models

abstract: We present the mixture-of-parents maximum entropy Markov model (MoP-MEMM), a class of directed graphical models extending MEMMs. The MoP-MEMM allows tractable incorporation of long-range dependencies between nodes by restricting the conditional distribution of each node to be a mixture of distributions given the parents. We show how to efficiently compute the exact marginal posterior node distributions, regardless of the range of the dependencies. This enables us to model non-sequential correlations present within text documents, as well as between interconnected documents, such as hyperlinked web pages. We apply the MoP-MEMM to a named entity recognition task and a web page classification task. In each, our model shows significant improvement over the basic MEMM, and is competitive with other long-range sequence models that use approximate inference.


title: Causal Bounds and Instruments

abstract: Instrumental variables have proven useful, in particular within the social sciences and economics, for making inference about the causal effect of a random variable, B, on another random variable, C, in the presence of unobserved confounders. In the case where relationships are linear, causal effects can be identified exactly from studying the regression of C on A and the regression of B on A, where A is the instrument. In the more general case, bounds have been developed in the literature for the causal effect of B on C, given observational data on the joint distribution of C, B and A. Using an approach based on the analysis of convex polytopes, we develop bounds for the same causal effect when given data on (C,A) and (B,A) only. The bounds developed are thus in direct analogy to the standard use of instruments in econometrics, but we make no assumption of linearity. Use of the bounds is illustrated for experiments with partial compliance. The bounds are, for example, relevant in genetic epidemiology, where the 'Mendelian instrument' S represents a genotype, and where joint data on all of C, B and A may rarely be available but studies involving pairs of these may be abundant. Other examples of bounding causal effects are considered to show that the method applies to DAGs in general, subject to certain conditions.


title: Reading Dependencies from Polytree-Like Bayesian Networks

abstract: We present a graphical criterion for reading dependencies from the minimal directed independence map G of a graphoid p when G is a polytree and p satisfies composition and weak transitivity. We prove that the criterion is sound and complete. We argue that assuming composition and weak transitivity is not too restrictive.


title: Apprenticeship Learning using Inverse Reinforcement Learning and Gradient Methods

abstract: In this paper we propose a novel gradient algorithm to learn a policy from an expert's observed behavior assuming that the expert behaves optimally with respect to some unknown reward function of a Markovian Decision Problem. The algorithm's aim is to find a reward function such that the resulting optimal policy matches well the expert's observed behavior. The main difficulty is that the mapping from the parameters to policies is both nonsmooth and highly redundant. Resorting to subdifferentials solves the first difficulty, while the second one is over- come by computing natural gradients. We tested the proposed method in two artificial domains and found it to be more reliable and efficient than some previous methods.


title: Consensus ranking under the exponential model

abstract: We analyze the generalized Mallows model, a popular exponential model over rankings. Estimating the central (or consensus) ranking from data is NP-hard. We obtain the following new results: (1) We show that search methods can estimate both the central ranking pi0 and the model parameters theta exactly. The search is n! in the worst case, but is tractable when the true distribution is concentrated around its mode; (2) We show that the generalized Mallows model is jointly exponential in (pi0; theta), and introduce the conjugate prior for this model class; (3) The sufficient statistics are the pairwise marginal probabilities that item i is preferred to item j. Preliminary experiments confirm the theoretical predictions and compare the new algorithm and existing heuristics.


title: AND/OR Multi-Valued Decision Diagrams (AOMDDs) for Weighted Graphical Models

abstract: Compiling graphical models has recently been under intense investigation, especially for probabilistic modeling and processing. We present here a novel data structure for compiling weighted graphical models (in particular, probabilistic models), called AND/OR Multi-Valued Decision Diagram (AOMDD). This is a generalization of our previous work on constraint networks, to weighted models. The AOMDD is based on the frameworks of AND/OR search spaces for graphical models, and Ordered Binary Decision Diagrams (OBDD). The AOMDD is a canonical representation of a graphical model, and its size and compilation time are bounded exponentially by the treewidth of the graph, rather than pathwidth as is known for OBDDs. We discuss a Variable Elimination schedule for compilation, and present the general APPLY algorithm that combines two weighted AOMDDs, and also present a search based method for compilation method. The preliminary experimental evaluation is quite encouraging, showing the potential of the AOMDD data structure.


title: Collaborative Filtering and the Missing at Random Assumption

abstract: Rating prediction is an important application, and a popular research topic in collaborative filtering. However, both the validity of learning algorithms, and the validity of standard testing procedures rest on the assumption that missing ratings are missing at random (MAR). In this paper we present the results of a user study in which we collect a random sample of ratings from current users of an online radio service. An analysis of the rating data collected in the study shows that the sample of random ratings has markedly different properties than ratings of user-selected songs. When asked to report on their own rating behaviour, a large number of users indicate they believe their opinion of a song does affect whether they choose to rate that song, a violation of the MAR condition. Finally, we present experimental results showing that incorporating an explicit model of the missing data mechanism can lead to significant improvements in prediction performance on the random sample of ratings.


title: Best-First AND/OR Search for Most Probable Explanations

abstract: The paper evaluates the power of best-first search over AND/OR search spaces for solving the Most Probable Explanation (MPE) task in Bayesian networks. The main virtue of the AND/OR representation of the search space is its sensitivity to the structure of the problem, which can translate into significant time savings. In recent years depth-first AND/OR Branch-and- Bound algorithms were shown to be very effective when exploring such search spaces, especially when using caching. Since best-first strategies are known to be superior to depth-first when memory is utilized, exploring the best-first control strategy is called for. The main contribution of this paper is in showing that a recent extension of AND/OR search algorithms from depth-first Branch-and-Bound to best-first is indeed very effective for computing the MPE in Bayesian networks. We demonstrate empirically the superiority of the best-first search approach on various probabilistic networks.


title: Determining the Number of Non-Spurious Arcs in a Learned DAG Model: Investigation of a Bayesian and a Frequentist Approach

abstract: In many application domains, such as computational biology, the goal of graphical model structure learning is to uncover discrete relationships between entities. For example, in our problem of interest concerning HIV vaccine design, we want to infer which HIV peptides interact with which immune system molecules (HLA molecules). For problems of this nature, we are interested in determining the number of nonspurious arcs in a learned graphical model. We describe both a Bayesian and frequentist approach to this problem. In the Bayesian approach, we use the posterior distribution over model structures to compute the expected number of true arcs in a learned model. In the frequentist approach, we develop a method based on the concept of the False Discovery Rate. On synthetic data sets generated from models similar to the ones learned, we find that both the Bayesian and frequentist approaches yield accurate estimates of the number of non-spurious arcs. In addition, we speculate that the frequentist approach, which is non-parametric, may outperform the parametric Bayesian approach in situations where the models learned are less representative of the data. Finally, we apply the frequentist approach to our problem of HIV vaccine design.


title: Nonparametric Bayes Pachinko Allocation

abstract: Recent advances in topic models have explored complicated structured distributions to represent topic correlation. For example, the pachinko allocation model (PAM) captures arbitrary, nested, and possibly sparse correlations between topics using a directed acyclic graph (DAG). While PAM provides more flexibility and greater expressive power than previous models like latent Dirichlet allocation (LDA), it is also more difficult to determine the appropriate topic structure for a specific dataset. In this paper, we propose a nonparametric Bayesian prior for PAM based on a variant of the hierarchical Dirichlet process (HDP). Although the HDP can capture topic correlations defined by nested data structure, it does not automatically discover such correlations from unstructured data. By assuming an HDP-based prior for PAM, we are able to learn both the number of topics and how the topics are correlated. We evaluate our model on synthetic and real-world text datasets, and show that nonparametric PAM achieves performance matching the best of PAM without manually tuning the number of topics.


title: Learning Bayesian Network Structure from Correlation-Immune Data

abstract: Searching the complete space of possible Bayesian networks is intractable for problems of interesting size, so Bayesian network structure learning algorithms, such as the commonly used Sparse Candidate algorithm, employ heuristics. However, these heuristics also restrict the types of relationships that can be learned exclusively from data. They are unable to learn relationships that exhibit "correlation-immunity", such as parity. To learn Bayesian networks in the presence of correlation-immune relationships, we extend the Sparse Candidate algorithm with a technique called "skewing". This technique uses the observation that relationships that are correlation-immune under a specific input distribution may not be correlation-immune under another, sufficiently different distribution. We show that by extending Sparse Candidate with this technique we are able to discover relationships between random variables that are approximately correlation-immune, with a significantly lower computational cost than the alternative of considering multiple parents of a node at a time.


title: Evaluation of the Causal Effect of Control Plans in Nonrecursive Structural Equation Models

abstract: When observational data is available from practical studies and a directed cyclic graph for how various variables affect each other is known based on substantive understanding of the process, we consider a problem in which a control plan of a treatment variable is conducted in order to bring a response variable close to a target value with variation reduction. We formulate an optimal control plan concerning a certain treatment variable through path coefficients in the framework of linear nonrecursive structural equation models. Based on the formulation, we clarify the properties of causal effects when conducting a control plan. The results enable us to evaluate the effect of a control plan on the variance from observational data.


title: Survey Propagation Revisited

abstract: Survey propagation (SP) is an exciting new technique that has been remarkably successful at solving very large hard combinatorial problems, such as determining the satisfiability of Boolean formulas. In a promising attempt at understanding the success of SP, it was recently shown that SP can be viewed as a form of belief propagation, computing marginal probabilities over certain objects called covers of a formula. This explanation was, however, shortly dismissed by experiments suggesting that non-trivial covers simply do not exist for large formulas. In this paper, we show that these experiments were misleading: not only do covers exist for large hard random formulas, SP is surprisingly accurate at computing marginals over these covers despite the existence of many cycles in the formulas. This re-opens a potentially simpler line of reasoning for understanding SP, in contrast to some alternative lines of explanation that have been proposed assuming covers do not exist.


title: On Discarding, Caching, and Recalling Samples in Active Learning

abstract: We address challenges of active learning under scarce informational resources in non-stationary environments. In real-world settings, data labeled and integrated into a predictive model may become invalid over time. However, the data can become informative again with switches in context and such changes may indicate unmodeled cyclic or other temporal dynamics. We explore principles for discarding, caching, and recalling labeled data points in active learning based on computations of value of information. We review key concepts and study the value of the methods via investigations of predictive performance and costs of acquiring data for simulated and real-world data sets.


title: Polynomial Constraints in Causal Bayesian Networks

abstract: We use the implicitization procedure to generate polynomial equality constraints on the set of distributions induced by local interventions on variables governed by a causal Bayesian network with hidden variables. We show how we may reduce the complexity of the implicitization problem and make the problem tractable in certain causal Bayesian networks. We also show some preliminary results on the algebraic structure of polynomial constraints. The results have applications in distinguishing between causal models and in testing causal models with combined observational and experimental data.


title: Template Based Inference in Symmetric Relational Markov Random Fields

abstract: Relational Markov Random Fields are a general and flexible framework for reasoning about the joint distribution over attributes of a large number of interacting entities. The main computational difficulty in learning such models is inference. Even when dealing with complete data, where one can summarize a large domain by sufficient statistics, learning requires one to compute the expectation of the sufficient statistics given different parameter choices. The typical solution to this problem is to resort to approximate inference procedures, such as loopy belief propagation. Although these procedures are quite efficient, they still require computation that is on the order of the number of interactions (or features) in the model. When learning a large relational model over a complex domain, even such approximations require unrealistic running time. In this paper we show that for a particular class of relational MRFs, which have inherent symmetry, we can perform the inference needed for learning procedures using a template-level belief propagation. This procedure's running time is proportional to the size of the relational model rather than the size of the domain. Moreover, we show that this computational procedure is equivalent to sychronous loopy belief propagation. This enables a dramatic speedup in inference and learning time. We use this procedure to learn relational MRFs for capturing the joint distribution of large protein-protein interaction networks.


title: Accuracy Bounds for Belief Propagation

abstract: The belief propagation (BP) algorithm is widely applied to perform approximate inference on arbitrary graphical models, in part due to its excellent empirical properties and performance. However, little is known theoretically about when this algorithm will perform well. Using recent analysis of convergence and stability properties in BP and new results on approximations in binary systems, we derive a bound on the error in BP's estimates for pairwise Markov random fields over discrete valued random variables. Our bound is relatively simple to compute, and compares favorably with a previous method of bounding the accuracy of BP.


title: Fast Nonparametric Conditional Density Estimation

abstract: Conditional density estimation generalizes regression by modeling a full density f(yjx) rather than only the expected value E(yjx). This is important for many tasks, including handling multi-modality and generating prediction intervals. Though fundamental and widely applicable, nonparametric conditional density estimators have received relatively little attention from statisticians and little or none from the machine learning community. None of that work has been applied to greater than bivariate data, presumably due to the computational difficulty of data-driven bandwidth selection. We describe the double kernel conditional density estimator and derive fast dual-tree-based algorithms for bandwidth selection using a maximum likelihood criterion. These techniques give speedups of up to 3.8 million in our experiments, and enable the first applications to previously intractable large multivariate datasets, including a redshift prediction problem from the Sloan Digital Sky Survey.


title: Making life better one large system at a time: Challenges for UAI research

abstract: The rapid growth and diversity in service offerings and the ensuing complexity of information technology ecosystems present numerous management challenges (both operational and strategic). Instrumentation and measurement technology is, by and large, keeping pace with this development and growth. However, the algorithms, tools, and technology required to transform the data into relevant information for decision making are not. The claim in this paper (and the invited talk) is that the line of research conducted in Uncertainty in Artificial Intelligence is very well suited to address the challenges and close this gap. I will support this claim and discuss open problems using recent examples in diagnosis, model discovery, and policy optimization on three real life distributed systems.


title: Ranking Under Uncertainty

abstract: Ranking objects is a simple and natural procedure for organizing data. It is often performed by assigning a quality score to each object according to its relevance to the problem at hand. Ranking is widely used for object selection, when resources are limited and it is necessary to select a subset of most relevant objects for further processing. In real world situations, the object's scores are often calculated from noisy measurements, casting doubt on the ranking reliability. We introduce an analytical method for assessing the influence of noise levels on the ranking reliability. We use two similarity measures for reliability evaluation, Top-K-List overlap and Kendall's tau measure, and show that the former is much more sensitive to noise than the latter. We apply our method to gene selection in a series of microarray experiments of several cancer types. The results indicate that the reliability of the lists obtained from these experiments is very poor, and that experiment sizes which are necessary for attaining reasonably stable Top-K-Lists are much larger than those currently available. Simulations support our analytical results.


title: Learning Selectively Conditioned Forest Structures with Applications to DBNs and Classification

abstract: Dealing with uncertainty in Bayesian Network structures using maximum a posteriori (MAP) estimation or Bayesian Model Averaging (BMA) is often intractable due to the superexponential number of possible directed, acyclic graphs. When the prior is decomposable, two classes of graphs where efficient learning can take place are tree structures, and fixed-orderings with limited in-degree. We show how MAP estimates and BMA for selectively conditioned forests (SCF), a combination of these two classes, can be computed efficiently for ordered sets of variables. We apply SCFs to temporal data to learn Dynamic Bayesian Networks having an intra-timestep forest and inter-timestep limited in-degree structure, improving model accuracy over DBNs without the combination of structures. We also apply SCFs to Bayes Net classification to learn selective forest augmented Naive Bayes classifiers. We argue that the built-in feature selection of selective augmented Bayes classifiers makes them preferable to similar non-selective classifiers based on empirical evidence.


title: A Characterization of Markov Equivalence Classes for Directed Acyclic Graphs with Latent Variables

abstract: Different directed acyclic graphs (DAGs) may be Markov equivalent in the sense that they entail the same conditional independence relations among the observed variables. Meek (1995) characterizes Markov equivalence classes for DAGs (with no latent variables) by presenting a set of orientation rules that can correctly identify all arrow orientations shared by all DAGs in a Markov equivalence class, given a member of that class. For DAG models with latent variables, maximal ancestral graphs (MAGs) provide a neat representation that facilitates model search. Earlier work (Ali et al. 2005) has identified a set of orientation rules sufficient to construct all arrowheads common to a Markov equivalence class of MAGs. In this paper, we provide extra rules sufficient to construct all common tails as well. We end up with a set of orientation rules sound and complete for identifying commonalities across a Markov equivalence class of MAGs, which is particularly useful for causal inference.


title: Bayesian Active Distance Metric Learning

abstract: Distance metric learning is an important component for many tasks, such as statistical classification and content-based image retrieval. Existing approaches for learning distance metrics from pairwise constraints typically suffer from two major problems. First, most algorithms only offer point estimation of the distance metric and can therefore be unreliable when the number of training examples is small. Second, since these algorithms generally select their training examples at random, they can be inefficient if labeling effort is limited. This paper presents a Bayesian framework for distance metric learning that estimates a posterior distribution for the distance metric from labeled pairwise constraints. We describe an efficient algorithm based on the variational method for the proposed Bayesian approach. Furthermore, we apply the proposed Bayesian framework to active distance metric learning by selecting those unlabeled example pairs with the greatest uncertainty in relative distance. Experiments in classification demonstrate that the proposed framework achieves higher classification accuracy and identifies more informative training examples than the non-Bayesian approach and state-of-the-art distance metric learning algorithms.


title: More-or-Less CP-Networks

abstract: Preferences play an important role in our everyday lives. CP-networks, or CP-nets in short, are graphical models for representing conditional qualitative preferences under ceteris paribus ("all else being equal") assumptions. Despite their intuitive nature and rich representation, dominance testing with CP-nets is computationally complex, even when the CP-nets are restricted to binary-valued preferences. Tractable algorithms exist for binary CP-nets, but these algorithms are incomplete for multi-valued CPnets. In this paper, we identify a class of multivalued CP-nets, which we call more-or-less CPnets, that have the same computational complexity as binary CP-nets. More-or-less CP-nets exploit the monotonicity of the attribute values and use intervals to aggregate values that induce similar preferences. We then present a search control rule for dominance testing that effectively prunes the search space while preserving completeness.


title: Importance Sampling via Variational Optimization

abstract: Computing the exact likelihood of data in large Bayesian networks consisting of thousands of vertices is often a difficult task. When these models contain many deterministic conditional probability tables and when the observed values are extremely unlikely even alternative algorithms such as variational methods and stochastic sampling often perform poorly. We present a new importance sampling algorithm for Bayesian networks which is based on variational techniques. We use the updates of the importance function to predict whether the stochastic sampling converged above or below the true likelihood, and change the proposal distribution accordingly. The validity of the method and its contribution to convergence is demonstrated on hard networks of large genetic linkage analysis tasks.


title: MAP Estimation, Linear Programming and Belief Propagation with Convex Free Energies

abstract: Finding the most probable assignment (MAP) in a general graphical model is known to be NP hard but good approximations have been attained with max-product belief propagation (BP) and its variants. In particular, it is known that using BP on a single-cycle graph or tree reweighted BP on an arbitrary graph will give the MAP solution if the beliefs have no ties. In this paper we extend the setting under which BP can be used to provably extract the MAP. We define Convex BP as BP algorithms based on a convex free energy approximation and show that this class includes ordinary BP with single-cycle, tree reweighted BP and many other BP variants. We show that when there are no ties, fixed-points of convex max-product BP will provably give the MAP solution. We also show that convex sum-product BP at sufficiently small temperatures can be used to solve linear programs that arise from relaxing the MAP problem. Finally, we derive a novel condition that allows us to derive the MAP solution even if some of the convex BP beliefs have ties. In experiments, we show that our theorems allow us to find the MAP in many real-world instances of graphical models where exact inference using junction-tree is impossible.


title: Policy Iteration for Relational MDPs

abstract: Relational Markov Decision Processes are a useful abstraction for complex reinforcement learning problems and stochastic planning problems. Recent work developed representation schemes and algorithms for planning in such problems using the value iteration algorithm. However, exact versions of more complex algorithms, including policy iteration, have not been developed or analyzed. The paper investigates this potential and makes several contributions. First we observe two anomalies for relational representations showing that the value of some policies is not well defined or cannot be calculated for restricted representation schemes used in the literature. On the other hand, we develop a variant of policy iteration that can get around these anomalies. The algorithm includes an aspect of policy improvement in the process of policy evaluation and thus differs from the original algorithm. We show that despite this difference the algorithm converges to the optimal policy.


title: Constrained Automated Mechanism Design for Infinite Games of Incomplete Information

abstract: We present a functional framework for automated mechanism design based on a two-stage game model of strategic interaction between the designer and the mechanism participants, and apply it to several classes of two-player infinite games of incomplete information. At the core of our framework is a black-box optimization algorithm which guides the selection process of candidate mechanisms. Our approach yields optimal or nearly optimal mechanisms in several application domains using various objective functions. By comparing our results with known optimal mechanisms, and in some cases improving on the best known mechanisms, we provide evidence that ours is a promising approach to parametric design of indirect mechanisms.


title: A Criterion for Parameter Identification in Structural Equation Models

abstract: This paper deals with the problem of identifying direct causal effects in recursive linear structural equation models. The paper establishes a sufficient criterion for identifying individual causal effects and provides a procedure computing identified causal effects in terms of observed covariance matrix.


title: Imitation Learning with a Value-Based Prior

abstract: The goal of imitation learning is for an apprentice to learn how to behave in a stochastic environment by observing a mentor demonstrating the correct behavior. Accurate prior knowledge about the correct behavior can reduce the need for demonstrations from the mentor. We present a novel approach to encoding prior knowledge about the correct behavior, where we assume that this prior knowledge takes the form of a Markov Decision Process (MDP) that is used by the apprentice as a rough and imperfect model of the mentor's behavior. Specifically, taking a Bayesian approach, we treat the value of a policy in this modeling MDP as the log prior probability of the policy. In other words, we assume a priori that the mentor's behavior is likely to be a high value policy in the modeling MDP, though quite possibly different from the optimal policy. We describe an efficient algorithm that, given a modeling MDP and a set of demonstrations by a mentor, provably converges to a stationary point of the log posterior of the mentor's policy, where the posterior is computed with respect to the "value based" prior. We also present empirical evidence that this prior does in fact speed learning of the mentor's policy, and is an improvement in our experiments over similar previous methods.


title: Improved Dynamic Schedules for Belief Propagation

abstract: Belief propagation and its variants are popular methods for approximate inference, but their running time and even their convergence depend greatly on the schedule used to send the messages. Recently, dynamic update schedules have been shown to converge much faster on hard networks than static schedules, namely the residual BP schedule of Elidan et al. [2006]. But that RBP algorithm wastes message updates: many messages are computed solely to determine their priority, and are never actually performed. In this paper, we show that estimating the residual, rather than calculating it directly, leads to significant decreases in the number of messages required for convergence, and in the total running time. The residual is estimated using an upper bound based on recent work on message errors in BP. On both synthetic and real-world networks, this dramatically decreases the running time of BP, in some cases by a factor of five, without affecting the quality of the solution.


title: Markov Logic in Infinite Domains

abstract: Combining first-order logic and probability has long been a goal of AI. Markov logic (Richardson & Domingos, 2006) accomplishes this by attaching weights to first-order formulas and viewing them as templates for features of Markov networks. Unfortunately, it does not have the full power of first-order logic, because it is only defined for finite domains. This paper extends Markov logic to infinite domains, by casting it in the framework of Gibbs measures (Georgii, 1988). We show that a Markov logic network (MLN) admits a Gibbs measure as long as each ground atom has a finite number of neighbors. Many interesting cases fall in this category. We also show that an MLN admits a unique measure if the weights of its non-unit clauses are small enough. We then examine the structure of the set of consistent measures in the non-unique case. Many important phenomena, including systems with phase transitions, are represented by MLNs with non-unique measures. We relate the problem of satisfiability in first-order logic to the properties of MLN measures, and discuss how Markov logic relates to previous infinite models.


title: On Sensitivity of the MAP Bayesian Network Structure to the Equivalent Sample Size Parameter

abstract: BDeu marginal likelihood score is a popular model selection criterion for selecting a Bayesian network structure based on sample data. This non-informative scoring criterion assigns same score for network structures that encode same independence statements. However, before applying the BDeu score, one must determine a single parameter, the equivalent sample size alpha. Unfortunately no generally accepted rule for determining the alpha parameter has been suggested. This is disturbing, since in this paper we show through a series of concrete experiments that the solution of the network structure optimization problem is highly sensitive to the chosen alpha parameter value. Based on these results, we are able to give explanations for how and why this phenomenon happens, and discuss ideas for solving this problem.


title: What Counterfactuals Can Be Tested

abstract: Counterfactual statements, e.g., "my headache would be gone had I taken an aspirin" are central to scientific discourse, and are formally interpreted as statements derived from "alternative worlds". However, since they invoke hypothetical states of affairs, often incompatible with what is actually known or observed, testing counterfactuals is fraught with conceptual and practical difficulties. In this paper, we provide a complete characterization of "testable counterfactuals," namely, counterfactual statements whose probabilities can be inferred from physical experiments. We provide complete procedures for discerning whether a given counterfactual is testable and, if so, expressing its probability in terms of experimental data.


title: Improved Memory-Bounded Dynamic Programming for Decentralized POMDPs

abstract: Memory-Bounded Dynamic Programming (MBDP) has proved extremely effective in solving decentralized POMDPs with large horizons. We generalize the algorithm and improve its scalability by reducing the complexity with respect to the number of observations from exponential to polynomial. We derive error bounds on solution quality with respect to this new approximation and analyze the convergence behavior. To evaluate the effectiveness of the improvements, we introduce a new, larger benchmark problem. Experimental results show that despite the high complexity of decentralized POMDPs, scalable solution techniques such as MBDP perform surprisingly well.


title: ExELS: an exoplanet legacy science proposal for the ESA Euclid mission I. Cold exoplanets

abstract: Euclid is the second M-class mission of the ESA Cosmic Vision programme, with the principal science goal of studying dark energy. Euclid is also expected to undertake additional Legacy Science programmes. One proposal is the Exoplanet Euclid Legacy Survey (ExELS) which will be the first survey able to measure the abundance of exoplanets down to Earth mass for host separations from ~1AU out to the free-floating (unbound) regime. The cold and free-floating exoplanet regimes represent a crucial discovery space for testing planet formation theories. ExELS will use the gravitational microlensing technique and will detect 1000 microlensing events per month over 1.6 deg^2 of the Galactic bulge. We assess how many of these events will have detectable planetary signatures using a detailed multi-wavelength microlensing simulator (MABuLS) which incorporates the Besancon Galactic model with 3D extinction. MABuLS is the first theoretical simulation of microlensing to treat the effects of point spread function (PSF) blending self-consistently with the underlying Galactic model. We use MABuLS, together with current numerical models for the Euclid PSFs, to explore a number of designs and de-scope options for ExELS, including the exoplanet yield as a function of filter choice and slewing time, and the effect of systematic photometry errors. Using conservative extrapolations of current empirical exoplanet mass functions determined from ground-based microlensing and radial velocity surveys, ExELS can expect to detect a few hundred cold exoplanets around mainly G, K and M-type stellar hosts, including ~45 Earth-mass planets and ~6 Mars-mass planets for an observing programme totalling 10 months. ExELS will be capable of measuring the cold exoplanet mass function down to Earth mass or below, with orbital separations from ~1AU to the free-floating regime. (Abridged)


title: Quantum theory of two-photon interference

abstract: In this paper, we study two-photon interference with the approach of photon quantum theory, with specific attention to the two-photon interference experiment carried out by Milena D'Angelo et al. (Phys. Rev. Lett 87:013602, 2001). We find the theoretical result is accordance with experiment data.


title: Limited Urban Growth: London's Street Network Dynamics since the 18th Century

abstract: We investigate the growth dynamics of Greater London defined by the administrative boundary of the Greater London Authority, based on the evolution of its street network during the last two centuries. This is done by employing a unique dataset, consisting of the planar graph representation of nine time slices of Greater London's road network spanning 224 years, from 1786 to 2010. Within this time-frame, we address the concept of the metropolitan area or city in physical terms, in that urban evolution reveals observable transitions in the distribution of relevant geometrical properties. Given that London has a hard boundary enforced by its long-standing green belt, we show that its street network dynamics can be described as a fractal space-filling phenomena up to a capacitated limit, whence its growth can be predicted with a striking level of accuracy. This observation is confirmed by the analytical calculation of key topological properties of the planar graph, such as the topological growth of the network and its average connectivity. This study thus represents an example of a strong violation of Gibrat's law. In particular, we are able to show analytically how London evolves from a more loop-like structure, typical of planned cities, toward a more tree-like structure, typical of self-organized cities. These observations are relevant to the discourse on sustainable urban planning with respect to the control of urban sprawl in many large cities, which have developed under the conditions of spatial constraints imposed by green belts and hard urban boundaries.


title: A note on the (h,q)-Zeta type function with weight alpha

abstract: The objective of this paper is to derive symmetric property of (h,q)-Zeta function with weight alpha. By using this property, we give some interesting identities for (h,q)-Genocchi polynomials with weight alpha. As a result, our applications possess a number of interesting property which we state in this paper.


title: Turbulent Kinetic Energy Spectra of Solar Convection from NST Observations and Realistic MHD Simulations

abstract: Turbulent properties of the quiet Sun represent the basic state of surface conditions, and a background for various processes of solar activity. Therefore understanding of properties and dynamics of this `basic' state is important for investigation of more complex phenomena, formation and development of observed phenomena in the photosphere and atmosphere. For characterization of the turbulent properties we compare kinetic energy spectra on granular and sub-granular scales obtained from infrared TiO observations with the New Solar Telescope (Big Bear Solar Observatory) and from 3D radiative MHD numerical simulations ('SolarBox' code). We find that the numerical simulations require a high spatial resolution with 10 - 25 km grid-step in order to reproduce the inertial (Kolmogorov) turbulence range. The observational data require an averaging procedure to remove noise and potential instrumental artifacts. The resulting kinetic energy spectra show a good agreement between the simulations and observations, opening new perspectives for detailed joint analysis of more complex turbulent phenomena on the Sun, and possibly on other stars. In addition, using the simulations and observations we investigate effects of background magnetic field, which is concentrated in self-organized complicated structures in intergranular lanes, and find an increase of the small-scale turbulence energy and its decrease at larger scales due to magnetic field effects.


title: Yukawa Unification and the Superpartner Mass Scale

abstract: Naturalness in supersymmetry (SUSY) is under siege by increasingly stringent LHC constraints, but natural electroweak symmetry breaking still remains the most powerful motivation for superpartner masses within experimental reach. If naturalness is the wrong criterion then what determines the mass scale of the superpartners? We motivate supersymmetry by (1) gauge coupling unification, (2) dark matter, and (3) precision b-tau Yukawa unification. We show that for an LSP that is a bino-Higgsino admixture, these three requirements lead to an upper-bound on the stop and sbottom masses in the several TeV regime because the threshold correction to the bottom mass at the superpartner scale is required to have a particular size. For tan beta about 50, which is needed for t-b-tau unification, the stops must be lighter than 2.8 TeV when A_t has the opposite sign of the gluino mass, as is favored by renormalization group scaling. For lower values of tan beta, the top and bottom squarks must be even lighter. Yukawa unification plus dark matter implies that superpartners are likely in reach of the LHC, after the upgrade to 14 (or 13) TeV, independent of any considerations of naturalness. We present a model-independent, bottom-up analysis of the SUSY parameter space that is simultaneously consistent with Yukawa unification and the hint for m_h = 125 GeV. We study the flavor and dark matter phenomenology that accompanies this Yukawa unification. A large portion of the parameter space predicts that the branching fraction for B_s to mu^+ mu^- will be observed to be significantly lower than the SM value.


title: Toward an accurate mass function for precision cosmology

abstract: Cosmological surveys aim to use the evolution of the abundance of galaxy clusters to accurately constrain the cosmological model. In the context of LCDM, we show that it is possible to achieve the required percent level accuracy in the halo mass function with gravity-only cosmological simulations, and we provide simulation start and run parameter guidelines for doing so. Some previous works have had sufficient statistical precision, but lacked robust verification of absolute accuracy. Convergence tests of the mass function with, for example, simulation start redshift can exhibit false convergence of the mass function due to counteracting errors, potentially misleading one to infer overly optimistic estimations of simulation accuracy. Percent level accuracy is possible if initial condition particle mapping uses second order Lagrangian Perturbation Theory, and if the start epoch is between 10 and 50 expansion factors before the epoch of halo formation of interest. The mass function for halos with fewer than ~1000 particles is highly sensitive to simulation parameters and start redshift, implying a practical minimum mass resolution limit due to mass discreteness. The narrow range in converged start redshift suggests that it is not presently possible for a single simulation to capture accurately the cluster mass function while also starting early enough to model accurately the numbers of reionisation era galaxies, whose baryon feedback processes may affect later cluster properties. Ultimately, to fully exploit current and future cosmological surveys will require accurate modeling of baryon physics and observable properties, a formidable challenge for which accurate gravity-only simulations are just an initial step.


title: Natural SUSY Predicts: Higgs Couplings

abstract: We study Higgs production and decays in the context of natural SUSY, allowing for an extended Higgs sector to account for a 125 GeV lightest Higgs boson. Under broad assumptions, Higgs observables at the LHC depend on at most four free parameters with restricted numerical ranges. Two parameters suffice to describe MSSM particle loops. The MSSM loop contribution to the diphoton rate is constrained from above by direct stop and chargino searches and by electroweak precision tests. Naturalness, in particular in demanding that rare B decays remain consistent with experiment without fine-tuned cancellations, provides a lower (upper) bound to the stop contribution to the Higgs-gluon coupling (Higgs mass). Two parameters suffice to describe Higgs mixing, even in the presence of loop induced non-holomorphic Yukawa couplings. Generic classes of MSSM extensions, that address the fine-tuning problem, predict sizable modifications to the effective bottom Yukawa, yb. Non-decoupling gauge extensions enhance yb, while a heavy SM singlet reduces yb. A factor of 4-6 enhancement in the diphoton rate at the LHC, compared to the SM prediction, can be accommodated. The ratio of the enhancements in the diphoton vs. the WW and ZZ channels cannot exceed 1.4. The h to bbbar rate in associated production cannot exceed the SM rate by more than 50%.


title: The Spectral and Temporal Properties of Transient Sources in Early-Type Galaxies

abstract: We report the spectral and temporal variability properties of 18 candidate transient and potential transient (TC and PTC) sources detected in deep multi-epoch Chandra observation of the nearby elliptical galaxies, NGC 3379, NGC 4278 and NGC 4697. Only one source can be identified with a background counterpart, leaving 17 TCs + PTCs in the galaxies. Of these, 14 are in the galaxy field, supporting the theoretical picture that the majority of field X-ray binaries (XRBs) will exhibit transient accretion for >75% of their lifetime. Three sources are coincident with globular clusters (GCs), including two high-luminosity candidate black hole (BH) XRBs, with Lx=5.4E38 erg/s, and Lx=2.8E39 erg/s, respectively. The spectra, luminosities and temporal behavior of these 17 sources suggest that the transient population is heterogeneous, including neutron star (NS) and BH XRBs in both normal and high-rate accretion modes, and super soft sources containing white dwarf binaries. Our TC and PTC detections are noticeably fewer that the number expected from the populations synthesis (PS) models of Fragos et al. (2009), tailored to our new Chandra pointings of NGC 4278. We attribute this discrepancy to the PS assumption that the transient population is composed of NS XRBs, as well as differences between the statistical analysis and error estimates used in the model and our observations.


title: Towards a Holographic Realization of Homes' Law

abstract: Gauge/gravity duality has proved to be a very successful tool for describing strongly coupled systems in particle physics and heavy ion physics. The application of the gauge/gravity duality to quantum matter is a promising candidate to explain questions concerning non-zero temperature dynamics and transport coefficients. To a large extent, the success of applications of gauge/gravity duality to the quark-gluon plasma is founded on the derivation of a universal result, the famous ratio of shear viscosity and entropy density. As a base for applications to condensed matter physics, it is highly desirable to have a similar universal relation in this context as well. A candidate for such a universal law is given by Homes' law: High Tc superconductors, as well as some conventional superconductors, exhibit a universal scaling relation between the superfluid density at zero temperature and the conductivity at the critical temperature times the critical temperature itself. In this work we describe progress in employing the models of holographic superconductors to realize Homes' law and to find a universal relation governing strongly correlated quantum matter. We calculate diffusive processes, including the backreaction of the gravitational matter fields on the geometry. We consider both holographic s-wave and p-wave superconductors. We show that a particular form of Homes' law holds in the absence of backreaction. Moreover, we suggest further steps to be taken for holographically realizing Homes' law more generally in the presence of backreaction.


title: A derivation of (half) the dark matter distribution function

abstract: All dark matter structures appear to follow a set of universalities, such as phase-space density or velocity anisotropy profiles, however, the origin of these universalities remains a mystery. Any equilibrated dark matter structure can be fully described by two functions, namely the radial and the tangential velocity distribution functions (VDF), and when we will understand these two then we will understand all the observed universalities. Here we demonstrate that if we know the radial VDF, then we can derive and understand the tangential VDF. This is based on simple dynamical arguments about properties of collisionless systems. We use a range of controlled numerical simulations to demonstrate the accuracy of this result. We therefore boil the question of the dark matter structural properties down to understanding the radial VDF.


title: A hot Uranus transiting the nearby M dwarf GJ3470. Detected with HARPS velocimetry. Captured in transit with TRAPPIST photometry

abstract: We report on the discovery of GJ3470b, a transiting hot Uranus of mass m_p = 14.0+-1.8 Mearth, radius R_p = 4.2+-0.6 Rearth and period P=3.3371+-0.0002 day. Its host star is a nearby (d=25.2+-2.9pc) M1.5 dwarf of mass M_s=0.54+-0.07 Msol and radius R_s=0.50+-0.06 Rsol. The detection originates from a radial-velocity campaign with HARPS that focused on the search for short-period planets orbiting M dwarfs. Once the planet was discovered and the transit-search window narrowed to about 10% of an orbital period, a photometric search started with TRAPPIST and quickly detected the ingress of the planet. Additional observations with TRAPPIST, EulerCam and NITES definitely confirmed the transiting nature of GJ3470b and allow for the determination of its true mass and radius. The star's visible or infrared brightness (V=12.3, K=8.0 mag), together with a large eclipse depth D=0.57+-0.05%, ranks GJ3470b among the most favorable planets for follow-up characterizations.


title: Bars in hydrodynamical cosmological simulations

abstract: We study the properties of two bars formed in fully cosmological hydrodynamical simulations of the formation of Milky Way-mass galaxies. In one case, the bar formed in a system with disc, bulge and halo components and is relatively strong and long, as could be expected for a system where the spheroid strongly influences the evolution. The second bar is less strong, shorter, and formed in a galaxy with no significant bulge component. We study the strength and length of the bars, the stellar density profiles along and across the bars and the velocity fields in the bar region. We compare them with the results of dynamical (idealised) simulations and with observations, and find, in general, a good agreement, although we detect some important differences as well. Our results show that more or less realistic bars can form naturally in a $\Lambda$CDM cosmology, and open up the possibility to study the bar formation process in a more consistent way than previously done, since the host galaxies grow, accrete matter and significantly evolve during the formation and evolution of the bar.


title: The Clustering of Galaxies in the SDSS-III DR9 Baryon Oscillation Spectroscopic Survey: Testing Deviations from $\Lambda$ and General Relativity using anisotropic clustering of galaxies

abstract: We use the joint measurement of geometry and growth from anisotropic galaxy clustering in the Baryon Oscillation Spectroscopic Survey Data Release 9 CMASS sample reported by Reid et al. to constrain dark energy properties and possible deviations from the General Relativity. Assuming GR and taking a prior on the linear matter power spectrum at high redshift from the cosmic microwave background (CMB), anisotropic clustering of the CMASS DR9 galaxies alone constrains $\Omega_{\rm m} = 0.308 \pm 0.022$ and $100\Omega_{\rm k} = 5.9 \pm 4.8$ for $w = -1$, or $w = -0.91 \pm 0.12$ for $\Omega_k = 0$. When combined with the full CMB likelihood, the addition of the anisotropic clustering measurements to the spherically-averaged BAO location increases the constraining power on dark energy by a factor of 4 in a flat CDM cosmology with constant dark energy equation of state $w$ (giving $w = -0.87 \pm 0.05$). This impressive gain depends on our measurement of both the growth of structure and Alcock-Paczynski effect, and is not realised when marginalising over the amplitude of redshift space distortions. Combining with both the CMB and Supernovae Type Ia (SNeIa), we find $\Omega_{\rm m} = 0.281 \pm 0.014$ and $1000\Omega_{\rm k}=-9.2\pm5.0$ for $w = -1$, or $w_0 = -1.13 \pm 0.12$ and $w_{\rm a}=0.65 \pm 0.36$ assuming $\Omega_k = 0$. Finally, when a $\Lambda$CDM background expansion is assumed, the combination of our estimate of the growth rate with previous growth measurements provides tight constraints on the parameters describing possible deviations from GR giving $\gamma = 0.64 \pm 0.05$. For one parameter extensions of the flat $\Lambda$CDM model, we find a $\sim 2\sigma$ preference either for $w > -1$ or slower growth than in GR. However, the data is fully consistent with the concordance model, and the evidence for these additional parameters is weaker than $2\sigma$.


title: Meson spectroscopy with unitary coupled-channels model for heavy-meson decay into three mesons

abstract: We develop a model for describing excited mesons decay into three mesons. The properties of the excited mesons can be extracted with this model. The model maintains the three-body unitarity that has been missed in previous data analyses based on the conventional isobar models. We study an importance of the three-body unitarity in extracting hadron properties from data. For this purpose, we use the unitary and isobar models to analyze the same pseudo data of gamma p -> pi+pi+pi-n, and extract the properties of excited mesons. We find a significant difference between the unitary and isobar models in the extracted properties of excited mesons, such as the mass, width and coupling strength to decay channels.


title: Semiclassical Calculation of Multiparticle Scattering Cross Sections in Classicalizing Theories

abstract: It has been suggested in arXiv:1010.1415 that certain derivatively coupled non-renormalizable scalar field theories might restore the perturbative unitarity of high energy hard scatterings by classicalization, i.e. formation of multiparticle states of soft quanta. Here we apply the semiclassical method of calculating the multiparticle production rates to the scalar Dirac-Born-Infeld (DBI) theory which is suggested to classicalize. We find that the semiclassical method is applicable for the energies in the final state above the cutoff scale of the theory L_*^{-1}. We encounter that the cross section of the process two to N ceases to be exponentially suppressed for the particle number in the final state N smaller than a critical particle number N_{crit} ~ (E L_*)^{4/3}. It coincides with the typical particle number produced in two-particle collisions at high energies predicted by classicalization arguments.


title: On stationary solutions of two-dimensional Euler Equation

abstract: We study the geometry of streamlines and stability properties for steady state solutions of the Euler equations for ideal fluid.


title: Go Heuristics for Coverage of Dense Wireless Sensor Networks

abstract: This paper collects heuristics of Go Game and employs them to achieve coverage of dense wireless sensor networks. In this paper, we propose an algorithm based on Go heuristics and validate it. Investigations show that it is very promising and could be seen as a good optimization. Keywords: Go Heuristics, Wireless Sensor Networks, Coverage, Density


title: Tight Binding Model of Mn12 Single Molecule Magnets: Electronic and Magnetic Structure and Transport Properties

abstract: We describe and analyze a tight-binding model of single molecule magnets (SMMs) that captures both the spin and spatial aspects of the SMM electronic structure. The model generalizes extended Huckel theory to include the effects of spin polarization and spin-orbit coupling. For neutral and negatively charged Mn12 SMMs with acetate or benzoate ligands the model yields the total SMM spin, the spins of the individual Mn ions, the magnetic easy axis orientation, the size of the magnetic anisotropy barrier and the size of the HOMO-LUMO gap consistent with experiment. For neutral molecules the predicted spins and spatial locations of the HOMO are consistent with the results of density functional calculations. For the total spin and location of the LUMO density functional theory-based calculations yield varied results while the present model yield results consistent with experiments on negatively charged molecules. For Mn12 SMMs with thiolate- and methylsulphide-terminated benzoate ligands (Mn12-Ph-Th) we find the HOMO to be located on the magnetic core of the molecule, but (unlike for the Mn12 SMMs that have previously been studied theoretically), we predict the LUMO and near LUMO orbitals of Mn12-Ph-Th to be located on ligands. Therefore we predict that for these Mn12 SMMs resonant and off-resonant coherent transport via near-LUMO orbitals, not subject to Coulomb blockade, should occur. We propose that this effect can be used to identify specific experimentally realized SMM transistors in which the easy axis and magnetic moment are approximately parallel to the direction of the current flow. We also predict effective spin filtering by these SMMs to occur at low bias whether the transport is mediated by the HOMO that is on the magnetic core of the SMM or by near LUMO orbitals located on the nominally non-magnetic ligands.


title: Deformed Lorentz symmetry and relative locality in a curved/expanding spacetime

abstract: The interest of part of the quantum-gravity community in the possibility of Planck-scale-deformed Lorentz symmetry is also fueled by the opportunities for testing the relevant scenarios with analyses, from a signal-propagation perspective, of observations of bursts of particles from cosmological distances. In this respect the fact that so far the implications of deformed Lorentz symmetry have been investigated only for flat (Minkowskian) spacetimes represents a very significant limitation, since for propagation over cosmological distances the curvature/expansion of spacetime is evidently tangible. We here provide a significant step toward filling this gap by exhibiting an explicit example of Planck-scale-deformed relativistic symmetries of a spacetime with constant rate of expansion (deSitterian). Technically we obtain the first ever example of a relativistic theory of worldlines of particles with 3 nontrivial relativistic invariants: a large speed scale ("speed-of-light scale"), a large distance scale (inverse of the "expansion-rate scale"), and a large momentum scale ("Planck scale"). We address some of the challenges that had obstructed success for previous attempts by exploiting the recent understanding of the connection between deformed Lorentz symmetry and relativity of spacetime locality. We also offer a preliminary analysis of the differences between the scenario we here propose and the most studied scenario for broken (rather than deformed) Lorentz symmetry in expanding spacetimes.


title: Desingularization by blowings-up avoiding simple normal crossings

abstract: It is shown that, for any reduced algebraic variety in characteristic zero, one can resolve all but simple normal crossings (snc) singularities by a finite sequence of blowings-up with smooth centres which, at every step, avoids points where the transformed variety together with the exceptional divisor has only snc singularities. The proof follows the philosophy of arXiv:1107.5595 that the desingularization invariant can be used together with natural geometric information to compute local normal forms of singularities.