On the complexity of the Whitehead minimization problem

The Whitehead minimization problem consists in finding a minimum size element in the automorphic orbit of a word, a cyclic word or a finitely generated subgroup in a finite rank free group. We give the first fully polynomial algorithm to solve this problem, that is, an algorithm that is polynomial both in the length of the input word and in the rank of the free group. Earlier algorithms had an exponential dependency in the rank of the free group. It follows that the primitivity problem – to decide whether a word is an element of some basis of the free group – and the free factor problem can also be solved in polynomial time.

Avaluació dels algorismes d'encaminament per a una NoC amb topologia Mesh 2D

Aquest projecte presenta una avaluació de les diferents alternatives d'encaminament per a una NoC amb una topologia mesh 2D. Per tal d'exposar aquestes alternatives s'ha estudiat la composició d'un router implementat amb l'algorisme determinista XY i s'ha adaptat per tal que aquest suportés els algorismes parcialment adaptatius West First, North Last i Negative First. Un cop tenim els routers implementats es disposa un estudi dels diferents algorismes i com cadascun d'aquests actuen en front uns mateixos estímuls per tal de crear una comparativa entre ells que ens faciliti una elecció a priori.

The Euler characteristic of a category

The Euler characteristic of a finite category is defined and shown to be compatible with Euler characteristics of other types of object, including orbifolds. A formula is proved for the cardinality of a colimit of sets, generalizing the classical inclusion-exclusion formula. Both rest on a generalization of Rota's Möbius inversion from posets to categories.

Net spaces and boundedness of integral operators

In this paper we introduce new functional spaces which we call the net spaces. Using their properties, the necessary and sufficient conditions for the integral operators to be of strong or weak-type are obtained. The estimates of the norm of the convolution operator in weighted Lebesgue spaces are presented.

Geometria integral i convexitat en espais de curvatura holomorfa constant

En aquest treball es tracten qüestions de la geometria integral clàssica a l'espai hiperbòlic i projectiu complex i a l'espai hermític estàndard, els anomenats espais de curvatura holomorfa constant. La geometria integral clàssica estudia, entre d'altres, l'expressió en termes geomètrics de la mesura de plans que tallen un domini convex fixat de l'espai euclidià. Aquesta expressió es dóna en termes de les integrals de curvatura mitja. Un dels resultats principals d'aquest treball expressa la mesura de plans complexos que tallen un domini fixat a l'espai hiperbòlic complex, en termes del que definim com volums intrínsecs hermítics, que generalitzen les integrals de curvatura mitja. Una altra de les preguntes que tracta la geometria integral clàssica és: donat un domini convex i l'espai de plans, com s'expressa la integral de la s-èssima integral de curvatura mitja del convex intersecció entre un pla i el convex fixat? A l'espai euclidià, a l'espai projectiu i hiperbòlic reals, aquesta integral correspon amb la s-èssima integral de curvatura mitja del convex inicial: se satisfà una propietat de reproductibitat, que no es té en els espais de curvatura holomorfa constant. En el treball donem l'expressió explícita de la integral de la curvatura mitja quan integrem sobre l'espai de plans complexos. L'expressem en termes de la integral de curvatura mitja del domini inicial i de la integral de la curvatura normal en una direcció especial: l'obtinguda en aplicar l'estructura complexa al vector normal. La motivació per estudiar els espais de curvatura holomorfa constant i, en particular, l'espai hiperbòlic complex, es troba en l'estudi del següent problema clàssic en geometria. Quin valor pren el quocient entre l'àrea i el perímetre per a successions de figures convexes del pla que creixen tendint a omplir-lo? Fins ara es coneixia el comportament d'aquest quocient en els espais de curvatura seccional negativa i que a l'espai hiperbòlic real les fites obtingudes són òptimes. Aquí provem que a l'espai hiperbòlic complex, les cotes generals no són òptimes i optimitzem la superior.

HSU-Robbins and Spitzer's theorems for the variations of fractional Brownian motion

Using recent results on the behavior of multiple Wiener-Itô integrals based on Stein's method, we prove Hsu-Robbins and Spitzer's theorems for sequences of correlated random variables related to the increments of the fractional Brownian motion.

Sharp A₂ inequality for haar shift operators

"Vegeu el resum a l'inici del document del fitxer adjunt."

Sharp weighted bounds for fractional integral operators

The relationship between the operator norms of fractional integral operators acting on weighted Lebesgue spaces and the constant of the weights is investigated. Sharp bounds are obtained for both the fractional integral operators and the associated fractional maximal functions. As an application improved Sobolev inequalities are obtained. Some of the techniques used include a sharp off-diagonal version of the extrapolation theorem of Rubio de Francia and characterizations of two-weight norm inequalities.

Optimització i implementació en Simulink de l'adquisició d'un senyal GPS amb blocs FFT

Aquest projecte es tracta de la optimització i la implementació de l’etapa d’adquisició d’un receptor GPS. També inclou una revisió breu del sistema GPS i els seus principis de funcionament. El procés d’adquisició s’ha estudiat amb detall i programat en els entorns de treball Matlab i Simulink. El fet d’implementar aquesta etapa en dos entorns diferents ha estat molt útil tant de cara a l’aprenentatge com també per la comprovació dels resultats obtinguts. El principal objectiu del treball és el disseny d’un model Simulink que es capaç d’adquirir una senyal capturada amb hardware real. En realitat, s’han fet dues implementacions: una que utilitza blocs propis de Simulink i l’altra que utilitza blocs de la llibreria Xilinx. D’aquesta manera, posteriorment, es facilitaria la transició del model a la FPGA utilitzant l’entorn ISE de Xilinx. La implementació de l’etapa d’adquisició es basa en el mètode de cerca de fase de codi en paral·lel, el qual empra la operació correlació creuada mitjançant la transformada ràpida de Fourier (FFT). Per aquest procés es necessari realitzar dues transformades (per a la senyal entrant i el codi de referència) i una antitransformada de Fourier (per al resultat de la correlació). Per tal d’optimitzar el disseny s’utilitza un bloc FFT, ja que tres blocs consumeixen gran part dels recursos d’una FPGA. En lloc de replicar el bloc FFT, en el model el bloc és compartit en el temps gràcies a l’ús de buffers i commutadors, com a resultat la quantitat de recursos requerits per una implementació en una FPGA es podria reduir considerablement.

Application of standard and refined heat balance integral methods to one-dimensional Stefan problems

The work in this paper concerns the study of conventional and refined heat balance integral methods for a number of phase change problems. These include standard test problems, both with one and two phase changes, which have exact solutions to enable us to test the accuracy of the approximate solutions. We also consider situations where no analytical solution is available and compare these to numerical solutions. It is popular to use a quadratic profile as an approximation of the temperature, but we show that a cubic profile, seldom considered in the literature, is far more accurate in most circumstances. In addition, the refined integral method can give greater improvement still and we develop a variation on this method which turns out to be optimal in some cases. We assess which integral method is better for various problems, showing that it is largely dependent on the specified boundary conditions.

Generic Nekhoroshev theory without small divisors

In this article, we present a new approach of Nekhoroshev theory for a generic unperturbed Hamiltonian which completely avoids small divisors problems. The proof is an extension of a method introduced by P. Lochak which combines averaging along periodic orbits with simultaneous Diophantine approximation and uses geometric arguments designed by the second author to handle generic integrable Hamiltonians. This method allows to deal with generic non-analytic Hamiltonians and to obtain new results of generic stability around linearly stable tori.

The eta invariant and equivariant index of transversally elliptic operators

We prove a formula for the multiplicities of the index of an equivariant transversally elliptic operator on a G-manifold. The formula is a sum of integrals over blowups of the strata of the group action and also involves eta invariants of associated elliptic operators. Among the applications, we obtain an index formula for basic Dirac operators on Riemannian foliations, a problem that was open for many years.

The eta invariant and equivariant index of transversally elliptic operators

We prove a formula for the multiplicities of the index of an equivariant transversally elliptic operator on a G-manifold. The formula is a sum of integrals over blowups of the strata of the group action and also involves eta invariants of associated elliptic operators. Among the applications, we obtain an index formula for basic Dirac operators on Riemannian foliations, a problem that was open for many years.

Index theory for basic Dirac operators on Riemannian foliations

In this paper we prove a formula for the analytic index of a basic Dirac-type operator on a Riemannian foliation, solving a problem that has been open for many years. We also consider more general indices given by twisting the basic Dirac operator by a representation of the orthogonal group. The formula is a sum of integrals over blowups of the strata of the foliation and also involves eta invariants of associated elliptic operators. As a special case, a Gauss-Bonnet formula for the basic Euler characteristic is obtained using two independent proofs.