title: New enumeration formulas for alternating sign matrices and square ice partition functions

abstract: The refined enumeration of alternating sign matrices (ASMs) of given order having prescribed behavior near one or more of their boundary edges has been the subject of extensive study, starting with the Refined Alternating Sign Matrix Conjecture of Mills-Robbins-Rumsey, its proof by Zeilberger, and more recent work on doubly-refined and triply-refined enumeration by several authors. In this paper we extend the previously known results on this problem by deriving explicit enumeration formulas for the "top-left-bottom" (triply-refined) and "top-left-bottom-right" (quadruply-refined) enumerations. The latter case solves the problem of computing the full boundary correlation function for ASMs. The enumeration formulas are proved by deriving new representations, which are of independent interest, for the partition function of the square ice model with domain wall boundary conditions at the "combinatorial point" 2{\pi}/3.

categories: math.CO cond-mat.stat-mech math-ph math.MP math.PR


title: Nonlinear modes in finite-dimensional PT-symmetric systems

abstract: By rearrangements of waveguide arrays with gain and losses one can simulate transformations among parity-time (PT-) symmetric systems not affecting their pure real linear spectra. Subject to such transformations, however, the nonlinear properties of the systems undergo significant changes. On an example of an array of four waveguides described by the discrete nonlinear Schr\"odinger equation with dissipation and gain, we show that the equivalence of the underlying linear spectra implies similarity of neither structure nor stability of the nonlinear modes in the arrays. Even the existence of one-parametric families of nonlinear modes is not guaranteed by the PT symmetry of a newly obtained system. Neither the stability is directly related to the PT symmetry: stable nonlinear modes exist even when the spectrum of the linear array is not purely real. We use graph representation of PT-symmetric networks allowing for simple illustration of linearly equivalent networks and indicating on their possible experimental design.


title: Information Transmission using the Nonlinear Fourier Transform, Part I: Mathematical Tools

abstract: The nonlinear Fourier transform (NFT), a powerful tool in soliton theory and exactly solvable models, is a method for solving integrable partial differential equations governing wave propagation in certain nonlinear media. The NFT decorrelates signal degrees-of-freedom in such models, in much the same way that the Fourier transform does for linear systems. In this three-part series of papers, this observation is exploited for data transmission over integrable channels such as optical fibers, where pulse propagation is governed by the nonlinear Schr\"odinger equation. In this transmission scheme, which can be viewed as a nonlinear analogue of orthogonal frequency-division multiplexing commonly used in linear channels, information is encoded in the nonlinear frequencies and their spectral amplitudes. Unlike most other fiber-optic transmission schemes, this technique deals with both dispersion and nonlinearity directly and unconditionally without the need for dispersion or nonlinearity compensation methods. This first paper explains the mathematical tools that underlie the method.


title: Two-dimensional incommensurate magnetic fluctuations in Sr$_2$(Ru$_{0.99}$Ti$_{0.01}$)O$_4$

abstract: We investigate the imaginary part of the wave vector dependent dynamic spin susceptibility in Sr$_2$(Ru$_{0.99}$Ti$_{0.01}$)O$_4$ as a function of temperature using neutron scattering. At T=5 K, two-dimensional incommensurate (IC) magnetic fluctuations are clearly observed around $\mathbf{Q}_\text{c}=(0.3,0.3,L)$ up to approximately 60 meV energy transfer. We find that the IC excitations disperse to ridges around the $(\pi,\pi)$ point. Below 50 K, the energy and temperature dependent excitations are well described by the phenomenological response function for a Fermi liquid system with a characteristic energy of 4.0(1) meV. Although the wave vector dependence of the IC magnetic fluctuations in Sr$_2$(Ru$_{0.99}$Ti$_{0.01}$)O$_4$ is similar to that in the Fermi liquid state of the parent compound, Sr$_2$RuO$_4$, the magnetic fluctuations are clearly suppressed by the Ti-doping.


title: A Weak Galerkin Mixed Finite Element Method for Second-Order Elliptic Problems

abstract: A new weak Galerkin (WG) method is introduced and analyzed for the second order elliptic equation formulated as a system of two first order linear equations. This method, called WG-MFEM, is designed by using discontinuous piecewise polynomials on finite element partitions with arbitrary shape of polygons/polyhedra. The WG-MFEM is capable of providing very accurate numerical approximations for both the primary and flux variables. Allowing the use of discontinuous approximating functions on arbitrary shape of polygons/polyhedra makes the method highly flexible in practical computation. Optimal order error estimates in both discrete $H^1$ and $L^2$ norms are established for the corresponding weak Galerkin mixed finite element solutions.


title: Spectral density in a nematic state of iron pnictides

abstract: Using cluster-perturbation theory, we calculate the spectral density A(k,w) for a nematic phase of models describing pnictide superconductors, where very short-range magnetic correlations choose the ordering vector (pi,0) over the equivalent (0,pi) and thus break the fourfold rotation symmetry of the underlying lattice without inducing long-range magnetic order. In excellent agreement with angle resolved photo-emission spectroscopy (ARPES), we find that the yz bands at X move to higher energies. When onsite Coulomb repulsion brings the system close to a spin--density-wave (SDW) and renormalizes the band width by a factor of approx. 2, even small anisotropic couplings of 10 to 15 meV strongly distort the bands, splitting the formerly degenerate states at X and Y by approx. 70 meV and shifting the yz states at X above the chemical potential. This similarity to the SDW bands is in excellent agreement with ARPES. An important difference to the SDW bands is that the yz bands still cross the Fermi level, again in agreement with experiment. We find that orbital weights near the Fermi surface provide a better characterization than overall orbital densities and orbital polarization.


title: TNOs are Cool: A survey of the trans-Neptunian region V. Physical characterization of 18 Plutinos using Herschel PACS observations

abstract: We present Herschel PACS photometry of 18 Plutinos and determine sizes and albedos for these objects using thermal modeling. We analyze our results for correlations, draw conclusions on the Plutino size distribution, and compare to earlier results. Flux densities are derived from PACS mini scan-maps using specialized data reduction and photometry methods. In order to improve the quality of our results, we combine our PACS data with existing Spitzer MIPS data where possible, and refine existing absolute magnitudes for the targets. The physical characterization of our sample is done using a thermal model. Uncertainties of the physical parameters are derived using customized Monte Carlo methods. The correlation analysis is performed using a bootstrap Spearman rank analysis. We find the sizes of our Plutinos to range from 150 to 730 km and geometric albedos to vary between 0.04 and 0.28. The average albedo of the sample is 0.08 \pm 0.03, which is comparable to the mean albedo of Centaurs, Jupiter Family comets and other Trans-Neptunian Objects. We were able to calibrate the Plutino size scale for the first time and find the cumulative Plutino size distribution to be best fit using a cumulative power law with q = 2 at sizes ranging from 120-400 km and q = 3 at larger sizes. We revise the bulk density of 1999 TC36 and find a density of 0.64 (+0.15/-0.11) g cm-3. On the basis of a modified Spearman rank analysis technique our Plutino sample appears to be biased with respect to object size but unbiased with respect to albedo. Furthermore, we find biases based on geometrical aspects and color in our sample. There is qualitative evidence that icy Plutinos have higher albedos than the average of the sample.


title: Stability of nonstationary states of spin-2 Bose-Einstein condensates

abstract: The dynamical stability of nonstationary states of homogeneous spin-2 rubidium Bose-Einstein condensates is studied. The states considered are such that the spin vector remains parallel to the magnetic field throughout the time evolution, making it possible to study the stability analytically. These states are shown to be stable in the absence of an external magnetic field, but they become unstable when a finite magnetic field is introduced. It is found that the growth rate and wavelength of the instabilities can be controlled by tuning the strength of the magnetic field and the size of the condensate.


title: Optomechanical circuits for nanomechanical continuous variable quantum state processing

abstract: We propose and analyze a nanomechanical architecture where light is used to perform linear quantum operations on a set of many vibrational modes. Suitable amplitude modulation of a single laser beam is shown to generate squeezing, entanglement, and state-transfer between modes that are selected according to their mechanical oscillation frequency. Current optomechanical devices based on photonic crystals may provide a platform for realizing this scheme.


title: Hecke algebras associated to $\Lambda$-adic modular forms

abstract: We show that if an Eisenstein component of the $p$-adic Hecke algebra associated to modular forms is Gorenstein, then it is necessary that the plus-part of a certain ideal class group is trivial. We also show that this condition is sufficient whenever a conjecture of Sharifi holds.


title: Comparison of EPOS and QGSJET-II in EAS Simulation using CORSIKA

abstract: In this work we compare the predictions of two representative hadronic interaction models, EPOS 1.99, and QGSJET II-03 with several extensive air showers (EAS) parameters for proton and iron primaries in the energy range $10^{17}$ - $10^{19} eV$ using CORSIKA-6990. The EAS parameters depth of shower maximum, shower size, size of muon shower, muon number distribution, electron number distribution,size of hadron shower, hadron energy sum, electron muon correlations, and, hadron energy spectra are studied in this paper.


title: Search for the time dependence of the 137Cs decay constant

abstract: Starting from June 2011, the activity of a 137Cs source has been measured by means of a HPGe detector installed deep underground in the Gran Sasso Laboratory. In total about 5100 energy spectra, one hour measuring time each, have been collected. These data allowed the search for time variations of the decay constant with periods from a few hours to 1 year. No signal with amplitude larger than 9.6{\cdot}10-5 at 95% C.L. has been detected. These limits are more than one order of magnitude lower than the values on the oscillation amplitude reported in literature. In particular, for 1 year period an oscillation amplitude larger than 8.5{\cdot}10-5 has been excluded at 95% C.L., independently of the phase. The same data give a value of 29.96{\pm}0.08 years for the 137Cs half life, in good agreement with the world mean value of 30.05{\pm}0.08 years.


title: Guaranteed clustering and biclustering via semidefinite programming

abstract: Identifying clusters of similar objects in data plays a significant role in a wide range of applications. As a model problem for clustering, we consider the densest k-disjoint-clique problem, whose goal is to identify the collection of k disjoint cliques of a given weighted complete graph maximizing the sum of the densities of the complete subgraphs induced by these cliques. In this paper, we establish conditions ensuring exact recovery of the densest k cliques of a given graph from the optimal solution of a particular semidefinite program. In particular, the semidefinite relaxation is exact for input graphs corresponding to data consisting of k large, distinct clusters and a smaller number of outliers. This approach also yields a semidefinite relaxation for the biclustering problem with similar recovery guarantees. Given a set of objects and a set of features exhibited by these objects, biclustering seeks to simultaneously group the objects and features according to their expression levels. This problem may be posed as partitioning the nodes of a weighted bipartite complete graph such that the sum of the densities of the resulting bipartite complete subgraphs is maximized. As in our analysis of the densest k-disjoint-clique problem, we show that the correct partition of the objects and features can be recovered from the optimal solution of a semidefinite program in the case that the given data consists of several disjoint sets of objects exhibiting similar features. Empirical evidence from numerical experiments supporting these theoretical guarantees is also provided.


title: Interfacial friction between semiflexible polymers and crystalline surfaces

abstract: The results obtained from molecular dynamics simulations of the friction at an interface between polymer melts and weakly attractive crystalline surfaces are reported. We consider a coarse-grained bead-spring model of linear chains with adjustable intrinsic stiffness. The structure and relaxation dynamics of polymer chains near interfaces are quantified by the radius of gyration and decay of the time autocorrelation function of the first normal mode. We found that the friction coefficient at small slip velocities exhibits a distinct maximum which appears due to shear-induced alignment of semiflexible chain segments in contact with solid walls. At large slip velocities the decay of the friction coefficient is independent of the chain stiffness. The data for the friction coefficient and shear viscosity are used to elucidate main trends in the nonlinear shear rate dependence of the slip length. The influence of chain stiffness on the relationship between the friction coefficient and the structure factor in the first fluid layer is discussed.


title: emcee: The MCMC Hammer

abstract: We introduce a stable, well tested Python implementation of the affine-invariant ensemble sampler for Markov chain Monte Carlo (MCMC) proposed by Goodman & Weare (2010). The code is open source and has already been used in several published projects in the astrophysics literature. The algorithm behind emcee has several advantages over traditional MCMC sampling methods and it has excellent performance as measured by the autocorrelation time (or function calls per independent sample). One major advantage of the algorithm is that it requires hand-tuning of only 1 or 2 parameters compared to $\sim N^2$ for a traditional algorithm in an N-dimensional parameter space. In this document, we describe the algorithm and the details of our implementation and API. Exploiting the parallelism of the ensemble method, emcee permits any user to take advantage of multiple CPU cores without extra effort. The code is available online at http://dan.iel.fm/emcee under the MIT License.


title: On the connection between the magneto-elliptic and magneto-rotational instabilities

abstract: It has been recently suggested that the magneto-rotational instability (MRI) is a limiting case of the magneto-elliptic instability (MEI). This limit is obtained for horizontal modes in the presence of rotation and an external vertical magnetic field, when the aspect ratio of the elliptic streamlines tends to infinite. In this paper we unveil the link between these previously unconnected mechanisms, explaining both the MEI and the MRI as different manifestations of the same Magneto-Elliptic-Rotational Instability (MERI). The growth rates are found and the influence of the magnetic and rotational effects is explained, in particular the effect of the magnetic field on the range of negative Rossby numbers at which the horizontal instability is excited. Furthermore, we show how the horizontal rotational MEI in the rotating shear flow limit links to the MRI by the use of the local shearing box model, typically used in the study of accretion discs. In such limit the growth rates of the two instability types coincide for any power-type background angular velocity radial profile with negative exponent corresponding to the value of the Rossby number of the rotating shear flow. The MRI requirement for instability is that the background angular velocity profile is a decreasing function of the distance from the centre of the disk which corresponds to the horizontal rotational MEI requirement of negative Rossby numbers. Finally a physical interpretation of the horizontal instability, based on a balance between the strain, the Lorentz force and the Coriolis force is given.


title: On Directly Mapping Relational Databases to RDF and OWL (Extended Version)

abstract: Mapping relational databases to RDF is a fundamental problem for the development of the Semantic Web. We present a solution, inspired by draft methods defined by the W3C where relational databases are directly mapped to RDF and OWL. Given a relational database schema and its integrity constraints, this direct mapping produces an OWL ontology, which, provides the basis for generating RDF instances. The semantics of this mapping is defined using Datalog. Two fundamental properties are information preservation and query preservation. We prove that our mapping satisfies both conditions, even for relational databases that contain null values. We also consider two desirable properties: monotonicity and semantics preservation. We prove that our mapping is monotone and also prove that no monotone mapping, including ours, is semantic preserving. We realize that monotonicity is an obstacle for semantic preservation and thus present a non-monotone direct mapping that is semantics preserving.


title: Anisotropic to Isotropic Phase Transitions in the Early Universe

abstract: We propose that the early Universe was not Lorentz symmetric and that a gradual transition to the Lorentz symmetric phase occurred. An underlying form of the Dirac equation hints to such a transition for fermions. Fermions were coupled to space-time in a non-trivial manner such that they were massless in the Lorentz violating phase. The partition function is used as a transfer matrix to model this transition on a two level thermodynamics system that describes how such a transition might have occurred. The system that models this transition evolves, with temperature, from a state of large to negligible entropy and this is interpreted as describing the transition to a state with Lorentz symmetry. In addition to this, analogy is created with the properties of this system to describe how the fields were massless and how a baryon asymmetry can be generated in this model.


title: GPUs as Storage System Accelerators

abstract: Massively multicore processors, such as Graphics Processing Units (GPUs), provide, at a comparable price, a one order of magnitude higher peak performance than traditional CPUs. This drop in the cost of computation, as any order-of-magnitude drop in the cost per unit of performance for a class of system components, triggers the opportunity to redesign systems and to explore new ways to engineer them to recalibrate the cost-to-performance relation. This project explores the feasibility of harnessing GPUs' computational power to improve the performance, reliability, or security of distributed storage systems. In this context, we present the design of a storage system prototype that uses GPU offloading to accelerate a number of computationally intensive primitives based on hashing, and introduce techniques to efficiently leverage the processing power of GPUs. We evaluate the performance of this prototype under two configurations: as a content addressable storage system that facilitates online similarity detection between successive versions of the same file and as a traditional system that uses hashing to preserve data integrity. Further, we evaluate the impact of offloading to the GPU on competing applications' performance. Our results show that this technique can bring tangible performance gains without negatively impacting the performance of concurrently running applications.


title: Euclid's theorem on the infinitude of primes: a historical survey of its proofs (300 B.C.--2022) and another new proof

abstract: {\bf In the fourth extended version of this article, we provide a comprehensive historical survey of 200 different proofs of famous Euclid's theorem on the infinitude of prime numbers (300 {\small B.C.}--2022)}. The author is trying to collect almost all the known proofs on infinitude of primes, including some proofs that can be easily obtained as consequences of some known problems or divisibility properties. Furthermore, here are listed numerous elementary proofs of the infinitude of primes in different arithmetic progressions. All the references concerning the proofs of Euclid's theorem that use similar methods and ideas are exposed subsequently. Namely, presented proofs are divided into the first five subsections of Section 2 in dependence of the methods that are used in them. 14 proofs which are proved from 2012 to 2017 are given in Subsection 2.9, and 18 recent proofs from 2018 to 2022 are presented in Subsection 2.10. In Section 3, we mainly survey elementary proofs of the infinitude of primes in different arithmetic progressions. Presented proofs are special cases of Dirichlet's theorem. In Section 4, we give a new simple ''Euclidean's proof'' of the infinitude of primes.


title: High-frequency limit of the Maxwell-Landau-Lifshitz system in the diffractive optics regime

abstract: We study semilinear Maxwell-Landau-Lifshitz systems in one space dimension. For highly oscillatory and prepared initial data, we construct WKB approximate solutions over long times $O(1/\e)$. The leading terms of the WKB solutions solve cubic Schr\"odinger equations. We show that the nonlinear normal form method of Joly, M\'etivier and Rauch applies to this context. This implies that the Schr\"odinger approximation stays close to the exact solution of Maxwell-Landau-Lifshitz over its existence time. In the context of Maxwell-Landau-Lifshitz, this extends the analysis of Colin and Lannes from times $O(|\ln \e|)$ up to $O(1/\e)$.


title: Higher-order illative combinatory logic

abstract: We show a model construction for a system of higher-order illative combinatory logic $\mathcal{I}_\omega$, thus establishing its strong consistency. We also use a variant of this construction to provide a complete embedding of first-order intuitionistic predicate logic with second-order propositional quantifiers into the system $\mathcal{I}_0$ of Barendregt, Bunder and Dekkers, which gives a partial answer to a question posed by these authors.


title: Finding decompositions of a class of separable states

abstract: By definition a separable state has the form \sum A_i \otimes B_i, where 0 \leq A_i, B_i for each i. In this paper we consider the class of states which admit such a decomposition with B_1, ..., B_p having independent images. We give a simple intrinsic characterization of this class of states, and starting with a density matrix in this class, describe a procedure to find such a decomposition with B_1, ..., B_p having independent images, and A_1, ..., A_p being distinct with unit trace. Such a decomposition is unique, and we relate this to the facial structure of the set of separable states. A special subclass of such separable states are those for which the rank of the matrix matches one marginal rank. Such states have arisen in previous studies of separability (e.g., they are known to be a class for which the PPT condition is equivalent to separability). The states investigated also include a class that corresponds (under the Choi-Jamio{\l}kowski isomorphism) to the quantum channels called quantum-classical and classical-quantum by Holevo.


title: Full photon statistics of a light beam transmitted through an optomechanical system

abstract: In this paper, we study the full statistics of photons transmitted through an optical cavity coupled to nanomechanical motion. We analyze the entire temporal evolution of the photon correlations, the Fano factor, and the effects of strong laser driving, all of which show pronounced features connected to the mechanical backaction. In the regime of single-photon strong coupling, this allows us to predict a transition from sub-Poissonian to super-Poissonian statistics for larger observation time intervals. Furthermore, we predict cascades of transmitted photons triggered by multi-photon transitions. In this regime, we observe Fano factors that are drastically enhanced due to the mechanical motion.


title: Nonlinear mechanics with photonic crystal nanomembranes

abstract: Optomechanical systems close to their quantum ground state and nonlinear nanoelectromechanical systems are two hot topics of current physics research. As high-reflectivity and low mass are crucial features to improve optomechanical coupling towards the ground state, we have designed, fabricated and characterized photonic crystal nanomembranes, at the crossroad of both topics. Here we demonstrate a number of nonlinear effects with these membranes. We first characterize the nonlinear behavior of a single mechanical mode and we demonstrate its nonlocal character by monitoring the subsequent actuation-related frequency shift of a different mode. We then proceed to study the underlying nonlinear dynamics, both by monitoring the phase-space trajectory of the free resonator and by characterizing the mechanical response in presence of a strong pump excitation. We observe in particular the frequency evolution during a ring-down oscillation decay, and the emergence of a phase conjugate mechanical response to a weaker probe actuation. Our results are crucial to understand the full nonlinear features of the PhC membranes, and possibly to look for nonlinear signatures of the quantum dynamics.


title: Orbital Selective Magnetism in the Spin-Ladder Iron Selenides Ba$_{1-x}$K$_{x}$Fe$_2$Se$_3$

abstract: Here we show that the 2.80(8) {\mu}B/Fe block antiferromagnetic order of BaFe2Se3 transforms into stripe antiferromagnetic order in KFe2Se3 with a decrease in moment to 2.1(1) {\mu}B/Fe. This reduction is larger than expected from the change in electron count from Ba$^{2+}$ to K$^{+}$, and occurs with the loss of the displacements of Fe atoms from ideal positions in the ladders, as found by neutron pair distribution function analysis. Intermediate compositions remain insulating, and magnetic susceptibility measurements show a suppression of magnetic order and probable formation of a spin-glass. Together, these results imply an orbital-dependent selection of magnetic versus bonded behavior, driven by relative bandwidths and fillings.


title: Sobolev Metrics on Diffeomorphism Groups and the Derived Geometry of Spaces of Submanifolds

abstract: Given a finite dimensional manifold $N$, the group $\operatorname{Diff}_{\mathcal S}(N)$ of diffeomorphism of $N$ which fall suitably rapidly to the identity, acts on the manifold $B(M,N)$ of submanifolds on $N$ of diffeomorphism type $M$ where $M$ is a compact manifold with $\dim M<\dim N$. For a right invariant weak Riemannian metric on $\operatorname{Diff}_{\mathcal S}(N)$ induced by a quite general operator $L:\frak X_{\mathcal S}(N)\to \Gamma(T^*N\otimes\operatorname{vol}(N))$, we consider the induced weak Riemannian metric on $B(M,N)$ and we compute its geodesics and sectional curvature. For that we derive a covariant formula for curvature in finite and infinite dimensions, we show how it makes O'Neill's formula very transparent, and we use it finally to compute sectional curvature on $B(M,N)$.


title: STEREO measurements of electron acceleration beyond fast Fermi at the bow shock

abstract: Solar wind electrons are accelerated and reflected upstream by the terrestrial bow shock into a region known as the electron foreshock. Previously observed electron spectra at low energies are consistent with a fast Fermi mechanism, based on the adiabatic conservation of the magnetic moment ({\mu}) of the accelerated electrons. At higher energies, suprathermal power law tails are observed beyond the level predicted by fast Fermi. The SWEA and STE electron detectors on STEREO enable measurements of foreshock electrons with good energy resolution and sensitivity over the entire foreshock beam. We investigate the electron acceleration mechanism by comparing observed STEREO electron spectra with predictions based on a Liouville mapping of upstream electrons through a shock encounter. The foreshock electron beam extends up to several tens of keV, energies for which the Larmor radii of electrons is tens of km or greater. These radii are comparable to the scale sizes of the shock, and {\mu} conservation no longer applies. We show that the observed enhancement in the foreshock beam beyond fast Fermi levels begins at energies where this assumption breaks down. We also demonstrate, using the Liouville mapping technique, that the strahl plays an important role in the formation of the bump on tail instability. We discuss this in the context of recent observations in the foreshock and in solar wind magnetic holes.


title: Production of Photons and Dileptons in the Glasma

abstract: We study the production of photons and dileptons during the pre-equilibrium Glasma stage in heavy ion collisions and discuss the implications in light of the PHENIX data. We find that the measured distributions of such electromagnetic emissions, while having some features not well understood if hypothesized to entirely arise from a thermalized Quark-Gluon Plasma, have some qualitative features that might be described after including effects from a thermalizing Glasma. The shape and centrality dependence of the transverse momentum spectra of the so-called "thermal photons" are well described. The mass and transverse momentum dependence of intermediate mass dileptons also agree with our estimates. The low transverse momenta from which the excessive dileptons (in low to intermediate mass region) arise is suggestive of emissions from a Bose condensate. We also predict the centrality dependence of dilepton production. Uncertainties in the current approach and improvements in the future are discussed.


title: Record-dependent measures on the symmetric groups

abstract: A probability measure $P_n$ on the symmetric group ${\mathfrak S}_n$ is said to be record-dependent if $P_n(\sigma)$ depends only on the set of records of a permutation $\sigma\in{\mathfrak S}_n$. A sequence $P=(P_n)_{n\in{\mathbb N}}$ of consistent record-dependent measures determines a random order on $\mathbb N$. In this paper we describe the extreme elements of the convex set of such $P$. This problem turns out to be related to the study of asymptotic behavior of permutation-valued growth processes, to random extensions of partial orders, and to the measures on the Young-Fibonacci lattice.


title: Ruled CR-submanifolds of locally conformal K\"{a}hler manifolds

abstract: The purpose of this paper is to study the canonical totally real foliations of CR-submanifolds in a locally conformal K\"{a}hler manifold.


title: Lutetium thermometry for Oklo natural reactors: a new look at old data

abstract: Lutetium thermometry has been used to analyze Oklo natural nuclear reactor zones but leads to widely varying and puzzling predictions for the temperatures $T_O$ which in turn impacts bounds on time variation of the fine structure constant $\alpha$. We revisit results for reactor zone RZ10 in light of new measurements of the isomer branching ratio $B^g$ in $^{175}$Lu neutron capture at 5 and 25 keV. We recalculate predictions for $T_O$ as a function of $B^g$ using realistic models of the Oklo neutron flux. We find $T_O = 100 \pm 30$ C using a new value of $B^g$, in contrast to $350 < T_O < 500 $ C using the evaluated value at thermal energy. Lutetium thermometry can be applicable to analyses of Oklo reactor data, but a better measurement of $B^g$ with thermal neutrons is needed to confirm the reliability of temperature predictions.


title: Optimal bandwidth-aware VM allocation for Infrastructure-as-a-Service

abstract: Infrastructure-as-a-Service (IaaS) providers need to offer richer services to be competitive while optimizing their resource usage to keep costs down. Richer service offerings include new resource request models involving bandwidth guarantees between virtual machines (VMs). Thus we consider the following problem: given a VM request graph (where nodes are VMs and edges represent virtual network connectivity between the VMs) and a real data center topology, find an allocation of VMs to servers that satisfies the bandwidth guarantees for every virtual network edge---which maps to a path in the physical network---and minimizes congestion of the network. Previous work has shown that for arbitrary networks and requests, finding the optimal embedding satisfying bandwidth requests is $\mathcal{NP}$-hard. However, in most data center architectures, the routing protocols employed are based on a spanning tree of the physical network. In this paper, we prove that the problem remains $\mathcal{NP}$-hard even when the physical network topology is restricted to be a tree, and the request graph topology is also restricted. We also present a dynamic programming algorithm for computing the optimal embedding in a tree network which runs in time $O(3^kn)$, where $n$ is the number of nodes in the physical topology and $k$ is the size of the request graph, which is well suited for practical requests which have small $k$. Such requests form a large class of web-service and enterprise workloads. Also, if we restrict the requests topology to a clique (all VMs connected to a virtual switch with uniform bandwidth requirements), we show that the dynamic programming algorithm can be modified to output the minimum congestion embedding in time $O(k^2n)$.


title: Generalized Boundaries from Multiple Image Interpretations

abstract: Boundary detection is essential for a variety of computer vision tasks such as segmentation and recognition. In this paper we propose a unified formulation and a novel algorithm that are applicable to the detection of different types of boundaries, such as intensity edges, occlusion boundaries or object category specific boundaries. Our formulation leads to a simple method with state-of-the-art performance and significantly lower computational cost than existing methods. We evaluate our algorithm on different types of boundaries, from low-level boundaries extracted in natural images, to occlusion boundaries obtained using motion cues and RGB-D cameras, to boundaries from soft-segmentation. We also propose a novel method for figure/ground soft-segmentation that can be used in conjunction with our boundary detection method and improve its accuracy at almost no extra computational cost.


title: Evolutionary Game Theory on Measure Spaces: Well-Posedness

abstract: An attempt is made to find a comprehensive mathematical framework in which to investigate the problems of well-posedness and asymptotic analysis for fully nonlinear evolutionary game theoretic models. The model should be rich enough to include all classical nonlinearities, e.g., Beverton-Holt or Ricker type. For several such models formulated on the space of integrable functions, it is known that as the variance of the payoff kernel becomes small the solution converges in the long term to a Dirac measure centered at the fittest strategy; thus the limit of the solution is not in the state space of integrable functions. Starting with the replicator-mutator equation and a generalized logistic equation as bases, a general model is formulated as a dynamical system on the state space of finite signed measures. Well-posedness is established, and then it is shown that by choosing appropriate payoff kernels this model includes all classical density models, both selection and mutation, and discrete and continuous strategy (trait) spaces.


title: Inferential or Differential: Privacy Laws Dictate

abstract: So far, privacy models follow two paradigms. The first paradigm, termed inferential privacy in this paper, focuses on the risk due to statistical inference of sensitive information about a target record from other records in the database. The second paradigm, known as differential privacy, focuses on the risk to an individual when included in, versus when not included in, the database. The contribution of this paper consists of two parts. The first part presents a critical analysis on differential privacy with two results: (i) the differential privacy mechanism does not provide inferential privacy, (ii) the impossibility result about achieving Dalenius's privacy goal [5] is based on an adversary simulated by a Turing machine, but a human adversary may behave differently; consequently, the practical implication of the impossibility result remains unclear. The second part of this work is devoted to a solution addressing three major drawbacks in previous approaches to inferential privacy: lack of flexibility for handling variable sensitivity, poor utility, and vulnerability to auxiliary information.


title: Co-H-spaces and almost localization

abstract: Apart from simply-connected spaces, a non simply-connected co-H-space is a typical example of a space X with a co-action of $B\pi_1(X)$ along $r^X : X \rightarrow B\pi_{1}(X)$ the classifying map of the universal covering. If such a space X is actually a co-H-space, then the fibrewise p-localization of $r^X$ (or the `almost' p-localization of X) is a fibrewise co-H-space (or an `almost' co-H-space, resp.) for every prime p. In this paper, we show that the converse statement is true, i.e., for a non simply-connected space X with a co-action of $B\pi_1(X)$ along $r^X$, X is a co-H-space if, for every prime p, the almost p-localization of X is an almost co-H-space.


title: Gluing construction of initial data with Kerr-de Sitter ends

abstract: We construct initial data sets which satisfy the vacuum constraint equa- tions of General Relativity with positive cosmologigal constant. More pre- silely, we deform initial data with ends asymptotic to Schwarzschild-de Sitter to obtain non-trivial initial data with exactly Kerr-de Sitter ends. The method is inspired from Corvino's gluing method. We obtain here a extension of a previous result for the time-symmetric case by Chru\'sciel and Pollack.


title: Evolutionary Game Theory on Measure Spaces: Asymptotic Behavior of Solutions

abstract: In [12] we formulated an evolutionary game theory model as a dynamical system on the state space of finite signed Borel measures under the weak* topology. The focus of this paper is to extend the analysis to include the long-time behavior of solutions to the model. In particular, we show that M(Q), the finite signed Borel measures are asymptotically closed. This means that if the initial condition is a finite signed Borel measure and if the asymptotic limit of the model solution exists, then it will be a measure (note that function spaces such as L1(Q) and C(Q) do not have this property). We also establish permanence results for the full replicator mutator model. Then, we study the asymptotic analysis in the case where there is more than one strategy of a given fitness (a continuum of strategies of a given fitness), a case that often arises in applications. To study this case our mathematical structure must include the ability to demonstrate the convergence of the model solution to a measure supported on a continuum of strategies. For this purpose, we demonstrate how to perform completions of the space of measures and how to use these completions to formulate weak (generalized) asymptotic limits. In particular, we show that for the pure replicator dynamics the (weak) solution of the dynamical system converges to a Dirac measure centered at the fittest strategy class; thus this Dirac measure is a globally attractive equilibrium point which is termed a continuously stable strategy (CSS). It is also shown that in the discrete case of the pure replicator dynamics and even for small perturbation of the pure replicator dynamics (i.e., selection with small mutation) there exists a globally asymptotically stable equilibrium.


title: Hybrid zone dynamics under weak Haldane's rule

abstract: The ability of genetic isolation to block gene flow plays a key role in the speciation of sexually reproducing organisms. This paper analyses the hybrid zone dynamics affected by "weak" Haldane's rule, namely the incomplete hybrids inferiority (sterility/inviability) against the heterogametic (XY or ZW) sex caused by a Dobzhansky-Muller incompatibility. Different strengths of incompatibility, dispersal and density-dependent regulation are considered; and the gene flow and clinal structures of allele frequencies in the presence of short-range dispersal (the stepping-stone model) are examined. I show that a weak heterogametic hybrid incompatibility could constitute a substantial barrier that could reduce gene flow and result in non-coincident and discordant clines of alleles. It is found that the differential gene flow is more pronounced under a stronger density-dependent regulation. This study provides a mechanistic explanation for how an adaptive mutation, which may only have a marginal fitness effect, could set a gene up as an evolutionary hot-spot.


title: Summary of working group g: beam material interaction

abstract: For the first time, the workshop on High-Intensity and High-Brightness Hadron Beams (HB2010), held at Morschach, Switzerland and organized by the Paul Scherrer Institute, included a Working group dealing with the interaction between beam and material. Due to the high power beams of existing and future facilities, this topic is already of great relevance for such machines and is expected to become even more important in the future. While more specialized workshops related to topics of radiation damage, activation or thermo - mechanical calculations, already exist, HB2010 provided the occasion to discuss the interplay of these topics, focusing on components like targets, beam dumps and collimators, whose reliability are crucial for a user facility. In addition, a broader community of people working on a variety of issues related to the operation of accelerators could be informed and their interest sparked.


title: An R^4 non-renormalisation theorem in N=4 supergravity

abstract: We consider the four-graviton amplitudes in CHL constructions providing four-dimensional N=4 models with various numbers of vector multiplets. We show that in these models the two-loop amplitude has a prefactor of d^2R^4. This implies a non-renormalisation theorem for the R^4 term, which forbids the appearance of a three-loop ultraviolet divergence in four dimensions in the four-graviton amplitude. We connect the special nature of the R^4 term to the U(1) anomaly of pure N=4 supergravity.


title: A blow-up criterion for 3-D compressible visco-elasticity

abstract: In this paper, we shall prove a blow-up criteria in terms of the upper bound of the density, deformation tensor and the gradient of deformation tensor for 3D compressible visco-elasticity. Based on the structure of deformation tensor, we find a cancelation in higher order derivatives, which brings us the desired results.


title: Finite Fault Analysis and Near Field Dynamic Strains and Rotations due to the 11/05/2011 (Mw5.2) Lorca Earthquake, South-Eastern Spain

abstract: The 11/5/2011 Lorca, Spain earthquake (Mw5.2) and related seismicity produced extensive damage in the town of Lorca and vicinity. During these earthquakes, evidence of rotations and permanent deformations in structures were observed. To analyze these aspects and study the source properties from the near field, the displacement time histories were obtained including the static component at Lorca station. Displacement time histories were computed by an appropriate double time integration procedure of accelerograms. Using these data, the foreshock and mainshock slip distributions were calculated by means of a complete waveform kinematic inversion. To study the dynamic deformations, the 3D tensor of displacement gradients at Lorca station was first estimated by a single station method. Using the finite fault inversion results and by means of a first order finite difference approach, the dynamic deformations tensor at surface was calculated at the recording site. In order to estimate the distribution of the peak dynamic deformations, the calculation was extended to the close neighboring area of the town. The possible influence of the near-field deformations on the surface structures was analyzed.


title: Deterministic elliptic curve primality proving for a special sequence of numbers

abstract: We give a deterministic algorithm that very quickly proves the primality or compositeness of the integers N in a certain sequence, using an elliptic curve E/Q with complex multiplication by the ring of integers of Q(sqrt(-7)). The algorithm uses O(log N) arithmetic operations in the ring Z/NZ, implying a bit complexity that is quasi-quadratic in log N. Notably, neither of the classical "N-1" or "N+1" primality tests apply to the integers in our sequence. We discuss how this algorithm may be applied, in combination with sieving techniques, to efficiently search for very large primes. This has allowed us to prove the primality of several integers with more than 100,000 decimal digits, the largest of which has more than a million bits in its binary representation. At the time it was found, it was the largest proven prime N for which no significant partial factorization of N-1 or N+1 is known.


title: Drag force in a strongly coupled anisotropic plasma

abstract: We calculate the drag force experienced by an infinitely massive quark propagating at constant velocity through an anisotropic, strongly coupled N=4 plasma by means of its gravity dual. We find that the gluon cloud trailing behind the quark is generally misaligned with the quark velocity, and that the latter is also misaligned with the force. The drag coefficient $\mu$ can be larger or smaller than the corresponding isotropic value depending on the velocity and the direction of motion. In the ultra-relativistic limit we find that generically $\mu \propto p$. We discuss the conditions under which this behaviour may extend to more general situations.


title: Fingerprinting Higgs Suspects at the LHC

abstract: We outline a method for characterizing deviations from the properties of a Standard Model (SM) Higgs boson. We apply it to current data in order to characterize up to which degree the SM Higgs boson interpretation is consistent with experiment. We find that the SM Higgs boson is consistent with the current data set at the 82 % confidence level, based on data of excess events reported by CMS and ATLAS, which are interpreted to be related to the mass scale mh = 124-126 GeV, and on published CL_s exclusion regions. We perform a global fit in terms of two parameters characterizing the deviation from the SM value in the gauge and fermion couplings of a Higgs boson. We find two minima in the global fit and identify observables that can remove this degeneracy. An update for Moriond 2012 data is included in the Appendix, which finds that the SM Higgs boson is now consistent with the current data set at only the 94 % confidence level (which corresponds to ~ 2 sigma tension compared to the best fit point).


title: Extended Lifted Inference with Joint Formulas

abstract: The First-Order Variable Elimination (FOVE) algorithm allows exact inference to be applied directly to probabilistic relational models, and has proven to be vastly superior to the application of standard inference methods on a grounded propositional model. Still, FOVE operators can be applied under restricted conditions, often forcing one to resort to propositional inference. This paper aims to extend the applicability of FOVE by providing two new model conversion operators: the first and the primary is joint formula conversion and the second is just-different counting conversion. These new operations allow efficient inference methods to be applied directly on relational models, where no existing efficient method could be applied hitherto. In addition, aided by these capabilities, we show how to adapt FOVE to provide exact solutions to Maximum Expected Utility (MEU) queries over relational models for decision under uncertainty. Experimental evaluations show our algorithms to provide significant speedup over the alternatives.


title: Learning is planning: near Bayes-optimal reinforcement learning via Monte-Carlo tree search

abstract: Bayes-optimal behavior, while well-defined, is often difficult to achieve. Recent advances in the use of Monte-Carlo tree search (MCTS) have shown that it is possible to act near-optimally in Markov Decision Processes (MDPs) with very large or infinite state spaces. Bayes-optimal behavior in an unknown MDP is equivalent to optimal behavior in the known belief-space MDP, although the size of this belief-space MDP grows exponentially with the amount of history retained, and is potentially infinite. We show how an agent can use one particular MCTS algorithm, Forward Search Sparse Sampling (FSSS), in an efficient way to act nearly Bayes-optimally for all but a polynomial number of steps, assuming that FSSS can be used to act efficiently in any possible underlying MDP.


title: Solving Cooperative Reliability Games

abstract: Cooperative games model the allocation of profit from joint actions, following considerations such as stability and fairness. We propose the reliability extension of such games, where agents may fail to participate in the game. In the reliability extension, each agent only "survives" with a certain probability, and a coalition's value is the probability that its surviving members would be a winning coalition in the base game. We study prominent solution concepts in such games, showing how to approximate the Shapley value and how to compute the core in games with few agent types. We also show that applying the reliability extension may stabilize the game, making the core non-empty even when the base game has an empty core.


title: Active Diagnosis via AUC Maximization: An Efficient Approach for Multiple Fault Identification in Large Scale, Noisy Networks

abstract: The problem of active diagnosis arises in several applications such as disease diagnosis, and fault diagnosis in computer networks, where the goal is to rapidly identify the binary states of a set of objects (e.g., faulty or working) by sequentially selecting, and observing, (noisy) responses to binary valued queries. Current algorithms in this area rely on loopy belief propagation for active query selection. These algorithms have an exponential time complexity, making them slow and even intractable in large networks. We propose a rank-based greedy algorithm that sequentially chooses queries such that the area under the ROC curve of the rank-based output is maximized. The AUC criterion allows us to make a simplifying assumption that significantly reduces the complexity of active query selection (from exponential to near quadratic), with little or no compromise on the performance quality.


title: Semi-supervised Learning with Density Based Distances

abstract: We present a simple, yet effective, approach to Semi-Supervised Learning. Our approach is based on estimating density-based distances (DBD) using a shortest path calculation on a graph. These Graph-DBD estimates can then be used in any distance-based supervised learning method, such as Nearest Neighbor methods and SVMs with RBF kernels. In order to apply the method to very large data sets, we also present a novel algorithm which integrates nearest neighbor computations into the shortest path search and can find exact shortest paths even in extremely large dense graphs. Significant runtime improvement over the commonly used Laplacian regularization method is then shown on a large scale dataset.


title: Factored Filtering of Continuous-Time Systems

abstract: We consider filtering for a continuous-time, or asynchronous, stochastic system where the full distribution over states is too large to be stored or calculated. We assume that the rate matrix of the system can be compactly represented and that the belief distribution is to be approximated as a product of marginals. The essential computation is the matrix exponential. We look at two different methods for its computation: ODE integration and uniformization of the Taylor expansion. For both we consider approximations in which only a factored belief state is maintained. For factored uniformization we demonstrate that the KL-divergence of the filtering is bounded. Our experimental results confirm our factored uniformization performs better than previously suggested uniformization methods and the mean field algorithm.


title: Near-Optimal Target Learning With Stochastic Binary Signals

abstract: We study learning in a noisy bisection model: specifically, Bayesian algorithms to learn a target value V given access only to noisy realizations of whether V is less than or greater than a threshold theta. At step t = 0, 1, 2, ..., the learner sets threshold theta t and observes a noisy realization of sign(V - theta t). After T steps, the goal is to output an estimate V^ which is within an eta-tolerance of V . This problem has been studied, predominantly in environments with a fixed error probability q < 1/2 for the noisy realization of sign(V - theta t). In practice, it is often the case that q can approach 1/2, especially as theta -> V, and there is little known when this happens. We give a pseudo-Bayesian algorithm which provably converges to V. When the true prior matches our algorithm's Gaussian prior, we show near-optimal expected performance. Our methods extend to the general multiple-threshold setting where the observation noisily indicates which of k >= 2 regions V belongs to.


title: Filtered Fictitious Play for Perturbed Observation Potential Games and Decentralised POMDPs

abstract: Potential games and decentralised partially observable MDPs (Dec-POMDPs) are two commonly used models of multi-agent interaction, for static optimisation and sequential decisionmaking settings, respectively. In this paper we introduce filtered fictitious play for solving repeated potential games in which each player's observations of others' actions are perturbed by random noise, and use this algorithm to construct an online learning method for solving Dec-POMDPs. Specifically, we prove that noise in observations prevents standard fictitious play from converging to Nash equilibrium in potential games, which also makes fictitious play impractical for solving Dec-POMDPs. To combat this, we derive filtered fictitious play, and provide conditions under which it converges to a Nash equilibrium in potential games with noisy observations. We then use filtered fictitious play to construct a solver for Dec-POMDPs, and demonstrate our new algorithm's performance in a box pushing problem. Our results show that we consistently outperform the state-of-the-art Dec-POMDP solver by an average of 100% across the range of noise in the observation function.


title: A Framework for Optimizing Paper Matching

abstract: At the heart of many scientific conferences is the problem of matching submitted papers to suitable reviewers. Arriving at a good assignment is a major and important challenge for any conference organizer. In this paper we propose a framework to optimize paper-to-reviewer assignments. Our framework uses suitability scores to measure pairwise affinity between papers and reviewers. We show how learning can be used to infer suitability scores from a small set of provided scores, thereby reducing the burden on reviewers and organizers. We frame the assignment problem as an integer program and propose several variations for the paper-to-reviewer matching domain. We also explore how learning and matching interact. Experiments on two conference data sets examine the performance of several learning methods as well as the effectiveness of the matching formulations.


title: A temporally abstracted Viterbi algorithm

abstract: Hierarchical problem abstraction, when applicable, may offer exponential reductions in computational complexity. Previous work on coarse-to-fine dynamic programming (CFDP) has demonstrated this possibility using state abstraction to speed up the Viterbi algorithm. In this paper, we show how to apply temporal abstraction to the Viterbi problem. Our algorithm uses bounds derived from analysis of coarse timescales to prune large parts of the state trellis at finer timescales. We demonstrate improvements of several orders of magnitude over the standard Viterbi algorithm, as well as significant speedups over CFDP, for problems whose state variables evolve at widely differing rates.


title: Smoothing Proximal Gradient Method for General Structured Sparse Learning

abstract: We study the problem of learning high dimensional regression models regularized by a structured-sparsity-inducing penalty that encodes prior structural information on either input or output sides. We consider two widely adopted types of such penalties as our motivating examples: 1) overlapping group lasso penalty, based on the l1/l2 mixed-norm penalty, and 2) graph-guided fusion penalty. For both types of penalties, due to their non-separability, developing an efficient optimization method has remained a challenging problem. In this paper, we propose a general optimization approach, called smoothing proximal gradient method, which can solve the structured sparse regression problems with a smooth convex loss and a wide spectrum of structured-sparsity-inducing penalties. Our approach is based on a general smoothing technique of Nesterov. It achieves a convergence rate faster than the standard first-order method, subgradient method, and is much more scalable than the most widely used interior-point method. Numerical results are reported to demonstrate the efficiency and scalability of the proposed method.


title: EDML: A Method for Learning Parameters in Bayesian Networks

abstract: We propose a method called EDML for learning MAP parameters in binary Bayesian networks under incomplete data. The method assumes Beta priors and can be used to learn maximum likelihood parameters when the priors are uninformative. EDML exhibits interesting behaviors, especially when compared to EM. We introduce EDML, explain its origin, and study some of its properties both analytically and empirically.


title: Strictly Proper Mechanisms with Cooperating Players

abstract: Prediction markets provide an efficient means to assess uncertain quantities from forecasters. Traditional and competitive strictly proper scoring rules have been shown to incentivize players to provide truthful probabilistic forecasts. However, we show that when those players can cooperate, these mechanisms can instead discourage them from reporting what they really believe. When players with different beliefs are able to cooperate and form a coalition, these mechanisms admit arbitrage and there is a report that will always pay coalition members more than their truthful forecasts. If the coalition were created by an intermediary, such as a web portal, the intermediary would be guaranteed a profit.


title: A Logical Characterization of Constraint-Based Causal Discovery

abstract: We present a novel approach to constraint-based causal discovery, that takes the form of straightforward logical inference, applied to a list of simple, logical statements about causal relations that are derived directly from observed (in)dependencies. It is both sound and complete, in the sense that all invariant features of the corresponding partial ancestral graph (PAG) are identified, even in the presence of latent variables and selection bias. The approach shows that every identifiable causal relation corresponds to one of just two fundamental forms. More importantly, as the basic building blocks of the method do not rely on the detailed (graphical) structure of the corresponding PAG, it opens up a range of new opportunities, including more robust inference, detailed accountability, and application to large models.


title: Ensembles of Kernel Predictors

abstract: This paper examines the problem of learning with a finite and possibly large set of p base kernels. It presents a theoretical and empirical analysis of an approach addressing this problem based on ensembles of kernel predictors. This includes novel theoretical guarantees based on the Rademacher complexity of the corresponding hypothesis sets, the introduction and analysis of a learning algorithm based on these hypothesis sets, and a series of experiments using ensembles of kernel predictors with several data sets. Both convex combinations of kernel-based hypotheses and more general Lq-regularized nonnegative combinations are analyzed. These theoretical, algorithmic, and empirical results are compared with those achieved by using learning kernel techniques, which can be viewed as another approach for solving the same problem.


title: Bayesian network learning with cutting planes

abstract: The problem of learning the structure of Bayesian networks from complete discrete data with a limit on parent set size is considered. Learning is cast explicitly as an optimisation problem where the goal is to find a BN structure which maximises log marginal likelihood (BDe score). Integer programming, specifically the SCIP framework, is used to solve this optimisation problem. Acyclicity constraints are added to the integer program (IP) during solving in the form of cutting planes. Finding good cutting planes is the key to the success of the approach -the search for such cutting planes is effected using a sub-IP. Results show that this is a particularly fast method for exact BN learning.


title: Active Learning for Developing Personalized Treatment

abstract: The personalization of treatment via bio-markers and other risk categories has drawn increasing interest among clinical scientists. Personalized treatment strategies can be learned using data from clinical trials, but such trials are very costly to run. This paper explores the use of active learning techniques to design more efficient trials, addressing issues such as whom to recruit, at what point in the trial, and which treatment to assign, throughout the duration of the trial. We propose a minimax bandit model with two different optimization criteria, and discuss the computational challenges and issues pertaining to this approach. We evaluate our active learning policies using both simulated data, and data modeled after a clinical trial for treating depressed individuals, and contrast our methods with other plausible active learning policies.


title: A Unifying Framework for Linearly Solvable Control

abstract: Recent work has led to the development of an elegant theory of Linearly Solvable Markov Decision Processes (LMDPs) and related Path-Integral Control Problems. Traditionally, MDPs have been formulated using stochastic policies and a control cost based on the KL divergence. In this paper, we extend this framework to a more general class of divergences: the Renyi divergences. These are a more general class of divergences parameterized by a continuous parameter that include the KL divergence as a special case. The resulting control problems can be interpreted as solving a risk-sensitive version of the LMDP problem. For a > 0, we get risk-averse behavior (the degree of risk-aversion increases with a) and for a < 0, we get risk-seeking behavior. We recover LMDPs in the limit as a -> 0. This work generalizes the recently developed risk-sensitive path-integral control formalism which can be seen as the continuous-time limit of results obtained in this paper. To the best of our knowledge, this is a general theory of linearly solvable control and includes all previous work as a special case. We also present an alternative interpretation of these results as solving a 2-player (cooperative or competitive) Markov Game. From the linearity follow a number of nice properties including compositionality of control laws and a path-integral representation of the value function. We demonstrate the usefulness of the framework on control problems with noise where different values of lead to qualitatively different control behaviors.


title: Boosting as a Product of Experts

abstract: In this paper, we derive a novel probabilistic model of boosting as a Product of Experts. We re-derive the boosting algorithm as a greedy incremental model selection procedure which ensures that addition of new experts to the ensemble does not decrease the likelihood of the data. These learning rules lead to a generic boosting algorithm - POE- Boost which turns out to be similar to the AdaBoost algorithm under certain assumptions on the expert probabilities. The paper then extends the POEBoost algorithm to POEBoost.CS which handles hypothesis that produce probabilistic predictions. This new algorithm is shown to have better generalization performance compared to other state of the art algorithms.


title: PAC-Bayesian Policy Evaluation for Reinforcement Learning

abstract: Bayesian priors offer a compact yet general means of incorporating domain knowledge into many learning tasks. The correctness of the Bayesian analysis and inference, however, largely depends on accuracy and correctness of these priors. PAC-Bayesian methods overcome this problem by providing bounds that hold regardless of the correctness of the prior distribution. This paper introduces the first PAC-Bayesian bound for the batch reinforcement learning problem with function approximation. We show how this bound can be used to perform model-selection in a transfer learning scenario. Our empirical results confirm that PAC-Bayesian policy evaluation is able to leverage prior distributions when they are informative and, unlike standard Bayesian RL approaches, ignore them when they are misleading.


title: On the Complexity of Decision Making in Possibilistic Decision Trees

abstract: When the information about uncertainty cannot be quantified in a simple, probabilistic way, the topic of possibilistic decision theory is often a natural one to consider. The development of possibilistic decision theory has lead to a series of possibilistic criteria, e.g pessimistic possibilistic qualitative utility, possibilistic likely dominance, binary possibilistic utility and possibilistic Choquet integrals. This paper focuses on sequential decision making in possibilistic decision trees. It proposes a complexity study of the problem of finding an optimal strategy depending on the monotonicity property of the optimization criteria which allows the application of dynamic programming that offers a polytime reduction of the decision problem. It also shows that possibilistic Choquet integrals do not satisfy this property, and that in this case the optimization problem is NP - hard.


title: Inference in Probabilistic Logic Programs using Weighted CNF's

abstract: Probabilistic logic programs are logic programs in which some of the facts are annotated with probabilities. Several classical probabilistic inference tasks (such as MAP and computing marginals) have not yet received a lot of attention for this formalism. The contribution of this paper is that we develop efficient inference algorithms for these tasks. This is based on a conversion of the probabilistic logic program and the query and evidence to a weighted CNF formula. This allows us to reduce the inference tasks to well-studied tasks such as weighted model counting. To solve such tasks, we employ state-of-the-art methods. We consider multiple methods for the conversion of the programs as well as for inference on the weighted CNF. The resulting approach is evaluated experimentally and shown to improve upon the state-of-the-art in probabilistic logic programming.


title: Efficient Inference in Markov Control Problems

abstract: Markov control algorithms that perform smooth, non-greedy updates of the policy have been shown to be very general and versatile, with policy gradient and Expectation Maximisation algorithms being particularly popular. For these algorithms, marginal inference of the reward weighted trajectory distribution is required to perform policy updates. We discuss a new exact inference algorithm for these marginals in the finite horizon case that is more efficient than the standard approach based on classical forward-backward recursions. We also provide a principled extension to infinite horizon Markov Decision Problems that explicitly accounts for an infinite horizon. This extension provides a novel algorithm for both policy gradients and Expectation Maximisation in infinite horizon problems.


title: Dynamic consistency and decision making under vacuous belief

abstract: The ideas about decision making under ignorance in economics are combined with the ideas about uncertainty representation in computer science. The combination sheds new light on the question of how artificial agents can act in a dynamically consistent manner. The notion of sequential consistency is formalized by adapting the law of iterated expectation for plausibility measures. The necessary and sufficient condition for a certainty equivalence operator for Nehring-Puppe's preference to be sequentially consistent is given. This result sheds light on the models of decision making under uncertainty.


title: Hierarchical Affinity Propagation

abstract: Affinity propagation is an exemplar-based clustering algorithm that finds a set of data-points that best exemplify the data, and associates each datapoint with one exemplar. We extend affinity propagation in a principled way to solve the hierarchical clustering problem, which arises in a variety of domains including biology, sensor networks and decision making in operational research. We derive an inference algorithm that operates by propagating information up and down the hierarchy, and is efficient despite the high-order potentials required for the graphical model formulation. We demonstrate that our method outperforms greedy techniques that cluster one layer at a time. We show that on an artificial dataset designed to mimic the HIV-strain mutation dynamics, our method outperforms related methods. For real HIV sequences, where the ground truth is not available, we show our method achieves better results, in terms of the underlying objective function, and show the results correspond meaningfully to geographical location and strain subtypes. Finally we report results on using the method for the analysis of mass spectra, showing it performs favorably compared to state-of-the-art methods.


title: Approximation by Quantization

abstract: Inference in graphical models consists of repeatedly multiplying and summing out potentials. It is generally intractable because the derived potentials obtained in this way can be exponentially large. Approximate inference techniques such as belief propagation and variational methods combat this by simplifying the derived potentials, typically by dropping variables from them. We propose an alternate method for simplifying potentials: quantizing their values. Quantization causes different states of a potential to have the same value, and therefore introduces context-specific independencies that can be exploited to represent the potential more compactly. We use algebraic decision diagrams (ADDs) to do this efficiently. We apply quantization and ADD reduction to variable elimination and junction tree propagation, yielding a family of bounded approximate inference schemes. Our experimental tests show that our new schemes significantly outperform state-of-the-art approaches on many benchmark instances.


title: Probabilistic Theorem Proving

abstract: Many representation schemes combining first-order logic and probability have been proposed in recent years. Progress in unifying logical and probabilistic inference has been slower. Existing methods are mainly variants of lifted variable elimination and belief propagation, neither of which take logical structure into account. We propose the first method that has the full power of both graphical model inference and first-order theorem proving (in finite domains with Herbrand interpretations). We first define probabilistic theorem proving, their generalization, as the problem of computing the probability of a logical formula given the probabilities or weights of a set of formulas. We then show how this can be reduced to the problem of lifted weighted model counting, and develop an efficient algorithm for the latter. We prove the correctness of this algorithm, investigate its properties, and show how it generalizes previous approaches. Experiments show that it greatly outperforms lifted variable elimination when logical structure is present. Finally, we propose an algorithm for approximate probabilistic theorem proving, and show that it can greatly outperform lifted belief propagation.


title: Generalized Fisher Score for Feature Selection

abstract: Fisher score is one of the most widely used supervised feature selection methods. However, it selects each feature independently according to their scores under the Fisher criterion, which leads to a suboptimal subset of features. In this paper, we present a generalized Fisher score to jointly select features. It aims at finding an subset of features, which maximize the lower bound of traditional Fisher score. The resulting feature selection problem is a mixed integer programming, which can be reformulated as a quadratically constrained linear programming (QCLP). It is solved by cutting plane algorithm, in each iteration of which a multiple kernel learning problem is solved alternatively by multivariate ridge regression and projected gradient descent. Experiments on benchmark data sets indicate that the proposed method outperforms Fisher score as well as many other state-of-the-art feature selection methods.


title: Active Semi-Supervised Learning using Submodular Functions

abstract: We consider active, semi-supervised learning in an offline transductive setting. We show that a previously proposed error bound for active learning on undirected weighted graphs can be generalized by replacing graph cut with an arbitrary symmetric submodular function. Arbitrary non-symmetric submodular functions can be used via symmetrization. Different choices of submodular functions give different versions of the error bound that are appropriate for different kinds of problems. Moreover, the bound is deterministic and holds for adversarially chosen labels. We show exactly minimizing this error bound is NP-complete. However, we also introduce for any submodular function an associated active semi-supervised learning method that approximately minimizes the corresponding error bound. We show that the error bound is tight in the sense that there is no other bound of the same form which is better. Our theoretical results are supported by experiments on real data.


title: Bregman divergence as general framework to estimate unnormalized statistical models

abstract: We show that the Bregman divergence provides a rich framework to estimate unnormalized statistical models for continuous or discrete random variables, that is, models which do not integrate or sum to one, respectively. We prove that recent estimation methods such as noise-contrastive estimation, ratio matching, and score matching belong to the proposed framework, and explain their interconnection based on supervised learning. Further, we discuss the role of boosting in unsupervised learning.


title: Reasoning about RoboCup Soccer Narratives

abstract: This paper presents an approach for learning to translate simple narratives, i.e., texts (sequences of sentences) describing dynamic systems, into coherent sequences of events without the need for labeled training data. Our approach incorporates domain knowledge in the form of preconditions and effects of events, and we show that it outperforms state-of-the-art supervised learning systems on the task of reconstructing RoboCup soccer games from their commentaries.


title: Suboptimality Bounds for Stochastic Shortest Path Problems

abstract: We consider how to use the Bellman residual of the dynamic programming operator to compute suboptimality bounds for solutions to stochastic shortest path problems. Such bounds have been previously established only in the special case that "all policies are proper," in which case the dynamic programming operator is known to be a contraction, and have been shown to be easily computable only in the more limited special case of discounting. Under the condition that transition costs are positive, we show that suboptimality bounds can be easily computed even when not all policies are proper. In the general case when there are no restrictions on transition costs, the analysis is more complex. But we present preliminary results that show such bounds are possible.


title: Sequential Inference for Latent Force Models

abstract: Latent force models (LFMs) are hybrid models combining mechanistic principles with non-parametric components. In this article, we shall show how LFMs can be equivalently formulated and solved using the state variable approach. We shall also show how the Gaussian process prior used in LFMs can be equivalently formulated as a linear statespace model driven by a white noise process and how inference on the resulting model can be efficiently implemented using Kalman filter and smoother. Then we shall show how the recently proposed switching LFM can be reformulated using the state variable approach, and how we can construct a probabilistic model for the switches by formulating a similar switching LFM as a switching linear dynamic system (SLDS). We illustrate the performance of the proposed methodology in simulated scenarios and apply it to inferring the switching points in GPS data collected from car movement data in urban environment.


title: What Cannot be Learned with Bethe Approximations

abstract: We address the problem of learning the parameters in graphical models when inference is intractable. A common strategy in this case is to replace the partition function with its Bethe approximation. We show that there exists a regime of empirical marginals where such Bethe learning will fail. By failure we mean that the empirical marginals cannot be recovered from the approximated maximum likelihood parameters (i.e., moment matching is not achieved). We provide several conditions on empirical marginals that yield outer and inner bounds on the set of Bethe learnable marginals. An interesting implication of our results is that there exists a large class of marginals that cannot be obtained as stable fixed points of belief propagation. Taken together our results provide a novel approach to analyzing learning with Bethe approximations and highlight when it can be expected to work or fail.


title: Sum-Product Networks: A New Deep Architecture

abstract: The key limiting factor in graphical model inference and learning is the complexity of the partition function. We thus ask the question: what are general conditions under which the partition function is tractable? The answer leads to a new kind of deep architecture, which we call sum-product networks (SPNs). SPNs are directed acyclic graphs with variables as leaves, sums and products as internal nodes, and weighted edges. We show that if an SPN is complete and consistent it represents the partition function and all marginals of some graphical model, and give semantics to its nodes. Essentially all tractable graphical models can be cast as SPNs, but SPNs are also strictly more general. We then propose learning algorithms for SPNs, based on backpropagation and EM. Experiments show that inference and learning with SPNs can be both faster and more accurate than with standard deep networks. For example, SPNs perform image completion better than state-of-the-art deep networks for this task. SPNs also have intriguing potential connections to the architecture of the cortex.


title: Lipschitz Parametrization of Probabilistic Graphical Models

abstract: We show that the log-likelihood of several probabilistic graphical models is Lipschitz continuous with respect to the lp-norm of the parameters. We discuss several implications of Lipschitz parametrization. We present an upper bound of the Kullback-Leibler divergence that allows understanding methods that penalize the lp-norm of differences of parameters as the minimization of that upper bound. The expected log-likelihood is lower bounded by the negative lp-norm, which allows understanding the generalization ability of probabilistic models. The exponential of the negative lp-norm is involved in the lower bound of the Bayes error rate, which shows that it is reasonable to use parameters as features in algorithms that rely on metric spaces (e.g. classification, dimensionality reduction, clustering). Our results do not rely on specific algorithms for learning the structure or parameters. We show preliminary results for activity recognition and temporal segmentation.


title: Efficient Probabilistic Inference with Partial Ranking Queries

abstract: Distributions over rankings are used to model data in various settings such as preference analysis and political elections. The factorial size of the space of rankings, however, typically forces one to make structural assumptions, such as smoothness, sparsity, or probabilistic independence about these underlying distributions. We approach the modeling problem from the computational principle that one should make structural assumptions which allow for efficient calculation of typical probabilistic queries. For ranking models, "typical" queries predominantly take the form of partial ranking queries (e.g., given a user's top-k favorite movies, what are his preferences over remaining movies?). In this paper, we argue that riffled independence factorizations proposed in recent literature [7, 8] are a natural structural assumption for ranking distributions, allowing for particularly efficient processing of partial ranking queries.


title: Noisy-OR Models with Latent Confounding

abstract: Given a set of experiments in which varying subsets of observed variables are subject to intervention, we consider the problem of identifiability of causal models exhibiting latent confounding. While identifiability is trivial when each experiment intervenes on a large number of variables, the situation is more complicated when only one or a few variables are subject to intervention per experiment. For linear causal models with latent variables Hyttinen et al. (2010) gave precise conditions for when such data are sufficient to identify the full model. While their result cannot be extended to discrete-valued variables with arbitrary cause-effect relationships, we show that a similar result can be obtained for the class of causal models whose conditional probability distributions are restricted to a `noisy-OR' parameterization. We further show that identification is preserved under an extension of the model that allows for negative influences, and present learning algorithms that we test for accuracy, scalability and robustness.


title: Discovering causal structures in binary exclusive-or skew acyclic models

abstract: Discovering causal relations among observed variables in a given data set is a main topic in studies of statistics and artificial intelligence. Recently, some techniques to discover an identifiable causal structure have been explored based on non-Gaussianity of the observed data distribution. However, most of these are limited to continuous data. In this paper, we present a novel causal model for binary data and propose a new approach to derive an identifiable causal structure governing the data based on skew Bernoulli distributions of external noise. Experimental evaluation shows excellent performance for both artificial and real world data sets.


title: Detecting low-complexity unobserved causes

abstract: We describe a method that infers whether statistical dependences between two observed variables X and Y are due to a "direct" causal link or only due to a connecting causal path that contains an unobserved variable of low complexity, e.g., a binary variable. This problem is motivated by statistical genetics. Given a genetic marker that is correlated with a phenotype of interest, we want to detect whether this marker is causal or it only correlates with a causal one. Our method is based on the analysis of the location of the conditional distributions P(Y|x) in the simplex of all distributions of Y. We report encouraging results on semi-empirical data.


title: Learning Determinantal Point Processes

abstract: Determinantal point processes (DPPs), which arise in random matrix theory and quantum physics, are natural models for subset selection problems where diversity is preferred. Among many remarkable properties, DPPs offer tractable algorithms for exact inference, including computing marginal probabilities and sampling; however, an important open question has been how to learn a DPP from labeled training data. In this paper we propose a natural feature-based parameterization of conditional DPPs, and show how it leads to a convex and efficient learning formulation. We analyze the relationship between our model and binary Markov random fields with repulsive potentials, which are qualitatively similar but computationally intractable. Finally, we apply our approach to the task of extractive summarization, where the goal is to choose a small subset of sentences conveying the most important information from a set of documents. In this task there is a fundamental tradeoff between sentences that are highly relevant to the collection as a whole, and sentences that are diverse and not repetitive. Our parameterization allows us to naturally balance these two characteristics. We evaluate our system on data from the DUC 2003/04 multi-document summarization task, achieving state-of-the-art results.


title: Message-Passing Algorithms for Quadratic Programming Formulations of MAP Estimation

abstract: Computing maximum a posteriori (MAP) estimation in graphical models is an important inference problem with many applications. We present message-passing algorithms for quadratic programming (QP) formulations of MAP estimation for pairwise Markov random fields. In particular, we use the concave-convex procedure (CCCP) to obtain a locally optimal algorithm for the non-convex QP formulation. A similar technique is used to derive a globally convergent algorithm for the convex QP relaxation of MAP. We also show that a recently developed expectation-maximization (EM) algorithm for the QP formulation of MAP can be derived from the CCCP perspective. Experiments on synthetic and real-world problems confirm that our new approach is competitive with max-product and its variations. Compared with CPLEX, we achieve more than an order-of-magnitude speedup in solving optimally the convex QP relaxation.


title: An Efficient Protocol for Negotiation over Combinatorial Domains with Incomplete Information

abstract: We study the problem of agent-based negotiation in combinatorial domains. It is difficult to reach optimal agreements in bilateral or multi-lateral negotiations when the agents' preferences for the possible alternatives are not common knowledge. Self-interested agents often end up negotiating inefficient agreements in such situations. In this paper, we present a protocol for negotiation in combinatorial domains which can lead rational agents to reach optimal agreements under incomplete information setting. Our proposed protocol enables the negotiating agents to identify efficient solutions using distributed search that visits only a small subspace of the whole outcome space. Moreover, the proposed protocol is sufficiently general that it is applicable to most preference representation models in combinatorial domains. We also present results of experiments that demonstrate the feasibility and computational efficiency of our approach.


title: Noisy Search with Comparative Feedback

abstract: We present theoretical results in terms of lower and upper bounds on the query complexity of noisy search with comparative feedback. In this search model, the noise in the feedback depends on the distance between query points and the search target. Consequently, the error probability in the feedback is not fixed but varies for the queries posed by the search algorithm. Our results show that a target out of n items can be found in O(log n) queries. We also show the surprising result that for k possible answers per query, the speedup is not log k (as for k-ary search) but only log log k in some cases.


title: Variational Algorithms for Marginal MAP

abstract: Marginal MAP problems are notoriously difficult tasks for graphical models. We derive a general variational framework for solving marginal MAP problems, in which we apply analogues of the Bethe, tree-reweighted, and mean field approximations. We then derive a "mixed" message passing algorithm and a convergent alternative using CCCP to solve the BP-type approximations. Theoretically, we give conditions under which the decoded solution is a global or local optimum, and obtain novel upper bounds on solutions. Experimentally we demonstrate that our algorithms outperform related approaches. We also show that EM and variational EM comprise a special case of our framework.


title: Belief change with noisy sensing in the situation calculus

abstract: Situation calculus has been applied widely in artificial intelligence to model and reason about actions and changes in dynamic systems. Since actions carried out by agents will cause constant changes of the agents' beliefs, how to manage these changes is a very important issue. Shapiro et al. [22] is one of the studies that considered this issue. However, in this framework, the problem of noisy sensing, which often presents in real-world applications, is not considered. As a consequence, noisy sensing actions in this framework will lead to an agent facing inconsistent situation and subsequently the agent cannot proceed further. In this paper, we investigate how noisy sensing actions can be handled in iterated belief change within the situation calculus formalism. We extend the framework proposed in [22] with the capability of managing noisy sensings. We demonstrate that an agent can still detect the actual situation when the ratio of noisy sensing actions vs. accurate sensing actions is limited. We prove that our framework subsumes the iterated belief change strategy in [22] when all sensing actions are accurate. Furthermore, we prove that our framework can adequately handle belief introspection, mistaken beliefs, belief revision and belief update even with noisy sensing, as done in [22] with accurate sensing actions only.


title: Improving the Scalability of Optimal Bayesian Network Learning with External-Memory Frontier Breadth-First Branch and Bound Search

abstract: Previous work has shown that the problem of learning the optimal structure of a Bayesian network can be formulated as a shortest path finding problem in a graph and solved using A* search. In this paper, we improve the scalability of this approach by developing a memory-efficient heuristic search algorithm for learning the structure of a Bayesian network. Instead of using A*, we propose a frontier breadth-first branch and bound search that leverages the layered structure of the search graph of this problem so that no more than two layers of the graph, plus solution reconstruction information, need to be stored in memory at a time. To further improve scalability, the algorithm stores most of the graph in external memory, such as hard disk, when it does not fit in RAM. Experimental results show that the resulting algorithm solves significantly larger problems than the current state of the art.


title: Order-of-Magnitude Influence Diagrams

abstract: In this paper, we develop a qualitative theory of influence diagrams that can be used to model and solve sequential decision making tasks when only qualitative (or imprecise) information is available. Our approach is based on an order-of-magnitude approximation of both probabilities and utilities and allows for specifying partially ordered preferences via sets of utility values. We also propose a dedicated variable elimination algorithm that can be applied for solving order-of-magnitude influence diagrams.


title: Asymptotic Efficiency of Deterministic Estimators for Discrete Energy-Based Models: Ratio Matching and Pseudolikelihood

abstract: Standard maximum likelihood estimation cannot be applied to discrete energy-based models in the general case because the computation of exact model probabilities is intractable. Recent research has seen the proposal of several new estimators designed specifically to overcome this intractability, but virtually nothing is known about their theoretical properties. In this paper, we present a generalized estimator that unifies many of the classical and recently proposed estimators. We use results from the standard asymptotic theory for M-estimators to derive a generic expression for the asymptotic covariance matrix of our generalized estimator. We apply these results to study the relative statistical efficiency of classical pseudolikelihood and the recently-proposed ratio matching estimator.


title: Reconstructing Pompeian Households

abstract: A database of objects discovered in houses in the Roman city of Pompeii provides a unique view of ordinary life in an ancient city. Experts have used this collection to study the structure of Roman households, exploring the distribution and variability of tasks in architectural spaces, but such approaches are necessarily affected by modern cultural assumptions. In this study we present a data-driven approach to household archeology, treating it as an unsupervised labeling problem. This approach scales to large data sets and provides a more objective complement to human interpretation.


title: Conditional Restricted Boltzmann Machines for Structured Output Prediction

abstract: Conditional Restricted Boltzmann Machines (CRBMs) are rich probabilistic models that have recently been applied to a wide range of problems, including collaborative filtering, classification, and modeling motion capture data. While much progress has been made in training non-conditional RBMs, these algorithms are not applicable to conditional models and there has been almost no work on training and generating predictions from conditional RBMs for structured output problems. We first argue that standard Contrastive Divergence-based learning may not be suitable for training CRBMs. We then identify two distinct types of structured output prediction problems and propose an improved learning algorithm for each. The first problem type is one where the output space has arbitrary structure but the set of likely output configurations is relatively small, such as in multi-label classification. The second problem is one where the output space is arbitrarily structured but where the output space variability is much greater, such as in image denoising or pixel labeling. We show that the new learning algorithms can work much better than Contrastive Divergence on both types of problems.


title: Compact Mathematical Programs For DEC-MDPs With Structured Agent Interactions

abstract: To deal with the prohibitive complexity of calculating policies in Decentralized MDPs, researchers have proposed models that exploit structured agent interactions. Settings where most agent actions are independent except for few actions that affect the transitions and/or rewards of other agents can be modeled using Event-Driven Interactions with Complex Rewards (EDI-CR). Finding the optimal joint policy can be formulated as an optimization problem. However, existing formulations are too verbose and/or lack optimality guarantees. We propose a compact Mixed Integer Linear Program formulation of EDI-CR instances. The key insight is that most action sequences of a group of agents have the same effect on a given agent. This allows us to treat these sequences similarly and use fewer variables. Experiments show that our formulation is more compact and leads to faster solution times and better solutions than existing formulations.


title: Fractional Moments on Bandit Problems

abstract: Reinforcement learning addresses the dilemma between exploration to find profitable actions and exploitation to act according to the best observations already made. Bandit problems are one such class of problems in stateless environments that represent this explore/exploit situation. We propose a learning algorithm for bandit problems based on fractional expectation of rewards acquired. The algorithm is theoretically shown to converge on an eta-optimal arm and achieve O(n) sample complexity. Experimental results show the algorithm incurs substantially lower regrets than parameter-optimized eta-greedy and SoftMax approaches and other low sample complexity state-of-the-art techniques.


title: Dynamic Mechanism Design for Markets with Strategic Resources

abstract: The assignment of tasks to multiple resources becomes an interesting game theoretic problem, when both the task owner and the resources are strategic. In the classical, nonstrategic setting, where the states of the tasks and resources are observable by the controller, this problem is that of finding an optimal policy for a Markov decision process (MDP). When the states are held by strategic agents, the problem of an efficient task allocation extends beyond that of solving an MDP and becomes that of designing a mechanism. Motivated by this fact, we propose a general mechanism which decides on an allocation rule for the tasks and resources and a payment rule to incentivize agents' participation and truthful reports. In contrast to related dynamic strategic control problems studied in recent literature, the problem studied here has interdependent values: the benefit of an allocation to the task owner is not simply a function of the characteristics of the task itself and the allocation, but also of the state of the resources. We introduce a dynamic extension of Mezzetti's two phase mechanism for interdependent valuations. In this changed setting, the proposed dynamic mechanism is efficient, within period ex-post incentive compatible, and within period ex-post individually rational.