Sherali-Adams Relaxations and Indistinguishability in Counting Logics

Two graphs with adjacency matrices $\mathbf{A}$ and $\mathbf{B}$ are isomorphic if there exists a permutation matrix $\mathbf{P}$ for which the identity $\mathbf{P}^{\mathrm{T}} \mathbf{A} \mathbf{P} = \mathbf{B}$ holds. Multiplying through by $\mathbf{P}$ and relaxing the permutation matrix to a doubly stochastic matrix leads to the linear programming relaxation known as fractional isomorphism. We show that the levels of the Sherali--Adams (SA) hierarchy of linear programming relaxations applied to fractional isomorphism interleave in power with the levels of a well-known color-refinement heuristic for graph isomorphism called the Weisfeiler--Lehman algorithm, or, equivalently, with the levels of indistinguishability in a logic with counting quantifiers and a bounded number of variables. This tight connection has quite striking consequences. For example, it follows immediately from a deep result of Grohe in the context of logics with counting quantifiers that a fixed number of levels of SA suffice to determine isomorphism of planar and minor-free graphs. We also offer applications in both finite model theory and polyhedral combinatorics. First, we show that certain properties of graphs, such as that of having a flow circulation of a prescribed value, are definable in the infinitary logic with counting with a bounded number of variables. Second, we exploit a lower bound construction due to Cai, Fürer, and Immerman in the context of counting logics to give simple explicit instances that show that the SA relaxations of the vertex-cover and cut polytopes do not reach their integer hulls for up to $\Omega(n)$ levels, where $n$ is the number of vertices in the graph.

Geography of talent and regional differences in Spain

Tentative empirical evidence suggests that the agglomeration of talent contributes to regional development. However, given that talented people are not evenly distributed across regions, this paper seeks to determine how the concentration of talent affects patterns of regional development. Here, we empirically evaluate the effects of the distribution of talent on regional differences by means of a detailed analysis of the 17 Autonomous Communities of Spain between 1996 and 2004. We hypothesise that regions specialising in strategic sectors that are creative and which can be assumed to enjoy rapid growth in productivity will experience faster rates of development and, in turn, that this concentration of talent will have a positive impact on the region’s economic performance. Thus, we believe that this mechanism can explain the marked regional imbalances in Spain. Our findings confirm that regional differences, measured in terms of GDP per capita and by, - industrial and service- oriented production, are influenced by the Communities’ talent bases as determined by, educational attainment and employment in assumed to be strategic for regional development, inasmuch as these sectors provide economic specialization.

Productivity and innovation spillovers: Micro evidence from Spain

This article analyses the impact that innovation expenditure and intrasectoral and intersectoral externalities have on productivity in Spanish firms. While there is an extensive literature analysing the relationship between innovation and productivity, in this particular area there are far fewer studies that examine the importance of sectoral externalities, especially with the focus on Spain. One novelty of the study, which covers the industrial and service sectors, is that we also consider jointly the technology level of the sector in which the firm operates and the firm size. The database used is the Technological Innovation Panel, PITEC, which includes 12,813 firms for the year 2008 and has been little used in this type of study. The estimation method used is Iteratively Reweighted Least Squares method, IRLS, which is very useful for obtaining robust estimations in the presence of outliers. The results confirm that innovation has a positive effect on productivity, especially in high-tech and large firms. The impact of externalities is more heterogeneous because, while intrasectoral externalities have a poitive and significant effect, especially in low-tech firms independently of size, intersectoral externalities have a more ambiguous effect, being clearly significant for advanced industries in which size has a positive effect.

Asymptotic analysis of stock price densities and implied volatilities in mixed stochastic models

In this paper, we obtain sharp asymptotic formulas with error estimates for the Mellin con- volution of functions de ned on (0;1), and use these formulas to characterize the asymptotic behavior of marginal distribution densities of stock price processes in mixed stochastic models. Special examples of mixed models are jump-di usion models and stochastic volatility models with jumps. We apply our general results to the Heston model with double exponential jumps, and make a detailed analysis of the asymptotic behavior of the stock price density, the call option pricing function, and the implied volatility in this model. We also obtain similar results for the Heston model with jumps distributed according to the NIG law.

Determinació de compostos orgànics contaminants en aigües residuals industrials

La determinació de compostos orgànics contaminants en aigües residuals d’origen urbà i industrial és un tema que ha suscitat un creixent interès, tant des del punt de vista del problema mediambiental que es deriva de l’abocament d’aquestes aigües al medi aquàtic públic com des de la perspectiva de reutilització de les aigües tractades en processos industrials. La majoria d’aquests contaminants no s’eliminen completament en plantes de tractament d’aigües convencionals, pel que s’han de controlar. Aquest fet implica desenvolupar nous processos de tractament que permetin millorar l'eficiència de l'eliminació de les plantes de tractament convencionals. Per tal d'investigar la presència d'aquests compostos contaminants a baixes concentracions és necessari desenvolupar nous mètodes analítics altament sensibles. En el nostre projecte s'han desenvolupat diferents mètodes analítics per determinar compostos orgànics contaminants en aigües residuals provinents de plantes de tractament d'aigües industrials, urbanes i plantes potabilitzadores, utilizant principalment la microextracció en fase sòlida (SPME) seguida de la cromatografia de gasos acoblada a un espectròmetre de masses (GC-MS). S'ha estudiat la presència de diferents famílies de compostos en aquestes aigües, com són: ftalats, amines alifàtiques primàries i nitrosamines. A més a més, s'han desenvolupat mètodes analítics per determinar amines alifàtiques primàries en llots actius provinents de diferents tipus de plantes de tractament d'aigües i plantes potabilitzadores.

Tienda virtual para una empresa de muebles de cocina

El projecte estarà dedicat a dos tipus de clients: particulars i industrials ia la gestió que s'haurà de fer dels productes oferts (altes, baixes, manteniments, etc.). El web estarà configurada en un servidor d'aplicacions i constarà de dues parts: La interfície de l'administrador per al manteniment dels clients i articles i la interfície del client que li permetrà navegar pel catàleg i així poder fer les comandes dels productes que estiguin interessats. Utilitzarem els estàndards que ofereix el mercat per al programari de servidor (JSP, Struts, J2EE, etc.).

Cardiac injuries in blunt chest trauma

Blunt chest traumas are a clinical challenge, both for diagnosis and treatment. The use ofCardiovascular Magnetic Resonance can play a major role in this setting. We present two cases: a12-year-old boy and 45-year-old man. Late gadolinium enhancement imaging enabled visualizationof myocardial damage resulting from the trauma.

Characterization of myocardial deformation in patients with different etiologies of left ventricular hypertrophy by using strain distribution from Magnetic Resonance Imaging

Introducción y objetivos. Se ha señalado que, en la miocardiopatía hipertrófica (MCH), la desorganización de las fibras regionales da lugar a segmentos en los que la deformación es nula o está gravemente reducida, y que estos segmentos tienen una distribución no uniforme en el ventrículo izquierdo (VI). Esto contrasta con lo observado en otros tipos de hipertrofia como en el corazón de atleta o la hipertrofia ventricular izquierda hipertensiva (HVI-HT), en los que puede haber una deformación cardiaca anormal, pero nunca tan reducida como para que se observe ausencia de deformación. Así pues, proponemos el empleo de la distribución de los valores de strain para estudiar la deformación en la MCH. Métodos. Con el empleo de resonancia magnética marcada (tagged), reconstruimos la deformación sistólica del VI de 12 sujetos de control, 10 atletas, 12 pacientes con MCH y 10 pacientes con HVI-HT. La deformación se cuantificó con un algoritmo de registro no rígido y determinando los valores de strain sistólico máximo radial y circunferencial en 16 segmentos del VI. Resultados. Los pacientes con MCH presentaron unos valores medios de strain significativamente inferiores a los de los demás grupos. Sin embargo, aunque la deformación observada en los individuos sanos y en los pacientes con HVI-HT se concentraba alrededor del valor medio, en la MCH coexistían segmentos con contracción normal y segmentos con una deformación nula o significativamente reducida, con lo que se producía una mayor heterogeneidad de los valores de strain. Se observaron también algunos segmentos sin deformación incluso en ausencia de fibrosis o hipertrofia. Conclusiones. La distribución de strain caracteriza los patrones específicos de deformación miocárdica en pacientes con diferentes etiologías de la HVI. Los pacientes con MCH presentaron un valor medio de strain significativamente inferior, así como una mayor heterogeneidad de strain (en comparación con los controles, los atletas y los pacientes con HVI-HT), y tenían regiones sin deformación.

Line search multilevel optimization as computational methods for dense optical flow

We evaluate the performance of different optimization techniques developed in the context of optical flow computation with different variational models. In particular, based on truncated Newton methods (TN) that have been an effective approach for large-scale unconstrained optimization, we de- velop the use of efficient multilevel schemes for computing the optical flow. More precisely, we evaluate the performance of a standard unidirectional mul- tilevel algorithm - called multiresolution optimization (MR/OPT), to a bidrec- tional multilevel algorithm - called full multigrid optimization (FMG/OPT). The FMG/OPT algorithm treats the coarse grid correction as an optimiza- tion search direction and eventually scales it using a line search. Experimental results on different image sequences using four models of optical flow com- putation show that the FMG/OPT algorithm outperforms both the TN and MR/OPT algorithms in terms of the computational work and the quality of the optical flow estimation.

Families of periodic orbits for the spatial isosceles 3-body problem

We study the families of periodic orbits of the spatial isosceles 3-body problem (for small enough values of the mass lying on the symmetry axis) coming via the analytic continuation method from periodic orbits of the circular Sitnikov problem. Using the first integral of the angular momentum, we reduce the dimension of the phase space of the problem by two units. Since periodic orbits of the reduced isosceles problem generate invariant two-dimensional tori of the nonreduced problem, the analytic continuation of periodic orbits of the (reduced) circular Sitnikov problem at this level becomes the continuation of invariant two-dimensional tori from the circular Sitnikov problem to the nonreduced isosceles problem, each one filled with periodic or quasi-periodic orbits. These tori are not KAM tori but just isotropic, since we are dealing with a three-degrees-of-freedom system. The continuation of periodic orbits is done in two different ways, the first going directly from the reduced circular Sitnikov problem to the reduced isosceles problem, and the second one using two steps: first we continue the periodic orbits from the reduced circular Sitnikov problem to the reduced elliptic Sitnikov problem, and then we continue those periodic orbits of the reduced elliptic Sitnikov problem to the reduced isosceles problem. The continuation in one or two steps produces different results. This work is merely analytic and uses the variational equations in order to apply Poincar´e’s continuation method.

Trust region versus line search for computing the optical flow

We consider the numerical treatment of the optical flow problem by evaluating the performance of the trust region method versus the line search method. To the best of our knowledge, the trust region method is studied here for the first time for variational optical flow computation. Four different optical flow models are used to test the performance of the proposed algorithm combining linear and nonlinear data terms with quadratic and TV regularization. We show that trust region often performs better than line search; especially in the presence of non-linearity and non-convexity in the model.

Procés de patrimonialització cultural de la central nuclear de Lemoiz (Bizkaia)

El propòsit central d’aquest treball és el de plantejar un procés d’activació del patrimoni cultural i històric, concretament el de la Central Nuclear de Lemoiz (Biscaia). Si la central fos declarada patrimoni industrial i històric es podria establir un punt de partida per a la resolució d’una situació complexa a nivell social, polític, urbanístic i medi-ambiental com és l’existència de la central nuclear

Reliable computation of robust response tori on the verge of breakdown

We prove the existence and local uniqueness of invariant tori on the verge of breakdown for two systems: the quasi-periodically driven logistic map and the quasi-periodically forced standard map. These systems exemplify two scenarios: the Heagy-Hammel route for the creation of strange non- chaotic attractors and the nonsmooth bifurcation of saddle invariant tori. Our proofs are computer- assisted and are based on a tailored version of the Newton-Kantorovich theorem. The proofs cannot be performed using classical perturbation theory because the two scenarios are very far from the perturbative regime, and fundamental hypotheses such as reducibility or hyperbolicity either do not hold or are very close to failing. Our proofs are based on a reliable computation of the invariant tori and a careful study of their dynamical properties, leading to the rigorous validation of the numerical results with our novel computational techniques.

Trust region versus line search for computing the optical flow

We consider the numerical treatment of the optical flow problem by evaluating the performance of the trust region method versus the line search method. To the best of our knowledge, the trust region method is studied here for the first time for variational optical flow computation. Four different optical flow models are used to test the performance of the proposed algorithm combining linear and nonlinear data terms with quadratic and TV regularization. We show that trust region often performs better than line search; especially in the presence of non-linearity and non-convexity in the model.

On the computation of reducible invariant tori on a parallel computer

We present an algorithm for the computation of reducible invariant tori of discrete dynamical systems that is suitable for tori of dimensions larger than 1. It is based on a quadratically convergent scheme that approximates, at the same time, the Fourier series of the torus, its Floquet transformation, and its Floquet matrix. The Floquet matrix describes the linearization of the dynamics around the torus and, hence, its linear stability. The algorithm presents a high degree of parallelism, and the computational effort grows linearly with the number of Fourier modes needed to represent the solution. For these reasons it is a very good option to compute quasi-periodic solutions with several basic frequencies. The paper includes some examples (flows) to show the efficiency of the method in a parallel computer. In these flows we compute invariant tori of dimensions up to 5, by taking suitable sections.