title:
Finite p-groups with a Frobenius group of automorphisms whose kernel is
  a cyclic p-group

abstract:
  Suppose that a finite $p$-group $P$ admits a Frobenius group of automorphisms
$FH$ with kernel $F$ that is a cyclic $p$-group and with complement $H$. It is
proved that if the fixed-point subgroup $C_P(H)$ of the complement is nilpotent
of class $c$, then $P$ has a characteristic subgroup of index bounded in terms
of $c$, $|C_P(F)|$, and $|F|$ whose nilpotency class is bounded in terms of $c$
and $|H|$ only. Examples show that the condition of $F$ being cyclic is
essential. The proof is based on a Lie ring method and a theorem of the authors
and P. Shumyatsky about Lie rings with a metacyclic Frobenius group of
automorphisms $FH$. It is also proved that $P$ has a characteristic subgroup of
$(|C_P(F)|, |F|)$-bounded index whose order and rank are bounded in terms of
$|H|$ and the order and rank of $C_P(H)$, respectively, and whose exponent is
bounded in terms of the exponent of $C_P(H)$.


title: Ends for subsemigroups of finite index

abstract:
  In this paper we study ends of finitely generated semigroups. The ends we are
working with are the ends of the undirected graphs of Cayley graphs of finitely
generated semigroups. We prove that the number of ends is preserved for
subsemigroups of finite Rees index, and prove the same result for finite Green
index subsemigroups of cancellative semigroups.


title:
The regularizing Levenberg-Marquardt scheme for history matching of
  petroleum reservoirs,

abstract:
  In this paper we study a history matching approach that consists of finding
stable approximations to the problem of minimizing the weighted least-squares
functional that penalizes the misfit between the reservoir model predictions
$G(u)$ and noisy observations $y^{\eta}$. In other words, we are interested in
computing $u^{\eta}\equiv \arg\min_{u\in X}\frac{1}{2}\vert\vert
\Gamma^{-1/2}(y-G(u))\vert\vert_{Y}^{2} $ where $\Gamma$ is the measurements
error covariance, $Y$ is the observation space and $X$ is a set of admissible
parameters. This is an ill-posed nonlinear inverse problem that we address by
means of the regularizing Levenberg-Marquardt scheme developed in
\cite{Hanke,Hanke2}. Under certain conditions on $G$, the theory of
\cite{Hanke,Hanke2} ensures convergence of the scheme to stable approximations
to the inverse problem. We propose an implementation of the regularizing
Levenberg-Marquardt scheme that enforces prior knowledge of the geologic
properties. In particular, the prior mean $\overline{u}$ is incorporated in the
initial guess of the algorithm and the prior error covariance $C$ is enforced
through the definition of the parameter space $X$. Our main goal is to
numerically show that the proposed implementation of the regularizing
Levenberg-Marquardt scheme of Hanke is a robust method capable of providing
accurate estimates of the geologic properties for small noise measurements. The
performance for recovering the true permeability with the regularizing
Levenberg-Marquardt scheme is compared against the more standard techniques for
history matching proposed in \cite{Li,Tavakoli,svdRML,Oliver}. Our numerical
experiments suggest that the history matching approach based on iterative
regularization is robust and could potentially be used to improve further on
various methodologies already proposed as effective tools for history matching
in petroleum reservoirs


title:
Unified approach to contextuality, non-locality, and temporal
  correlations

abstract:
  We highlight the existence of a joint probability distribution as the common
underpinning assumption behind Bell-type, contextuality, and Leggett-Garg-type
tests. We then present a procedure to translate contextual scenarios into
temporal Leggett-Garg-type and spatial Bell-type ones. To demonstrate the
generality of this approach we construct a family of spatial Bell-type
inequalities. We show that in Leggett-Garg scenario a necessary condition for
contextuality in time is given by a violation of consistency conditions in
Consistent Histories approach to quantum mechanics.


title:
Faustmann Rotation and population dynamics in the presence of a risk of
  destructive events

abstract:
  The impact of the presence of risk of destructive event on the silvicultural
practice of a forest stand is investigated. For that, we consider a model of
population dynamics. This model has allowed us to make the comparison without
and with risk, and highlight the influence of the presence of risk of
destructive event on optimal thinning and optimal rotation period.


title: Superconducting Vortex Lattices for Ultracold Atoms

abstract:
  We propose and analyze a nanoengineered vortex array in a thin-film type-II
superconductor as a magnetic lattice for ultracold atoms. This proposal
addresses several of the key questions in the development of atomic quantum
simulators. By trapping atoms close to the surface, tools of nanofabrication
and structuring of lattices on the scale of few tens of nanometers become
available with a corresponding benefit in energy scales and temperature
requirements. This can be combined with the possibility of magnetic single site
addressing and manipulation together with a favorable scaling of
superconducting surface-induced decoherence.

categories: cond-mat.quant-gas cond-mat.mes-hall cond-mat.supr-con quant-ph


title: Quasiparticle properties of an impurity in a Fermi gas

abstract:
  We report on a study of a spin-down impurity strongly coupled to a spin-up
Fermi sea (a so-called Fermi polaron) with the diagrammatic Monte-Carlo
(DiagMC) technique. Conditions of zero temperature and three dimensions are
considered for an ultracold atomic gas with resonant interactions in the
zero-range limit. A Feynman diagrammatic series is developed for the one-body
and two-body propagators providing information about the polaron and molecule
channel respectively. The DiagMC technique allows us to reach diagram orders
that are high enough for extrapolation to infinite order. The robustness of the
extracted results is examined by checking various resummation techniques and by
running the simulations with various choices for the propagators and vertex
functions. It turns out that dressing the lines in the diagrams as much as
possible is not always the optimal choice. We also identify classes of dominant
diagrams for the one-body and two-body self-energy in the region of strong
interaction. These dominant diagrams turn out to be the leading processes of
the strong-coupling limit. The quasiparticle energies and $Z$-factor are
obtained as a function of the interaction strength. We find that the DiagMC
results for the molecule and polaron properties are very similar to those
obtained with a variational ansatz. Surprisingly, this variational ansatz gives
very good predictions for the quasiparticle residue even when this residue is
significantly smaller than one.


title:
The Cauchy Problem for Non-Archimedean Pseudodifferential Equations of
  Klein-Gordon Type

abstract:
  In this article we introduce a new class of non-Archimedean
pseudodifferential equations of Klein-Gordon type and study the corresponding
Cauchy problem for these equations. A remarkable fact is that the
non-Archimedean Klein-Gordon equations exhibit many similar properties to the
classical Klein-Gordon equations.


title: Discrepancy of random graphs and hypergraphs

abstract:
  Answering in a strong form a question posed by Bollob\'as and Scott, in this
paper we determine the discrepancy between two random k-uniform hypergraphs, up
to a constant factor depending solely on k.


title: The classical ether-drift experiments: a modern re-interpretation

abstract:
  The condensation of elementary quanta and their macroscopic occupation of the
same quantum state, say k=0 in some reference frame Sigma, is the essential
ingredient of the degenerate vacuum of present-day elementary particle physics.
This represents a sort of `quantum ether' which characterizes the physically
realized form of relativity and could play the role of preferred reference
frame in a modern re-formulation of the Lorentzian approach. In spite of this,
the so called `null results' of the classical ether-drift experiments,
traditionally interpreted as confirmations of Special Relativity, have so
deeply influenced scientific thought as to prevent a critical discussion on the
real reasons underlying its alleged supremacy. In this paper, we argue that
this traditional null interpretation is far from obvious. In fact, by using
Lorentz transformations to connect the Earth's frame to Sigma, the small
observed effects point to an average Earth's velocity of about 300 km/s, as in
most cosmic motions. A common feature is the irregular behaviour of the data.
While this has motivated, so far, their standard interpretation as instrumental
artifacts, our new re-analysis of the very accurate Joos experiment gives clear
indications for the type of Earth's motion associated with the CMB anisotropy
and leaves little space for this traditional interpretation. The new
explanation requires instead a view of the vacuum as a stochastic medium,
similar to a fluid in a turbulent state of motion, in agreement with basic
foundational aspects of both quantum physics and relativity. The overall
consistency of this picture with the present experiments with vacuum optical
resonators and the need for a new generation of dedicated ether-drift
experiments are also emphasized.


title: Universal Separability and Entanglement in Identical Particle Systems

abstract:
  Entanglement is known to be a relative notion, defined with respect to the
choice of physical observables to be measured (i.e., the measurement setup
used). This implies that, in general, the same state can be both separable and
entangled for different measurement setups, but this does not exclude the
existence of states which are separable (or entangled) for all possible setups.
We show that for systems of bosonic particles there indeed exist such
universally separable states: they are i.i.d. pure states. In contrast, there
is no such state for fermionic systems with a few exceptional cases. We also
find that none of the fermionic and bosonic systems admits universally
entangled states.


title: On the derivative of two functions from Denjoy-Tichy-Uitz family

abstract:
  The family of functions, we investigate in this article, was originally
introduced by A.Denjoy and later rediscovered by R Tichy and J. Uitz. We denote
the functions of the family by $g_{\lambda}(x),$ where $\lambda\in(0,1)$. The
definition will be given in the following section. The most famous function of
the family is the Minkiowski question-mark function. As we would see, it
corresponds to $\lambda=\frac12$. All functions of the family are continuous,
strictly increasing and map the segment $[0,1]$ onto itself. Moreover, they are
singular i.e. $\forall \lambda$ the derivative $g'_{\lambda}(x),$ if exists,
can take only two values: 0 and $+\infty.$ In this paper we consider two
functions of the class which correspond to $\lambda$ equals $\frac{\sqrt5-1}2$
or $1-\frac{\sqrt5-1}2.$ The aim of this paper is to prove some theorems about
essential conditions on x such that if the condition holds then the derivative
$g'_{\lambda}(x)$ exists and has determined value. The constants used in our
theorems are non-improvable.
  Our paper is wirtten in Russian. However Introduction and the formulation of
main results are written in English.


title:
Analytical study of quadratic and non-quadratic short-time behavior of
  quantum decay

abstract:
  The short-time behavior of quantum decay of an unstable state initially
located within an interaction region of finite range is investigated using a
resonant expansion of the survival amplitude. It is shown that in general the
short-time behavior of the survival probability $S(t)$ has a dependence on the
initial state and may behave either as $S(t)=1-\mathcal{O}(t^{3/2})$ or as
$S(t)=1-\mathcal{O}(t^{2})$. The above cases are illustrated by solvable
models. The experiment reported in Ref. [1] does not distinguish between the
above short-time behaviors.


title: Some remarks on the complex heat kernel in the scalar potential case

abstract:
  In previous works, we used a so-called deformation formula in order to study,
in particular, the Borel summability of the heat kernel of some operators. A
goal of this paper is to collect miscellaneous remarks related to these works.
Here the complex setting plays an important role. Moreover, the deformation
formula provides a solution of the heat equation in "unusual" cases. We also
give a uniqueness statement concerning these cases.


title:
Pontryagin Maximum Principle for finite dimensional nonlinear optimal
  control problems on time scales

abstract:
  In this article we derive a strong version of the Pontryagin Maximum
Principle for general nonlinear optimal control problems on time scales in
finite dimension. The final time can be fixed or not, and in the case of
general boundary conditions we derive the corresponding transversality
conditions. Our proof is based on Ekeland's variational principle. Our
statement and comments clearly show the distinction between right-dense points
and right-scattered points. At right-dense points a maximization condition of
the Hamiltonian is derived, similarly to the continuous-time case. At
right-scattered points a weaker condition is derived, in terms of so-called
stable $\Omega$-dense directions. We do not make any specific restrictive
assumption on the dynamics or on the set $\Omega$ of control constraints. Our
statement encompasses the classical continuous-time and discrete-time versions
of the Pontryagin Maximum Principle, and holds on any general time scale, that
is any closed subset of $\R$.


title: Beta-hypergeometric probability distribution on symmetric matrices

abstract:
  Some remarkable properties of the beta distribution are based on relations
involving independence between beta random variables such that a parameter of
one among them is the sum of the parameters of an other (see (1.1) et (1.2)
below). Asci, Letac and Piccioni \cite{6} have used the real
beta-hypergeometric distribution on $ \reel$ to give a general version of these
properties without the condition on the parameters. In the present paper, we
extend the properties of the real beta to the beta distribution on symmetric
matrices, we use on the positive definite matrices the division algorithm
defined by the Cholesky decomposition to define a matrix-variate
beta-hypergeometric distribution, and we extend to this distribution the
proprieties established in the real case by Asci, Letac and Piccioni


title: On the nature of dark energy: the lattice Universe

abstract:
  There is something unknown in the cosmos. Something big. Which causes the
acceleration of the Universe expansion, that is perhaps the most surprising and
unexpected discovery of the last decades, and thus represents one of the most
pressing mysteries of the Universe. The current standard $\Lambda$CDM model
uses two unknown entities to make everything fit: dark energy and dark matter,
which together would constitute more than 95% of the energy density of the
Universe. A bit like saying that we have understood almost nothing, but without
openly admitting it. Here we start from the recent theoretical results that
come from the extension of general relativity to antimatter, through CPT
symmetry. This theory predicts a mutual gravitational repulsion between matter
and antimatter. Our basic assumption is that the Universe contains equal
amounts of matter and antimatter, with antimatter possibly located in cosmic
voids, as discussed in previous works. From this scenario we develop a simple
cosmological model, from whose equations we derive the first results. While the
existence of the elusive dark energy is completely replaced by gravitational
repulsion, the presence of dark matter is not excluded, but not strictly
required, as most of the related phenomena can also be ascribed to
repulsive-gravity effects. With a matter energy density ranging from $\sim5%$
(baryonic matter alone, and as much antimatter) to $\sim25%$ of the so-called
critical density, the present age of the Universe varies between about 13 and
$15\rm\,Gyr$. The SN Ia test is successfully passed, with residuals comparable
with those of the $\Lambda$CDM model in the observed redshift range, but with a
clear prediction for fainter SNe at higher $z$. Moreover, this model has
neither horizon nor coincidence problems, and no initial singularity is
requested. In conclusion, we have replaced all the tough problems of the
current


title: Laminar-turbulent separatrix in a boundary layer flow

abstract:
  The transitional boundary layer flow over a flat plate is investigated. The
boundary layer flow is known to develop unstable Tollmien-Schlichting waves
above a critical value of the Reynolds number. However, it is also known that
this transition can be observed for sub-critical Reynolds numbers. In that
case, the basin of attraction of the laminar state coexists with the sustained
turbulence. In this article, the trajectory on the separatrix between these two
states is simulated. The state on the separatrix is independent from the
initial condition and is dynamically connected to both the laminar flow and the
turbulence. Such an edge state provides information regarding the basic
features of the transitional flow. The solution takes the form of a low speed
streak, flanked by two quasi-streamwise sinuous vortices. The shape of the
streaks is close to that simulated with the linear optimal perturbation method.
This solution is compared to existing results concerning streak breakdown. The
simulations are realized in a temporal framework for a local boundary layer,
with periodic boundary conditions in the streamwise direction. A dedicated
model, based on a scale separation, is presented. The mean flow is a solution
of the Prandtl boundary layer equations while the superposed small-scale
fluctuations are a solution of the periodic Navier-Stokes equations. The model
is validated with turbulent flow simulations and satisfactorily reproduces the
physical characteristics of a boundary layer flow, especially in the outer
region, where external fluid is entrained toward the boundary layer.


title: The 10830 He I Absorption Line Among Metal-Poor Subdwarfs

abstract:
  Spectra of the He I 10830 line have been obtained for 23 metal-poor stars,
the majority of which are dwarfs ranging in metallicity from [Fe/H] = -2.1 to
-0.8. The data were acquired with the NIRSPEC spectrograph on the Keck 2
telescope. Most of these subdwarfs and dwarfs are found to exhibit a He I
absorption line indicative of the presence of chromospheres. The equivalent
width of the 10830 absorption profile is generally less than 70 mA, and covers
a range similar to that found in solar metallicity stars of low activity. Among
the subdwarfs the He I equivalent width does not correlate with either [Fe/H]
metallicity or (B-V) color. Some evidence for asymmetric profiles is found
among metal-poor dwarfs, but not the high-speed blue-shifted absorption
displayed by some metal-poor red giants.


title:
Analysis of the Min-Sum Algorithm for Packing and Covering Problems via
  Linear Programming

abstract:
  Message-passing algorithms based on belief-propagation (BP) are successfully
used in many applications including decoding error correcting codes and solving
constraint satisfaction and inference problems. BP-based algorithms operate
over graph representations, called factor graphs, that are used to model the
input. Although in many cases BP-based algorithms exhibit impressive empirical
results, not much has been proved when the factor graphs have cycles.
  This work deals with packing and covering integer programs in which the
constraint matrix is zero-one, the constraint vector is integral, and the
variables are subject to box constraints. We study the performance of the
min-sum algorithm when applied to the corresponding factor graph models of
packing and covering LPs.
  We compare the solutions computed by the min-sum algorithm for packing and
covering problems to the optimal solutions of the corresponding linear
programming (LP) relaxations. In particular, we prove that if the LP has an
optimal fractional solution, then for each fractional component, the min-sum
algorithm either computes multiple solutions or the solution oscillates below
and above the fraction. This implies that the min-sum algorithm computes the
optimal integral solution only if the LP has a unique optimal solution that is
integral.
  The converse is not true in general. For a special case of packing and
covering problems, we prove that if the LP has a unique optimal solution that
is integral and on the boundary of the box constraints, then the min-sum
algorithm computes the optimal solution in pseudo-polynomial time.
  Our results unify and extend recent results for the maximum weight matching
problem by [Sanghavi et al.,'2011] and [Bayati et al., 2011] and for the
maximum weight independent set problem [Sanghavi et al.'2009].


title: On the coset structure of a skew lattice

abstract:
  The class of skew lattices can be seen as an algebraic category. It models an
algebraic theory in the category of Sets where the Green's relation D is a
congruence describing an adjunction to the category of Lattices. In this paper
we will discuss the relevance of this approach, revisit some known
decompositions and relate the order structure of a skew lattice with its coset
structure that describes the internal coset decomposition of the respective
algebra.


title: 2D kinematics of the edge-on spiral galaxy ESO 379-G006

abstract:
  We present a kinematical study of the nearly edge-on galaxy ESO 379-G006 that
shows the existence of extraplanar ionized gas. With Fabry-Perot spectroscopy
at H-alpha, we study the kinematics of ESO 379-G006 using velocity maps and
position-velocity diagrams parallel to the major and to the minor axis of the
galaxy. We build the rotation curve of the disk and discuss the role of
projection effects due to the fact of viewing this galaxy nearly edge-on. The
twisting of the isovelocities in the radial velocity field of the disk of ESO
379-G006 as well as the kinematic asymmetries found in some position-velocity
diagrams parallel to the minor axis of the galaxy suggest the existence of
deviations to circular motions in the disk that can be modeled and explained
with the inclusion of a radial inflow probably generated by a bar or by spiral
arms. We succeeded in detecting extraplanar Diffuse Ionized Gas in this galaxy.
At the same time, from the analysis of position-velocity diagrams, we found
some evidence that the extraplanar gas could lag in rotation velocity with
respect to the midplane rotation.


title: New cases of p-adic uniformization

abstract:
  We prove a Cherednik style $p$-adic uniformization theorem for Shimura
varieties associated to certain groups of unitary similitudes of size two over
totally real fields. Our basic tool is the alternative modular interpretation
of the Drinfeld $p$-adic halfplane of our earlier paper (arXiv 1108.5713)


title:
Fermion Self Energy Correction in Light-Front QED using Coherent State
  Basis

abstract:
  We discuss IR divergences in lepton mass renormalization in Light-Front
Quantum Electrodynamics (LFQED) in Feynman gauge. We consider LFQED with
Pauli-Villars fields and using old-fashioned time ordered perturbation theory
(TOPT), we show that our earlier result regarding cancellation of true IR
divergences upto $O(e^4)$ in coherent state basis holds in Feynman gauge also.


title: Quantum Hall effect in n-p-n and n-2D Topological Insulator-n junctions

abstract:
  We have studied quantized transport in HgTe wells with inverted band
structure corresponding to the two-dimensional topological insulator phase (2D
TI) with locally-controlled density allowing n-p-n and n-2D TI-n junctions. The
resistance reveals the fractional plateau $2h/e^{2}$ in n-p-n regime in the
presence of the strong perpendicular magnetic field. We found that in n-2D TI-n
regime the plateaux in resistance in not universal and results from the edge
state equilibration at the interface between chiral and helical edge modes. We
provided the simple model describing the resistance quantization in n-2D TI-n
regime.


title: Adams operations on the virtual K-theory of P(1,n)

abstract:
  We analyze the structure of the virtual (orbifold) K-theory ring of the
complex orbifold P(1,n) and its virtual Adams (or power) operations, by using
the non-Abelian localization theorem of Edidin-Graham. In particular, we
identify the group of virtual line elements and obtain a natural presentation
for the virtual K-theory ring in terms of these virtual line elements. This
yields a surjective homomorphism from the virtual K-theory ring of P(1,n) to
the ordinary K-theory ring of a crepant resolution of the cotangent bundle of
P(1,n) which respects the Adams operations. Furthermore, there is a natural
subring of the virtual K-theory ring of P(1,n) which is isomorphic to the
ordinary K-theory ring of the resolution. This generalizes the results of
Edidin-Jarvis-Kimura who proved the latter for n=2,3.


title:
Impact of SUSY-QCD corrections on neutralino-stop co-annihilation and
  the neutralino relic density

abstract:
  We have calculated the full O(alpha_s) supersymmetric QCD corrections to
neutralino-stop co-annihilation into electroweak vector and Higgs bosons within
the Minimal Supersymmetric Standard Model (MSSM). We performed a parameter
study within the phenomenological MSSM and demonstrated that the studied
co-annihilation processes are phenomenologically relevant, especially in the
context of a 126 GeV Higgs-like particle. By means of an example scenario we
discuss the effect of the full next-to-leading order corrections on the
co-annihilation cross section and show their impact on the predicted neutralino
relic density. We demonstrate that the impact of these corrections on the
cosmologically preferred region of parameter space is larger than the current
experimental uncertainty of WMAP data.


title:
Formaldehyde Densitometry of Starburst Galaxies: Density-Independent
  Global Star Formation

abstract:
  Accurate techniques which allow for the derivation of the spatial density in
star formation regions are rare. A technique which has found application for
the derivation of spatial densities in Galactic star formation regions utilizes
the density-sensitive properties of the K-doublet transitions of formaldehyde
(H2CO). In this paper, we present an extension of our survey of the
formaldehyde 1(10)-1(11) (lambda = 6.2 cm) and 2(11)-2(12) (lambda = 2.1 cm)
K-doublet transitions of H2CO in a sample of 56 starburst systems (Mangum etal.
2008). We have extended the number of galaxies in which both transitions have
been detected from 5 to 13. We have improved our spatial density measurements
by incorporating kinetic temperatures based upon NH3 measurements of 11 of the
galaxies with a total of 14 velocity components in our sample (Mangum etal.
2013). Our spatial density measurements lie in a relatively narrow range of
from 10^(4.5) to 10^(5.5) cm^(-3). This implies that the Schmidt-Kennicutt
relation between L_(IR) and M_(dense): (1) Is an indication of the dense gas
mass reservoir available to form stars, and (2) Is not directly dependent upon
a higher average density driving the star formation process in the most
luminous starburst galaxies. We have also used our H2CO measurements to derive
two separate measures of the dense gas mass which are generally smaller, in
many cases by a factor of 10^2-10^3, than those derived using HCN. This
disparity suggests that H2CO traces a denser, more compact, component of the
giant molecular clouds in our starburst galaxy sample.
  We also report measurements of the rotationally-excited lambda = 6.3 cm
2P_(1/2) J=1/2 state of OH and the H111alpha radio recombination line taken
concurrently with our H2CO 1(10)-1(11) measurements.


title: Knot topology in QCD

abstract:
  We consider topological structure of classical vacuum solutions in quantum
chromodynamics. Topologically non-equivalent vacuum configurations are
classified by non-trivial second and third homotopy groups for coset of the
color group SU(N) (N=2,3) under the action of maximal Abelian stability group.
Starting with explicit vacuum knot configurations we study possible exact
classical solutions as vacuum excitations. Exact analytic non-static knot
solution in a simple CP^1 model in Euclidean space-time has been obtained. We
construct an ansatz based on knot and monopole topological vacuum structure for
searching new solutions in SU(2) and SU(3) QCD. We show that singular knot-like
solutions in QCD in Minkowski space-time can be naturally obtained from knot
solitons in integrable CP^1 models. A family of Skyrme type low energy
effective theories of QCD admitting exact analytic solutions with non-vanishing
Hopf charge is proposed.


title:
Improved determination of Heavy Quarkonium magnetic dipole transitions
  in pNRQCD

abstract:
  We compute the magnetic dipole transitions between low lying Heavy Quarkonium
states in a model independent way. We use the weak-coupling version of the
effective field theory named potential NRQCD with the static potential exactly
incorporated in the leading order Hamiltonian. The precision we reach is
$k_{\gamma}^3/m^2\times{\cal O}(\alpha_s^2,v^2)$ and
$k_{\gamma}^3/m^2\times{\cal O}(v^4)$ for the allowed and forbidden transitions
respectively. We also resum the large logarithms associated to the heavy quark
mass scale. The specific transitions considered in this paper are the
following: $\Upsilon(1S) \to \eta_b(1S)\,\gamma$, $J/\psi(1S) \to
\eta_c(1S)\,\gamma$, $h_b(1P) \to \chi_{b0,1}(1P)\,\gamma$, $\chi_{b2}(1P) \to
h_b(1P)\,\gamma$, $\Upsilon(2S) \to \eta_b(2S)\,\gamma$, $\Upsilon(2S) \to
\eta_b(1S)\,\gamma$ and $\eta_b(2S)\to\Upsilon(1S)\,\gamma$. The effect of the
new power counting is found to be large and the exact treatment of the soft
logarithms of the static potential makes the factorization scale dependence
much smaller. The convergence for the $b\bar b$ ground state is quite good, and
also quite reasonable for the $c\bar c$ ground state and the $b\bar b$ 1P
state. For all of them we give solid predictions. For the 2S decays the
situation is less conclusive, yet our results are perfectly consistent with
existing data, as the previous disagreement with experiment for the
$\Upsilon(2S) \to \eta_b(1S)\,\gamma$ decay fades away. We also profit to
compute some expectation values like the electromagnetic radius, r^2, or p^2.
We find r^2 to be nicely convergent in all cases, whereas the convergence of
p^2 is typically worse.


title: From Inherent Structures Deformation to Elastic Heterogeneities

abstract:
  Using a well defined soft model glass in the framework of Molecular Dynamics
simulations, the inherent structures are probed by means of a recently
developed deformation protocol that aims to capture the Dynamical
Heterogeneities (DH), as well as by the use of the isoconfigurational ensemble.
Comparisons of both methods are performed by extracting the corresponding
inherent characteristic length scales as the temperature of the system is
cooled down from the liquid to the glassy state. The obtained lengths grow and
depict an identical trend as the system falls out-off equilibrium, and appear
to converge to the characteristic length scale that characterizes the Elastic
Heterogeneities (EH) of the materials in the very low temperature limit, which
is deeply related to the properties of the glass. This provides a first
evidence of a relationship between DH and EH.


title: Duality between equilibrium and growing networks

abstract:
  In statistical physics any given system can be either at an equilibrium or
away from it. Networks are not an exception. Most network models can be
classified as either equilibrium or growing. Here we show that under certain
conditions there exists an equilibrium formulation for any growing network
model, and vice versa. The equivalence between the equilibrium and
nonequilibrium formulations is exact not only asymptotically, but even for any
finite system size. The required conditions are satisfied in random geometric
graphs in general and causal sets in particular, and to a large extent in some
real networks.


title: Singularities in the entropy of asymptotically large simple graphs

abstract:
  We prove that the asymptotic entropy of large simple graphs, as a function of
fixed edge and triangle densities, is nondifferentiable along a certain curve.


title: Large-$N_c$ gauge theory and chiral random matrix theory

abstract:
  We discuss how the $1/N_c$ expansion and the chiral random matrix theory
($\chi$RMT) can be used in the study of large-$N_c$ gauge theories. We first
clarify the parameter region in which each of these two approaches is valid:
while the fermion mass $m$ is fixed in the standard large-$N_c$ arguments ('t
Hooft large-$N_c$ limit), $m$ must be scaled appropriately with a certain
negative power of $N_c$ in order for the gauge theories to be described by the
$\chi$RMT. Then, although these two limits are not compatible in general, we
show that the breakdown of chiral symmetry can be detected by combining the
large-$N_c$ argument and the $\chi$RMT with some cares. As a concrete example,
we numerically study the four dimensional $SU(N_c)$ gauge theory with $N_f=2$
heavy adjoint fermions, introduced as the center symmetry preserver keeping the
infrared physics intact, on a $2^4$ lattice. By looking at the low-lying
eigenvalues of the Dirac operator for a massless probe fermion in the adjoint
representation, we find that the chiral symmetry is indeed broken with the
expected breaking pattern. This result reproduces a well-known fact that the
chiral symmetry is spontaneously broken in the pure $SU(N_c)$ gauge theory in
the large-$N_c$ and the large-volume limit, and therefore supports the validity
of the combined approach. We also provide the interpretation of the gap and
unexpected $N_c$-scaling, both of which are observed in the Dirac spectrum.


title: The Top Ten Spitzer YSOs in 30 Doradus

abstract:
  The most luminous Spitzer point sources in the 30 Doradus triggered second
generation are investigated coherently in the 3-8 micron region. Remarkable
diversity and complexity in their natures are revealed. Some are also among the
brightest JHK sources, while others are not. Several of them are multiple when
examined at higher angular resolutions with HST NICMOS and WFPC2/WFC3 as
available, or with VISTA/VMC otherwise. One is a dusty compact H II region near
the far northwestern edge of the complex, containing a half dozen bright I-band
sources. Three others appear closely associated with luminous WN stars and
causal connections are suggested. Some are in the heads of dust pillars
oriented toward R136, as previously discussed from the NICMOS data. One resides
in a compact cluster of much fainter sources, while another appears monolithic
at the highest resolutions. Surprisingly, one is the brighter of the two
extended "mystery spots" associated with Knot 2 of Walborn et al. Masses are
derived from YSO models for unresolved sources and lie in the 10-30 M_{sun}
range. Further analysis of the IR sources in this unique region will advance
understanding of triggered massive star formation, perhaps in some unexpected
and unprecedented ways.


title: Singularities in Fully Developed Turbulence

abstract:
  Phenomenological arguments are used to explore finite-time singularity
development in different physical fully-developed turbulence (FDT) situations.
The role played by the cascade physics underlying this process is investigated.
Such diverse aspects as the effects of spatial intermittency and fluid
compressibility in three-dimensional (3D) FDT and the role of the divorticity
amplification mechanism in two-dimensional (2D) FDT and quasi-2D
quasi-geostrophic FDT and the advection-diffusion mechanism in
magnetohydrodynamic turbulence are considered to provide physical insights into
this process in variant cascade physics situations. The quasi-geostrophic FDT
results connect with the 2D FDT results in the barotropic limit while they
connect with 3D FDT results in the baroclinic limit (on doing the necessary
interchange of vorticity in the 3D case with divorticity in the quasi-2D case);
hence they seem to provide a kind of bridge between 2D FDT and 3D FDT results.


title: Fluctuating flow angles and anisotropic flow measurements

abstract:
  Event-by-event fluctuations in the initial density distributions of the
fireballs created in relativistic heavy-ion collisions lead to event-by-event
fluctuations of the final anisotropic flow angles, and density inhomogeneities
in the initial state cause these flow angles to vary with the transverse
momentum of the emitted particles. It is shown that these effects lead to
characteristically different transverse momentum dependencies for anisotropic
flow coefficients extracted from different experimental methods. These
differences can be used to experimentally constrain flow angle fluctuations in
the final state of heavy-ion collisions which, in turn, are sensitive to the
initial state density fluctuations and the shear viscosity of the expanding
fireball medium.


title:
Dissipative soliton excitability induced by spatial inhomogeneities and
  drift

abstract:
  We show that excitability is generic in systems displaying dissipative
solitons when spatial inhomogeneities and drift are present. Thus, dissipative
solitons in systems which do not have oscillatory states, such as the
prototypical Swift-Hohenberg equation, display oscillations and Type I and II
excitability when adding inhomogeneities and drift to the system. This rich
dynamical behavior arises from the interplay between the pinning to the
inhomogeneity and the pulling of the drift. The scenario presented here
provides a general theoretical understanding of oscillatory regimes of
dissipative solitons reported in semiconductor microresonators. Our results
open also the possibility to observe this phenomenon in a wide variety of
physical systems.


title: High-Velocity Line Forming Regions in the Type Ia Supernova 2009ig

abstract:
  We report measurements and analysis of high-velocity (> 20,000 km/s) and
photospheric absorption features in a series of spectra of the Type Ia
supernova (SN) 2009ig obtained between -14d and +13d with respect to the time
of maximum B-band luminosity. We identify lines of Si II, Si III, S II, Ca II
and Fe II that produce both high-velocity (HVF) and photospheric-velocity (PVF)
absorption features. SN 2009ig is unusual for the large number of lines with
detectable HVF in the spectra, but the light-curve parameters correspond to a
slightly overluminous but unexceptional SN Ia (M_B = -19.46 mag and Delta_m15
(B) = 0.90 mag). Similarly, the Si II lambda_6355 velocity at the time of B-max
is greater than "normal" for a SN Ia, but it is not extreme (v_Si = 13,400
km/s). The -14d and -13d spectra clearly resolve HVF from Si II lambda_6355 as
separate absorptions from a detached line forming region. At these very early
phases, detached HVF are prevalent in all lines. From -12d to -6d, HVF and PVF
are detected simultaneously, and the two line forming regions maintain a
constant separation of about 8,000 km/s. After -6d all absorption features are
PVF. The observations of SN 2009ig provide a complete picture of the transition
from HVF to PVF. Most SN Ia show evidence for HVF from multiple lines in
spectra obtained before -10d, and we compare the spectra of SN 2009ig to
observations of other SN. We show that each of the unusual line profiles for Si
II lambda_6355 found in early-time spectra of SN Ia correlate to a specific
phase in a common development sequence from HVF to PVF.


title:
The Evolution of Circumplanetary Disks around Planets in Wide Orbits:
  Implications for Formation Theory, Observations, and Moon Systems

abstract:
  Using radiation hydrodynamics simulations, we explore the evolution of
circumplanetary disks around wide-orbit proto-gas giants. At large distances
from the star (~100 AU), gravitational instability followed by disk
fragmentation can form low-mass substellar companions (massive gas giants
and/or brown dwarfs) that are likely to host large disks. We examine the
initial evolution of these subdisks and their role in regulating the growth of
their substellar companions, as well as explore consequences of their
interactions with circumstellar material. We find that subdisks that form in
the context of GIs evolve quickly from a very massive state. Long-term
accretion rates from the subdisk onto the proto-gas giant reach ~0.3 Jupiter
masses per kyr. We also find consistency with previous simulations,
demonstrating that subdisks are truncated at ~1/3 of the companion's Hill
radius and are thick, with (h/r) of great than or equal to 0.2. The thickness
of subdisks draws to question the use of thin-disk approximations for
understanding the behavior of subdisks, and the morphology of subdisks has
implications for the formation and extent of satellite systems. These subdisks
create heating events in otherwise cold regions of the circumstellar disk, and
serve as planet formation beacons that can be detected by instruments such as
ALMA.


title: A tree-level 3-point function in the su(3)-sector of planar N=4 SYM

abstract:
  We classify the 3-point functions of local gauge-invariant single-trace
operators in the scalar sector of planar N=4 supersymmetric Yang-Mills
involving at least one su(3) operator. In the case of two su(3) and one su(2)
operators, the tree-level 3-point function can be expressed in terms of scalar
products of su(3) Bethe vectors. Moreover, if the second level Bethe roots of
one of the su(3) operators is trivial (set to infinity), this 3-point function
can be written in a determinant form. Using the determinant representation, we
evaluate the structure constant in the semi-classical limit, when the number of
roots goes to infinity.


title: Virasoro constraints in Drinfeld-Sokolov hierarchies

abstract:
  We describe a geometric theory of Virasoro constraints in generalized
Drinfeld-Sokolov hierarchies. Solutions of Drinfeld-Sokolov hierarchies are
succinctly described by giving a principal bundle on a complex curve together
with the data of a Higgs field near infinity. String solutions for these
hierarchies are defined as points having a big stabilizer under a certain Lie
algebra action. We characterize principal bundles coming from string solutions
as those possessing connections compatible with the Higgs field near infinity.
We show that tau-functions of string solutions satisfy second-order
differential equations generalizing the Virasoro constraints of 2d quantum
gravity.


title: An analysis of NK and generalized NK landscapes

abstract:
  Simulated landscapes have been used for decades to evaluate search strategies
whose goal is to find the landscape location with maximum fitness. Applications
include modeling the capacity of enzymes to catalyze reactions and the clinical
effectiveness of medical treatments. Understanding properties of landscapes is
important for understanding search difficulty. This paper presents a novel and
transparent characterization of NK landscapes.
  We prove that NK landscapes can be represented by parametric linear
interaction models where model coefficients have meaningful interpretations. We
derive the statistical properties of the model coefficients, providing insight
into how the NK algorithm parses importance to main effects and interactions.
An important insight derived from the linear model representation is that the
rank of the linear model defined by the NK algorithm is correlated with the
number of local optima, a strong determinant of landscape complexity and search
difficulty. We show that the maximal rank for an NK landscape is achieved
through epistatic interactions that form partially balanced incomplete block
designs. Finally, an analytic expression representing the expected number of
local optima on the landscape is derived, providing a way to quickly compute
the expected number of local optima for very large landscapes.


title: Direct CP violation in singly Cabibbo-suppressed D-meson decays

abstract:
  The LHCb and CDF collaborations reported a surprisingly large difference
between the direct CP asymmetries, Delta A_CP, in the D0 -> K+ K- and D0 -> pi+
pi- decay modes. We show that this measurement can be plausibly explained
within the standard model under the assumption of large penguin contractions
matrix elements and nominal U-spin breaking. A consistent picture arises,
accommodating the large difference between the decay rates, and the measured
decay rates of the D -> K pi modes.


title: Low-rate renewal theory and estimation

abstract:
  Certain renewal theorems are extended to the case that the rate of the
renewal process goes to 0 and, more generally, to the case that the drift of
the random walk goes to infinity. These extensions are motivated by and applied
to the problem of decentralized parameter estimation under severe communication
constraints.


title: Power spectrum for inflation models with quantum and thermal noises

abstract:
  We determine the power spectrum for inflation models covering all regimes
from cold (isentropic) to warm (nonisentropic) inflation. We work in the
context of the stochastic inflation approach, which can nicely describe both
types of inflationary regimes concomitantly. A throughout analysis is carried
out to determine the allowed parameter space for simple single field polynomial
chaotic inflation models that is consistent with the most recent cosmological
data from the nine-year Wilkinson Microwave Anisotropy Probe (WMAP) and in
conjunction with other observational cosmological sources. We present the
results for both the amplitude of the power spectrum, the spectral index and
for the tensor to scalar curvature perturbation amplitude ratio. We briefly
discuss cases when running is present. Despite single field polynomial-type
inflaton potential models be strongly disfavored, or even be already ruled out
in their simplest versions in the case of cold inflation, this is not the case
for nonisentropic inflation models in general (warm inflation in particular),
though higher order polynomial potentials (higher than quartic order) tend to
become less favorable also in this case, presenting a much smaller region of
parameter space compatible with the recent observational cosmological data. Our
findings also remain valid in face of the recently released Planck results.


title: Displaying Asynchronous Reactions to a Document: Two Goals and a Design

abstract:
  We describe and motivate three goals for the screen display of asynchronous
text deliberation pertaining to a document: (1) visibility of relationships
between comments and the text they reference, between different comments, and
between group members and the document and discussion, and (2)
distinguishability of boundaries between contextually related and unrelated
text and comments and between individual authors of documents and comments.
Interfaces for document-centered discussion generally fail to fulfill one or
both of these goals as well as they could. We describe the design of the new
version of Deme, a Web-based platform for online deliberation, and argue that
it achieves the two goals better than other recent designs.


title:
Effectiveness of conditional punishment for the evolution of public
  cooperation

abstract:
  Collective actions, from city marathons to labor strikes, are often
mass-driven and subject to the snowball effect. Motivated by this, we study
evolutionary advantages of conditional punishment in the spatial public goods
game. Unlike unconditional punishers who always impose the same fines on
defectors, conditional punishers do so proportionally with the number of other
punishers in the group. Phase diagrams in dependence on the punishment fine and
cost reveal that the two types of punishers cannot coexist. Spontaneous
coarsening of the two strategies leads to an indirect territorial competition
with the defectors, which is won by unconditional punishers only if the
sanctioning is inexpensive. Otherwise conditional punishers are the victors of
the indirect competition, indicating that under more realistic conditions they
are indeed the more effective strategy. Both continuous and discontinuous phase
transitions as well as tricritical points characterize the complex evolutionary
dynamics, which is due to multipoint interactions that are introduced by
conditional punishment. We propose indirect territorial competition as a
generally applicable mechanism relying on pattern formation, by means of which
spatial structure can be utilized by seemingly subordinate strategies to avoid
evolutionary extinction.


title: Fourier-Mukai transform in the quantized setting

abstract:
  We prove that a coherent DQ-kernel induces an equivalence between the derived
categories of DQ-modules with coherent cohomology if and only if the graded
commutative kernel associated to it induces an equivalence between the derived
categories of coherent sheaves.


title: On Realizations of a Joint Degree Matrix

abstract:
  The joint degree matrix of a graph gives the number of edges between vertices
of degree i and degree j for every pair (i,j). One can perform restricted swap
operations to transform a graph into another with the same joint degree matrix.
We prove that the space of all realizations of a given joint degree matrix over
a fixed vertex set is connected via these restricted swap operations. This was
claimed before, but there is an error in the previous proof, which we
illustrate by example. We also give a simplified proof of the necessary and
sufficient conditions for a matrix to be a joint degree matrix. Finally, we
address some of the issues concerning the mixing time of the corresponding MCMC
method to sample uniformly from these realizations.


title: An Algorithm for Finding Minimum d-Separating Sets in Belief Networks

abstract:
  The criterion commonly used in directed acyclic graphs (dags) for testing
graphical independence is the well-known d-separation criterion. It allows us
to build graphical representations of dependency models (usually probabilistic
dependency models) in the form of belief networks, which make easy
interpretation and management of independence relationships possible, without
reference to numerical parameters (conditional probabilities). In this paper,
we study the following combinatorial problem: finding the minimum d-separating
set for two nodes in a dag. This set would represent the minimum information
(in the sense of minimum number of variables) necessary to prevent these two
nodes from influencing each other. The solution to this basic problem and some
of its extensions can be useful in several ways, as we shall see later. Our
solution is based on a two-step process: first, we reduce the original problem
to the simpler one of finding a minimum separating set in an undirected graph,
and second, we develop an algorithm for solving it.


title:
Constraining Influence Diagram Structure by Generative Planning: An
  Application to the Optimization of Oil Spill Response

abstract:
  This paper works through the optimization of a real world planning problem,
with a combination of a generative planning tool and an influence diagram
solver. The problem is taken from an existing application in the domain of oil
spill emergency response. The planning agent manages constraints that order
sets of feasible equipment employment actions. This is mapped at an
intermediate level of abstraction onto an influence diagram. In addition, the
planner can apply a surveillance operator that determines observability of the
state---the unknown trajectory of the oil. The uncertain world state and the
objective function properties are part of the influence diagram structure, but
not represented in the planning agent domain. By exploiting this structure
under the constraints generated by the planning agent, the influence diagram
solution complexity simplifies considerably, and an optimum solution to the
employment problem based on the objective function is found. Finding this
optimum is equivalent to the simultaneous evaluation of a range of plans. This
result is an example of bounded optimality, within the limitations of this
hybrid generative planner and influence diagram architecture.


title:
Inference Using Message Propagation and Topology Transformation in
  Vector Gaussian Continuous Networks

abstract:
  We extend Gaussian networks - directed acyclic graphs that encode
probabilistic relationships between variables - to its vector form. Vector
Gaussian continuous networks consist of composite nodes representing
multivariates, that take continuous values. These vector or composite nodes can
represent correlations between parents, as opposed to conventional univariate
nodes. We derive rules for inference in these networks based on two methods:
message propagation and topology transformation. These two approaches lead to
the development of algorithms, that can be implemented in either a centralized
or a decentralized manner. The domain of application of these networks are
monitoring and estimation problems. This new representation along with the
rules for inference developed here can be used to derive current Bayesian
algorithms such as the Kalman filter, and provide a rich foundation to develop
new algorithms. We illustrate this process by deriving the decentralized form
of the Kalman filter. This work unifies concepts from artificial intelligence
and modern control theory.


title:
A Structurally and Temporally Extended Bayesian Belief Network Model:
  Definitions, Properties, and Modeling Techniques

abstract:
  We developed the language of Modifiable Temporal Belief Networks (MTBNs) as a
structural and temporal extension of Bayesian Belief Networks (BNs) to
facilitate normative temporal and causal modeling under uncertainty. In this
paper we present definitions of the model, its components, and its fundamental
properties. We also discuss how to represent various types of temporal
knowledge, with an emphasis on hybrid temporal-explicit time modeling, dynamic
structures, avoiding causal temporal inconsistencies, and dealing with models
that involve simultaneously actions (decisions) and causal and non-causal
associations. We examine the relationships among BNs, Modifiable Belief
Networks, and MTBNs with a single temporal granularity, and suggest areas of
application suitable to each one of them.


title: An Alternative Markov Property for Chain Graphs

abstract:
  Graphical Markov models use graphs, either undirected, directed, or mixed, to
represent possible dependences among statistical variables. Applications of
undirected graphs (UDGs) include models for spatial dependence and image
analysis, while acyclic directed graphs (ADGs), which are especially convenient
for statistical analysis, arise in such fields as genetics and psychometrics
and as models for expert systems and Bayesian belief networks. Lauritzen,
Wermuth and Frydenberg (LWF) introduced a Markov property for chain graphs,
which are mixed graphs that can be used to represent simultaneously both causal
and associative dependencies and which include both UDGs and ADGs as special
cases. In this paper an alternative Markov property (AMP) for chain graphs is
introduced, which in some ways is a more direct extension of the ADG Markov
property than is the LWF property for chain graph.


title: Plan Development using Local Probabilistic Models

abstract:
  Approximate models of world state transitions are necessary when building
plans for complex systems operating in dynamic environments. External event
probabilities can depend on state feature values as well as time spent in that
particular state. We assign temporally -dependent probability functions to
state transitions. These functions are used to locally compute state
probabilities, which are then used to select highly probable goal paths and
eliminate improbable states. This probabilistic model has been implemented in
the Cooperative Intelligent Real-time Control Architecture (CIRCA), which
combines an AI planner with a separate real-time system such that plans are
developed, scheduled, and executed with real-time guarantees. We present flight
simulation tests that demonstrate how our probabilistic model may improve CIRCA
performance.


title: Entailment in Probability of Thresholded Generalizations

abstract:
  A nonmonotonic logic of thresholded generalizations is presented. Given
propositions A and B from a language L and a positive integer k, the
thresholded generalization A=>B{k} means that the conditional probability
P(B|A) falls short of one by no more than c*d^k. A two-level probability
structure is defined. At the lower level, a model is defined to be a
probability function on L. At the upper level, there is a probability
distribution over models. A definition is given of what it means for a
collection of thresholded generalizations to entail another thresholded
generalization. This nonmonotonic entailment relation, called "entailment in
probability", has the feature that its conclusions are "probabilistically
trustworthy" meaning that, given true premises, it is improbable that an
entailed conclusion would be false. A procedure is presented for ascertaining
whether any given collection of premises entails any given conclusion. It is
shown that entailment in probability is closely related to Goldszmidt and
Pearl's System-Z^+, thereby demonstrating that the conclusions of System-Z^+
are probabilistically trustworthy.


title: Object Recognition with Imperfect Perception and Redundant Description

abstract:
  This paper deals with a scene recognition system in a robotics contex. The
general problem is to match images with <I>a priori</I> descriptions. A typical
mission would consist in identifying an object in an installation with a vision
system situated at the end of a manipulator and with a human operator provided
description, formulated in a pseudo-natural language, and possibly redundant.
The originality of this work comes from the nature of the description, from the
special attention given to the management of imprecision and uncertainty in the
interpretation process and from the way to assess the description redundancy so
as to reinforce the overall matching likelihood.


title:
Approximations for Decision Making in the Dempster-Shafer Theory of
  Evidence

abstract:
  The computational complexity of reasoning within the Dempster-Shafer theory
of evidence is one of the main points of criticism this formalism has to face.
To overcome this difficulty various approximation algorithms have been
suggested that aim at reducing the number of focal elements in the belief
functions involved. Besides introducing a new algorithm using this method, this
paper describes an empirical study that examines the appropriateness of these
approximation procedures in decision making situations. It presents the
empirical findings and discusses the various tradeoffs that have to be taken
into account when actually applying one of these methods.


title:
A Sufficiently Fast Algorithm for Finding Close to Optimal Junction
  Trees

abstract:
  An algorithm is developed for finding a close to optimal junction tree of a
given graph G. The algorithm has a worst case complexity O(c^k n^a) where a and
c are constants, n is the number of vertices, and k is the size of the largest
clique in a junction tree of G in which this size is minimized. The algorithm
guarantees that the logarithm of the size of the state space of the heaviest
clique in the junction tree produced is less than a constant factor off the
optimal value. When k = O(log n), our algorithm yields a polynomial inference
algorithm for Bayesian networks.


title:
Coping with the Limitations of Rational Inference in the Framework of
  Possibility Theory

abstract:
  Possibility theory offers a framework where both Lehmann's "preferential
inference" and the more productive (but less cautious) "rational closure
inference" can be represented. However, there are situations where the second
inference does not provide expected results either because it cannot produce
them, or even provide counter-intuitive conclusions. This state of facts is not
due to the principle of selecting a unique ordering of interpretations (which
can be encoded by one possibility distribution), but rather to the absence of
constraints expressing pieces of knowledge we have implicitly in mind. It is
advocated in this paper that constraints induced by independence information
can help finding the right ordering of interpretations. In particular,
independence constraints can be systematically assumed with respect to formulas
composed of literals which do not appear in the conditional knowledge base, or
for default rules with respect to situations which are "normal" according to
the other default rules in the base. The notion of independence which is used
can be easily expressed in the qualitative setting of possibility theory.
Moreover, when a counter-intuitive plausible conclusion of a set of defaults,
is in its rational closure, but not in its preferential closure, it is always
possible to repair the set of defaults so as to produce the desired conclusion.


title: Arguing for Decisions: A Qualitative Model of Decision Making

abstract:
  We develop a qualitative model of decision making with two aims: to describe
how people make simple decisions and to enable computer programs to do the
same. Current approaches based on Planning or Decisions Theory either ignore
uncertainty and tradeoffs, or provide languages and algorithms that are too
complex for this task. The proposed model provides a language based on rules, a
semantics based on high probabilities and lexicographical preferences, and a
transparent decision procedure where reasons for and against decisions
interact. The model is no substitude for Decision Theory, yet for decisions
that people find easy to explain it may provide an appealing alternative.


title:
Learning Conventions in Multiagent Stochastic Domains using Likelihood
  Estimates

abstract:
  Fully cooperative multiagent systems - those in which agents share a joint
utility model- is of special interest in AI. A key problem is that of ensuring
that the actions of individual agents are coordinated, especially in settings
where the agents are autonomous decision makers. We investigate approaches to
learning coordinated strategies in stochastic domains where an agent's actions
are not directly observable by others. Much recent work in game theory has
adopted a Bayesian learning perspective to the more general problem of
equilibrium selection, but tends to assume that actions can be observed. We
discuss the special problems that arise when actions are not observable,
including effects on rates of convergence, and the effect of action failure
probabilities and asymmetries. We also use likelihood estimates as a means of
generalizing fictitious play learning models in our setting. Finally, we
propose the use of maximum likelihood as a means of removing strategies from
consideration, with the aim of convergence to a conventional equilibrium, at
which point learning and deliberation can cease.


title: Context-Specific Independence in Bayesian Networks

abstract:
  Bayesian networks provide a language for qualitatively representing the
conditional independence properties of a distribution. This allows a natural
and compact representation of the distribution, eases knowledge acquisition,
and supports effective inference algorithms. It is well-known, however, that
there are certain independencies that we cannot capture qualitatively within
the Bayesian network structure: independencies that hold only in certain
contexts, i.e., given a specific assignment of values to certain variables. In
this paper, we propose a formal notion of context-specific independence (CSI),
based on regularities in the conditional probability tables (CPTs) at a node.
We present a technique, analogous to (and based on) d-separation, for
determining when such independence holds in a given network. We then focus on a
particular qualitative representation scheme - tree-structured CPTs - for
capturing CSI. We suggest ways in which this representation can be used to
support effective inference algorithms. In particular, we present a structural
decomposition of the resulting network which can improve the performance of
clustering algorithms, and an alternative algorithm based on cutset
conditioning.


title:
Decision-Theoretic Troubleshooting: A Framework for Repair and
  Experiment

abstract:
  We develop and extend existing decision-theoretic methods for troubleshooting
a nonfunctioning device. Traditionally, diagnosis with Bayesian networks has
focused on belief updating---determining the probabilities of various faults
given current observations. In this paper, we extend this paradigm to include
taking actions. In particular, we consider three classes of actions: (1) we can
make observations regarding the behavior of a device and infer likely faults as
in traditional diagnosis, (2) we can repair a component and then observe the
behavior of the device to infer likely faults, and (3) we can change the
configuration of the device, observe its new behavior, and infer the likelihood
of faults. Analysis of latter two classes of troubleshooting actions requires
incorporating notions of persistence into the belief-network formalism used for
probabilistic inference.


title: Tail Sensitivity Analysis in Bayesian Networks

abstract:
  The paper presents an efficient method for simulating the tails of a target
variable Z=h(X) which depends on a set of basic variables X=(X_1, ..., X_n). To
this aim, variables X_i, i=1, ..., n are sequentially simulated in such a
manner that Z=h(x_1, ..., x_i-1, X_i, ..., X_n) is guaranteed to be in the tail
of Z. When this method is difficult to apply, an alternative method is
proposed, which leads to a low rejection proportion of sample values, when
compared with the Monte Carlo method. Both methods are shown to be very useful
to perform a sensitivity analysis of Bayesian networks, when very large
confidence intervals for the marginal/conditional probabilities are required,
as in reliability or risk analysis. The methods are shown to behave best when
all scores coincide. The required modifications for this to occur are
discussed. The methods are illustrated with several examples and one example of
application to a real case is used to illustrate the whole process.


title:
Decision-Analytic Approaches to Operational Decision Making: Application
  and Observation

abstract:
  Decision analysis (DA) and the rich set of tools developed by researchers in
decision making under uncertainty show great potential to penetrate the
technological content of the products and services delivered by firms in a
variety of industries as well as the business processes used to deliver those
products and services to market. In this paper I describe work in progress at
Sun Microsystems in the application of decision-analytic methods to Operational
Decision Making (ODM) in its World-Wide Operations (WWOPS) Business Management
Group. Working with membersof product engineering, marketing, and sales,
operations planners from WWOPS have begun to use a decision-analytic framework
called SCRAM (Supply Communication/Risk Assessment and Management) to structure
and solve problems in product planning, tracking, and transition. Concepts such
as information value provide a powerful method of managing huge information
sets and thereby enable managers to focus attention on factors that matter most
for their business. Finally, our process-oriented introduction of
decision-analytic methods to Sun managers has led to a focused effort to
develop decision support software based on methods from decision making under
uncertainty.


title: Learning Equivalence Classes of Bayesian Networks Structures

abstract:
  Approaches to learning Bayesian networks from data typically combine a
scoring function with a heuristic search procedure. Given a Bayesian network
structure, many of the scoring functions derived in the literature return a
score for the entire equivalence class to which the structure belongs. When
using such a scoring function, it is appropriate for the heuristic search
algorithm to search over equivalence classes of Bayesian networks as opposed to
individual structures. We present the general formulation of a search space for
which the states of the search correspond to equivalence classes of structures.
Using this space, any one of a number of heuristic search algorithms can easily
be applied. We compare greedy search performance in the proposed search space
to greedy search performance in a search space for which the states correspond
to individual Bayesian network structures.


title:
Efficient Approximations for the Marginal Likelihood of Incomplete Data
  Given a Bayesian Network

abstract:
  We discuss Bayesian methods for learning Bayesian networks when data sets are
incomplete. In particular, we examine asymptotic approximations for the
marginal likelihood of incomplete data given a Bayesian network. We consider
the Laplace approximation and the less accurate but more efficient BIC/MDL
approximation. We also consider approximations proposed by Draper (1993) and
Cheeseman and Stutz (1995). These approximations are as efficient as BIC/MDL,
but their accuracy has not been studied in any depth. We compare the accuracy
of these approximations under the assumption that the Laplace approximation is
the most accurate. In experiments using synthetic data generated from discrete
naive-Bayes models having a hidden root node, we find that the CS measure is
the most accurate.


title: Independence with Lower and Upper Probabilities

abstract:
  It is shown that the ability of the interval probability representation to
capture epistemological independence is severely limited. Two events are
epistemologically independent if knowledge of the first event does not alter
belief (i.e., probability bounds) about the second. However, independence in
this form can only exist in a 2-monotone probability function in degenerate
cases i.e., if the prior bounds are either point probabilities or entirely
vacuous. Additional limitations are characterized for other classes of lower
probabilities as well. It is argued that these phenomena are simply a matter of
interpretation. They appear to be limitations when one interprets probability
bounds as a measure of epistemological indeterminacy (i.e., uncertainty arising
from a lack of knowledge), but are exactly as one would expect when probability
intervals are interpreted as representations of ontological indeterminacy
(indeterminacy introduced by structural approximations). The ontological
interpretation is introduced and discussed.


title: Propagation of 2-Monotone Lower Probabilities on an Undirected Graph

abstract:
  Lower and upper probabilities, also known as Choquet capacities, are widely
used as a convenient representation for sets of probability distributions. This
paper presents a graphical decomposition and exact propagation algorithm for
computing marginal posteriors of 2-monotone lower probabilities (equivalently,
2-alternating upper probabilities).


title:
Quasi-Bayesian Strategies for Efficient Plan Generation: Application to
  the Planning to Observe Problem

abstract:
  Quasi-Bayesian theory uses convex sets of probability distributions and
expected loss to represent preferences about plans. The theory focuses on
decision robustness, i.e., the extent to which plans are affected by deviations
in subjective assessments of probability. The present work presents solutions
for plan generation when robustness of probability assessments must be
included: plans contain information about the robustness of certain actions.
The surprising result is that some problems can be solved faster in the
Quasi-Bayesian framework than within usual Bayesian theory. We investigate this
on the planning to observe problem, i.e., an agent must decide whether to take
new observations or not. The fundamental question is: How, and how much, to
search for a "best" plan, based on the robustness of probability assessments?
Plan generation algorithms are derived in the context of material
classification with an acoustic robotic probe. A package that constructs
Quasi-Bayesian plans is available through anonymous ftp.


title: Some Experiments with Real-Time Decision Algorithms

abstract:
  Real-time Decision algorithms are a class of incremental resource-bounded
[Horvitz, 89] or anytime [Dean, 93] algorithms for evaluating influence
diagrams. We present a test domain for real-time decision algorithms, and the
results of experiments with several Real-time Decision Algorithms in this
domain. The results demonstrate high performance for two algorithms, a
decision-evaluation variant of Incremental Probabilisitic Inference [D'Ambrosio
93] and a variant of an algorithm suggested by Goldszmidt, [Goldszmidt, 95],
PK-reduced. We discuss the implications of these experimental results and
explore the broader applicability of these algorithms.


title:
Bucket Elimination: A Unifying Framework for Several Probabilistic
  Inference

abstract:
  Probabilistic inference algorithms for finding the most probable explanation,
the maximum aposteriori hypothesis, and the maximum expected utility and for
updating belief are reformulated as an elimination--type algorithm called
bucket elimination. This emphasizes the principle common to many of the
algorithms appearing in that literature and clarifies their relationship to
nonserial dynamic programming algorithms. We also present a general way of
combining conditioning and elimination within this framework. Bounds on
complexity are given for all the algorithms as a function of the problem's
structure.


title: Topological Parameters for Time-Space Tradeoff

abstract:
  In this paper we propose a family of algorithms combining tree-clustering
with conditioning that trade space for time. Such algorithms are useful for
reasoning in probabilistic and deterministic networks as well as for
accomplishing optimization tasks. By analyzing the problem structure it will be
possible to select from a spectrum the algorithm that best meets a given
time-space specification.


title:
Sound Abstraction of Probabilistic Actions in The Constraint Mass
  Assignment Framework

abstract:
  This paper provides a formal and practical framework for sound abstraction of
probabilistic actions. We start by precisely defining the concept of sound
abstraction within the context of finite-horizon planning (where each plan is a
finite sequence of actions). Next we show that such abstraction cannot be
performed within the traditional probabilistic action representation, which
models a world with a single probability distribution over the state space. We
then present the constraint mass assignment representation, which models the
world with a set of probability distributions and is a generalization of mass
assignment representations. Within this framework, we present sound abstraction
procedures for three types of action abstraction. We end the paper with
discussions and related work on sound and approximate abstraction. We give
pointers to papers in which we discuss other sound abstraction-related issues,
including applications, estimating loss due to abstraction, and automatically
generating abstraction hierarchies.


title: Belief Revision with Uncertain Inputs in the Possibilistic Setting

abstract:
  This paper discusses belief revision under uncertain inputs in the framework
of possibility theory. Revision can be based on two possible definitions of the
conditioning operation, one based on min operator which requires a purely
ordinal scale only, and another based on product, for which a richer structure
is needed, and which is a particular case of Dempster's rule of conditioning.
Besides, revision under uncertain inputs can be understood in two different
ways depending on whether the input is viewed, or not, as a constraint to
enforce. Moreover, it is shown that M.A. Williams' transmutations, originally
defined in the setting of Spohn's functions, can be captured in this framework,
as well as Boutilier's natural revision.


title:
An Evaluation of Structural Parameters for Probabilistic Reasoning:
  Results on Benchmark Circuits

abstract:
  Many algorithms for processing probabilistic networks are dependent on the
topological properties of the problem's structure. Such algorithms (e.g.,
clustering, conditioning) are effective only if the problem has a sparse graph
captured by parameters such as tree width and cycle-cut set size. In this paper
we initiate a study to determine the potential of structure-based algorithms in
real-life applications. We analyze empirically the structural properties of
problems coming from the circuit diagnosis domain. Specifically, we locate
those properties that capture the effectiveness of clustering and conditioning
as well as of a family of conditioning+clustering algorithms designed to
gradually trade space for time. We perform our analysis on 11 benchmark
circuits widely used in the testing community. We also report on the effect of
ordering heuristics on tree-clustering and show that, on our benchmarks, the
well-known max-cardinality ordering is substantially inferior to an ordering
called min-degree.


title: Learning Bayesian Networks with Local Structure

abstract:
  In this paper we examine a novel addition to the known methods for learning
Bayesian networks from data that improves the quality of the learned networks.
Our approach explicitly represents and learns the local structure in the
conditional probability tables (CPTs), that quantify these networks. This
increases the space of possible models, enabling the representation of CPTs
with a variable number of parameters that depends on the learned local
structures. The resulting learning procedure is capable of inducing models that
better emulate the real complexity of the interactions present in the data. We
describe the theoretical foundations and practical aspects of learning local
structures, as well as an empirical evaluation of the proposed method. This
evaluation indicates that learning curves characterizing the procedure that
exploits the local structure converge faster than these of the standard
procedure. Our results also show that networks learned with local structure
tend to be more complex (in terms of arcs), yet require less parameters.


title: A Qualitative Markov Assumption and its Implications for Belief Change

abstract:
  The study of belief change has been an active area in philosophy and AI. In
recent years two special cases of belief change, belief revision and belief
update, have been studied in detail. Roughly, revision treats a surprising
observation as a sign that previous beliefs were wrong, while update treats a
surprising observation as an indication that the world has changed. In general,
we would expect that an agent making an observation may both want to revise
some earlier beliefs and assume that some change has occurred in the world. We
define a novel approach to belief change that allows us to do this, by applying
ideas from probability theory in a qualitative setting. The key idea is to use
a qualitative Markov assumption, which says that state transitions are
independent. We show that a recent approach to modeling qualitative uncertainty
using plausibility measures allows us to make such a qualitative Markov
assumption in a relatively straightforward way, and show how the Markov
assumption can be used to provide an attractive belief-change model.


title: On the Sample Complexity of Learning Bayesian Networks

abstract:
  In recent years there has been an increasing interest in learning Bayesian
networks from data. One of the most effective methods for learning such
networks is based on the minimum description length (MDL) principle. Previous
work has shown that this learning procedure is asymptotically successful: with
probability one, it will converge to the target distribution, given a
sufficient number of samples. However, the rate of this convergence has been
hitherto unknown. In this work we examine the sample complexity of MDL based
learning procedures for Bayesian networks. We show that the number of samples
needed to learn an epsilon-close approximation (in terms of entropy distance)
with confidence delta is O((1/epsilon)^(4/3)log(1/epsilon)log(1/delta)loglog
(1/delta)). This means that the sample complexity is a low-order polynomial in
the error threshold and sub-linear in the confidence bound. We also discuss how
the constants in this term depend on the complexity of the target distribution.
Finally, we address questions of asymptotic minimality and propose a method for
using the sample complexity results to speed up the learning process.


title: Asymptotic Model Selection for Directed Networks with Hidden Variables

abstract:
  We extend the Bayesian Information Criterion (BIC), an asymptotic
approximation for the marginal likelihood, to Bayesian networks with hidden
variables. This approximation can be used to select models given large samples
of data. The standard BIC as well as our extension punishes the complexity of a
model according to the dimension of its parameters. We argue that the dimension
of a Bayesian network with hidden variables is the rank of the Jacobian matrix
of the transformation between the parameters of the network and the parameters
of the observable variables. We compute the dimensions of several networks
including the naive Bayes model with a hidden root node.


title: Theoretical Foundations for Abstraction-Based Probabilistic Planning

abstract:
  Modeling worlds and actions under uncertainty is one of the central problems
in the framework of decision-theoretic planning. The representation must be
general enough to capture real-world problems but at the same time it must
provide a basis upon which theoretical results can be derived. The central
notion in the framework we propose here is that of the affine-operator, which
serves as a tool for constructing (convex) sets of probability distributions,
and which can be considered as a generalization of belief functions and
interval mass assignments. Uncertainty in the state of the worlds is modeled
with sets of probability distributions, represented by affine-trees while
actions are defined as tree-manipulators. A small set of key properties of the
affine-operator is presented, forming the basis for most existing
operator-based definitions of probabilistic action projection and action
abstraction. We derive and prove correct three projection rules, which vividly
illustrate the precision-complexity tradeoff in plan projection. Finally, we
show how the three types of action abstraction identified by Haddawy and Doan
are manifested in the present framework.


title:
Why Is Diagnosis Using Belief Networks Insensitive to Imprecision In
  Probabilities?

abstract:
  Recent research has found that diagnostic performance with Bayesian belief
networks is often surprisingly insensitive to imprecision in the numerical
probabilities. For example, the authors have recently completed an extensive
study in which they applied random noise to the numerical probabilities in a
set of belief networks for medical diagnosis, subsets of the CPCS network, a
subset of the QMR (Quick Medical Reference) focused on liver and bile diseases.
The diagnostic performance in terms of the average probabilities assigned to
the actual diseases showed small sensitivity even to large amounts of noise. In
this paper, we summarize the findings of this study and discuss possible
explanations of this low sensitivity. One reason is that the criterion for
performance is average probability of the true hypotheses, rather than average
error in probability, which is insensitive to symmetric noise distributions.
But, we show that even asymmetric, logodds-normal noise has modest effects. A
second reason is that the gold-standard posterior probabilities are often near
zero or one, and are little disturbed by noise.


title: Flexible Policy Construction by Information Refinement

abstract:
  We report on work towards flexible algorithms for solving decision problems
represented as influence diagrams. An algorithm is given to construct a tree
structure for each decision node in an influence diagram. Each tree represents
a decision function and is constructed incrementally. The improvements to the
tree converge to the optimal decision function (neglecting computational costs)
and the asymptotic behaviour is only a constant factor worse than dynamic
programming techniques, counting the number of Bayesian network queries.
Empirical results show how expected utility increases with the size of the tree
and the number of Bayesian net calculations.


title:
Efficient Search-Based Inference for Noisy-OR Belief Networks:
  TopEpsilon

abstract:
  Inference algorithms for arbitrary belief networks are impractical for large,
complex belief networks. Inference algorithms for specialized classes of belief
networks have been shown to be more efficient. In this paper, we present a
search-based algorithm for approximate inference on arbitrary, noisy-OR belief
networks, generalizing earlier work on search-based inference for two-level,
noisy-OR belief networks. Initial experimental results appear promising.


title: A Probabilistic Model For Sensor Validation

abstract:
  The validation of data from sensors has become an important issue in the
operation and control of modern industrial plants. One approach is to use
knowledge based techniques to detect inconsistencies in measured data. This
article presents a probabilistic model for the detection of such
inconsistencies. Based on probability propagation, this method is able to find
the existence of a possible fault among the set of sensors. That is, if an
error exists, many sensors present an apparent fault due to the propagation
from the sensor(s) with a real fault. So the fault detection mechanism can only
tell if a sensor has a potential fault, but it can not tell if the fault is
real or apparent. So the central problem is to develop a theory, and then an
algorithm, for distinguishing real and apparent faults, given that one or more
sensors can fail at the same time. This article then, presents an approach
based on two levels: (i) probabilistic reasoning, to detect a potential fault,
and (ii) constraint management, to distinguish the real fault from the apparent
ones. The proposed approach is exemplified by applying it to a power plant
model.


title: Computing Upper and Lower Bounds on Likelihoods in Intractable Networks

abstract:
  We present deterministic techniques for computing upper and lower bounds on
marginal probabilities in sigmoid and noisy-OR networks. These techniques
become useful when the size of the network (or clique size) precludes exact
computations. We illustrate the tightness of the bounds by numerical
experiments.


title: MIDAS - An Influence Diagram for Management of Mildew in Winter Wheat

abstract:
  We present a prototype of a decision support system for management of the
fungal disease mildew in winter wheat. The prototype is based on an influence
diagram which is used to determine the optimal time and dose of mildew
treatments. This involves multiple decision opportunities over time,
stochasticity, inaccurate information and incomplete knowledge. The paper
describes the practical and theoretical problems encountered during the
construction of the influence diagram, and also the experience with the
prototype.


title:
Computational Complexity Reduction for BN2O Networks Using Similarity of
  States

abstract:
  Although probabilistic inference in a general Bayesian belief network is an
NP-hard problem, computation time for inference can be reduced in most
practical cases by exploiting domain knowledge and by making approximations in
the knowledge representation. In this paper we introduce the property of
similarity of states and a new method for approximate knowledge representation
and inference which is based on this property. We define two or more states of
a node to be similar when the ratio of their probabilities, the likelihood
ratio, does not depend on the instantiations of the other nodes in the network.
We show that the similarity of states exposes redundancies in the joint
probability distribution which can be exploited to reduce the computation time
of probabilistic inference in networks with multiple similar states, and that
the computational complexity in the networks with exponentially many similar
states might be polynomial. We demonstrate our ideas on the example of a BN2O
network -- a two layer network often used in diagnostic problems -- by reducing
it to a very close network with multiple similar states. We show that the
answers to practical queries converge very fast to the answers obtained with
the original network. The maximum error is as low as 5% for models that require
only 10% of the computation time needed by the original BN2O model.


title: Uncertain Inferences and Uncertain Conclusions

abstract:
  Uncertainty may be taken to characterize inferences, their conclusions, their
premises or all three. Under some treatments of uncertainty, the inferences
itself is never characterized by uncertainty. We explore both the significance
of uncertainty in the premises and in the conclusion of an argument that
involves uncertainty. We argue that for uncertainty to characterize the
conclusion of an inference is natural, but that there is an interplay between
uncertainty in the premises and uncertainty in the procedure of argument
itself. We show that it is possible in principle to incorporate all uncertainty
in the premises, rendering uncertainty arguments deductively valid. But we then
argue (1) that this does not reflect human argument, (2) that it is
computationally costly, and (3) that the gain in simplicity obtained by
allowing uncertainty inference can sometimes outweigh the loss of flexibility
it entails.


title: Bayesian Learning of Loglinear Models for Neural Connectivity

abstract:
  This paper presents a Bayesian approach to learning the connectivity
structure of a group of neurons from data on configuration frequencies. A major
objective of the research is to provide statistical tools for detecting changes
in firing patterns with changing stimuli. Our framework is not restricted to
the well-understood case of pair interactions, but generalizes the Boltzmann
machine model to allow for higher order interactions. The paper applies a
Markov Chain Monte Carlo Model Composition (MC3) algorithm to search over
connectivity structures and uses Laplace's method to approximate posterior
probabilities of structures. Performance of the methods was tested on synthetic
data. The models were also applied to data obtained by Vaadia on multi-unit
recordings of several neurons in the visual cortex of a rhesus monkey in two
different attentional states. Results confirmed the experimenters' conjecture
that different attentional states were associated with different interaction
structures.


title: Network Engineering for Complex Belief Networks

abstract:
  Like any large system development effort, the construction of a complex
belief network model requires systems engineering to manage the design and
construction process. We propose a rapid prototyping approach to network
engineering. We describe criteria for identifying network modules and the use
of "stubs" to represent not-yet-constructed modules. We propose an object
oriented representation for belief networks which captures the semantics of the
problem in addition to conditional independencies and probabilities. Methods
for evaluating complex belief network models are discussed. The ideas are
illustrated with examples from a large belief network construction problem in
the military intelligence domain.


title: Probabilistic Disjunctive Logic Programming

abstract:
  In this paper we propose a framework for combining Disjunctive Logic
Programming and Poole's Probabilistic Horn Abduction. We use the concept of
hypothesis to specify the probability structure. We consider the case in which
probabilistic information is not available. Instead of using probability
intervals, we allow for the specification of the probabilities of disjunctions.
Because minimal models are used as characteristic models in disjunctive logic
programming, we apply the principle of indifference on the set of minimal
models to derive default probability values. We define the concepts of
explanation and partial explanation of a formula, and use them to determine the
default probability distribution(s) induced by a program. An algorithm for
calculating the default probability of a goal is presented.


title: Toward a Market Model for Bayesian Inference

abstract:
  We present a methodology for representing probabilistic relationships in a
general-equilibrium economic model. Specifically, we define a precise mapping
from a Bayesian network with binary nodes to a market price system where
consumers and producers trade in uncertain propositions. We demonstrate the
correspondence between the equilibrium prices of goods in this economy and the
probabilities represented by the Bayesian network. A computational market model
such as this may provide a useful framework for investigations of belief
aggregation, distributed probabilistic inference, resource allocation under
uncertainty, and other problems of decentralized uncertainty.


title: Geometric Implications of the Naive Bayes Assumption

abstract:
  A naive (or Idiot) Bayes network is a network with a single hypothesis node
and several observations that are conditionally independent given the
hypothesis. We recently surveyed a number of members of the UAI community and
discovered a general lack of understanding of the implications of the Naive
Bayes assumption on the kinds of problems that can be solved by these networks.
It has long been recognized [Minsky 61] that if observations are binary, the
decision surfaces in these networks are hyperplanes. We extend this result
(hyperplane separability) to Naive Bayes networks with m-ary observations. In
addition, we illustrate the effect of observation-observation dependencies on
decision surfaces. Finally, we discuss the implications of these results on
knowledge acquisition and research in learning.


title: Identifying Independencies in Causal Graphs with Feedback

abstract:
  We show that the d -separation criterion constitutes a valid test for
conditional independence relationships that are induced by feedback systems
involving discrete variables.


title: A Graph-Theoretic Analysis of Information Value

abstract:
  We derive qualitative relationships about the informational relevance of
variables in graphical decision models based on a consideration of the topology
of the models. Specifically, we identify dominance relations for the expected
value of information on chance variables in terms of their position and
relationships in influence diagrams. The qualitative relationships can be
harnessed to generate nonnumerical procedures for ordering uncertain variables
in a decision model by their informational relevance.


title:
A Framework for Decision-Theoretic Planning I: Combining the Situation
  Calculus, Conditional Plans, Probability and Utility

abstract:
  This paper shows how we can combine logical representations of actions and
decision theory in such a manner that seems natural for both. In particular we
assume an axiomatization of the domain in terms of situation calculus, using
what is essentially Reiter's solution to the frame problem, in terms of the
completion of the axioms defining the state change. Uncertainty is handled in
terms of the independent choice logic, which allows for independent choices and
a logic program that gives the consequences of the choices. As part of the
consequences are a specification of the utility of (final) states. The robot
adopts robot plans, similar to the GOLOG programming language. Within this
logic, we can define the expected utility of a conditional plan, based on the
axiomatization of the actions, the uncertainty and the utility. The ?planning'
problem is to find the plan with the highest expected utility. This is related
to recent structured representations for POMDPs; here we use stochastic
situation calculus rules to specify the state transition function and the
reward/value function. Finally we show that with stochastic frame axioms,
actions representations in probabilistic STRIPS are exponentially larger than
using the representation proposed here.


title: Optimal Monte Carlo Estimation of Belief Network Inference

abstract:
  We present two Monte Carlo sampling algorithms for probabilistic inference
that guarantee polynomial-time convergence for a larger class of network than
current sampling algorithms provide. These new methods are variants of the
known likelihood weighting algorithm. We use of recent advances in the theory
of optimal stopping rules for Monte Carlo simulation to obtain an inference
approximation with relative error epsilon and a small failure probability
delta. We present an empirical evaluation of the algorithms which demonstrates
their improved performance.


title: A Discovery Algorithm for Directed Cyclic Graphs

abstract:
  Directed acyclic graphs have been used fruitfully to represent causal
strucures (Pearl 1988). However, in the social sciences and elsewhere models
are often used which correspond both causally and statistically to directed
graphs with directed cycles (Spirtes 1995). Pearl (1993) discussed predicting
the effects of intervention in models of this kind, so-called linear
non-recursive structural equation models. This raises the question of whether
it is possible to make inferences about causal structure with cycles, form
sample data. In particular do there exist general, informative, feasible and
reliable precedures for inferring causal structure from conditional
independence relations among variables in a sample generated by an unknown
causal structure? In this paper I present a discovery algorithm that is correct
in the large sample limit, given commonly (but often implicitly) made plausible
assumptions, and which provides information about the existence or
non-existence of causal pathways from one variable to another. The algorithm is
polynomial on sparse graphs.