Bounding right-arm rotation distances

Rotation distance quantifies the difference in shape between two rooted binary trees of the same size by counting the minimum number of elementary changes needed to transform one tree to the other. We describe several types of rotation distance, and provide upper bounds on distances between trees with a fixed number of nodes with respect to each type. These bounds are obtained by relating each restricted rotation distance to the word length of elements of Thompson's group F with respect to different generating sets, including both finite and infinite generating sets.

Absolute type shaft encoding using LFSR

Maximal-length binary sequences have been known for a long time. They have many interesting properties, one of them is that when taken in blocks of n consecutive positions they form 2ⁿ-1 different codes in a closed circular sequence. This property can be used for measuring absolute angular positions as the circle can be divided in as many parts as different codes can be retrieved. This paper describes how can a closed binary sequence with arbitrary length be effectively designed with the minimal possible block-length, using linear feedback shift registers (LFSR). Such sequences can be used for measuring a specified exact number of angular positions, using the minimal possible number of sensors that linear methods allow.

Tree automorphisms and quasi-isometries of Thompson's group F

We prove that automorphisms of the infinite binary rooted tree T2 do not yield quasi-isometries of Thompson's group F, except for the map which reverses orientation on the unit interval, a natural outer automorphism of F. This map, together with the identity map, forms a subgroup of Aut(T2) consisting of 2-adic automorphisms, following standard terminology used in the study of branch groups. However, for more general p, we show that the analgous groups of p-adic tree automorphisms do not give rise to quasiisometries of F(p).

Communication for Public Goods

This paper studies information transmission between multiple agents with di¤erent preferences and a welfare maximizing decision maker who chooses the quality or quantity of a public good (e.g. provision of public health service; carbon emissions policy; pace of lectures in a classroom) that is consumed by all of them. Communication in such circumstances suffers from the agents' incentive to "exaggerate" their preferences relative to the average of the other agents, since the decision maker's reaction to each agent's message is weaker than in one-to-one communication. As the number of agents becomes larger the quality of information transmission diminishes. The use of binary messages (e.g. "yes" or "no") is shown to be a robust mode of communication when the main source of informational distortion is exaggeration.

Códigos binarios no lineales en MAGMA

La finalitat d'aquest projecte és aconseguir representar codis binaris no lineals de manera eficient en un ordinador. Per fer-ho, hem desenvolupat funcions per representar un codi binari a partir del super dual. Hem millorat la funció de càlcul del kernel d'un codi binari, implementada en projectes d'anys anteriors. També hem desenvolupat un paquet software per l'intèrpret MAGMA. Aquest paquet ens proveeix d'eines per al tractament de codis binaris no necessàriament lineals.

Disentangling the effects of key innovations on the diversification of Bromelioideae (bromeliaceae).

The evolution of key innovations, novel traits that promote diversification, is often seen as major driver for the unequal distribution of species richness within the tree of life. In this study, we aim to determine the factors underlying the extraordinary radiation of the subfamily Bromelioideae, one of the most diverse clades among the neotropical plant family Bromeliaceae. Based on an extended molecular phylogenetic data set, we examine the effect of two putative key innovations, that is, the Crassulacean acid metabolism (CAM) and the water-impounding tank, on speciation and extinction rates. To this aim, we develop a novel Bayesian implementation of the phylogenetic comparative method, binary state speciation and extinction, which enables hypotheses testing by Bayes factors and accommodates the uncertainty on model selection by Bayesian model averaging. Both CAM and tank habit were found to correlate with increased net diversification, thus fulfilling the criteria for key innovations. Our analyses further revealed that CAM photosynthesis is correlated with a twofold increase in speciation rate, whereas the evolution of the tank had primarily an effect on extinction rates that were found five times lower in tank-forming lineages compared to tank-less clades. These differences are discussed in the light of biogeography, ecology, and past climate change.

Regiones salientes complejas para aplicaciones de seguimiento facial

Este trabajo presenta una metodología para detectar y realizar el seguimiento de características faciales. En el primer paso del procedimiento se detectan caras mediante Adaboost con cascadas de clasificadores débiles. El segundo paso busca las características internas de la cara mediante el CSR, detectando zonas de interés. Una vez que estas características se capturan, un proceso de tracking basado en el descriptor SIFT, que hemos llamado pseudo-SIFT, es capaz de guardar información sobre la evolución de movimiento en las regiones detectadas. Además, un conjunto de datos públicos ha sido desarrollado con el propósito de compartirlo con otras investigaciones sobre detección, clasificación y tracking. Experimentos reales muestran la robustez de este trabajo y su adaptabilidad para trabajos futuros.

Codis Z2Z4-additius en Magma

En aquest projecte es presenta el desenvolupament d'un paquet d'aplicacions en l'entorn de programació matemàtica Magma, per al tractament dels codis anomenats Z2Z4-additius. Els codis Z2Z4-additius permeten representar alguns codis binaris, com a codis lineals en l'espai dels codis Z2Z4-additius. Aquest fet permetrà l'estudi de tota una sèrie de codis binaris no lineals que fins ara eren intractables.

Sharp Bounds on Heterogeneous Individual Treatment Responses

This paper discusses how to identify individual-specific causal effects of an ordered discrete endogenous variable. The counterfactual heterogeneous causal information is recovered by identifying the partial differences of a structural relation. The proposed refutable nonparametric local restrictions exploit the fact that the pattern of endogeneity may vary across the level of the unobserved variable. The restrictions adopted in this paper impose a sense of order to an unordered binary endogeneous variable. This allows for a uni.ed structural approach to studying various treatment effects when self-selection on unobservables is present. The usefulness of the identi.cation results is illustrated using the data on the Vietnam-era veterans. The empirical findings reveal that when other observable characteristics are identical, military service had positive impacts for individuals with low (unobservable) earnings potential, while it had negative impacts for those with high earnings potential. This heterogeneity would not be detected by average effects which would underestimate the actual effects because different signs would be cancelled out. This partial identification result can be used to test homogeneity in response. When homogeneity is rejected, many parameters based on averages may deliver misleading information.

EEG-based functional brain networks: does the network size matter?

Functional connectivity in human brain can be represented as a network using electroencephalography (EEG) signals. These networks--whose nodes can vary from tens to hundreds--are characterized by neurobiologically meaningful graph theory metrics. This study investigates the degree to which various graph metrics depend upon the network size. To this end, EEGs from 32 normal subjects were recorded and functional networks of three different sizes were extracted. A state-space based method was used to calculate cross-correlation matrices between different brain regions. These correlation matrices were used to construct binary adjacency connectomes, which were assessed with regards to a number of graph metrics such as clustering coefficient, modularity, efficiency, economic efficiency, and assortativity. We showed that the estimates of these metrics significantly differ depending on the network size. Larger networks had higher efficiency, higher assortativity and lower modularity compared to those with smaller size and the same density. These findings indicate that the network size should be considered in any comparison of networks across studies.

Codis no lineals en MAGMA: construcció de codis perfectes

La finalitat d'aquest projecte és aconseguir construir codis binaris perfectes no lineals de manera eficient. Per a fer-ho, hem desenvolupat un paquet de software per a l'intèrpret MAGMA que conté funcions per a la construcció de codis perfectes, càlcul d'invariants de codis i altres funcions complementàries per a fer càlculs sobre les paraules d'un codi.

Intestinal content detection in capsule endoscopy using robust features

This work covers two aspects. First, it generally compares and summarizes the similarities and differences of state of the art feature detector and descriptor and second it presents a novel approach of detecting intestinal content (in particular bubbles) in capsule endoscopy images. Feature detectors and descriptors providing invariance to change of perspective, scale, signal-noise-ratio and lighting conditions are important and interesting topics in current research and the number of possible applications seems to be numberless. After analysing a selection of in the literature presented approaches, this work investigates in their suitability for applications information extraction in capsule endoscopy images. Eventually, a very good performing detector of intestinal content in capsule endoscopy images is presented. A accurate detection of intestinal content is crucial for all kinds of machine learning approaches and other analysis on capsule endoscopy studies because they occlude the field of view of the capsule camera and therefore those frames need to be excluded from analysis. As a so called “byproduct” of this investigation a graphical user interface supported Feature Analysis Tool is presented to execute and compare the discussed feature detectors and descriptor on arbitrary images, with configurable parameters and visualized their output. As well the presented bubble classifier is part of this tool and if a ground truth is available (or can also be generated using this tool) a detailed visualization of the validation result will be performed.

Quality of life: a potentially useful measure to indicate subclinical flares in Crohn disease.

Background:  While quality of life (QoL) is a well-recognised outcome measure of Crohn disease (CD) activity, its influence on other outcome measures, including exacerbation of CD is poorly understood. If QoL measures were to be associated with intestinal inflammatory activity, they might be useful for early detection of subclinical flares. Aims:  We hypothesised that low QoL might be associated with subsequent CD flares. Methods:  A cohort of 318 adult CD patients was observed for 1 year after assessment of baseline characteristics. Data were collected in Swiss university hospitals, regional hospitals and private practices. At inclusion, patients completed the Inflammatory Bowel Disease QoL Questionnaire (gastrointestinal QoL; range: 32 to 224 points) and the Short Form-36 Health Survey (general QoL; range: 35 to 145 points). During follow up, flares were recorded. Binary logistic regression was performed to estimate the relation between QoL and the odds of subsequent flares. Results:  A twofold decrease in the odds of flares (99% CI: 1.1; 4.0) per standard deviation of gastrointestinal QoL and a threefold decrease (99% CI: 1.5; 6.2) per standard deviation of general QoL were observed. Conclusions:  The close association between QoL and subsequent flares suggests that QoL measures might be useful in detecting upcoming flares before they become clinically apparent.

The analysis of approximate quickselect and related problems

Approximate Quickselect, a simple modification of the well known Quickselect algorithm for selection, can be used to efficiently find an element with rank k in a given range [i..j], out of n given elements. We study basic cost measures of Approximate Quickselect by computing exact and asymptotic results for the expected number of passes, comparisons and data moves during the execution of this algorithm. The key element appearing in the analysis of Approximate Quickselect is a trivariate recurrence that we solve in full generality. The general solution of the recurrence proves to be very useful, as it allows us to tackle several related problems, besides the analysis that originally motivated us. In particular, we have been able to carry out a precise analysis of the expected number of moves of the ith element when selecting the jth smallest element with standard Quickselect, where we are able to give both exact and asymptotic results. Moreover, we can apply our general results to obtain exact and asymptotic results for several parameters in binary search trees, namely the expected number of common ancestors of the nodes with rank i and j, the expected size of the subtree rooted at the least common ancestor of the nodes with rank i and j, and the expected distance between the nodes of ranks i and j.