title: Combining local search techniques and path following for bimatrix games

abstract: Computing a Nash equilibrium (NE) is a central task in computer science. An NE is a particularly appropriate solution concept for two-agent settings because coalitional deviations are not an issue. However, even in this case, finding an NE is PPAD-complete. In this paper, we combine path following algorithms with local search techniques to design new algorithms for finding exact and approximate NEs. We show that our algorithms largely outperform the state of the art and that almost all the known benchmark game classes are easily solvable or approximable (except for the GAMUT CovariantGameRand class).


title: Mechanism Design for Cost Optimal PAC Learning in the Presence of Strategic Noisy Annotators

abstract: We consider the problem of Probably Approximate Correct (PAC) learning of a binary classifier from noisy labeled examples acquired from multiple annotators (each characterized by a respective classification noise rate). First, we consider the complete information scenario, where the learner knows the noise rates of all the annotators. For this scenario, we derive sample complexity bound for the Minimum Disagreement Algorithm (MDA) on the number of labeled examples to be obtained from each annotator. Next, we consider the incomplete information scenario, where each annotator is strategic and holds the respective noise rate as a private information. For this scenario, we design a cost optimal procurement auction mechanism along the lines of Myerson's optimal auction design framework in a non-trivial manner. This mechanism satisfies incentive compatibility property, thereby facilitating the learner to elicit true noise rates of all the annotators.


title: Spectral Estimation of Conditional Random Graph Models for Large-Scale Network Data

abstract: Generative models for graphs have been typically committed to strong prior assumptions concerning the form of the modeled distributions. Moreover, the vast majority of currently available models are either only suitable for characterizing some particular network properties (such as degree distribution or clustering coefficient), or they are aimed at estimating joint probability distributions, which is often intractable in large-scale networks. In this paper, we first propose a novel network statistic, based on the Laplacian spectrum of graphs, which allows to dispense with any parametric assumption concerning the modeled network properties. Second, we use the defined statistic to develop the Fiedler random graph model, switching the focus from the estimation of joint probability distributions to a more tractable conditional estimation setting. After analyzing the dependence structure characterizing Fiedler random graphs, we evaluate them experimentally in edge prediction over several real-world networks, showing that they allow to reach a much higher prediction accuracy than various alternative statistical models.


title: Uniform Solution Sampling Using a Constraint Solver As an Oracle

abstract: We consider the problem of sampling from solutions defined by a set of hard constraints on a combinatorial space. We propose a new sampling technique that, while enforcing a uniform exploration of the search space, leverages the reasoning power of a systematic constraint solver in a black-box scheme. We present a series of challenging domains, such as energy barriers and highly asymmetric spaces, that reveal the difficulties introduced by hard constraints. We demonstrate that standard approaches such as Simulated Annealing and Gibbs Sampling are greatly affected, while our new technique can overcome many of these difficulties. Finally, we show that our sampling scheme naturally defines a new approximate model counting technique, which we empirically show to be very accurate on a range of benchmark problems.


title: Sample-efficient Nonstationary Policy Evaluation for Contextual Bandits

abstract: We present and prove properties of a new offline policy evaluator for an exploration learning setting which is superior to previous evaluators. In particular, it simultaneously and correctly incorporates techniques from importance weighting, doubly robust evaluation, and nonstationary policy evaluation approaches. In addition, our approach allows generating longer histories by careful control of a bias-variance tradeoff, and further decreases variance by incorporating information about randomness of the target policy. Empirical evidence from synthetic and realworld exploration learning problems shows the new evaluator successfully unifies previous approaches and uses information an order of magnitude more efficiently.


title: DBN-Based Combinatorial Resampling for Articulated Object Tracking

abstract: Particle Filter is an effective solution to track objects in video sequences in complex situations. Its key idea is to estimate the density over the possible states of the object using a weighted sample whose elements are called particles. One of its crucial step is a resampling step in which particles are resampled to avoid some degeneracy problem. In this paper, we introduce a new resampling method called Combinatorial Resampling that exploits some features of articulated objects to resample over an implicitly created sample of an exponential size better representing the density to estimate. We prove that it is sound and, through experimentations both on challenging synthetic and real video sequences, we show that it outperforms all classical resampling methods both in terms of the quality of its results and in terms of response times.


title: Graph-Coupled HMMs for Modeling the Spread of Infection

abstract: We develop Graph-Coupled Hidden Markov Models (GCHMMs) for modeling the spread of infectious disease locally within a social network. Unlike most previous research in epidemiology, which typically models the spread of infection at the level of entire populations, we successfully leverage mobile phone data collected from 84 people over an extended period of time to model the spread of infection on an individual level. Our model, the GCHMM, is an extension of widely-used Coupled Hidden Markov Models (CHMMs), which allow dependencies between state transitions across multiple Hidden Markov Models (HMMs), to situations in which those dependencies are captured through the structure of a graph, or to social networks that may change over time. The benefit of making infection predictions on an individual level is enormous, as it allows people to receive more personalized and relevant health advice.


title: Scaling Up Decentralized MDPs Through Heuristic Search

abstract: Decentralized partially observable Markov decision processes (Dec-POMDPs) are rich models for cooperative decision-making under uncertainty, but are often intractable to solve optimally (NEXP-complete). The transition and observation independent Dec-MDP is a general subclass that has been shown to have complexity in NP, but optimal algorithms for this subclass are still inefficient in practice. In this paper, we first provide an updated proof that an optimal policy does not depend on the histories of the agents, but only the local observations. We then present a new algorithm based on heuristic search that is able to expand search nodes by using constraint optimization. We show experimental results comparing our approach with the state-of-the-art DecMDP and Dec-POMDP solvers. These results show a reduction in computation time and an increase in scalability by multiple orders of magnitude in a number of benchmarks.


title: A Bayesian Approach to Constraint Based Causal Inference

abstract: We target the problem of accuracy and robustness in causal inference from finite data sets. Some state-of-the-art algorithms produce clear output complete with solid theoretical guarantees but are susceptible to propagating erroneous decisions, while others are very adept at handling and representing uncertainty, but need to rely on undesirable assumptions. Our aim is to combine the inherent robustness of the Bayesian approach with the theoretical strength and clarity of constraint-based methods. We use a Bayesian score to obtain probability estimates on the input statements used in a constraint-based procedure. These are subsequently processed in decreasing order of reliability, letting more reliable decisions take precedence in case of con icts, until a single output model is obtained. Tests show that a basic implementation of the resulting Bayesian Constraint-based Causal Discovery (BCCD) algorithm already outperforms established procedures such as FCI and Conservative PC. It can also indicate which causal decisions in the output have high reliability and which do not.


title: Lifted Relational Variational Inference

abstract: Hybrid continuous-discrete models naturally represent many real-world applications in robotics, finance, and environmental engineering. Inference with large-scale models is challenging because relational structures deteriorate rapidly during inference with observations. The main contribution of this paper is an efficient relational variational inference algorithm that factors largescale probability models into simpler variational models, composed of mixtures of iid (Bernoulli) random variables. The algorithm takes probability relational models of largescale hybrid systems and converts them to a close-to-optimal variational models. Then, it efficiently calculates marginal probabilities on the variational models by using a latent (or lifted) variable elimination or a lifted stochastic sampling. This inference is unique because it maintains the relational structure upon individual observations and during inference steps.


title: Graphical-model Based Multiple Testing under Dependence, with Applications to Genome-wide Association Studies

abstract: Large-scale multiple testing tasks often exhibit dependence, and leveraging the dependence between individual tests is still one challenging and important problem in statistics. With recent advances in graphical models, it is feasible to use them to perform multiple testing under dependence. We propose a multiple testing procedure which is based on a Markov-random-field-coupled mixture model. The ground truth of hypotheses is represented by a latent binary Markov random field, and the observed test statistics appear as the coupled mixture variables. The parameters in our model can be automatically learned by a novel EM algorithm. We use an MCMC algorithm to infer the posterior probability that each hypothesis is null (termed local index of significance), and the false discovery rate can be controlled accordingly. Simulations show that the numerical performance of multiple testing can be improved substantially by using our procedure. We apply the procedure to a real-world genome-wide association study on breast cancer, and we identify several SNPs with strong association evidence.


title: Response Aware Model-Based Collaborative Filtering

abstract: Previous work on recommender systems mainly focus on fitting the ratings provided by users. However, the response patterns, i.e., some items are rated while others not, are generally ignored. We argue that failing to observe such response patterns can lead to biased parameter estimation and sub-optimal model performance. Although several pieces of work have tried to model users' response patterns, they miss the effectiveness and interpretability of the successful matrix factorization collaborative filtering approaches. To bridge the gap, in this paper, we unify explicit response models and PMF to establish the Response Aware Probabilistic Matrix Factorization (RAPMF) framework. We show that RAPMF subsumes PMF as a special case. Empirically we demonstrate the merits of RAPMF from various aspects.


title: Crowdsourcing Control: Moving Beyond Multiple Choice

abstract: To ensure quality results from crowdsourced tasks, requesters often aggregate worker responses and use one of a plethora of strategies to infer the correct answer from the set of noisy responses. However, all current models assume prior knowledge of all possible outcomes of the task. While not an unreasonable assumption for tasks that can be posited as multiple-choice questions (e.g. n-ary classification), we observe that many tasks do not naturally fit this paradigm, but instead demand a free-response formulation where the outcome space is of infinite size (e.g. audio transcription). We model such tasks with a novel probabilistic graphical model, and design and implement LazySusan, a decision-theoretic controller that dynamically requests responses as necessary in order to infer answers to these tasks. We also design an EM algorithm to jointly learn the parameters of our model while inferring the correct answers to multiple tasks at a time. Live experiments on Amazon Mechanical Turk demonstrate the superiority of LazySusan at solving SAT Math questions, eliminating 83.2% of the error and achieving greater net utility compared to the state-ofthe-art strategy, majority-voting. We also show in live experiments that our EM algorithm outperforms majority-voting on a visualization task that we design.


title: Learning Mixtures of Submodular Shells with Application to Document Summarization

abstract: We introduce a method to learn a mixture of submodular "shells" in a large-margin setting. A submodular shell is an abstract submodular function that can be instantiated with a ground set and a set of parameters to produce a submodular function. A mixture of such shells can then also be so instantiated to produce a more complex submodular function. What our algorithm learns are the mixture weights over such shells. We provide a risk bound guarantee when learning in a large-margin structured-prediction setting using a projected subgradient method when only approximate submodular optimization is possible (such as with submodular function maximization). We apply this method to the problem of multi-document summarization and produce the best results reported so far on the widely used NIST DUC-05 through DUC-07 document summarization corpora.


title: Nested Dictionary Learning for Hierarchical Organization of Imagery and Text

abstract: A tree-based dictionary learning model is developed for joint analysis of imagery and associated text. The dictionary learning may be applied directly to the imagery from patches, or to general feature vectors extracted from patches or superpixels (using any existing method for image feature extraction). Each image is associated with a path through the tree (from root to a leaf), and each of the multiple patches in a given image is associated with one node in that path. Nodes near the tree root are shared between multiple paths, representing image characteristics that are common among different types of images. Moving toward the leaves, nodes become specialized, representing details in image classes. If available, words (text) are also jointly modeled, with a path-dependent probability over words. The tree structure is inferred via a nested Dirichlet process, and a retrospective stick-breaking sampler is used to infer the tree depth and width.


title: Computing Optimal Security Strategies for Interdependent Assets

abstract: We introduce a novel framework for computing optimal randomized security policies in networked domains which extends previous approaches in several ways. First, we extend previous linear programming techniques for Stackelberg security games to incorporate benefits and costs of arbitrary security configurations on individual assets. Second, we offer a principled model of failure cascades that allows us to capture both the direct and indirect value of assets, and extend this model to capture uncertainty about the structure of the interdependency network. Third, we extend the linear programming formulation to account for exogenous (random) failures in addition to targeted attacks. The goal of our work is two-fold. First, we aim to develop techniques for computing optimal security strategies in realistic settings involving interdependent security. To this end, we evaluate the value of our technical contributions in comparison with previous approaches, and show that our approach yields much better defense policies and scales to realistic graphs. Second, our computational framework enables us to attain theoretical insights about security on networks. As an example, we study how allowing security to be endogenous impacts the relative resilience of different network topologies.


title: Dynamic Stochastic Orienteering Problems for Risk-Aware Applications

abstract: Orienteering problems (OPs) are a variant of the well-known prize-collecting traveling salesman problem, where the salesman needs to choose a subset of cities to visit within a given deadline. OPs and their extensions with stochastic travel times (SOPs) have been used to model vehicle routing problems and tourist trip design problems. However, they suffer from two limitations travel times between cities are assumed to be time independent and the route provided is independent of the risk preference (with respect to violating the deadline) of the user. To address these issues, we make the following contributions: We introduce (1) a dynamic SOP (DSOP) model, which is an extension of SOPs with dynamic (time-dependent) travel times; (2) a risk-sensitive criterion to allow for different risk preferences; and (3) a local search algorithm to solve DSOPs with this risk-sensitive criterion. We evaluated our algorithms on a real-world dataset for a theme park navigation problem as well as synthetic datasets employed in the literature.


title: A Theory of Goal-Oriented MDPs with Dead Ends

abstract: Stochastic Shortest Path (SSP) MDPs is a problem class widely studied in AI, especially in probabilistic planning. They describe a wide range of scenarios but make the restrictive assumption that the goal is reachable from any state, i.e., that dead-end states do not exist. Because of this, SSPs are unable to model various scenarios that may have catastrophic events (e.g., an airplane possibly crashing if it flies into a storm). Even though MDP algorithms have been used for solving problems with dead ends, a principled theory of SSP extensions that would allow dead ends, including theoretically sound algorithms for solving such MDPs, has been lacking. In this paper, we propose three new MDP classes that admit dead ends under increasingly weaker assumptions. We present Value Iteration-based as well as the more efficient heuristic search algorithms for optimally solving each class, and explore theoretical relationships between these classes. We also conduct a preliminary empirical study comparing the performance of our algorithms on different MDP classes, especially on scenarios with unavoidable dead ends.


title: Active Imitation Learning via Reduction to I.I.D. Active Learning

abstract: In standard passive imitation learning, the goal is to learn a target policy by passively observing full execution trajectories of it. Unfortunately, generating such trajectories can require substantial expert effort and be impractical in some cases. In this paper, we consider active imitation learning with the goal of reducing this effort by querying the expert about the desired action at individual states, which are selected based on answers to past queries and the learner's interactions with an environment simulator. We introduce a new approach based on reducing active imitation learning to i.i.d. active learning, which can leverage progress in the i.i.d. setting. Our first contribution, is to analyze reductions for both non-stationary and stationary policies, showing that the label complexity (number of queries) of active imitation learning can be substantially less than passive learning. Our second contribution, is to introduce a practical algorithm inspired by the reductions, which is shown to be highly effective in four test domains compared to a number of alternatives.


title: Incentive Decision Processes

abstract: We consider Incentive Decision Processes, where a principal seeks to reduce its costs due to another agent's behavior, by offering incentives to the agent for alternate behavior. We focus on the case where a principal interacts with a greedy agent whose preferences are hidden and static. Though IDPs can be directly modeled as partially observable Markov decision processes (POMDP), we show that it is possible to directly reduce or approximate the IDP as a polynomially-sized MDP: when this representation is approximate, we prove the resulting policy is boundedly-optimal for the original IDP. Our empirical simulations demonstrate the performance benefit of our algorithms over simpler approaches, and also demonstrate that our approximate representation results in a significantly faster algorithm whose performance is extremely close to the optimal policy for the original IDP.


title: Join-graph based cost-shifting schemes

abstract: We develop several algorithms taking advantage of two common approaches for bounding MPE queries in graphical models: minibucket elimination and message-passing updates for linear programming relaxations. Both methods are quite similar, and offer useful perspectives for the other; our hybrid approaches attempt to balance the advantages of each. We demonstrate the power of our hybrid algorithms through extensive empirical evaluation. Most notably, a Branch and Bound search guided by the heuristic function calculated by one of our new algorithms has recently won first place in the PASCAL2 inference challenge.


title: Causal Discovery of Linear Cyclic Models from Multiple Experimental Data Sets with Overlapping Variables

abstract: Much of scientific data is collected as randomized experiments intervening on some and observing other variables of interest. Quite often, a given phenomenon is investigated in several studies, and different sets of variables are involved in each study. In this article we consider the problem of integrating such knowledge, inferring as much as possible concerning the underlying causal structure with respect to the union of observed variables from such experimental or passive observational overlapping data sets. We do not assume acyclicity or joint causal sufficiency of the underlying data generating model, but we do restrict the causal relationships to be linear and use only second order statistics of the data. We derive conditions for full model identifiability in the most generic case, and provide novel techniques for incorporating an assumption of faithfulness to aid in inference. In each case we seek to establish what is and what is not determined by the data at hand.


title: Inferring Strategies from Limited Reconnaissance in Real-time Strategy Games

abstract: In typical real-time strategy (RTS) games, enemy units are visible only when they are within sight range of a friendly unit. Knowledge of an opponent's disposition is limited to what can be observed through scouting. Information is costly, since units dedicated to scouting are unavailable for other purposes, and the enemy will resist scouting attempts. It is important to infer as much as possible about the opponent's current and future strategy from the available observations. We present a dynamic Bayes net model of strategies in the RTS game Starcraft that combines a generative model of how strategies relate to observable quantities with a principled framework for incorporating evidence gained via scouting. We demonstrate the model's ability to infer unobserved aspects of the game from realistic observations.


title: Tightening Fractional Covering Upper Bounds on the Partition Function for High-Order Region Graphs

abstract: In this paper we present a new approach for tightening upper bounds on the partition function. Our upper bounds are based on fractional covering bounds on the entropy function, and result in a concave program to compute these bounds and a convex program to tighten them. To solve these programs effectively for general region graphs we utilize the entropy barrier method, thus decomposing the original programs by their dual programs and solve them with dual block optimization scheme. The entropy barrier method provides an elegant framework to generalize the message-passing scheme to high-order region graph, as well as to solve the block dual steps in closed-form. This is a key for computational relevancy for large problems with thousands of regions.


title: A Maximum Likelihood Approach For Selecting Sets of Alternatives

abstract: We consider the problem of selecting a subset of alternatives given noisy evaluations of the relative strength of different alternatives. We wish to select a k-subset (for a given k) that provides a maximum likelihood estimate for one of several objectives, e.g., containing the strongest alternative. Although this problem is NP-hard, we show that when the noise level is sufficiently high, intuitive methods provide the optimal solution. We thus generalize classical results about singling out one alternative and identifying the hidden ranking of alternatives by strength. Extensive experiments show that our methods perform well in practical settings.


title: A Model-Based Approach to Rounding in Spectral Clustering

abstract: In spectral clustering, one defines a similarity matrix for a collection of data points, transforms the matrix to get the Laplacian matrix, finds the eigenvectors of the Laplacian matrix, and obtains a partition of the data using the leading eigenvectors. The last step is sometimes referred to as rounding, where one needs to decide how many leading eigenvectors to use, to determine the number of clusters, and to partition the data points. In this paper, we propose a novel method for rounding. The method differs from previous methods in three ways. First, we relax the assumption that the number of clusters equals the number of eigenvectors used. Second, when deciding the number of leading eigenvectors to use, we not only rely on information contained in the leading eigenvectors themselves, but also use subsequent eigenvectors. Third, our method is model-based and solves all the three subproblems of rounding using a class of graphical models called latent tree models. We evaluate our method on both synthetic and real-world data. The results show that our method works correctly in the ideal case where between-clusters similarity is 0, and degrades gracefully as one moves away from the ideal case.


title: A Spectral Algorithm for Latent Junction Trees

abstract: Latent variable models are an elegant framework for capturing rich probabilistic dependencies in many applications. However, current approaches typically parametrize these models using conditional probability tables, and learning relies predominantly on local search heuristics such as Expectation Maximization. Using tensor algebra, we propose an alternative parameterization of latent variable models (where the model structures are junction trees) that still allows for computation of marginals among observed variables. While this novel representation leads to a moderate increase in the number of parameters for junction trees of low treewidth, it lets us design a local-minimum-free algorithm for learning this parameterization. The main computation of the algorithm involves only tensor operations and SVDs which can be orders of magnitude faster than EM algorithms for large datasets. To our knowledge, this is the first provably consistent parameter learning technique for a large class of low-treewidth latent graphical models beyond trees. We demonstrate the advantages of our method on synthetic and real datasets.


title: A Case Study in Complexity Estimation: Towards Parallel Branch-and-Bound over Graphical Models

abstract: We study the problem of complexity estimation in the context of parallelizing an advanced Branch and Bound-type algorithm over graphical models. The algorithm's pruning power makes load balancing, one crucial element of every distributed system, very challenging. We propose using a statistical regression model to identify and tackle disproportionally complex parallel subproblems, the cause of load imbalance, ahead of time. The proposed model is evaluated and analyzed on various levels and shown to yield robust predictions. We then demonstrate its effectiveness for load balancing in practice.


title: Exploiting Structure in Cooperative Bayesian Games

abstract: Cooperative Bayesian games (BGs) can model decision-making problems for teams of agents under imperfect information, but require space and computation time that is exponential in the number of agents. While agent independence has been used to mitigate these problems in perfect information settings, we propose a novel approach for BGs based on the observation that BGs additionally possess a different types of structure, which we call type independence. We propose a factor graph representation that captures both forms of independence and present a theoretical analysis showing that non-serial dynamic programming cannot effectively exploit type independence, while Max-Sum can. Experimental results demonstrate that our approach can tackle cooperative Bayesian games of unprecedented size.


title: Hilbert Space Embeddings of POMDPs

abstract: A nonparametric approach for policy learning for POMDPs is proposed. The approach represents distributions over the states, observations, and actions as embeddings in feature spaces, which are reproducing kernel Hilbert spaces. Distributions over states given the observations are obtained by applying the kernel Bayes' rule to these distribution embeddings. Policies and value functions are defined on the feature space over states, which leads to a feature space expression for the Bellman equation. Value iteration may then be used to estimate the optimal value function and associated policy. Experimental results confirm that the correct policy is learned using the feature space representation.


title: Local Structure Discovery in Bayesian Networks

abstract: Learning a Bayesian network structure from data is an NP-hard problem and thus exact algorithms are feasible only for small data sets. Therefore, network structures for larger networks are usually learned with various heuristics. Another approach to scaling up the structure learning is local learning. In local learning, the modeler has one or more target variables that are of special interest; he wants to learn the structure near the target variables and is not interested in the rest of the variables. In this paper, we present a score-based local learning algorithm called SLL. We conjecture that our algorithm is theoretically sound in the sense that it is optimal in the limit of large sample size. Empirical results suggest that SLL is competitive when compared to the constraint-based HITON algorithm. We also study the prospects of constructing the network structure for the whole node set based on local results by presenting two algorithms and comparing them to several heuristics.


title: Learning STRIPS Operators from Noisy and Incomplete Observations

abstract: Agents learning to act autonomously in real-world domains must acquire a model of the dynamics of the domain in which they operate. Learning domain dynamics can be challenging, especially where an agent only has partial access to the world state, and/or noisy external sensors. Even in standard STRIPS domains, existing approaches cannot learn from noisy, incomplete observations typical of real-world domains. We propose a method which learns STRIPS action models in such domains, by decomposing the problem into first learning a transition function between states in the form of a set of classifiers, and then deriving explicit STRIPS rules from the classifiers' parameters. We evaluate our approach on simulated standard planning domains from the International Planning Competition, and show that it learns useful domain descriptions from noisy, incomplete observations.


title: The Complexity of Approximately Solving Influence Diagrams

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


title: Hokusai - Sketching Streams in Real Time

abstract: We describe Hokusai, a real time system which is able to capture frequency information for streams of arbitrary sequences of symbols. The algorithm uses the CountMin sketch as its basis and exploits the fact that sketching is linear. It provides real time statistics of arbitrary events, e.g. streams of queries as a function of time. We use a factorizing approximation to provide point estimates at arbitrary (time, item) combinations. Queries can be answered in constant time.


title: Unsupervised Joint Alignment and Clustering using Bayesian Nonparametrics

abstract: Joint alignment of a collection of functions is the process of independently transforming the functions so that they appear more similar to each other. Typically, such unsupervised alignment algorithms fail when presented with complex data sets arising from multiple modalities or make restrictive assumptions about the form of the functions or transformations, limiting their generality. We present a transformed Bayesian infinite mixture model that can simultaneously align and cluster a data set. Our model and associated learning scheme offer two key advantages: the optimal number of clusters is determined in a data-driven fashion through the use of a Dirichlet process prior, and it can accommodate any transformation function parameterized by a continuous parameter vector. As a result, it is applicable to a wide range of data types, and transformation functions. We present positive results on synthetic two-dimensional data, on a set of one-dimensional curves, and on various image data sets, showing large improvements over previous work. We discuss several variations of the model and conclude with directions for future work.


title: Sparse Q-learning with Mirror Descent

abstract: This paper explores a new framework for reinforcement learning based on online convex optimization, in particular mirror descent and related algorithms. Mirror descent can be viewed as an enhanced gradient method, particularly suited to minimization of convex functions in highdimensional spaces. Unlike traditional gradient methods, mirror descent undertakes gradient updates of weights in both the dual space and primal space, which are linked together using a Legendre transform. Mirror descent can be viewed as a proximal algorithm where the distance generating function used is a Bregman divergence. A new class of proximal-gradient based temporal-difference (TD) methods are presented based on different Bregman divergences, which are more powerful than regular TD learning. Examples of Bregman divergences that are studied include p-norm functions, and Mahalanobis distance based on the covariance of sample gradients. A new family of sparse mirror-descent reinforcement learning methods are proposed, which are able to find sparse fixed points of an l1-regularized Bellman equation at significantly less computational cost than previous methods based on second-order matrix methods. An experimental study of mirror-descent reinforcement learning is presented using discrete and continuous Markov decision processes.


title: Heuristic Ranking in Tightly Coupled Probabilistic Description Logics

abstract: The Semantic Web effort has steadily been gaining traction in the recent years. In particular,Web search companies are recently realizing that their products need to evolve towards having richer semantic search capabilities. Description logics (DLs) have been adopted as the formal underpinnings for Semantic Web languages used in describing ontologies. Reasoning under uncertainty has recently taken a leading role in this arena, given the nature of data found on theWeb. In this paper, we present a probabilistic extension of the DL EL++ (which underlies the OWL2 EL profile) using Markov logic networks (MLNs) as probabilistic semantics. This extension is tightly coupled, meaning that probabilistic annotations in formulas can refer to objects in the ontology. We show that, even though the tightly coupled nature of our language means that many basic operations are data-intractable, we can leverage a sublanguage of MLNs that allows to rank the atomic consequences of an ontology relative to their probability values (called ranking queries) even when these values are not fully computed. We present an anytime algorithm to answer ranking queries, and provide an upper bound on the error that it incurs, as well as a criterion to decide when results are guaranteed to be correct.


title: Bayesian Vote Manipulation: Optimal Strategies and Impact on Welfare

abstract: Most analyses of manipulation of voting schemes have adopted two assumptions that greatly diminish their practical import. First, it is usually assumed that the manipulators have full knowledge of the votes of the nonmanipulating agents. Second, analysis tends to focus on the probability of manipulation rather than its impact on the social choice objective (e.g., social welfare). We relax both of these assumptions by analyzing optimal Bayesian manipulation strategies when the manipulators have only partial probabilistic information about nonmanipulator votes, and assessing the expected loss in social welfare (in the broad sense of the term). We present a general optimization framework for the derivation of optimal manipulation strategies given arbitrary voting rules and distributions over preferences. We theoretically and empirically analyze the optimal manipulability of some popular voting rules using distributions and real data sets that go well beyond the common, but unrealistic, impartial culture assumption. We also shed light on the stark difference between the loss in social welfare and the probability of manipulation by showing that even when manipulation is likely, impact to social welfare is slight (and often negligible).


title: Closed-Form Learning of Markov Networks from Dependency Networks

abstract: Markov networks (MNs) are a powerful way to compactly represent a joint probability distribution, but most MN structure learning methods are very slow, due to the high cost of evaluating candidates structures. Dependency networks (DNs) represent a probability distribution as a set of conditional probability distributions. DNs are very fast to learn, but the conditional distributions may be inconsistent with each other and few inference algorithms support DNs. In this paper, we present a closed-form method for converting a DN into an MN, allowing us to enjoy both the efficiency of DN learning and the convenience of the MN representation. When the DN is consistent, this conversion is exact. For inconsistent DNs, we present averaging methods that significantly improve the approximation. In experiments on 12 standard datasets, our methods are orders of magnitude faster than and often more accurate than combining conditional distributions using weight learning.


title: Belief Propagation for Structured Decision Making

abstract: Variational inference algorithms such as belief propagation have had tremendous impact on our ability to learn and use graphical models, and give many insights for developing or understanding exact and approximate inference. However, variational approaches have not been widely adoped for decision making in graphical models, often formulated through influence diagrams and including both centralized and decentralized (or multi-agent) decisions. In this work, we present a general variational framework for solving structured cooperative decision-making problems, use it to propose several belief propagation-like algorithms, and analyze them both theoretically and empirically.


title: Value Function Approximation in Noisy Environments Using Locally Smoothed Regularized Approximate Linear Programs

abstract: Recently, Petrik et al. demonstrated that L1Regularized Approximate Linear Programming (RALP) could produce value functions and policies which compared favorably to established linear value function approximation techniques like LSPI. RALP's success primarily stems from the ability to solve the feature selection and value function approximation steps simultaneously. RALP's performance guarantees become looser if sampled next states are used. For very noisy domains, RALP requires an accurate model rather than samples, which can be unrealistic in some practical scenarios. In this paper, we demonstrate this weakness, and then introduce Locally Smoothed L1-Regularized Approximate Linear Programming (LS-RALP). We demonstrate that LS-RALP mitigates inaccuracies stemming from noise even without an accurate model. We show that, given some smoothness assumptions, as the number of samples increases, error from noise approaches zero, and provide experimental examples of LS-RALP's success on common reinforcement learning benchmark problems.


title: Fast Exact Inference for Recursive Cardinality Models

abstract: Cardinality potentials are a generally useful class of high order potential that affect probabilities based on how many of D binary variables are active. Maximum a posteriori (MAP) inference for cardinality potential models is well-understood, with efficient computations taking O(DlogD) time. Yet efficient marginalization and sampling have not been addressed as thoroughly in the machine learning community. We show that there exists a simple algorithm for computing marginal probabilities and drawing exact joint samples that runs in O(Dlog2 D) time, and we show how to frame the algorithm as efficient belief propagation in a low order tree-structured model that includes additional auxiliary variables. We then develop a new, more general class of models, termed Recursive Cardinality models, which take advantage of this efficiency. Finally, we show how to do efficient exact inference in models composed of a tree structure and a cardinality potential. We explore the expressive power of Recursive Cardinality models and empirically demonstrate their utility.


title: Probability and Asset Updating using Bayesian Networks for Combinatorial Prediction Markets

abstract: A market-maker-based prediction market lets forecasters aggregate information by editing a consensus probability distribution either directly or by trading securities that pay off contingent on an event of interest. Combinatorial prediction markets allow trading on any event that can be specified as a combination of a base set of events. However, explicitly representing the full joint distribution is infeasible for markets with more than a few base events. A factored representation such as a Bayesian network (BN) can achieve tractable computation for problems with many related variables. Standard BN inference algorithms, such as the junction tree algorithm, can be used to update a representation of the entire joint distribution given a change to any local conditional probability. However, in order to let traders reuse assets from prior trades while never allowing assets to become negative, a BN based prediction market also needs to update a representation of each user's assets and find the conditional state in which a user has minimum assets. Users also find it useful to see their expected assets given an edit outcome. We show how to generalize the junction tree algorithm to perform all these computations.


title: An Approximate Solution Method for Large Risk-Averse Markov Decision Processes

abstract: Stochastic domains often involve risk-averse decision makers. While recent work has focused on how to model risk in Markov decision processes using risk measures, it has not addressed the problem of solving large risk-averse formulations. In this paper, we propose and analyze a new method for solving large risk-averse MDPs with hybrid continuous-discrete state spaces and continuous action spaces. The proposed method iteratively improves a bound on the value function using a linearity structure of the MDP. We demonstrate the utility and properties of the method on a portfolio optimization problem.


title: Efficiently Searching for Frustrated Cycles in MAP Inference

abstract: Dual decomposition provides a tractable framework for designing algorithms for finding the most probable (MAP) configuration in graphical models. However, for many real-world inference problems, the typical decomposition has a large integrality gap, due to frustrated cycles. One way to tighten the relaxation is to introduce additional constraints that explicitly enforce cycle consistency. Earlier work showed that cluster-pursuit algorithms, which iteratively introduce cycle and other higherorder consistency constraints, allows one to exactly solve many hard inference problems. However, these algorithms explicitly enumerate a candidate set of clusters, limiting them to triplets or other short cycles. We solve the search problem for cycle constraints, giving a nearly linear time algorithm for finding the most frustrated cycle of arbitrary length. We show how to use this search algorithm together with the dual decomposition framework and clusterpursuit. The new algorithm exactly solves MAP inference problems arising from relational classification and stereo vision.


title: Detecting Change-Points in Time Series by Maximum Mean Discrepancy of Ordinal Pattern Distributions

abstract: As a new method for detecting change-points in high-resolution time series, we apply Maximum Mean Discrepancy to the distributions of ordinal patterns in different parts of a time series. The main advantage of this approach is its computational simplicity and robustness with respect to (non-linear) monotonic transformations, which makes it particularly well-suited for the analysis of long biophysical time series where the exact calibration of measurement devices is unknown or varies with time. We establish consistency of the method and evaluate its performance in simulation studies. Furthermore, we demonstrate the application to the analysis of electroencephalography (EEG) and electrocardiography (ECG) recordings.


title: Spectrum Identification using a Dynamic Bayesian Network Model of Tandem Mass Spectra

abstract: Shotgun proteomics is a high-throughput technology used to identify unknown proteins in a complex mixture. At the heart of this process is a prediction task, the spectrum identification problem, in which each fragmentation spectrum produced by a shotgun proteomics experiment must be mapped to the peptide (protein subsequence) which generated the spectrum. We propose a new algorithm for spectrum identification, based on dynamic Bayesian networks, which significantly outperforms the de-facto standard tools for this task: SEQUEST and Mascot.


title: Latent Composite Likelihood Learning for the Structured Canonical Correlation Model

abstract: Latent variable models are used to estimate variables of interest quantities which are observable only up to some measurement error. In many studies, such variables are known but not precisely quantifiable (such as "job satisfaction" in social sciences and marketing, "analytical ability" in educational testing, or "inflation" in economics). This leads to the development of measurement instruments to record noisy indirect evidence for such unobserved variables such as surveys, tests and price indexes. In such problems, there are postulated latent variables and a given measurement model. At the same time, other unantecipated latent variables can add further unmeasured confounding to the observed variables. The problem is how to deal with unantecipated latents variables. In this paper, we provide a method loosely inspired by canonical correlation that makes use of background information concerning the "known" latent variables. Given a partially specified structure, it provides a structure learning approach to detect "unknown unknowns," the confounding effect of potentially infinitely many other latent variables. This is done without explicitly modeling such extra latent factors. Because of the special structure of the problem, we are able to exploit a new variation of composite likelihood fitting to efficiently learn this structure. Validation is provided with experiments in synthetic data and the analysis of a large survey done with a sample of over 100,000 staff members of the National Health Service of the United Kingdom.


title: Efficient MRF Energy Minimization via Adaptive Diminishing Smoothing

abstract: We consider the linear programming relaxation of an energy minimization problem for Markov Random Fields. The dual objective of this problem can be treated as a concave and unconstrained, but non-smooth function. The idea of smoothing the objective prior to optimization was recently proposed in a series of papers. Some of them suggested the idea to decrease the amount of smoothing (so called temperature) while getting closer to the optimum. However, no theoretical substantiation was provided. We propose an adaptive smoothing diminishing algorithm based on the duality gap between relaxed primal and dual objectives and demonstrate the efficiency of our approach with a smoothed version of Sequential Tree-Reweighted Message Passing (TRW-S) algorithm. The strategy is applicable to other algorithms as well, avoids adhoc tuning of the smoothing during iterations, and provably guarantees convergence to the optimum.


title: From imprecise probability assessments to conditional probabilities with quasi additive classes of conditioning events

abstract: In this paper, starting from a generalized coherent (i.e. avoiding uniform loss) intervalvalued probability assessment on a finite family of conditional events, we construct conditional probabilities with quasi additive classes of conditioning events which are consistent with the given initial assessment. Quasi additivity assures coherence for the obtained conditional probabilities. In order to reach our goal we define a finite sequence of conditional probabilities by exploiting some theoretical results on g-coherence. In particular, we use solutions of a finite sequence of linear systems.


title: Integrated Nested Laplace Approximation for Bayesian Nonparametric Phylodynamics

abstract: The goal of phylodynamics, an area on the intersection of phylogenetics and population genetics, is to reconstruct population size dynamics from genetic data. Recently, a series of nonparametric Bayesian methods have been proposed for such demographic reconstructions. These methods rely on prior specifications based on Gaussian processes and proceed by approximating the posterior distribution of population size trajectories via Markov chain Monte Carlo (MCMC) methods. In this paper, we adapt an integrated nested Laplace approximation (INLA), a recently proposed approximate Bayesian inference for latent Gaussian models, to the estimation of population size trajectories. We show that when a genealogy of sampled individuals can be reliably estimated from genetic data, INLA enjoys high accuracy and can replace MCMC entirely. We demonstrate significant computational efficiency over the state-of-the-art MCMC methods. We illustrate INLA-based population size inference using simulations and genealogies of hepatitis C and human influenza viruses.


title: Active Learning with Distributional Estimates

abstract: Active Learning (AL) is increasingly important in a broad range of applications. Two main AL principles to obtain accurate classification with few labeled data are refinement of the current decision boundary and exploration of poorly sampled regions. In this paper we derive a novel AL scheme that balances these two principles in a natural way. In contrast to many AL strategies, which are based on an estimated class conditional probability ^p(y|x), a key component of our approach is to view this quantity as a random variable, hence explicitly considering the uncertainty in its estimated value. Our main contribution is a novel mathematical framework for uncertainty-based AL, and a corresponding AL scheme, where the uncertainty in ^p(y|x) is modeled by a second-order distribution. On the practical side, we show how to approximate such second-order distributions for kernel density classification. Finally, we find that over a large number of UCI, USPS and Caltech4 datasets, our AL scheme achieves significantly better learning curves than popular AL methods such as uncertainty sampling and error reduction sampling, when all use the same kernel density classifier.


title: New Advances and Theoretical Insights into EDML

abstract: EDML is a recently proposed algorithm for learning MAP parameters in Bayesian networks. In this paper, we present a number of new advances and insights on the EDML algorithm. First, we provide the multivalued extension of EDML, originally proposed for Bayesian networks over binary variables. Next, we identify a simplified characterization of EDML that further implies a simple fixed-point algorithm for the convex optimization problem that underlies it. This characterization further reveals a connection between EDML and EM: a fixed point of EDML is a fixed point of EM, and vice versa. We thus identify also a new characterization of EM fixed points, but in the semantics of EDML. Finally, we propose a hybrid EDML/EM algorithm that takes advantage of the improved empirical convergence behavior of EDML, while maintaining the monotonic improvement property of EM.


title: Multi-objective Influence Diagrams

abstract: We describe multi-objective influence diagrams, based on a set of p objectives, where utility values are vectors in Rp, and are typically only partially ordered. These can still be solved by a variable elimination algorithm, leading to a set of maximal values of expected utility. If the Pareto ordering is used this set can often be prohibitively large. We consider approximate representations of the Pareto set based on e-coverings, allowing much larger problems to be solved. In addition, we define a method for incorporating user tradeoffs, which also greatly improves the efficiency.


title: FHHOP: A Factored Hybrid Heuristic Online Planning Algorithm for Large POMDPs

abstract: Planning in partially observable Markov decision processes (POMDPs) remains a challenging topic in the artificial intelligence community, in spite of recent impressive progress in approximation techniques. Previous research has indicated that online planning approaches are promising in handling large-scale POMDP domains efficiently as they make decisions "on demand" instead of proactively for the entire state space. We present a Factored Hybrid Heuristic Online Planning (FHHOP) algorithm for large POMDPs. FHHOP gets its power by combining a novel hybrid heuristic search strategy with a recently developed factored state representation. On several benchmark problems, FHHOP substantially outperformed state-of-the-art online heuristic search approaches in terms of both scalability and quality.


title: An Improved Admissible Heuristic for Learning Optimal Bayesian Networks

abstract: Recently two search algorithms, A* and breadth-first branch and bound (BFBnB), were developed based on a simple admissible heuristic for learning Bayesian network structures that optimize a scoring function. The heuristic represents a relaxation of the learning problem such that each variable chooses optimal parents independently. As a result, the heuristic may contain many directed cycles and result in a loose bound. This paper introduces an improved admissible heuristic that tries to avoid directed cycles within small groups of variables. A sparse representation is also introduced to store only the unique optimal parent choices. Empirical results show that the new techniques significantly improved the efficiency and scalability of A* and BFBnB on most of datasets tested in this paper.


title: Latent Structured Ranking

abstract: Many latent (factorized) models have been proposed for recommendation tasks like collaborative filtering and for ranking tasks like document or image retrieval and annotation. Common to all those methods is that during inference the items are scored independently by their similarity to the query in the latent embedding space. The structure of the ranked list (i.e. considering the set of items returned as a whole) is not taken into account. This can be a problem because the set of top predictions can be either too diverse (contain results that contradict each other) or are not diverse enough. In this paper we introduce a method for learning latent structured rankings that improves over existing methods by providing the right blend of predictions at the top of the ranked list. Particular emphasis is put on making this method scalable. Empirical results on large scale image annotation and music recommendation tasks show improvements over existing approaches.


title: Self-Confirming Price Prediction Strategies for Simultaneous One-Shot Auctions

abstract: Bidding in simultaneous auctions is challenging because an agent's value for a good in one auction may depend on the uncertain outcome of other auctions: the so-called exposure problem. Given the gap in understanding of general simultaneous auction games, previous works have tackled this problem with heuristic strategies that employ probabilistic price predictions. We define a concept of self-confirming prices, and show that within an independent private value model, Bayes-Nash equilibrium can be fully characterized as a profile of optimal price prediction strategies with self-confirming predictions. We exhibit practical procedures to compute approximately optimal bids given a probabilistic price prediction, and near self-confirming price predictions given a price-prediction strategy. An extensive empirical game-theoretic analysis demonstrates that self-confirming price prediction strategies are effective in simultaneous auction games with both complementary and substitutable preference structures.


title: A Cluster-Cumulant Expansion at the Fixed Points of Belief Propagation

abstract: We introduce a new cluster-cumulant expansion (CCE) based on the fixed points of iterative belief propagation (IBP). This expansion is similar in spirit to the loop-series (LS) recently introduced in [1]. However, in contrast to the latter, the CCE enjoys the following important qualities: 1) it is defined for arbitrary state spaces 2) it is easily extended to fixed points of generalized belief propagation (GBP), 3) disconnected groups of variables will not contribute to the CCE and 4) the accuracy of the expansion empirically improves upon that of the LS. The CCE is based on the same M\"obius transform as the Kikuchi approximation, but unlike GBP does not require storing the beliefs of the GBP-clusters nor does it suffer from convergence issues during belief updating.


title: Fast Graph Construction Using Auction Algorithm

abstract: In practical machine learning systems, graph based data representation has been widely used in various learning paradigms, ranging from unsupervised clustering to supervised classification. Besides those applications with natural graph or network structure data, such as social network analysis and relational learning, many other applications often involve a critical step in converting data vectors to an adjacency graph. In particular, a sparse subgraph extracted from the original graph is often required due to both theoretic and practical needs. Previous study clearly shows that the performance of different learning algorithms, e.g., clustering and classification, benefits from such sparse subgraphs with balanced node connectivity. However, the existing graph construction methods are either computationally expensive or with unsatisfactory performance. In this paper, we utilize a scalable method called auction algorithm and its parallel extension to recover a sparse yet nearly balanced subgraph with significantly reduced computational cost. Empirical study and comparison with the state-ofart approaches clearly demonstrate the superiority of the proposed method in both efficiency and accuracy.


title: Dynamic Teaching in Sequential Decision Making Environments

abstract: We describe theoretical bounds and a practical algorithm for teaching a model by demonstration in a sequential decision making environment. Unlike previous efforts that have optimized learners that watch a teacher demonstrate a static policy, we focus on the teacher as a decision maker who can dynamically choose different policies to teach different parts of the environment. We develop several teaching frameworks based on previously defined supervised protocols, such as Teaching Dimension, extending them to handle noise and sequences of inputs encountered in an MDP.We provide theoretical bounds on the learnability of several important model classes in this setting and suggest a practical algorithm for dynamic teaching.


title: Latent Dirichlet Allocation Uncovers Spectral Characteristics of Drought Stressed Plants

abstract: Understanding the adaptation process of plants to drought stress is essential in improving management practices, breeding strategies as well as engineering viable crops for a sustainable agriculture in the coming decades. Hyper-spectral imaging provides a particularly promising approach to gain such understanding since it allows to discover non-destructively spectral characteristics of plants governed primarily by scattering and absorption characteristics of the leaf internal structure and biochemical constituents. Several drought stress indices have been derived using hyper-spectral imaging. However, they are typically based on few hyper-spectral images only, rely on interpretations of experts, and consider few wavelengths only. In this study, we present the first data-driven approach to discovering spectral drought stress indices, treating it as an unsupervised labeling problem at massive scale. To make use of short range dependencies of spectral wavelengths, we develop an online variational Bayes algorithm for latent Dirichlet allocation with convolved Dirichlet regularizer. This approach scales to massive datasets and, hence, provides a more objective complement to plant physiological practices. The spectral topics found conform to plant physiological knowledge and can be computed in a fraction of the time compared to existing LDA approaches.


title: Factorized Multi-Modal Topic Model

abstract: Multi-modal data collections, such as corpora of paired images and text snippets, require analysis methods beyond single-view component and topic models. For continuous observations the current dominant approach is based on extensions of canonical correlation analysis, factorizing the variation into components shared by the different modalities and those private to each of them. For count data, multiple variants of topic models attempting to tie the modalities together have been presented. All of these, however, lack the ability to learn components private to one modality, and consequently will try to force dependencies even between minimally correlating modalities. In this work we combine the two approaches by presenting a novel HDP-based topic model that automatically learns both shared and private topics. The model is shown to be especially useful for querying the contents of one domain given samples of the other.


title: Perspectives on Core-Collapse Supernova Theory

abstract: Core-collapse theory brings together many facets of high-energy and nuclear astrophysics and the numerical arts to present theorists with one of the most important, yet frustrating, astronomical questions: "What is the mechanism of core-collapse supernova explosions?" A review of all the physics and the fifty-year history involved would soon bury the reader in minutiae that could easily obscure the essential elements of the phenomenon, as we understand it today. Moreover, much remains to be discovered and explained, and a complicated review of an unresolved subject in flux could grow stale fast. Therefore, in this paper I describe what I think are various important facts and perspectives that may have escaped the attention of those interested in this puzzle. Furthermore, I attempt to describe the modern theory's physical underpinnings and briefly summarize the current state of play. In the process, I identify a few myths (as I see them) that have crept into modern discourse. However, there is much more to do and humility in the face of this age-old challenge is clearly the most prudent stance as we seek its eventual resolution.


title: The 2HDM-X and Large Hadron Collider Data

abstract: We study the consistency of two Higgs doublet models in light of the new bosonic particle discovery at the LHC. We work within a general setup that we call the 2HDM-X, in which the quarks couple to both scalar doublets with aligned couplings such that flavor-changing neutral currents are absent at tree level. The 2HDM-X encompasses the traditional Type I, Type II, lepton specific, and flipped models, but also provides for more general possibilities. The best fit to the current data with a suppressed tau tau signal and a b bbar signal of Standard Model strength is given by the 2HDM-X with specific parameter choices; however, very good fits are also obtained within the lepton-specific model and a democratic model, the 2HDM-D, in which both the up-type and down-type quarks couple to each doublet with equal strengths. The approach provides a general framework in which to interpret future LHC Higgs data within extensions of the Standard Model with two Higgs doublets.


title: Topology and symmetry breaking in ABC trilayer graphene

abstract: The effects of topology and electron-electron interactions on the phase diagram of ABC stacked trilayer graphene (TLG) at the neutrality point are investigated within a weak coupling renormalization group approach. We find that the leading instability of TLG with only a forward scattering density-density interaction is towards a mirror-breaking gapless state. Addition of a small, but finite back scattering favors gapped phases, allowing us to make connections to the existing experiments on TLG. We identify a fundamental symmetry difference between TLG and bilayer graphene (BLG) which is responsible for disfavoring nematic states in TLG under the same conditions that favor nematic states in BLG.


title: Accretion disk parameters in HLX-1

abstract: We estimate the outer radius of the accretion disk in HLX-1 from its optical brightness and from the exponential timescale of the decline in the X-ray lightcurve after an outburst. We find that the disk is an order of magnitude smaller than the semimajor axis of the orbit. If the disk size is determined by the circularization radius near periastron, the eccentricity of the binary system must be >~ 0.95. We report on the discovery of H-alpha emission during the 2012 outburst, with a single-peaked, narrow profile (consistent with a nearly face-on view), and a central velocity displaced by ~490 km/s from that of the host galaxy.


title: N=8 SYM vs. N=6 Chern-Simons: Four-point amplitudes at two-loops

abstract: We compute the four-point amplitude in 3d N=8 SYM at two loops, by solving the three dimensional scalar doublebox in dimensional regularization. We compare it to the same result in the ABJM theory, to which maximal SYM should flow in the infrared at strong coupling. After proper rescalings, we find that the two amplitudes coincide in the Regge limit.


title: Impurity model for non-equilibrium steady states

abstract: We propose an out-of-equilibrium impurity model for the dynamical mean-field description of the Hubbard model driven by a finite electric field. The out-of-equilibrium impurity environment is represented by a collection of equilibrium reservoirs at different chemical potentials. We discuss the validity of the impurity model and propose a non-perturbative method, based on a quantum Monte Carlo solver, which provides the steady-state solutions of the impurity and original lattice problems. We discuss the relevance of this approach to other non-equilibrium steady-state contexts.


title: SHAM Beyond Clustering: New Tests of Galaxy-Halo Abundance Matching with Galaxy Groups

abstract: We construct mock catalogs of galaxy groups using subhalo abundance matching (SHAM) and undertake several new tests of the SHAM prescription for the galaxy-dark matter connection. All SHAM models we studied exhibit significant tension with galaxy groups observed in the Sloan Digital Sky Survey (SDSS). The SHAM prediction for the field galaxy luminosity function (LF) is systematically too dim, and the group galaxy LF systematically too bright, regardless of the details of the SHAM prescription. SHAM models connecting r-band luminosity, Mr, to Vacc, the maximum circular velocity of a subhalo at the time of accretion onto the host, faithfully reproduce galaxy group abundance as a function of richness, g(N). However, SHAM models connecting Mr with Vpeak, the peak value of Vmax over the entire merger history of the halo, over-predict galaxy group abundance. Our results suggest that no SHAM model can simultaneously reproduce the observed g(N) and two-point projected galaxy clustering. Nevertheless, we also report a new success of SHAM: an accurate prediction for Phi(m12), the abundance of galaxy groups as a function of magnitude gap m12, defined as the difference between the r-band absolute magnitude of the two brightest group members. We show that it may be possible to use joint measurements of g(N) and Phi(m12) to tightly constrain the details of the SHAM implementation. Additionally, we show that the hypothesis that the luminosity gap is constructed via random draws from a universal LF provides a poor description of the data, contradicting recent claims in the literature. Finally, we test a common assumption of the Conditional Luminosity Function (CLF) formalism, that the satellite LF need only be conditioned by the brightness of the central galaxy. We find this assumption to be well-supported by the observed Phi(m12).


title: A Redshift Survey of Herschel Far-Infrared Selected Starbursts and Implications for Obscured Star Formation

abstract: We present Keck spectroscopic observations and redshifts for a sample of 767 Herschel-SPIRE selected galaxies (HSGs) at 250, 350, and 500um, taken with the Keck I Low Resolution Imaging Spectrometer (LRIS) and the Keck II DEep Imaging Multi-Object Spectrograph (DEIMOS). The redshift distribution of these SPIRE sources from the Herschel Multitiered Extragalactic Survey (HerMES) peaks at z=0.85, with 731 sources at z<2 and a tail of sources out to z~5. We measure more significant disagreement between photometric and spectroscopic redshifts (<delta_z>/(1+z)>=0.29) than is seen in non-infrared selected samples, likely due to enhanced star formation rates and dust obscuration in infrared-selected galaxies. We estimate that the vast majority (72-83%) of z<2 Herschel-selected galaxies would drop out of traditional submillimeter surveys at 0.85-1mm. We estimate the luminosity function and implied star-formation rate density contribution of HSGs at z<1.6 and find overall agreement with work based on 24um extrapolations of the LIRG, ULIRG and total infrared contributions. This work significantly increased the number of spectroscopically confirmed infrared-luminous galaxies at z>>0 and demonstrates the growing importance of dusty starbursts for galaxy evolution studies and the build-up of stellar mass throughout cosmic time. [abridged]


title: Broken and unbroken: the Milky Way and M31 stellar haloes

abstract: We use the Bullock & Johnston suite of simulations to study the density profiles of L*-type galaxy stellar haloes. Observations of the Milky Way and M31 stellar haloes show contrasting results: the Milky Way has a `broken' profile, where the density falls off more rapidly beyond ~ 25 kpc, while M31 has a smooth profile out to 100 kpc with no obvious break. Simulated stellar haloes, built solely by the accretion of dwarf galaxies, also exhibit this behavior: some haloes have breaks, while others don't. The presence or absence of a break in the stellar halo profile can be related to the accretion history of the galaxy. We find that a break radius is strongly related to the build up of stars at apocentres. We relate these findings to observations, and find that the `break' in the Milky Way density profile is likely associated with a relatively early (~ 6-9 Gyr ago) and massive accretion event. In contrast, the absence of a break in the M31 stellar halo profile suggests that its accreted satellites have a wide range of apocentres. Hence, it is likely that M31 has had a much more prolonged accretion history than the Milky Way.


title: Worldwide site comparison for submillimetre astronomy

abstract: The most important limitation for ground-based submillimetre (submm) astronomy is the broad-band absorption of the total water vapour in the atmosphere above an observation site, often expressed as the Precipitable Water Vapour (PWV). A long-term statistic on the PWV is thus mandatory to characterize the quality of an existing or potential site for observational submm-astronomy. In this study we present a three-year statistic (2008-2010) of the PWV for ground-based telescope sites all around the world and for stratospheric altitudes relevant for SOFIA (Stratospheric Observatory for Far-infrared astronomy). The submm-transmission is calculated for typical PWVs using an atmospheric model. We present the absolute PWV values for each site sorted by year and time percentage. The PWV corresponding to the first decile (10%) and the quartiles (25%, 50%, 75%) are calculated and transmission curves between 150 {\mu}m and 3 mm for these values are shown. The Antarctic and South-American sites present very good conditions for submillimetre astronomy. The 350 {\mu}m and 450 {\mu}m atmospheric windows are open all year long whereas the 200 {\mu}m atmospheric window opens reasonably for 25 % of the time in Antarctica and the extremely high-altitude sites in Chile. Potential interesting new facilities are Macon in Argentinia and Summit in Greenland that show similar conditions as for example Mauna Kea (Hawaii). For SOFIA, we present in more detail transmission curves for different altitudes (11 to 14 km), PWV values, and higher frequencies (up to 5 THz). Though the atmosphere at these altitude is generally very transparent, the absorption at very high frequencies becomes more important, partly caused by minor species. In conclusion, the method presented in this paper could identify sites on Earth with a great potential for submillimetre astronomy, and guide future site testing campaigns in situ.


title: Efficient Wiener filtering without preconditioning

abstract: We present a new approach to calculate the Wiener filter solution of general data sets. It is trivial to implement, flexible, numerically absolutely stable, and guaranteed to converge. Most importantly, it does not require an ingenious choice of preconditioner to work well. The method is capable of taking into account inhomogeneous noise distributions and arbitrary mask geometries. It iteratively builds up the signal reconstruction by means of a messenger field, introduced to mediate between the different preferred bases in which signal and noise properties can be specified most conveniently. Using cosmic microwave background (CMB) radiation data as a showcase, we demonstrate the capabilities of our scheme by computing Wiener filtered WMAP7 temperature and polarization maps at full resolution for the first time. We show how the algorithm can be modified to synthesize fluctuation maps, which, combined with the Wiener filter solution, result in unbiased constrained signal realizations, consistent with the observations. The algorithm performs well even on simulated CMB maps with Planck resolution and dynamic range.


title: A Population of z>2 Far-Infrared Herschel-SPIRE selected Starbursts

abstract: We present spectroscopic observations for a sample of 36 Herschel-SPIRE 250-500um selected galaxies (HSGs) at 2<z<5 from the Herschel Multi-tiered Extragalactic Survey (HerMES). Redshifts are confirmed as part of a large redshift survey of Herschel-SPIRE-selected sources covering ~0.93deg^2 in six extragalactic legacy fields. Observations were taken with the Keck I Low Resolution Imaging Spectrometer (LRIS) and the Keck II DEep Imaging Multi-Object Spectrograph (DEIMOS). Precise astrometry, needed for spectroscopic follow-up, is determined by identification of counterparts at 24um or 1.4GHz using a cross-identification likelihood matching method. Individual source luminosities range from log(L_IR/Lsun)=12.5-13.6 (corresponding to star formation rates 500-9000Msun/yr, assuming a Salpeter IMF), constituting some of the most intrinsically luminous, distant infrared galaxies yet discovered. We present both individual and composite rest-frame ultraviolet spectra and infrared spectral energy distributions (SEDs). The selection of these HSGs is reproducible and well characterized across large areas of sky in contrast to most z>2 HyLIRGs in the literature which are detected serendipitously or via tailored surveys searching only for high-z HyLIRGs; therefore, we can place lower limits on the contribution of HSGs to the cosmic star formation rate density at (7+-2)x10^(-3)Msun/yr h^3Mpc^(-3) at z~2.5, which is >10% of the estimated total star formation rate density (SFRD) of the Universe from optical surveys. The contribution at z~4 has a lower limit of 3x10^(-3)Msun/yr h^3 Mpc^(-3), ~>20% of the estimated total SFRD. This highlights the importance of extremely infrared-luminous galaxies with high star formation rates to the build-up of stellar mass, even at the earliest epochs.


title: A Ly-alpha Emitter with an Extremely Large Rest-frame Equivalent Width of ~900A at z=6.5: A Candidate of Population III-dominated Galaxy?

abstract: We have identified a very interesting Ly-alpha emitter, whose Ly-alpha emission line has an extremely large observed equivalent width of EW_0=436^{+422}_{-149}A, which corresponds to an extraordinarily large intrinsic rest-frame equivalent width of EW_0^{int}=872^{+844}_{-298}A after the average intergalactic absorption correction. The object was spectroscopically confirmed to be a real Ly-alpha emitter by its apparent asymmetric Ly-alpha line profile detected at z=6.538. The continuum emission of the object was definitely detected in our deep z'-band image; thus, its EW_0 was reliably determined. Follow-up deep near-infrared spectroscopy revealed emission lines of neither He II lambda1640 as an apparent signature of Population III, nor C IV lambda1549 as a proof of active nucleus. No detection of short-lived He II lambda1640 line is not necessarily inconsistent with the interpretation that the underlying stellar population of the object is dominated by Population III. We found that the observed extremely large EW_0 of the Ly-alpha emission and the upper limit on the EW_0 of the He II lambda1640 emission can be explained by population synthesis models favoring a very young age less than 2-4Myr and massive metal-poor (Z<10^{-5}) or even metal-free stars. The observed large EW_0 of Ly-alpha is hardly explained by Population I/II synthesis models with Z>10^{-3}. However, we cannot conclusively rule out the possibility that this object is composed of a normal stellar population with a clumpy dust distribution, which could enhance the Ly-alpha EW_0, though its significance is still unclear.


title: Where are the Fermi Lines Coming From?

abstract: We estimate the spatial locations of sources of the the observed features in the Fermi-LAT photon spectrum at $E_\gamma=110$ and $E_\gamma=130$ GeV. We determine whether they are consistent with emission from a single source, as would be expected in their interpretation as $\gamma\gamma$ and $\gamma Z$ lines from dark matter annhiliation, as well as whether they are consistent with a dark matter halo positioned at the center of the galaxy. We take advantage of the per-photon measured incident angle in reconstructing the line features. In addition, we use a data-driven background model rather than making the assumption of a feature-less background. We localize the sources of the features at 110 and 130 GeV. Assuming an Einasto (NFW) density model we find the 130 GeV line to be offset from the galactic center by 285 (280) pc, the 110 GeV line by 60 (30) pc with a large relative separation of 220 (240) pc. However, we find this displacement of each source from the galactic center, as well as their relative displacement to be statistically consistent with a single Einasto or NFW dark matter halo at the center of the galaxy.


title: Holography for General Gauge Mediation

abstract: We construct a holographic model of spontaneous supersymmetry breaking in analogy to AdS/QCD models. Integrating out the bulk theory one obtains an entirely four dimensional effective action that encodes spontaneous supersymmetry breaking effects, coupled to external sources. Using only this four dimensional action it is possible to compute soft masses, scattering cross sections and determine the form factors of vector mesons. This construction lends itself to a more natural comparison with operator product expansions.


title: R-symmetric High Scale Supersymmetry

abstract: Introducing an R-symmetry to models of high scale supersymmetry (SUSY) can have interesting consequences, and we focus on two aspects. If Majorana masses are forbidden by an R-symmetry and the main source of electroweak gaugino masses are Dirac terms, then the Higgs quartic coupling vanishing at the SUSY scale and the Higgs boson mass will be near 125 GeV. Moreover, using an R-symmetry, models with only one Higgs doublet in the UV can be constructed and we argue that, since we desire only a single Higgs at the weak scale, this scenario is more aesthetic than existing models. We subsequently present a model which draws on both of these features. We comment on neutrino masses and dark matter in these scenarios and discuss how the models presented can be discerned from alternative constructions with high scale SUSY, including Split SUSY.


title: From Bi-immunity to Absolute Undecidability

abstract: An infinite binary sequence A is absolutely undecidable if it is impossible to compute A on a set of positions of positive upper density. Absolute undecidability is a weakening of bi-immunity. Downey, Jockusch and Schupp asked whether, unlike the case for bi-immunity, there is an absolutely undecidable set in every non-zero Turing degree. We provide a positive answer to this question by applying techniques from coding theory. We show how to use Walsh-Hadamard codes to build a truth-table functional which maps any sequence A to a sequence B, such that given any restriction of B to a set of positive upper density, one can recover A. This implies that if A is non-computable, then B is absolutely undecidable. Using a forcing construction, we show that this result cannot be strengthened in any significant fashion.


title: Improved proteomic analysis of nuclear proteins, as exemplified by the comparison of two myelo\"id cell lines nuclear proteomes

abstract: One of the challenges of the proteomic analysis by 2D-gel is to visualize the low abundance proteins, particularly those localized in organelles. An additional problem with nuclear proteins lies in their strong interaction with nuclear acids. Several experimental procedures have been tested to increase, in the nuclear extract, the ratio of nuclear proteins compared to contaminant proteins, and also to obtain reproducible conditions compatible with 2D-gel electrophoresis. The NaCl procedure has been chosen. To test the interest of this procedure, the nuclear protein expression profiles of macrophages and dendritic cells have been compared with a proteomic approach by 2D-gel electrophoresis. Delta 2D software and mass spectrometry analyses have allowed pointing out some proteins of interest. We have chosen some of them, involved in transcriptional regulation and/or chromatin structure for further validations. The immunoblotting experiments have shown that most of observed changes are due to post-translational modifications, thereby a exemplifying the interest of the 2D gel approach. Finally, this approach allowed us to reach not only high abundance nuclear proteins but also lower abundance proteins, such as the HP1 proteins and reinforces the interest of using 2DE-gel in proteomics because of its ability to visualize intact proteins with their modifications.


title: Time-fractional and memoryful $\Delta^{2^{k}}$ SIEs on $\Rp\times\Rd$: how far can we push white noise?

abstract: High order and fractional PDEs have become prominent in theory and in modeling many phenomena. Here, we focus on the regularizing effect of a large class of memoryful high-order or time-fractional PDEs---through their fundamental solutions---on stochastic integral equations (SIEs) driven by space-time white noise. Surprisingly, we show that maximum spatial regularity is achieved in the fourth-order-bi-Laplacian case; and any further increase of the spatial-Laplacian order is entirely translated into additional temporal regularization of the SIE. We started this program in (Allouba 2013, Allouba 2006), where we introduced two different stochastic versions of the fourth order memoryful PDE associated with the Brownian-time Brownian motion (BTBM): (1) the BTBM SIE and (2) the BTBM SPDE, both driven by space-time white noise. Under wide conditions, we showed the existence of random field locally-H\"older solutions to the BTBM SIE with striking and unprecedented time-space H\"older exponents, in spatial dimensions $d=1,2,3$. In particular, we proved that the spatial regularity of such solutions is nearly locally Lipschitz in $d=1,2$. This gave, for the first time, an example of a space-time white noise driven equation whose solutions are smoother than the corresponding Brownian sheet in either time or space. In this paper, we introduce the $2\beta^{-1}$-order $\beta$-inverse-stable-L\'evy-time Brownian motion ($\beta$-ISLTBM) SIEs, driven by space-time white noise. We show that the BTBM SIE spatial regularity and its random field third spatial dimension limit are maximal among all $\beta$-ISLTBM SIEs. Furthermore, we show that increasing the order of the Laplacian $\beta^{-1}$ beyond the BTBM bi-Laplacian manifests entirely as increased temporal regularity of our random field solutions that asymptotically approaches the temporal regularity of the Brownian sheet as $\beta\searrow0$.


title: Towards thermodynamics of universal horizons in Einstein-{\ae}ther theory

abstract: Holography grew out of black hole thermodynamics, which relies on the causal structure and general covariance of general relativity. In Einstein-{\ae}ther theory, a generally covariant theory with a dynamical timelike unit vector, every solution breaks local Lorentz invariance, thereby grossly modifying the causal structure of gravity. However, there are still absolute causal boundaries, called "universal horizons", which are not Killing horizons yet obey a first law of black hole mechanics and must have an entropy if they do not violate a generalized second law. We couple a scalar field to the timelike vector and show via the tunneling approach that the universal horizon radiates as a blackbody at a fixed temperature, even if the scalar field equations also violate local Lorentz invariance. This suggests that the class of holographic theories may be much broader than currently assumed.


title: Non-Linear Single Higgs MSSM

abstract: We present a non-linear MSSM with non-standard Higgs sector and goldstino field. Non-linear supersymmetry for the goldstino couplings is described by the constrained chiral superfield and, as usual, the Standard Model sector is encompassed in suitable chiral and vector supermultiplets. Two models are presented. In the first model (non-linear MSSM$3 1/2$), the second Higgs is replaced by a new supermultiplet of half-family with only a new generation of leptons (or quarks). In the second model, for anomaly cancellation purposes, the second Higgs is retained as a spectator superfield by imposing a discrete symmetry. Both models do not have a $\mu$-problem as a $\mu$-term is forbidden by the discrete symmetry in the case of a spectator second Higgs or not existing at all in the case of a single Higgs. Moreover, the tree level relation between the Higgs mass and the hidden sector SUSY breaking scale $\sqrt{f}$ is derived. Finally, we point out a relative suppression by $m_{soft}/\Lambda$ of the bottom and tau Yukawa couplings with respect to those of the top quark.


title: VLBI Observations of the Jet in M87 During the Very-High-Energy Gamma-ray Flare in April 2010

abstract: We report on the detailed radio status of the M87 jet during the Very-High-Energy (VHE) gamma-ray flaring event in April 2010, obtained from high-resolution, multi-frequency, phase-referencing VLBA observations. We especially focus on the properties for the jet base (the radio core) and the peculiar knot HST-1, which are currently favored as the gamma-ray emitting sites. During the VHE flaring event, the HST-1 region remains stable in terms of its structure and flux density in the optically thin regime above 2GHz, being consistent with no signs of enhanced activities reported at X-ray for this feature. The radio core shows an inverted spectrum at least up to 43GHz during this event. Astrometry of the core position, which is specified as ~20Rs from the central engine in our previous study, shows that the core position is stable on a level of 4Rs. The core at 43 and 22GHz tends to show slightly (~10%) higher flux level near the date of the VHE flux peak compared with the epochs before/after the event. The size of the 43-GHz core is estimated to be ~17Rs, which is close to the size of the emitting region suggested from the observed time scale of rapid variability at VHE. These results tend to favor the scenario that the VHE gamma-ray flare in 2010 April is associated with the radio core.


title: Red Galaxies from Hot Halos in Cosmological Hydro Simulations

abstract: I highlight three results from cosmological hydrodynamic simulations that yield a realistic red sequence of galaxies: 1) Major galaxy mergers are not responsible for shutting off star-formation and forming the red sequence. Starvation in hot halos is. 2) Massive galaxies grow substantially (about a factor of 2 in mass) after being quenched, primarily via minor (1:5) mergers. 3) Hot halo quenching naturally explains why galaxies are red when they either (a) are massive or (b) live in dense environments.


title: Field emission mechanism from nanotubes through gas ionization induced nanoscale surface charging

abstract: Experimental evidences reported in this letter show that the gas ionization induced positive charge accumulation can lead to the electron field emission from carbon nanotubes (CNTs) in an electrode system with proper range of gap spacing, where the CNT film with ethocel was covered with ZnO nanorods. The hypothesis for illustration is suggested that: 1) the cosmic ray ionization frequency increases 108~1010 times due to the metastable population resulted from the interaction between the gases and the CNTs; 2) the flux of positive charges is enhanced in the converged field due to the ZnO nanostructures. The resulted positive charge local density is high enough to trigger the field emission of the CNTs. The methodology may be useful in particle detectors and ionization gas sensors.


title: Medium-induced splitting kernels from SCET_G

abstract: Using the framework of soft-collinear effective theory with Glauber gluons ($\SCETG$), we evaluate medium-induced splitting kernels. Because of the power counting of the effective theory, our results are valid for arbitrary, not necessarily small values of the energy fraction $x$ taken by the emitted parton. In this framework we prove the factorization from the hard process and gauge invariance of the splitting kernels, we also show how nuclear recoil and the phase space cuts can be implemented into the phenomenology.


title: Note on the Analytical Solution of the Rabi Model

abstract: It is shown that a recent critique (arXiv:1210.1130 and arXiv:1211.4639) concerning the analytical solution of the Rabi model is unfounded.


title: Rotopulsators of the curved N-body problem

abstract: We consider the N-body problem in spaces of constant curvature and study its rotopulsators, i.e.\ solutions for which the configuration of the bodies rotates and changes size during the motion. Rotopulsators fall naturally into five groups: positive elliptic, positive elliptic-elliptic, negative elliptic, negative hyperbolic, and negative elliptic-hyperbolic, depending on the nature and number of their rotations and on whether they occur in spaces of positive or negative curvature. After obtaining existence criteria for each type of rotopulsator, we derive their conservation laws. We further deal with the existence and uniqueness of some classes of rotopulsators in the 2- and 3-body case and prove two general results about the qualitative behaviour of rotopulsators. More precisely, for positive curvature we show that there is no foliation of the 3-sphere with Clifford tori such that the motion of each body is confined to some Clifford torus. For negative curvature, a similar result is proved relative to foliations of the hyperbolic 3-sphere with hyperbolic cylinders.


title: Plump Cutthroat Trout and Thin Rainbow Trout in a Lentic Ecosystem

abstract: Background: Much has been written about introduced rainbow trout (Oncorhynchus mykiss) interbreeding and outcompeting cutthroat trout (Oncorhynchus clarkii). However, the specific mechanisms by which rainbow trout and their hybrids outcompete cutthroat trout have not been thoroughly explored, and the published data is limited to lotic ecosystems. Materials and Methods: Samples of rainbow trout and cutthroat trout were obtained from a lentic ecosystem by angling. The total length and weight of each fish was measured and the relative weight of each fish was computed (Anderson R.O., Neumann R.M. 1996. Length, Weight, and Associated Structural Indices, Pp. 447-481. In: Murphy B.E. and Willis D.W. (eds.) Fisheries Techniques, second edition. American Fisheries Society.), along with the mean and uncertainty in the mean for each species. Data from an independent source (K.D. Carlander, 1969. Handbook of Freshwater Fishery Biology, Volume One, Iowa University Press, Ames.) was also used to generate mean weight-length curves, as well as 25th and 75th percentile curves for each species to allow further comparison. Results: The mean relative weight of the rainbow trout was 72.5 (+/- 2.1); whereas, the mean relative weight of the cutthroat trout was 101.0 (+/- 4.9). The rainbow trout were thin; 80% weighed below the 25th percentile. The cutthroat trout were plump; 86% weighed above the 75th percentile, and 29% were above the heaviest recorded specimens at a given length in the Carlander (1969) data set. Conclusion: This data casts doubt on the hypothesis that rainbow trout are strong food competitors with cutthroat trout in lentic ecosystems. On the contrary, in the lake under study, the cutthroat trout seem to be outcompeting rainbow trout for the available food.


title: Pseudospectra of Isospectrally Reduced Matrices and Systems

abstract: The isospectral reduction of matrix, which is closely related to its Schur complement, allows to reduce the size of a matrix while maintaining its eigenvalues up to a known set. Here we generalize this procedure by increasing the number of possible ways a matrix can be isospectrally reduced. The reduced matrix has rational functions as entries. We show that the notion of pseudospectrum can be extended to this class of matrices and that the pseudospectrum of a matrix shrinks as the matrix is reduced. Hence the eigenvalues of a reduced matrix are more robust to entry-wise perturbations than the eigenvalues of the original matrix. We also introduce the notion of inverse pseudospectrum (or pseudoresonances), which indicates how stable the poles of a matrix with rational function entries are to certain matrix perturbations. A mass spring system is used to illustrate and give a physical interpretation to both pseudospectra and inverse pseudospectra.


title: On the stability of solutions of the Lichnerowicz-York equation

abstract: We study the stability of solution branches for the Lichnerowicz-York equation at moment of time symmetry with constant unscaled energy density. We prove that the weak-field lower branch of solutions is stable whilst the upper branch of strong-field solutions is unstable. The existence of unstable solutions is interesting since a theorem by Sattinger proves that the sub-super solution monotone iteration method only gives stable solutions.


title: On Gerstenhaber's theorem for spaces of nilpotent matrices over a skew field

abstract: Let K be a skew field, and K_0 be a subfield of the central subfield of K such that K has finite dimension q over K_0. Let V be a K_0-linear subspace of n by n nilpotent matrices with entries in K. We show that the dimension of V is bounded above by q n(n-1)/2, and that equality occurs if and only if V is similar to the space of all n by n strictly upper-triangular matrices over K. This generalizes famous theorems of Gerstenhaber and Serezhkin, which cover the special case K=K_0.


title: Transport of Entanglement

abstract: We consider the propagation of two-photon light in a random medium. We show that the Wigner distribution of the two-photon wave function obeys an equation that is analogous to the radiative transport equation for classical light. Using this result, we predict that the entanglement of a photon pair is destroyed with propagation.


title: Equivalence between indirect controllability and complete controllability for quantum systems

abstract: We consider a control scheme where a quantum system S is put in contact with an auxiliary quantum system A and the control can affect A only, while S is the system of interest. The system S is then controlled indirectly through the interaction with A. Complete controllability of S +A means that every unitary state transformation for the system S +A can be achieved with this scheme. Indirect controllability means that every unitary transformation on the system S can be achieved. We prove in this paper, under appropriate conditions and definitions, that these two notions are equivalent in finite dimension. We use Lie algebraic methods to prove this result.