title: Learning to Order BDD Variables in Verification

abstract: The size and complexity of software and hardware systems have significantly increased in the past years. As a result, it is harder to guarantee their correct behavior. One of the most successful methods for automated verification of finite-state systems is model checking. Most of the current model-checking systems use binary decision diagrams (BDDs) for the representation of the tested model and in the verification process of its properties. Generally, BDDs allow a canonical compact representation of a boolean function (given an order of its variables). The more compact the BDD is, the better performance one gets from the verifier. However, finding an optimal order for a BDD is an NP-complete problem. Therefore, several heuristic methods based on expert knowledge have been developed for variable ordering. We propose an alternative approach in which the variable ordering algorithm gains 'ordering experience' from training models and uses the learned knowledge for finding good orders. Our methodology is based on offline learning of pair precedence classifiers from training models, that is, learning which variable pair permutation is more likely to lead to a good order. For each training model, a number of training sequences are evaluated. Every training model variable pair permutation is then tagged based on its performance on the evaluated orders. The tagged permutations are then passed through a feature extractor and are given as examples to a classifier creation algorithm. Given a model for which an order is requested, the ordering algorithm consults each precedence classifier and constructs a pair precedence table which is used to create the order. Our algorithm was integrated with SMV, which is one of the most widely used verification systems. Preliminary empirical evaluation of our methodology, using real benchmark models, shows performance that is better than random ordering and is competitive with existing algorithms that use expert knowledge. We believe that in sub-domains of models (alu, caches, etc.) our system will prove even more valuable. This is because it features the ability to learn sub-domain knowledge, something that no other ordering algorithm does.


title: Decentralized Supply Chain Formation: A Market Protocol and Competitive Equilibrium Analysis

abstract: Supply chain formation is the process of determining the structure and terms of exchange relationships to enable a multilevel, multiagent production activity. We present a simple model of supply chains, highlighting two characteristic features: hierarchical subtask decomposition, and resource contention. To decentralize the formation process, we introduce a market price system over the resources produced along the chain. In a competitive equilibrium for this system, agents choose locally optimal allocations with respect to prices, and outcomes are optimal overall. To determine prices, we define a market protocol based on distributed, progressive auctions, and myopic, non-strategic agent bidding policies. In the presence of resource contention, this protocol produces better solutions than the greedy protocols common in the artificial intelligence and multiagent systems literature. The protocol often converges to high-value supply chains, and when competitive equilibria exist, typically to approximate competitive equilibria. However, complementarities in agent production technologies can cause the protocol to wastefully allocate inputs to agents that do not produce their outputs. A subsequent decommitment phase recovers a significant fraction of the lost surplus.


title: K-Implementation

abstract: This paper discusses an interested party who wishes to influence the behavior of agents in a game (multi-agent interaction), which is not under his control. The interested party cannot design a new game, cannot enforce agents' behavior, cannot enforce payments by the agents, and cannot prohibit strategies available to the agents. However, he can influence the outcome of the game by committing to non-negative monetary transfers for the different strategy profiles that may be selected by the agents. The interested party assumes that agents are rational in the commonly agreed sense that they do not use dominated strategies. Hence, a certain subset of outcomes is implemented in a given game if by adding non-negative payments, rational players will necessarily produce an outcome in this subset. Obviously, by making sufficiently big payments one can implement any desirable outcome. The question is what is the cost of implementation? In this paper we introduce the notion of k-implementation of a desired set of strategy profiles, where k stands for the amount of payment that need to be actually made in order to implement desirable outcomes. A major point in k-implementation is that monetary offers need not necessarily materialize when following desired behaviors. We define and study k-implementation in the contexts of games with complete and incomplete information. In the latter case we mainly focus on the VCG games. Our setting is later extended to deal with mixed strategies using correlation devices. Together, the paper introduces and studies the implementation of desirable outcomes by a reliable party who cannot modify game rules (i.e. provide protocols), complementing previous work in mechanism design, while making it more applicable to many realistic CS settings.


title: CP-nets: A Tool for Representing and Reasoning withConditional Ceteris Paribus Preference Statements

abstract: Information about user preferences plays a key role in automated decision making. In many domains it is desirable to assess such preferences in a qualitative rather than quantitative way. In this paper, we propose a qualitative graphical representation of preferences that reflects conditional dependence and independence of preference statements under a ceteris paribus (all else being equal) interpretation. Such a representation is often compact and arguably quite natural in many circumstances. We provide a formal semantics for this model, and describe how the structure of the network can be exploited in several inference tasks, such as determining whether one outcome dominates (is preferred to) another, ordering a set outcomes according to the preference relation, and constructing the best outcome subject to available evidence.


title: Complexity Results and Approximation Strategies for MAP Explanations

abstract: MAP is the problem of finding a most probable instantiation of a set of variables given evidence. MAP has always been perceived to be significantly harder than the related problems of computing the probability of a variable instantiation Pr, or the problem of computing the most probable explanation (MPE). This paper investigates the complexity of MAP in Bayesian networks. Specifically, we show that MAP is complete for NP^PP and provide further negative complexity results for algorithms based on variable elimination. We also show that MAP remains hard even when MPE and Pr become easy. For example, we show that MAP is NP-complete when the networks are restricted to polytrees, and even then can not be effectively approximated. Given the difficulty of computing MAP exactly, and the difficulty of approximating MAP while providing useful guarantees on the resulting approximation, we investigate best effort approximations. We introduce a generic MAP approximation framework. We provide two instantiations of the framework; one for networks which are amenable to exact inference Pr, and one for networks for which even exact inference is too hard. This allows MAP approximation on networks that are too complex to even exactly solve the easier problems, Pr and MPE. Experimental results indicate that using these approximation algorithms provides much better solutions than standard techniques, and provide accurate MAP estimates in many cases.


title: Taming Numbers and Durations in the Model Checking Integrated Planning System

abstract: The Model Checking Integrated Planning System (MIPS) is a temporal least commitment heuristic search planner based on a flexible object-oriented workbench architecture. Its design clearly separates explicit and symbolic directed exploration algorithms from the set of on-line and off-line computed estimates and associated data structures. MIPS has shown distinguished performance in the last two international planning competitions. In the last event the description language was extended from pure propositional planning to include numerical state variables, action durations, and plan quality objective functions. Plans were no longer sequences of actions but time-stamped schedules. As a participant of the fully automated track of the competition, MIPS has proven to be a general system; in each track and every benchmark domain it efficiently computed plans of remarkable quality. This article introduces and analyzes the most important algorithmic novelties that were necessary to tackle the new layers of expressiveness in the benchmark problems and to achieve a high level of performance. The extensions include critical path analysis of sequentially generated plans to generate corresponding optimal parallel plans. The linear time algorithm to compute the parallel plan bypasses known NP hardness results for partial ordering by scheduling plans with respect to the set of actions and the imposed precedence relations. The efficiency of this algorithm also allows us to improve the exploration guidance: for each encountered planning state the corresponding approximate sequential plan is scheduled. One major strength of MIPS is its static analysis phase that grounds and simplifies parameterized predicates, functions and operators, that infers knowledge to minimize the state description length, and that detects domain object symmetries. The latter aspect is analyzed in detail. MIPS has been developed to serve as a complete and optimal state space planner, with admissible estimates, exploration engines and branching cuts. In the competition version, however, certain performance compromises had to be made, including floating point arithmetic, weighted heuristic search exploration according to an inadmissible estimate and parameterized optimization.


title: IDL-Expressions: A Formalism for Representing and Parsing Finite Languages in Natural Language Processing

abstract: We propose a formalism for representation of finite languages, referred to as the class of IDL-expressions, which combines concepts that were only considered in isolation in existing formalisms. The suggested applications are in natural language processing, more specifically in surface natural language generation and in machine translation, where a sentence is obtained by first generating a large set of candidate sentences, represented in a compact way, and then by filtering such a set through a parser. We study several formal properties of IDL-expressions and compare this new formalism with more standard ones. We also present a novel parsing algorithm for IDL-expressions and prove a non-trivial upper bound on its time complexity.


title: Effective Dimensions of Hierarchical Latent Class Models

abstract: Hierarchical latent class (HLC) models are tree-structured Bayesian networks where leaf nodes are observed while internal nodes are latent. There are no theoretically well justified model selection criteria for HLC models in particular and Bayesian networks with latent nodes in general. Nonetheless, empirical studies suggest that the BIC score is a reasonable criterion to use in practice for learning HLC models. Empirical studies also suggest that sometimes model selection can be improved if standard model dimension is replaced with effective model dimension in the penalty term of the BIC score. Effective dimensions are difficult to compute. In this paper, we prove a theorem that relates the effective dimension of an HLC model to the effective dimensions of a number of latent class models. The theorem makes it computationally feasible to compute the effective dimensions of large HLC models. The theorem can also be used to compute the effective dimensions of general tree models.


title: Concurrent Auctions Across The Supply Chain

abstract: With the recent technological feasibility of electronic commerce over the Internet, much attention has been given to the design of electronic markets for various types of electronically-tradable goods. Such markets, however, will normally need to function in some relationship with markets for other related goods, usually those downstream or upstream in the supply chain. Thus, for example, an electronic market for rubber tires for trucks will likely need to be strongly influenced by the rubber market as well as by the truck market. In this paper we design protocols for exchange of information between a sequence of markets along a single supply chain. These protocols allow each of these markets to function separately, while the information exchanged ensures efficient global behavior across the supply chain. Each market that forms a link in the supply chain operates as a double auction, where the bids on one side of the double auction come from bidders in the corresponding segment of the industry, and the bids on the other side are synthetically generated by the protocol to express the combined information from all other links in the chain. The double auctions in each of the markets can be of several types, and we study several variants of incentive compatible double auctions, comparing them in terms of their efficiency and of the market revenue.


title: A Personalized System for Conversational Recommendations

abstract: Searching for and making decisions about information is becoming increasingly difficult as the amount of information and number of choices increases. Recommendation systems help users find items of interest of a particular type, such as movies or restaurants, but are still somewhat awkward to use. Our solution is to take advantage of the complementary strengths of personalized recommendation systems and dialogue systems, creating personalized aides. We present a system -- the Adaptive Place Advisor -- that treats item selection as an interactive, conversational process, with the program inquiring about item attributes and the user responding. Individual, long-term user preferences are unobtrusively obtained in the course of normal recommendation dialogues and used to direct future conversations with the same user. We present a novel user model that influences both item search and the questions asked during a conversation. We demonstrate the effectiveness of our system in significantly reducing the time and number of interactions required to find a satisfactory item, as compared to a control group of users interacting with a non-adaptive version of the system.


title: Coherent Integration of Databases by Abductive Logic Programming

abstract: We introduce an abductive method for a coherent integration of independent data-sources. The idea is to compute a list of data-facts that should be inserted to the amalgamated database or retracted from it in order to restore its consistency. This method is implemented by an abductive solver, called Asystem, that applies SLDNFA-resolution on a meta-theory that relates different, possibly contradicting, input databases. We also give a pure model-theoretic analysis of the possible ways to `recover' consistent data from an inconsistent database in terms of those models of the database that exhibit as minimal inconsistent information as reasonably possible. This allows us to characterize the `recovered databases' in terms of the `preferred' (i.e., most consistent) models of the theory. The outcome is an abductive-based application that is sound and complete with respect to a corresponding model-based, preferential semantics, and -- to the best of our knowledge -- is more expressive (thus more general) than any other implementation of coherent integration of databases.


title: Grounded Semantic Composition for Visual Scenes

abstract: We present a visually-grounded language understanding model based on a study of how people verbally describe objects in scenes. The emphasis of the model is on the combination of individual word meanings to produce meanings for complex referring expressions. The model has been implemented, and it is able to understand a broad range of spatial referring expressions. We describe our implementation of word level visually-grounded semantics and their embedding in a compositional parsing framework. The implemented system selects the correct referents in response to natural language expressions for a large percentage of test cases. In an analysis of the system's successes and failures we reveal how visual context influences the semantics of utterances and propose future extensions to the model that take such context into account.


title: Dihadron correlations in PbPb collisions at 2.76 TeV with CMS

abstract: Measurements of charged dihadron DeltaEta-DeltaPhi correlations from the CMS collaboration are presented for PbPb collisions at a center-of-mass energy of 2.76 TeV per nucleon pair over a broad range of pseudorapidity and the full range of azimuthal angle. A significant correlated yield is observed for pairs of particles with small DeltaPhi but large longitudinal separation DeltaEta, commonly known as the "ridge". The ridge persists up to at least |DeltaEta| = 4 and the dependence of the ridge region shape and yield on collision centrality and transverse momentum has been measured. A Fourier analysis of the long-range two-particle correlation is presented and discussed in the context of higher order flow coefficients.


title: Existence of Multiagent Equilibria with Limited Agents

abstract: Multiagent learning is a necessary yet challenging problem as multiagent systems become more prevalent and environments become more dynamic. Much of the groundbreaking work in this area draws on notable results from game theory, in particular, the concept of Nash equilibria. Learners that directly learn an equilibrium obviously rely on their existence. Learners that instead seek to play optimally with respect to the other players also depend upon equilibria since equilibria are fixed points for learning. From another perspective, agents with limitations are real and common. These may be undesired physical limitations as well as self-imposed rational limitations, such as abstraction and approximation techniques, used to make learning tractable. This article explores the interactions of these two important concepts: equilibria and limitations in learning. We introduce the question of whether equilibria continue to exist when agents have limitations. We look at the general effects limitations can have on agent behavior, and define a natural extension of equilibria that accounts for these limitations. Using this formalization, we make three major contributions: (i) a counterexample for the general existence of equilibria with limitations, (ii) sufficient conditions on limitations that preserve their existence, (iii) three general classes of games and limitations that satisfy these conditions. We then present empirical results from a specific multiagent learning algorithm applied to a specific instance of limited agents. These results demonstrate that learning with limitations is feasible, when the conditions outlined by our theoretical analysis hold.


title: Price Prediction in a Trading Agent Competition

abstract: The 2002 Trading Agent Competition (TAC) presented a challenging market game in the domain of travel shopping. One of the pivotal issues in this domain is uncertainty about hotel prices, which have a significant influence on the relative cost of alternative trip schedules. Thus, virtually all participants employ some method for predicting hotel prices. We survey approaches employed in the tournament, finding that agents apply an interesting diversity of techniques, taking into account differing sources of evidence bearing on prices. Based on data provided by entrants on their agents' actual predictions in the TAC-02 finals and semifinals, we analyze the relative efficacy of these approaches. The results show that taking into account game-specific information about flight prices is a major distinguishing factor. Machine learning methods effectively induce the relationship between flight and hotel prices from game data, and a purely analytical approach based on competitive equilibrium analysis achieves equal accuracy with no historical data. Employing a new measure of prediction quality, we relate absolute accuracy to bottom-line performance in the game.


title: Compositional Model Repositories via Dynamic Constraint Satisfaction with Order-of-Magnitude Preferences

abstract: The predominant knowledge-based approach to automated model construction, compositional modelling, employs a set of models of particular functional components. Its inference mechanism takes a scenario describing the constituent interacting components of a system and translates it into a useful mathematical model. This paper presents a novel compositional modelling approach aimed at building model repositories. It furthers the field in two respects. Firstly, it expands the application domain of compositional modelling to systems that can not be easily described in terms of interacting functional components, such as ecological systems. Secondly, it enables the incorporation of user preferences into the model selection process. These features are achieved by casting the compositional modelling problem as an activity-based dynamic preference constraint satisfaction problem, where the dynamic constraints describe the restrictions imposed over the composition of partial models and the preferences correspond to those of the user of the automated modeller. In addition, the preference levels are represented through the use of symbolic values that differ in orders of magnitude.


title: Can We Learn to Beat the Best Stock

abstract: A novel algorithm for actively trading stocks is presented. While traditional expert advice and "universal" algorithms (as well as standard technical trading heuristics) attempt to predict winners or trends, our approach relies on predictable statistical relations between all pairs of stocks in the market. Our empirical results on historical markets provide strong evidence that this type of technical trading can "beat the market" and moreover, can beat the best stock in the market. In doing so we utilize a new idea for smoothing critical parameters in the context of expert learning.


title: Competitive Coevolution through Evolutionary Complexification

abstract: Two major goals in machine learning are the discovery and improvement of solutions to complex problems. In this paper, we argue that complexification, i.e. the incremental elaboration of solutions through adding new structure, achieves both these goals. We demonstrate the power of complexification through the NeuroEvolution of Augmenting Topologies (NEAT) method, which evolves increasingly complex neural network architectures. NEAT is applied to an open-ended coevolutionary robot duel domain where robot controllers compete head to head. Because the robot duel domain supports a wide range of strategies, and because coevolution benefits from an escalating arms race, it serves as a suitable testbed for studying complexification. When compared to the evolution of networks with fixed structure, complexifying evolution discovers significantly more sophisticated strategies. The results suggest that in order to discover and improve complex solutions, evolution, and search in general, should be allowed to complexify as well as optimize.


title: Dual Modelling of Permutation and Injection Problems

abstract: When writing a constraint program, we have to choose which variables should be the decision variables, and how to represent the constraints on these variables. In many cases, there is considerable choice for the decision variables. Consider, for example, permutation problems in which we have as many values as variables, and each variable takes an unique value. In such problems, we can choose between a primal and a dual viewpoint. In the dual viewpoint, each dual variable represents one of the primal values, whilst each dual value represents one of the primal variables. Alternatively, by means of channelling constraints to link the primal and dual variables, we can have a combined model with both sets of variables. In this paper, we perform an extensive theoretical and empirical study of such primal, dual and combined models for two classes of problems: permutation problems and injection problems. Our results show that it often be advantageous to use multiple viewpoints, and to have constraints which channel between them to maintain consistency. They also illustrate a general methodology for comparing different constraint models.


title: An observation on the Tur\'an-Nazarov inequality

abstract: The main observation of this note is that the Lebesgue measure $\mu$ in the Tur\'an-Nazarov inequality for exponential polynomials can be replaced with a certain geometric invariant $\omega \ge \mu$, which can be effectively estimated in terms of the metric entropy of a set, and may be nonzero for discrete and even finite sets. While the frequencies (the imaginary parts of the exponents) do not enter in the original Tur\'an-Nazarov inequality, they necessarily enter the definition of $\omega$.


title: Generalizing Boolean Satisfiability I: Background and Survey of Existing Work

abstract: This is the first of three planned papers describing ZAP, a satisfiability engine that substantially generalizes existing tools while retaining the performance characteristics of modern high-performance solvers. The fundamental idea underlying ZAP is that many problems passed to such engines contain rich internal structure that is obscured by the Boolean representation used; our goal is to define a representation in which this structure is apparent and can easily be exploited to improve computational performance. This paper is a survey of the work underlying ZAP, and discusses previous attempts to improve the performance of the Davis-Putnam-Logemann-Loveland algorithm by exploiting the structure of the problem being solved. We examine existing ideas including extensions of the Boolean language to allow cardinality constraints, pseudo-Boolean representations, symmetry, and a limited form of quantification. While this paper is intended as a survey, our research results are contained in the two subsequent articles, with the theoretical structure of ZAP described in the second paper in this series, and ZAP's implementation described in the third.


title: PHA*: Finding the Shortest Path with A* in An Unknown Physical Environment

abstract: We address the problem of finding the shortest path between two points in an unknown real physical environment, where a traveling agent must move around in the environment to explore unknown territory. We introduce the Physical-A* algorithm (PHA*) for solving this problem. PHA* expands all the mandatory nodes that A* would expand and returns the shortest path between the two points. However, due to the physical nature of the problem, the complexity of the algorithm is measured by the traveling effort of the moving agent and not by the number of generated nodes, as in standard A*. PHA* is presented as a two-level algorithm, such that its high level, A*, chooses the next node to be expanded and its low level directs the agent to that node in order to explore it. We present a number of variations for both the high-level and low-level procedures and evaluate their performance theoretically and experimentally. We show that the travel cost of our best variation is fairly close to the optimal travel cost, assuming that the mandatory nodes of A* are known in advance. We then generalize our algorithm to the multi-agent case, where a number of cooperative agents are designed to solve the problem. Specifically, we provide an experimental implementation for such a system. It should be noted that the problem addressed here is not a navigation problem, but rather a problem of finding the shortest path between two points for future usage.


title: Restricted Value Iteration: Theory and Algorithms

abstract: Value iteration is a popular algorithm for finding near optimal policies for POMDPs. It is inefficient due to the need to account for the entire belief space, which necessitates the solution of large numbers of linear programs. In this paper, we study value iteration restricted to belief subsets. We show that, together with properly chosen belief subsets, restricted value iteration yields near-optimal policies and we give a condition for determining whether a given belief subset would bring about savings in space and time. We also apply restricted value iteration to two interesting classes of POMDPs, namely informative POMDPs and near-discernible POMDPs.


title: A Maximal Tractable Class of Soft Constraints

abstract: Many researchers in artificial intelligence are beginning to explore the use of soft constraints to express a set of (possibly conflicting) problem requirements. A soft constraint is a function defined on a collection of variables which associates some measure of desirability with each possible combination of values for those variables. However, the crucial question of the computational complexity of finding the optimal solution to a collection of soft constraints has so far received very little attention. In this paper we identify a class of soft binary constraints for which the problem of finding the optimal solution is tractable. In other words, we show that for any given set of such constraints, there exists a polynomial time algorithm to determine the assignment having the best overall combined measure of desirability. This tractable class includes many commonly-occurring soft constraints, such as 'as near as possible' or 'as soon as possible after', as well as crisp constraints such as 'greater than'. Finally, we show that this tractable class is maximal, in the sense that adding any other form of soft binary constraint which is not in the class gives rise to a class of problems which is NP-hard.


title: Towards Understanding and Harnessing the Potential of Clause Learning

abstract: Efficient implementations of DPLL with the addition of clause learning are the fastest complete Boolean satisfiability solvers and can handle many significant real-world problems, such as verification, planning and design. Despite its importance, little is known of the ultimate strengths and limitations of the technique. This paper presents the first precise characterization of clause learning as a proof system (CL), and begins the task of understanding its power by relating it to the well-studied resolution proof system. In particular, we show that with a new learning scheme, CL can provide exponentially shorter proofs than many proper refinements of general resolution (RES) satisfying a natural property. These include regular and Davis-Putnam resolution, which are already known to be much stronger than ordinary DPLL. We also show that a slight variant of CL with unlimited restarts is as powerful as RES itself. Translating these analytical results to practice, however, presents a challenge because of the nondeterministic nature of clause learning algorithms. We propose a novel way of exploiting the underlying problem structure, in the form of a high level problem description such as a graph or PDDL specification, to guide clause learning algorithms toward faster solutions. We show that this leads to exponential speed-ups on grid and randomized pebbling problems, as well as substantial improvements on certain ordering formulas.


title: Graduality in Argumentation

abstract: Argumentation is based on the exchange and valuation of interacting arguments, followed by the selection of the most acceptable of them (for example, in order to take a decision, to make a choice). Starting from the framework proposed by Dung in 1995, our purpose is to introduce 'graduality' in the selection of the best arguments, i.e., to be able to partition the set of the arguments in more than the two usual subsets of 'selected' and 'non-selected' arguments in order to represent different levels of selection. Our basic idea is that an argument is all the more acceptable if it can be preferred to its attackers. First, we discuss general principles underlying a 'gradual' valuation of arguments based on their interactions. Following these principles, we define several valuation models for an abstract argumentation system. Then, we introduce 'graduality' in the concept of acceptability of arguments. We propose new acceptability classes and a refinement of existing classes taking advantage of an available 'gradual' valuation.


title: Explicit Learning Curves for Transduction and Application to Clustering and Compression Algorithms

abstract: Inductive learning is based on inferring a general rule from a finite data set and using it to label new data. In transduction one attempts to solve the problem of using a labeled training set to label a set of unlabeled points, which are given to the learner prior to learning. Although transduction seems at the outset to be an easier task than induction, there have not been many provably useful algorithms for transduction. Moreover, the precise relation between induction and transduction has not yet been determined. The main theoretical developments related to transduction were presented by Vapnik more than twenty years ago. One of Vapnik's basic results is a rather tight error bound for transductive classification based on an exact computation of the hypergeometric tail. While tight, this bound is given implicitly via a computational routine. Our first contribution is a somewhat looser but explicit characterization of a slightly extended PAC-Bayesian version of Vapnik's transductive bound. This characterization is obtained using concentration inequalities for the tail of sums of random variables obtained by sampling without replacement. We then derive error bounds for compression schemes such as (transductive) support vector machines and for transduction algorithms based on clustering. The main observation used for deriving these new error bounds and algorithms is that the unlabeled test points, which in the transductive setting are known in advance, can be used in order to construct useful data dependent prior distributions over the hypothesis space.


title: Decentralized Control of Cooperative Systems: Categorization and Complexity Analysis

abstract: Decentralized control of cooperative systems captures the operation of a group of decision makers that share a single global objective. The difficulty in solving optimally such problems arises when the agents lack full observability of the global state of the system when they operate. The general problem has been shown to be NEXP-complete. In this paper, we identify classes of decentralized control problems whose complexity ranges between NEXP and P. In particular, we study problems characterized by independent transitions, independent observations, and goal-oriented objective functions. Two algorithms are shown to solve optimally useful classes of goal-oriented decentralized processes in polynomial time. This paper also studies information sharing among the decision-makers, which can improve their performance. We distinguish between three ways in which agents can exchange information: indirect communication, direct communication and sharing state features that are not controlled by the agents. Our analysis shows that for every class of problems we consider, introducing direct or indirect communication does not change the worst-case complexity. The results provide a better understanding of the complexity of decentralized control problems that arise in practice and facilitate the development of planning algorithms for these problems.


title: Reinforcement Learning for Agents with Many Sensors and Actuators Acting in Categorizable Environments

abstract: In this paper, we confront the problem of applying reinforcement learning to agents that perceive the environment through many sensors and that can perform parallel actions using many actuators as is the case in complex autonomous robots. We argue that reinforcement learning can only be successfully applied to this case if strong assumptions are made on the characteristics of the environment in which the learning is performed, so that the relevant sensor readings and motor commands can be readily identified. The introduction of such assumptions leads to strongly-biased learning systems that can eventually lose the generality of traditional reinforcement-learning algorithms. In this line, we observe that, in realistic situations, the reward received by the robot depends only on a reduced subset of all the executed actions and that only a reduced subset of the sensor inputs (possibly different in each situation and for each action) are relevant to predict the reward. We formalize this property in the so called 'categorizability assumption' and we present an algorithm that takes advantage of the categorizability of the environment, allowing a decrease in the learning time with respect to existing reinforcement-learning algorithms. Results of the application of the algorithm to a couple of simulated realistic-robotic problems (landmark-based navigation and the six-legged robot gait generation) are reported to validate our approach and to compare it to existing flat and generalization-based reinforcement-learning approaches.


title: How peculiar was the recent extended minimum - A hint towards double minima

abstract: In this paper, we address the controversy regarding the recent extended solar minimum as seen in helioseismic low- and intermediate-degree mode frequencies: studies from different instruments identify different epochs of seismic minima. Here we use mode frequencies from a network of six identical instruments, Global Oscillation Network Group, continuously collecting data for more than 15 years, to investigate the epoch of minimum in solar oscillation frequencies prior to the beginning of solar cycle 24. We include both low- and intermediate-degree modes in the $\ell$ range of 0 -- 120 and frequency range of 2.0 -- 3.5 mHz. In this analysis, we demonstrate that there were indeed two minima in oscillation frequencies, depending upon the degree of modes, or more precisely the lower turning point radius of the propagating wave. We also analyze frequencies as a function of latitude to identify the beginning of solar cycle 24. We observe two minima at high latitudes and a single minimum at mid/low latitudes. This scenario is in contrast to cycle 23 where the epoch of seismic minimum did not change with latitude or depth. Our results also hint towards a possible role of the relic magnetic field in modifying the oscillation frequencies of modes sampling deeper layers.


title: Additive Pattern Database Heuristics

abstract: We explore a method for computing admissible heuristic evaluation functions for search problems. It utilizes pattern databases, which are precomputed tables of the exact cost of solving various subproblems of an existing problem. Unlike standard pattern database heuristics, however, we partition our problems into disjoint subproblems, so that the costs of solving the different subproblems can be added together without overestimating the cost of solving the original problem. Previously, we showed how to statically partition the sliding-tile puzzles into disjoint groups of tiles to compute an admissible heuristic, using the same partition for each state and problem instance. Here we extend the method and show that it applies to other domains as well. We also present another method for additive heuristics which we call dynamically partitioned pattern databases. Here we partition the problem into disjoint subproblems for each state of the search dynamically. We discuss the pros and cons of each of these methods and apply both methods to three different problem domains: the sliding-tile puzzles, the 4-peg Towers of Hanoi problem, and finding an optimal vertex cover of a graph. We find that in some problem domains, static partitioning is most effective, while in others dynamic partitioning is a better choice. In each of these problem domains, either statically partitioned or dynamically partitioned pattern database heuristics are the best known heuristics for the problem.


title: On Prediction Using Variable Order Markov Models

abstract: This paper is concerned with algorithms for prediction of discrete sequences over a finite alphabet, using variable order Markov models. The class of such algorithms is large and in principle includes any lossless compression algorithm. We focus on six prominent prediction algorithms, including Context Tree Weighting (CTW), Prediction by Partial Match (PPM) and Probabilistic Suffix Trees (PSTs). We discuss the properties of these algorithms and compare their performance using real life sequences from three domains: proteins, English text and music pieces. The comparison is made with respect to prediction quality as measured by the average log-loss. We also compare classification algorithms based on these predictors with respect to a number of large protein classification tasks. Our results indicate that a "decomposed" CTW (a variant of the CTW algorithm) and PPM outperform all other algorithms in sequence prediction tasks. Somewhat surprisingly, a different algorithm, which is a modification of the Lempel-Ziv compression algorithm, significantly outperforms all algorithms on the protein classification problems.


title: Ordered Landmarks in Planning

abstract: Many known planning tasks have inherent constraints concerning the best order in which to achieve the goals. A number of research efforts have been made to detect such constraints and to use them for guiding search, in the hope of speeding up the planning process. We go beyond the previous approaches by considering ordering constraints not only over the (top-level) goals, but also over the sub-goals that will necessarily arise during planning. Landmarks are facts that must be true at some point in every valid solution plan. We extend Koehler and Hoffmann's definition of reasonable orders between top level goals to the more general case of landmarks. We show how landmarks can be found, how their reasonable orders can be approximated, and how this information can be used to decompose a given planning task into several smaller sub-tasks. Our methodology is completely domain- and planner-independent. The implementation demonstrates that the approach can yield significant runtime performance improvements when used as a control loop around state-of-the-art sub-optimal planning systems, as exemplified by FF and LPG.


title: Finding Approximate POMDP solutions Through Belief Compression

abstract: Standard value function approaches to finding policies for Partially Observable Markov Decision Processes (POMDPs) are generally considered to be intractable for large models. The intractability of these algorithms is to a large extent a consequence of computing an exact, optimal policy over the entire belief space. However, in real-world POMDP problems, computing the optimal policy for the full belief space is often unnecessary for good control even for problems with complicated policy classes. The beliefs experienced by the controller often lie near a structured, low-dimensional subspace embedded in the high-dimensional belief space. Finding a good approximation to the optimal value function for only this subspace can be much easier than computing the full value function. We introduce a new method for solving large-scale POMDPs by reducing the dimensionality of the belief space. We use Exponential family Principal Components Analysis (Collins, Dasgupta and Schapire, 2002) to represent sparse, high-dimensional belief spaces using small sets of learned features of the belief state. We then plan only in terms of the low-dimensional belief features. By planning in this low-dimensional space, we can find policies for POMDP models that are orders of magnitude larger than models that can be handled by conventional techniques. We demonstrate the use of this algorithm on a synthetic problem and on mobile robot navigation tasks.


title: A Comprehensive Trainable Error Model for Sung Music Queries

abstract: We propose a model for errors in sung queries, a variant of the hidden Markov model (HMM). This is a solution to the problem of identifying the degree of similarity between a (typically error-laden) sung query and a potential target in a database of musical works, an important problem in the field of music information retrieval. Similarity metrics are a critical component of query-by-humming (QBH) applications which search audio and multimedia databases for strong matches to oral queries. Our model comprehensively expresses the types of error or variation between target and query: cumulative and non-cumulative local errors, transposition, tempo and tempo changes, insertions, deletions and modulation. The model is not only expressive, but automatically trainable, or able to learn and generalize from query examples. We present results of simulations, designed to assess the discriminatory potential of the model, and tests with real sung queries, to demonstrate relevance to real-world applications.


title: Phase Transitions and Backbones of the Asymmetric Traveling Salesman Problem

abstract: In recent years, there has been much interest in phase transitions of combinatorial problems. Phase transitions have been successfully used to analyze combinatorial optimization problems, characterize their typical-case features and locate the hardest problem instances. In this paper, we study phase transitions of the asymmetric Traveling Salesman Problem (ATSP), an NP-hard combinatorial optimization problem that has many real-world applications. Using random instances of up to 1,500 cities in which intercity distances are uniformly distributed, we empirically show that many properties of the problem, including the optimal tour cost and backbone size, experience sharp transitions as the precision of intercity distances increases across a critical value. Our experimental results on the costs of the ATSP tours and assignment problem agree with the theoretical result that the asymptotic cost of assignment problem is pi ^2 /6 the number of cities goes to infinity. In addition, we show that the average computational cost of the well-known branch-and-bound subtour elimination algorithm for the problem also exhibits a thrashing behavior, transitioning from easy to difficult as the distance precision increases. These results answer positively an open question regarding the existence of phase transitions in the ATSP, and provide guidance on how difficult ATSP problem instances should be generated.


title: Fixed parameter algorithms for restricted coloring problems

abstract: In this paper, we obtain polynomial time algorithms to determine the acyclic chromatic number, the star chromatic number, the Thue chromatic number, the harmonious chromatic number and the clique chromatic number of $P_4$-tidy graphs and $(q,q-4)$-graphs, for every fixed $q$. These classes include cographs, $P_4$-sparse and $P_4$-lite graphs. All these coloring problems are known to be NP-hard for general graphs. These algorithms are fixed parameter tractable on the parameter $q(G)$, which is the minimum $q$ such that $G$ is a $(q,q-4)$-graph. We also prove that every connected $(q,q-4)$-graph with at least $q$ vertices is 2-clique-colorable and that every acyclic coloring of a cograph is also nonrepetitive.


title: Landau Level Spectrum of ABA- and ABC-stacked Trilayer Graphene

abstract: We study the Landau level spectrum of ABA- and ABC-stacked trilayer graphene. We derive analytic low energy expressions for the spectrum, the validity of which is confirmed by comparison to a \pi -band tight-binding calculation of the density of states on the honeycomb lattice. We further study the effect of a perpendicular electric field on the spectrum, where a zero-energy plateau appears for ABC stacking order, due to the opening of a gap at the Dirac point, while the ABA-stacked trilayer graphene remains metallic. We discuss our results in the context of recent electronic transport experiments. Furthermore, we argue that the expressions obtained can be useful in the analysis of future measurements of cyclotron resonance of electrons and holes in trilayer graphene.


title: Coherent vortex structures and 3D enstrophy cascade

abstract: Existence of 2D enstrophy cascade in a suitable mathematical setting, and under suitable conditions compatible with 2D turbulence phenomenology, is known both in the Fourier and in the physical scales. The goal of this paper is to show that the same geometric condition preventing the formation of singularities - 1/2-H\"older coherence of the vorticity direction - coupled with a suitable condition on a modified Kraichnan scale, and under a certain modulation assumption on evolution of the vorticity, leads to existence of 3D enstrophy cascade in physical scales of the flow.


title: Algorithm to compute the electric field gradient tensor in ionic crystals

abstract: A simple algorithm and a computational program to numerically compute the electric field gradient and the concomitant quadrupolar nuclear splitting is developed for an arbitrary ionic crystal. The calculations are performed using a point charge model. The program provides three different ways for the data input: by Bravais lattices, by lattice parameters, or by introducing any spatial structure. The program calculates the components of the electric field gradient, the asymmetry parameter and the quadrupolar splitting for a given number of nearest neighbors with respect to the nuclear charge as origin. In addition, the program allows the use of different Sternheimer antishielding factors.


title: On the degree-chromatic polynomial of a tree

abstract: The degree chromatic polynomial $Pm(G,k)$ of a graph $G$ counts the number of $k$-colorings in which no vertex has $m$ adjacent vertices of its same color. We prove Humpert and Martin's conjecture on the leading terms of the degree chromatic polynomial of a tree.


title: Shapiro Steps in the Absence of Microwave Radiation

abstract: The current-voltage I-V characteristics of a 1.2 \mum long Au nanowire contacted by superconducting electrodes were studied in details. Interestingly, the I-V curves over a wide range of temperatures display multiple steps at voltages V = (m/n)(V0/2e) in the absence of microwave radiation, where m, n are integer numbers and V0 ~ 92 \muV. We posit that these steps are the subharmonic Shapiro steps due to the interplay of the ac Josephson current and a minigap in the Au nanowire induced by superconducting electrodes via the proximity effect.


title: Optimal Multi-Robot Path Planning with Temporal Logic Constraints

abstract: In this paper we present a method for automatically planning optimal paths for a group of robots that satisfy a common high level mission specification. Each robot's motion in the environment is modeled as a weighted transition system. The mission is given as a Linear Temporal Logic formula. In addition, an optimizing proposition must repeatedly be satisfied. The goal is to minimize the maximum time between satisfying instances of the optimizing proposition. Our method is guaranteed to compute an optimal set of robot paths. We utilize a timed automaton representation in order to capture the relative position of the robots in the environment. We then obtain a bisimulation of this timed automaton as a finite transition system that captures the joint behavior of the robots and apply our earlier algorithm for the single robot case to optimize the group motion. We present a simulation of a persistent monitoring task in a road network environment.


title: Formal Model Engineering for Embedded Systems Using Real-Time Maude

abstract: This paper motivates why Real-Time Maude should be well suited to provide a formal semantics and formal analysis capabilities to modeling languages for embedded systems. One can then use the code generation facilities of the tools for the modeling languages to automatically synthesize Real-Time Maude verification models from design models, enabling a formal model engineering process that combines the convenience of modeling using an informal but intuitive modeling language with formal verification. We give a brief overview six fairly different modeling formalisms for which Real-Time Maude has provided the formal semantics and (possibly) formal analysis. These models include behavioral subsets of the avionics modeling standard AADL, Ptolemy II discrete-event models, two EMF-based timed model transformation systems, and a modeling language for handset software.


title: Rascal: From Algebraic Specification to Meta-Programming

abstract: Algebraic specification has a long tradition in bridging the gap between specification and programming by making specifications executable. Building on extensive experience in designing, implementing and using specification formalisms that are based on algebraic specification and term rewriting (namely Asf and Asf+Sdf), we are now focusing on using the best concepts from algebraic specification and integrating these into a new programming language: Rascal. This language is easy to learn by non-experts but is also scalable to very large meta-programming applications. We explain the algebraic roots of Rascal and its main application areas: software analysis, software transformation, and design and implementation of domain-specific languages. Some example applications in the domain of Model-Driven Engineering (MDE) are described to illustrate this.


title: Typed lambda-terms in categorical attributed graph transformation

abstract: This paper deals with model transformation based on attributed graph rewriting. Our contribution investigates a single pushout approach for applying the rewrite rules. The computation of graph attributes is obtained through the use of typed lambda-calculus with inductive types. In this paper we present solutions to cope with single pushout construction for the graph structure and the computations functions. As this rewrite system uses inductive types, the expressiveness of attribute computations is facilitated and appears more efficient than the one based on Sigma-algebras. Some examples showing the interest of our computation approach are described in this paper.


title: Formal Visual Modeling of Real-Time Systems in e-Motions: Two Case Studies

abstract: e-Motions is an Eclipse-based visual timed model transformation framework with a Real-Time Maude semantics that supports the usual Maude formal analysis methods, including simulation, reachability analysis, and LTL model checking. e-Motions is characterized by a novel and powerful set of constructs for expressing timed behaviors. In this paper we illustrate the use of these constructs --- and thereby implicitly investigate their suitability to define real-time systems in an intuitive way --- to define and formally analyze two prototypical and very different real-time systems: (i) a simple round trip time protocol for computing the time it takes a message to travel from one node to another, and back; and (ii) the EDF scheduling algorithm.


title: Prototyping the Semantics of a DSL using ASF+SDF: Link to Formal Verification of DSL Models

abstract: A formal definition of the semantics of a domain-specific language (DSL) is a key prerequisite for the verification of the correctness of models specified using such a DSL and of transformations applied to these models. For this reason, we implemented a prototype of the semantics of a DSL for the specification of systems consisting of concurrent, communicating objects. Using this prototype, models specified in the DSL can be transformed to labeled transition systems (LTS). This approach of transforming models to LTSs allows us to apply existing tools for visualization and verification to models with little or no further effort. The prototype is implemented using the ASF+SDF Meta-Environment, an IDE for the algebraic specification language ASF+SDF, which offers efficient execution of the transformation as well as the ability to read models and produce LTSs without any additional pre or post processing.


title: Tracing Properties of UML and OCL Models with Maude

abstract: The starting point of this paper is a system described in form of a UML class diagram where system states are characterized by OCL invariants and system transitions are defined by OCL pre- and postconditions. The aim of our approach is to assist the developer in learning about the consequences of the described system states and transitions and about the formal implications of the properties that are explicitly given. We propose to draw conclusions about the stated constraints by translating the UML and OCL model into the algebraic specification language and system Maude, which is based on rewrite logic. We will concentrate in this paper on employing Maude's capabilities for state search. Maude's state search offers the possibility to describe a start configuration of the system and then explore all configurations reachable by rewriting. The search can be adjusted by formulating requirements for the allowed states and the allowed transitions.


title: Properties of the superconducting state in molecular metallic hydrogen under pressure at 347 GPa

abstract: The thermodynamic properties of the superconducting state induced in metallic molecular hydrogen under the influence of pressure 347 GPa were determined. In particular, it has been shown that the critical temperature ($T_{C}$) changes in the range from 120 K to 90 K for $\mu^{*}\in<0.08,0.15>$, where $\mu^{*}$ is the value of the Coulomb pseudopotential. Next, the energy gap near the temperature of zero Kelvin ($2\Delta(0)$) was calculated. It has been stated, that the dimensionless ratio $2\Delta(0)/k_{B}T_{C}$ slightly decreases with the increase of $\mu^{*}$ from 3.98 to 3.84. In the last step, the ratio of effective electron mass ($m^{*}_{e}$) to the bare electron mass ($m_{e}$)) was determined. It has been proved that $m^{*}_{e}/m_{e}$ takes its highest value equal to 1.96 for $T=T_{C}$.


title: A Suzaku Observation of MCG-2-58-22: Constraining the Geometry of the Circumnuclear Material

abstract: We have analyzed a Suzaku long-look of the active galactic nucleus MCG-2-58-22, a type 1.5 Seyfert with very little X-ray absorption in the line of sight and prominent features arising from reflection off circumnuclear material: the Fe line and Compton reflection hump. We place tight constraints on the power law photon index (Gamma=1.80+/-0.02), the Compton reflection strength (R=0.69+/-0.05), and the Fe K emission line energy centroid and width (E=6.40+/-0.02 keV, v_FWHM < 7100 km/s). We find no significant evidence for emission from strongly ionized Fe, nor for a strong, relativistically broadened Fe line, indicating that perhaps there is no radiatively efficient accretion disk very close in to the central black hole. In addition we test a new self-consistent physical model from Murphy & Yaqoob, the "MYTorus" model, consisting of a donut-shaped torus of material surrounding the central illuminating source and producing both the Compton hump and the Fe K line emission. From the application of this model we find that the observed spectrum is consistent with a Compton-thick torus of material (column density NH=3.6(+1.3/-0.8) x 10^24 cm^-2) lying outside of the line of sight to the nucleus, leaving it bare of X-ray absorption in excess of the Galactic column. We calculate that this material is sufficient to produce all of the Fe line flux without the need for any flux contribution from additional Compton-thin circumnuclear material.


title: Kramers-Kronig, Bode, and the meaning of zero

abstract: The implications of causality, as captured by the Kramers-Kronig relations between the real and imaginary parts of a linear response function, are familiar parts of the physics curriculum. In 1937, Bode derived a similar relation between the magnitude (response gain) and phase. Although the Kramers-Kronig relations are an equality, Bode's relation is effectively an inequality. This perhaps-surprising difference is explained using elementary examples and ultimately traces back to delays in the flow of information within the system formed by the physical object and measurement apparatus.


title: Localization principle and relaxation

abstract: Relaxation theorems for multiple integrals on W^{1,p}(\Omega;\RR^m), where p\in]1,\infty[, are proved under general conditions on the integrand L:\MM\to[0,\infty] which is Borel measurable and not necessarily finite. We involve a localization principle that we previously used to prove a general lower semicontinuity result. We apply these general results to the relaxation of nonconvex integrals with exponential-growth.


title: SLUG Microwave Amplifier: Theory

abstract: We describe a novel scheme for low-noise phase-insensitive linear amplification at microwave frequencies based on the Superconducting Low-inductance Undulatory Galvanometer (SLUG). Direct integration of the junction equations of motion provides access to the full scattering matrix of the SLUG. We discuss the optimization of SLUG amplifiers and calculate amplifier gain and noise temperature in both the thermal and quantum regimes. Loading of the SLUG element by the finite input admittance is taken into account, and strategies for decoupling the SLUG from the higher-order modes of the input circuit are discussed. The microwave SLUG amplifier is expected to achieve noise performance approaching the standard quantum limit in the frequency range from 5-10 GHz, with gain around 15 dB for a single-stage device and instantaneous bandwidths of order 1 GHz.


title: Testing Machine for Expansive Mortar

abstract: The correct evaluation of a material property is fundamental to, on their application; they met all expectations that were designed for. In development of an expansive cement for ornamental rocks purpose, was denoted the absence of methodologies and equipments to evaluate the expansive pressure and temperature of expansive cement during their expansive process, having that data collected in a static state of the specimen. In that paper, is described equipment designed for evaluation of pressure and temperature of expansive cements applied to ornamental rocks.


title: Electronic structure of silicon-based nanostructures

abstract: We have developed an unifying tight-binding Hamiltonian that can account for the electronic properties of recently proposed Si-based nanostructures, namely, Si graphene-like sheets and Si nanotubes. We considered the $sp^3s^*$ and $sp^{3}$ models up to first- and second-nearest neighbors, respectively. Our results show that the Si graphene-like sheets considered here are metals or zero-gap semiconductors, and that the corresponding Si nanotubes follow the so-called Hamada's rule [Phys. Rev. Lett. {\bf 68}, 1579 1992]. Comparison to a recent {\it ab initio} calculation is made.


title: KARMA: Kalman-based autoregressive moving average modeling and inference for formant and antiformant tracking

abstract: Vocal tract resonance characteristics in acoustic speech signals are classically tracked using frame-by-frame point estimates of formant frequencies followed by candidate selection and smoothing using dynamic programming methods that minimize ad hoc cost functions. The goal of the current work is to provide both point estimates and associated uncertainties of center frequencies and bandwidths in a statistically principled state-space framework. Extended Kalman (K) algorithms take advantage of a linearized mapping to infer formant and antiformant parameters from frame-based estimates of autoregressive moving average (ARMA) cepstral coefficients. Error analysis of KARMA, WaveSurfer, and Praat is accomplished in the all-pole case using a manually marked formant database and synthesized speech waveforms. KARMA formant tracks exhibit lower overall root-mean-square error relative to the two benchmark algorithms, with third formant tracking more challenging. Antiformant tracking performance of KARMA is illustrated using synthesized and spoken nasal phonemes. The simultaneous tracking of uncertainty levels enables practitioners to recognize time-varying confidence in parameters of interest and adjust algorithmic settings accordingly.


title: The Stellar Archeology of the M33 Disk: Recent Star-Forming History and Constraints on the Timing of an Interaction with M31

abstract: Images recorded with MegaCam are used to investigate the recent star-forming history (SFH) of the Local Group Sc galaxy M33. The properties of the stellar disk change near R = 8 kpc. Within this radius the star formation rate (SFR) has been constant with time during at least the past 250 Myr, while at larger radii the SFR has declined during this same time period. That the recent SFR in the inner disk has been constant suggests that M33 has evolved in isolation for at least the past ~ 0.5 Gyr, thereby providing a constraint on the timing of any recent interaction with M31. The fractional contribution that young stars make to the total mass of the stellar disk changes with radius, peaking near 8 kpc. Evidence is also presented that the SFR during the past 100 Myr in the southern half of the galaxy has been ~ 0.4 dex higher than in the northern half. Finally, structures with sizes spanning many kpc that contain blue objects - presumably main sequence stars that formed during intermediate epochs - are identified near the disk boundary. It is argued that these are tidal features that were pulled from the main body of M33 and - in some cases - are the fossil remnants of star formation that occured in an extended disk during intermediate epochs.


title: Optimization of UAV Heading for the Ground-to-Air Uplink

abstract: In this paper we consider a collection of single-antenna ground nodes communicating with a multi-antenna unmanned aerial vehicle (UAV) over a multiple-access ground-to-air wireless communications link. The UAV uses beamforming to mitigate the inter-user interference and achieve spatial division multiple access (SDMA). First, we consider a simple scenario with two static ground nodes and analytically investigate the effect of the UAV heading on the system sum rate. We then study a more general setting with multiple mobile ground-based terminals, and develop an algorithm for dynamically adjusting the UAV heading in order to maximize a lower bound on the ergodic sum rate of the uplink channel, using a Kalman filter to track the positions of the mobile ground nodes. Fairness among the users can be guaranteed through weighting the bound for each user's ergodic rate with a factor inversely proportional to their average data rate. For the common scenario where a high $K$-factor channel exists between the ground nodes and UAV, we use an asymptotic analysis to find simplified versions of the algorithm for low and high SNR. We present simulation results that demonstrate the benefits of adapting the UAV heading in order to optimize the uplink communications performance. The simulation results also show that the simplified algorithms perform near-optimal performance.


title: Critical Multitype Branching Systems: Extinction Results

abstract: We consider a critical branching particle system in $\R^d$, composed of individuals of a finite number of types $i\in\{1,...,K\}$. Each individual of type $i$ moves independently according to a symmetric $\alpha_i$-stable motion. We assume that the particle lifetimes and offspring distributions are type-dependent. Under the usual independence assumptions in branching systems, we prove extinction theorems in the following cases: (1) all the particle lifetimes have finite mean, or (2) there is a type whose lifetime distribution has heavy tail, and the other lifetimes have finite mean. We get a more complex dynamics by assuming in case (2) that the most mobile particle type corresponds to a finite-mean lifetime: in this case, local extinction of the population is determined by an interaction of the parameters (offspring variability, mobility, longevity) of the long-living type and those of the most mobile type. The proofs are based on a precise analysis of the occupation times of a related Markov renewal process, which is of independent interest.


title: Elliptic and triangular flow of identified particles at ALICE

abstract: We report on the first measurements of elliptic and triangular flow for charged pions, kaons and anti-protons in lead-lead collisions at 2.76 TeV measured with the ALICE detector at the LHC. We compare the observed mass splitting of differential elliptic flow at LHC energies to RHIC measurements at lower energies and theory predictions. We test the quark coalescence picture with the quark number scaling of elliptic and triangular flow.


title: Primal-dual splitting algorithm for solving inclusions with mixtures of composite, Lipschitzian, and parallel-sum monotone operators

abstract: We propose a primal-dual splitting algorithm for solving monotone inclusions involving a mixture of sums, linear compositions, and parallel sums of set-valued and Lipschitzian operators. An important feature of the algorithm is that the Lipschitzian operators present in the formulation can be processed individually via explicit steps, while the set-valued operators are processed individually via their resolvents. In addition, the algorithm is highly parallel in that most of its steps can be executed simultaneously. This work brings together and notably extends various types of structured monotone inclusion problems and their solution methods. The application to convex minimization problems is given special attention.


title: A case of combination of evidence in the Dempster-Shafer theory inconsistent with evaluation of probabilities

abstract: The Dempster-Shafer theory of evidence accumulation is one of the main tools for combining data obtained from multiple sources. In this paper a special case of combination of two bodies of evidence with non-zero conflict coefficient is considered. It is shown that application of the Dempster-Shafer rule of combination in this case leads to an evaluation of masses of the combined bodies that is different from the evaluation of the corresponding probabilities obtained by application of the law of total probability. This finding supports the view that probabilistic interpretation of results of the Dempster-Shafer analysis in the general case is not appropriate.


title: Electrical Transport Properties of Graphene Nanoribbons Produced from Sonicating Graphite in Solution

abstract: A simple one-stage solution-based method was developed to produce graphene nanoribbons by sonicating graphite powder in organic solutions with polymer surfactant. The graphene nanoribbons were deposited on silicon substrate, and characterized by Raman spectroscopy and atomic force microscopy. Single-layer and few-layer graphene nanoribbons with a width ranging from sub-10 nm to tens of nm and length ranging from hundreds of nm to 1 {\mu}m were routinely observed. Electrical transport properties of individual graphene nanoribbons were measured in both the back-gate and polymer-electrolyte top-gate configurations. The mobility of the graphene nanoribbons was found to be over an order of magnitude higher when measured in the latter than in the former configuration (without the polymer electrolyte), which can be attributed to the screening of the charged impurities by the counter-ions in the polymer electrolyte. This finding suggests that the charge transport in these solution-produced graphene nanoribbons is largely limited by charged impurity scattering.


title: K0s-K0s correlations in 7 TeV pp collisions from the ALICE experiment at the LHC

abstract: Identical neutral kaon pair correlations are measured in 7 TeV pp collisions in the ALICE experiment. K0s-K0s correlation functions are formed in 3 multiplicity X 4 kT bins. The femtoscopic kaon source parameters Rinv and lambda are extracted from these correlation functions by fitting a (femtoscopy) X (PYTHIA) model to them, PYTHIA accounting for the non-flat baseline found in pp collisions. Source parameters are obtained from a fit which includes quantum statistics and final-state interactions of the a0/f0 resonance. K0s-K0s correlations show a systematic increase in Rinv for increasing multiplicity bin and decreasing Rinv for increasing kT bin as seen in pi-pi correlations in the pp system, as well as seen in heavy-ion collisions. Also, K0s-K0s correlations are observed to smoothly extend this pi-pi Rinv behavior for the pp system up to about three times higher kT than the kT range measured in pi-pi correlations.


title: Three-Fold Diffraction Symmetry in Epitaxial Graphene and the SiC Substrate

abstract: The crystallographic symmetries and spatial distribution of stacking domains in graphene films on SiC have been studied by low energy electron diffraction (LEED) and dark field imaging in a low energy electron microscope (LEEM). We find that the graphene diffraction spots from 2 and 3 atomic layers of graphene have 3-fold symmetry consistent with AB (Bernal) stacking of the layers. On the contrary, graphene diffraction spots from the buffer layer and monolayer graphene have apparent 6-fold symmetry, although the 3-fold nature of the satellite spots indicates a more complex periodicity in the graphene sheets.


title: An Assessment of "What does photon energy tell us about cellphone safety" by Dr. William Bruno

abstract: Dr. William Bruno asserts the well-known fact that cell phones radiate microwaves in the classical regime. This, he says, means that the photon energy is not relevant to assessing safety. Citing optical tweezers as an example of biologically relevant non-thermal effects of electromagnetic radiation, Bruno concludes that all other reports of non-thermal effects from microwaves are likely valid. He seeks safety thresholds based upon requiring that cell phone energy density be less than kBT. This proposal and related ideas produce thresholds many orders of magnitude below present values. While Dr. Bruno is correct that cell phone microwave radiation is generally in the classical regime, he uses peculiar estimates (number of photons per cubic wavelength) that overstate the circumstance by more than 20 factors of ten. He misunderstands the operation of optical tweezers and ignores their significant thermal effects. He credulously accepts poorly supported claims of non-thermal effects. He mistakenly believes that kBT is the average thermal energy (per cubic wavelength or per cell) in materials. It is not. It is twice the average energy per molecule per degree of freedom in the material. The thermal energy density is (1/2)kBT X (average number of degrees of freedom of the molecules) X (Avogadro's number). (Avogadro's number is 6 X 1026 molecules/mole.) Thus, Bruno's proposed safety thresholds are more than 1025 too low. Using the correct value for the average thermal energy would place the thresholds close to today's standards. Throughout his analysis he neglects the index of refraction of living tissue, n \cong 9, or the absorption length, {\alpha} \cong 1 cm-1, in the microwave region.


title: Understanding diffusion and density anomaly in a coarse-grained model for water confined between hydrophobic walls

abstract: We study, by Monte Carlo simulations, a coarse-grained model of a water monolayer between hydrophobic walls at partial hydration, with a wall-to-wall distance of about 0.5 nm. We analyze how the diffusion constant parallel to the walls, $D_{\parallel}$, changes and correlates to the phase diagram of the system. We find a locus of $D_{\parallel}$ maxima and a locus of $D_{\parallel}$ minima along isotherms, with lines of constant $D_{\parallel}$ resembling the melting line of bulk water. The two loci of $D_{\parallel}$ extrema envelope the line of temperatures of density maxima at constant $P$. We show how these loci are related to the anomalous volume behavior due to the hydrogen bonds. At much lower $T$, confined water becomes subdiffusive, and we discuss how this behavior is a consequence of the increased correlations among water molecules when the hydrogen bond network develops. Within the subdiffusive region, although translations are largely hampered, we observe that the hydrogen bond network can equilibrate and its rearrangement is responsible for the appearance of density minima along isobars. We clarify that the minima are not necessarily related to the saturation of the hydrogen bond network.


title: Sparse Sums of Positive Semidefinite Matrices

abstract: Recently there has been much interest in "sparsifying" sums of rank one matrices: modifying the coefficients such that only a few are nonzero, while approximately preserving the matrix that results from the sum. Results of this sort have found applications in many different areas, including sparsifying graphs. In this paper we consider the more general problem of sparsifying sums of positive semidefinite matrices that have arbitrary rank. We give several algorithms for solving this problem. The first algorithm is based on the method of Batson, Spielman and Srivastava (2009). The second algorithm is based on the matrix multiplicative weights update method of Arora and Kale (2007). We also highlight an interesting connection between these two algorithms. Our algorithms have numerous applications. We show how they can be used to construct graph sparsifiers with auxiliary constraints, sparsifiers of hypergraphs, and sparse solutions to semidefinite programs.


title: Towards a Reliable Framework of Uncertainty-Based Group Decision Support System

abstract: This study proposes a framework of Uncertainty-based Group Decision Support System (UGDSS). It provides a platform for multiple criteria decision analysis in six aspects including (1) decision environment, (2) decision problem, (3) decision group, (4) decision conflict, (5) decision schemes and (6) group negotiation. Based on multiple artificial intelligent technologies, this framework provides reliable support for the comprehensive manipulation of applications and advanced decision approaches through the design of an integrated multi-agents architecture.


title: Dual equivalence and Schur positivity

abstract: We define dual equivalence for any collection of combinatorial objects endowed with a descent set, and we show that giving a dual equivalence establishes the symmetry and Schur positivity of the quasi-symmetric generating function. We give an explicit formula for the Schur expansion of the generating function in terms of distinguished elements of the dual equivalence classes. These concepts and proofs simplify in the ubiquitous case when the collection of objects has a sufficiently nice reading word.


title: Absence of Resonances near Critical Line for CC Manifolds

abstract: We find a resonance free region polynomially close to the critical line on Conformally compact manifolds with polyhomogeneous metric.


title: Lower bounds for volumes of nodal sets: an improvement of a result of Sogge-Zelditch

abstract: We use the Dong-Sogge-Zelditch formula to obtain a lower bound for the volume of the nodal sets of eigenfunctions. Our result improves the recent results of Sogge-Zelditch and in dimensions n \leq 5 gives a new proof for the lower bounds of Colding-Minicozzi.


title: One-step error correction for multipartite polarization entanglement

abstract: We present two economical one-step error-correction protocols for multipartite polarization-entangled systems in a Greenberger-Horne-Zeilinger state. One uses spatial entanglement to correct errors in the polarization entanglement of an N-photon system, resorting to linear optical elements. The other uses frequency entanglement to correct errors in the polarization entanglement of an N-photon system. The parties in quantum communication can obtain a maximally entangled state from each N-photon system transmitted with one step in these two protocols, and both of their success probabilities are 100%, in principle. That is, they both work in a deterministic way, and they do not largely consume the less-entangled photon systems, which is far different from conventional multipartite entanglement purification schemes. These features may make these two protocols more useful for practical applications in long-distance quantum communication.


title: Inverse Systems of Zero-dimensional Schemes in P^n

abstract: The authors construct the global Macaulay inverse system for a zero-dimensional subscheme Z of projective n-space P^n, from the local inverse systems of the irreducible components of Z. They show that when Z is locally Gorenstein a generic homogeneous form F of degree d apolar to Z determines Z when d is larger than an invariant b(Z). They also show that a natural upper bound for the Hiilbert function of Gorenstein Artin quotient of the coordinate ring is achieved for large socle degree. They show the uniqueness of generalized additive decompositions of a homogeneous form F into powers of linear forms, under suitable hypotheses. They include many examples.


title: Effect of Co Impurities on Superconductivity of FeSe0.4Te0.6 single crystals

abstract: The effect of Co doping on supercoductivity of FeSe$_{0.4}$Te$_{0.6}$ single crystals is investigated. The superconducting transition temperature decreases linearly for Co doping with the rate -0.75 K/(Co %). On the other hand, the residual resistivity increase is less than 50 $/mu/Omega$cm for 4 % Co doping. These data are consistent with the sign changing interband scattering mechanism of superconductivity ($s_/pm$ symmetry).


title: Derivative Formula and Applications for Degenerate Diffusion Semigroups

abstract: By using the Malliavin calculus and solving a control problem, Bismut type derivative formulae are established for a class of degenerate diffusion semigroups with non-linear drifts. As applications, explicit gradient estimates and Harnack inequalities are derived.


title: Force Induced Unzipping of DNA with Long Range Correlated Noise

abstract: We derive and solve a Fokker-Planck equation for the stationary distribution of the free energy, in a model of unzipping of double-stranded DNA under external force. The autocorrelation function of the random DNA sequence can be a general form, including long range correlations. In the case of Orstein-Uhlenbeck noise, characterized by a finite correlation length, our result reduces to the exact result of Allahverdyan et al, with the average number of unzipped base pairs going as <X>~1/f^2 in the white noise limit, where f is the deviation from the critical force. In the case of long range correlated noise, where the integrated autocorrelation is divergent, we find that <X> is finite at f=0, with its value decreasing as the correlations become longer range. This shows that long range correlations actually stabilize the DNA sequence against unzipping. Our result is also in agreement with the findings of Allahverdyan et al, obtained using numerical generation of the long range correlated noise.


title: A Probabilistic Attack on NP-complete Problems

abstract: Using the probability theory-based approach, this paper reveals the equivalence of an arbitrary NP-complete problem to a problem of checking whether a level set of a specifically constructed harmonic cost function (with all diagonal entries of its Hessian matrix equal to zero) intersects with a unit hypercube in many-dimensional Euclidean space. This connection suggests the possibility that methods of continuous mathematics can provide crucial insights into the most intriguing open questions in modern complexity theory.


title: Optical and Near-IR long-term monitoring of NGC3783 and MR2251-178: evidence for variable near-IR emission from thin accretion discs

abstract: We present long term near-IR light curves for two nearby AGN: NGC3783 and MR2251-178. The near-IR data are complemented with optical photometry obtained over the same period of time. The light curves in all bands are highly variable and good correlations can be seen between optical and NIR variations. Cross-correlation analysis for NGC 3783 suggests that some disc near-IR emission is present in the J-band flux, while the H and K-bands are dominated by emission from a torus located at the dust sublimation radius. For MR2251-178 the cross-correlation analysis and the optical-near-IR flux-flux plots suggest that the near-IR flux is dominated by disc emission. We model the optical to near-IR Spectral Energy Distributions (SED) of both sources and find that disc flaring might be a necessary modification to the geometry of a thin disc in order to explain the observations. The SED of MR2251-178 gives some indications for the presence of NIR emission from a torus. Finally, we consider the implications of the standard alpha disc model to explain the different origin of the variable NIR emission in these AGN.


title: Obliquely rotating pulsars: screening of the inductive electric field

abstract: Pulsar electrodynamics has been built up by taking ingredients from two models, the vacuum-dipole model, which ignores the magnetosphere but includes the inductive electric field due to the obliquely rotating magnetic dipole, and the corotating-magnetosphere model, which neglects the vacuum inductive electric field and assumes a corotating magnetosphere. We argue that the inductive field can be neglected only if it is screened by a current, ${\bi J}_{\rm sc}$, which we calculate for a rigidly rotating magnetosphere. Screening of the parallel component of the inductive field can be effective, but the perpendicular component cannot be screened in a pulsar magnetosphere. The incompletely screened inductive electric field has not been included in any model for a pulsar magnetosphere, and taking it into account has important implications. One effect is that it implies that the magnetosphere cannot be corotating, and we suggest that drift relative to corotation offers a natural explanation for the drifting of subpulses. A second effect is that this screening of the parallel inductive electric field must break down in the outer magnetosphere, and this offers a natural explanation for the acceleration of the electrons that produce pulsed gamma-ray emission.


title: Existence of Dyons in Minimally Gauged Skyrme Model via Constrained Minimization

abstract: We prove the existence of electrically and magnetically charged particlelike static solutions, known as dyons, in the minimally gauged Skyrme model developed by Brihaye, Hartmann, and Tchrakian. The solutions are spherically symmetric, depend on two continuous parameters, and carry unit monopole and magnetic charges but continuous Skyrme charge and non-quantized electric charge induced from the 't Hooft electromagnetism. The problem amounts to obtaining a finite-energy critical point of an indefinite action functional, arising from the presence of electricity and the Minkowski spacetime signature. The difficulty with the absence of the Higgs field is overcome by achieving suitable strong convergence and obtaining uniform decay estimates at singular boundary points so that the negative sector of the action functional becomes tractable.


title: Acyclic embeddings of open Riemann surfaces into new examples of elliptic manifolds

abstract: The geometric notion of ellipticity for complex manifolds was introduced by Gromov in his seminal 1989 paper on the Oka principle, and is a sufficient condition for a manifold to be Oka. In the current paper we present contributions to three open questions involving elliptic and Oka manifolds. We show that quotients of C^n by discrete groups of affine transformations are elliptic. Combined with an example of Margulis, this yields new examples of elliptic manifolds with free fundamental groups and vanishing higher homotopy. Finally we show that every open Riemann surface embeds acyclically into an elliptic manifold, giving a partial answer to a question of Larusson.


title: Thermodynamics of (2+1) flavor QGP in quasiparticle model

abstract: Using our recently developed one parameter quasiparticle model, we analyze more recent (refined) results of (2+1) flavor QGP in lattice simulation of QCD by various groups \cite{f.1,k.1,u.1,d.1}. We got a remarkable good fit to lattice thermodynamics of Ref. Szabolcs Borsanyi {\it et al.}, [hep-lat/1007.2580v2] and reasonable good fit to Ref. A. Bazavov {\it it al.}, Phys. Rev. {\bf D80}, 014504 (2009) by adjusting single parameter of the model which may be related QCD scale parameter. Further we extend our model for above system with zero chemical potential to non-zero chemical potential and predict quark density without any new parameters which may be compared with future lattice data.


title: Approximating Tverberg Points in Linear Time for Any Fixed Dimension

abstract: Let P be a d-dimensional n-point set. A Tverberg-partition of P is a partition of P into r sets P_1, ..., P_r such that the convex hulls conv(P_1), ..., conv(P_r) have non-empty intersection. A point in the intersection of the conv(P_i)'s is called a Tverberg point of depth r for P. A classic result by Tverberg implies that there always exists a Tverberg partition of size n/(d+1), but it is not known how to find such a partition in polynomial time. Therefore, approximate solutions are of interest. We describe a deterministic algorithm that finds a Tverberg partition of size n/4(d+1)^3 in time d^{O(log d)} n. This means that for every fixed dimension we can compute an approximate Tverberg point (and hence also an approximate centerpoint) in linear time. Our algorithm is obtained by combining a novel lifting approach with a recent result by Miller and Sheehy (2010).


title: Superfluid/ferromagnet/superfluid-junction and $\pi$-phase in a superfluid Fermi gas at finite temperatures

abstract: We investigate the stability of $\pi$-phase in a polarized superfluid Fermi gas ($N_\uparrow>N_\downarrow$, where $N_\sigma$ is the number of atoms in the hyperfine state described by pseudospin-$\sigma$). In our previous paper [T. Kashimura, S. Tsuchiya, and Y. Ohashi, Phys. Rev. A {\bf 82}, 033617 (2010)], we showed that excess atoms ($\Delta N=N_\uparrow-N_\downarrow$) localized around a potential barrier embedded in the system induces the $\pi$-phase at T=0, where the phase of superfluid order parameter differ by $\pi$ across the junction. In this paper, we extend our previous work to include temperature effects within the mean-field theory. We show that the $\pi$-phase is stable even at finite temperatures, although transition from the $\pi$-phase to 0-phase eventually occurs at a certain temperature. Our results indicate that the $\pi$-phase is experimentally accessible in cold Fermi gases.


title: Calabi-Yau Problem for Legendrian curves in C^3 and applications

abstract: We construct a complete, bounded Legendrian immersion in C^3. As direct applications of it, we show the first examples of a weakly complete bounded flat front in hyperbolic 3-space, a weakly complete bounded flat front in de Sitter 3-space, and a weakly complete bounded improper affine front in R^3.


title: Bose-Einstein condensate in gases of rare atomic species

abstract: We report on the successful extension of production of Bose-Einstein Condensate (BEC) to rare species. Despite its low natural abundance of 0.13%, $^{168}$Yb is directly evaporatively cooled down to BEC. Our successful demonstration encourages attempts to obtain quantum gases of radioactive atoms, which extends the possibility of quantum many-body physics and precision measurement. Moreover, a stable binary mixture of $^{168}$Yb BEC and $^{174}$Yb BEC is successfully formed.


title: Observation of the antimatter helium-4 nucleus at RHIC

abstract: We present the observation of the \Heebar nucleus, the heaviest antinucleus observed to date. In total, 18 \Heebar counts were detected at the STAR experiment at RHIC in 10$^{9}$ recorded Au+Au collisions at beam energies of $\sqrt{s_{NN}}$ = 200 GeV and 62 GeV. The background has been estimated, and the misidentification probability is found to be lower than 10$^{-11}$.


title: Graphene-Wrapped Sulfur Particles as a Rechargeable Lithium-Sulfur-Battery Cathode Material with High Capacity and Cycling Stability

abstract: We report the synthesis of a graphene-sulfur composite material by wrapping polyethyleneglycol (PEG) coated submicron sulfur particles with mildly oxidized graphene oxide sheets decorated by carbon black nanoparticles. The PEG and graphene coating layers are important to accommodating volume expansion of the coated sulfur particles during discharge, trapping soluble polysulfide intermediates and rendering the sulfur particles electrically conducting. The resulting graphene-sulfur composite showed high and stable specific capacities up to ~600mAh/g over more than 100 cycles, representing a promising cathode material for rechargeable lithium batteries with high energy density.


title: Non-Markovian dynamics of system-reservoir entanglement

abstract: Using an exact approach, we study the dynamics of entanglement between two qubits coupled to independent reservoirs and between the two, initially disentangled, reservoirs. We also describe the transfer of bipartite entanglement from the two-qubits to their respective reservoirs focussing on the case of two atoms inside two different leaky cavities with a specific attention to the role of the detuning. We present a scheme to prepare the cavity fields in a maximally entangled state, without direct interaction between the cavities, by exploiting the initial qubits entanglement. We discuss a deterministic protocol, working in the presence of cavity losses, for the generation of a W-state of one qubit and two cavity fields and we describe a probabilistic scheme to entangle one of the atoms with the reservoir (cavity field) of the other atom.


title: LiMn1-xFexPO4 Nanorods Grown on Graphene Sheets for Ultra-High Rate Performance Lithium Ion Batteries

abstract: Following the successful utilization of LiFePO4 as a novel cathode material for rechargeable lithium batteries, interest and efforts have grown in the research of another olivine structured material LiMnPO4 due to its higher operating potential voltage and energy density. However, high rate performance for LiMnPO4-based cathode materials has been challenging due to its extremely low electrical and ionic conductivities. Here, we develop a synthesis of Fe-doped LiMnPO4 (LiMn0.75Fe0.25PO4) nanorods directly bonded on graphene sheets (reduced from graphene oxide) to render LiMn0.75Fe0.25PO4 nanorods superior electrical conductivity. The LiMn0.75Fe0.25PO4 nanorod morphology is unique to materials grown on graphene over those grown in free solution, and is ideal for fast Li+ diffusion with the diffusion path of [010] crystallographic axis along the short radial direction (~20-30nm) of the nanorods. These together lead to ultrafast discharge within ~30-40 seconds without using a high carbon content. With high columbic efficiency above 99.5% at a high operating voltage, our LiMn0.75Fe0.25PO4 nanorods/graphene hybrid exhibits the best rate performance among all doped LiMnPO4 cathode materials for Lithium ion batteries.


title: Nonlinear Analysis of the Solutions of the Hasegawa-Wakatani Equations

abstract: The Hasegawa-Wakatani models are used in the study of confinement of hot plasmas with externally imposed magnetic fields. The nonlinear terms in the Hasegawa-Wakatani models complicate the analysis of the system as they propagate local changes across the entire system. Centre manifold analysis allows us to project down onto much smaller systems that are more easily analysed. Qualitative information about the behaviour of the reduced system, such as whether it is stable or unstable, can be used to predict the behaviour of the original full system. We show how the simple structure of the linear part of the Hasegawa-Wakatani equations can be used to define these projection operators. The centre manifold analysis will be used on a few examples to highlight certain properties of the Hasegawa-Wakatani models.


title: Electric transport through circular graphene quantum dots: Presence of disorder

abstract: The electronic states of an electrostatically confined cylindrical graphene quantum dot and the electric transport through this device are studied theoretically within the continuum Dirac-equation approximation and compared with numerical results obtained from a tight-binding lattice description. A spectral gap, which may originate from strain effects, additional adsorbed atoms or substrate-induced sublattice-symmetry breaking, allows for bound and scattering states. As long as the diameter of the dot is much larger than the lattice constant, the results of the continuum and the lattice model are in very good agreement. We also investigate the influence of a sloping dot-potential step, of on-site disorder along the sample edges, of uncorrelated short-range disorder potentials in the bulk, and of random magnetic-fluxes that mimic ripple-disorder. The quantum dot's spectral and transport properties depend crucially on the specific type of disorder. In general, the peaks in the density of bound states are broadened but remain sharp only in the case of edge disorder.


title: Origin of the unconventional magnetoresistance in Sr2FeMoO6

abstract: The unusual magnetoresistance (MR) behavior in Sr2FeMoO6, recently termed as spin-valve type MR (SVMR), presents several anomalies that are little understood so far. The difficulty in probing the origin of this phenomenon, arising from the magnetic property of only a small volume fraction of the ferromagnetic bulk, is circumvented in the present study by the use of ac susceptibility measurements that are sensitive to the slope rather than the magnitude of the magnetization. The present study unravels a spin-glass (SG) like surface layer around each soft ferromagnetic (FM) grain of Sr2FeMoO6. It is also observed that there is a very strong exchange coupling between the two, generating `exchange bias' effect, which consequently creates the `valve', responsible for the unusual MR effects.