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.

Directional discrepancy in two dimensions

In the present paper, we study the geometric discrepancy with respect to families of rotated rectangles. The well-known extremal cases are the axis-parallel rectangles (logarithmic discrepancy) and rectangles rotated in all possible directions (polynomial discrepancy). We study several intermediate situations: lacunary sequences of directions, lacunary sets of finite order, and sets with small Minkowski dimension. In each of these cases, extensions of a lemma due to Davenport allow us to construct appropriate rotations of the integer lattice which yield small discrepancy.

Inversion of analytic characteristic functions and infinite convolutions of exponential and Laplace densities

This paper shows that certain quotients of entire functions are characteristic functions. Under some conditions, we provide expressions for the densities of such characteristic functions which turn out to be generalized Dirichlet series which in turn can be expressed as an infinite linear combination of exponential or Laplace densities. We apply these results to several examples.

Aspects of Iwasawa theory over function fields

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

On graphs with few disjoint t-stars

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

A general multiserver state-dependent queueing system

The work studies a general multiserver queue in which the service time of an arriving customer and the next interarrival period may depend on both the current waiting time and the server assigned to the arriving customer. Stability of the system is proved under general assumptions on the predetermined distributions describing the model. The proof exploits a combination of the Markov property of the workload process with a regenerative property of the process. The key idea leading to stability is a characterization of the limit behavior of the forward renewal process generated by regenerations. Extensions of the basic model are also studied.

Ribet bimodules and the specialization of Heegner points

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

A one-dimensional Keller-Segel equation with a drift issued from the boundary

We investigate in this note the dynamics of a one-dimensional Keller-Segel type model on the half-line. On the contrary to the classical configuration, the chemical production term is located on the boundary. We prove, under suitable assumptions, the following dichotomy which is reminiscent of the two-dimensional Keller-Segel system. Solutions are global if the mass is below the critical mass, they blow-up in finite time above the critical mass, and they converge to some equilibrium at the critical mass. Entropy techniques are presented which aim at providing quantitative convergence results for the subcritical case. This note is completed with a brief introduction to a more realistic model (still one-dimensional).

Level-wise node size distribution of randomly generated regular trees

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

Coefficients of Drinfeld modular forms and Hecke operators

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

Propagation connectivity of random hypergraphs

We study the concept of propagation connectivity on random 3-uniform hypergraphs. This concept is inspired by a simple linear time algorithm for solving instances of certain constraint satisfaction problems. We derive upper and lower bounds for the propagation connectivity threshold, and point out some algorithmic implications.

Efectos de lo real. Discursos acerca de los cuerpos artificiales

Los cuerpos artificiales ( muñecos, autómatas, maniquíes) son tratados a través de tres tipos de discurso: del artificio, de la mirada y del deseo. Esta perspectiva permite abordarlos, no como representaciones ni como dobles (Döppelgänger) sino como significantes en el discurso , como objetos de deseo y como puntos de articulación de la mirada. En el discurso del artificio se pasa revista al binomio natural/artificial y , a través de distintos textos , El tratado de Hombre de René Descarrtes, la “teoría de los maniquíes” y la “generatio aequivoca” de Bruno Schulz, y el film Jidlo (Comida) de Jan Svankmajer, se hace lo propio con los paradigmas desde los que se ha metaforizado al cuerpo humano. En el discurso de la mirada, se los aborda desde la perspectiva psicoanalítica del campo escópico, a través de El hombre de la arena, de ETA Hoffmann. Los discursos del deseo tratan de algunos aspectos de esta pulsión : el deseo masculino desde La Eva futura de Villiers de l’Isle Adam, el “deseo de hijo”, a través del film Otesánek de Jan Svankmajer y la genericidad del deseo en dos novelas de Gaston Leroux , La muñeca sangrienta y la máquina de asesinar . Los cuerpos artificiales, así, podrían ser considerados, en su potencia significativa, no ya como dobles , sino como efectos de lo real, como “pequeños otros”, como “objetos a” lacanianos y como simulacros.

La poética del desig: amor i bogeria a l'Orlando furioso

Aquesta tesina, amb el títol "La poètica del desig. amor i bogeria a l'Orlando furioso", proposa una nova lectura del poema de Ludovico Ariosto, prenent com a objectiu l'anàlisi de la bogeria del seu protagonista, el Comte Orlando, "che per amor venne in furore e matto / d'uom che sì saggio era stimato prima". Així doncs, pretenem esbrinar per què davant de la constatació de Matteo Maria Boiardo d'un "Orlando innmorato", Ariosto va respondre amb un "Orlando furioso", narrant així "cosa non detta in prosa mai né in rima". Per arribar fins al fons de la qüestió, ens hem preguntat quins són l'origen, la manifestació textual, la dimensió i el significat del concepte de "furor" en el text; interrogants que ens han conduït cap a una bogeria amorosa que és manifestació externa d'un desig insatisfet. Un concepte que, a més a més d'evocar l"Hercules furens" d'Eurípides i Sèneca, ens remet a la teoria dels humors de Galè, al concepte de 'melancholia' d'Aristòtil i a l'eròtica platònica, al mateix temps que reprodueix els models del que Cesare Segre anomena la 'follie littéraire' característica de l'època medieval. A partir d'aquesta anàlisi s'ha interpretat el text com una apologia de les passions en la que es destrona al savi com a paradigma i model ètic, acabant així amb la imatge de l'home com a "animal rationale", situant per contra la seva "humanitas" ja no en la racionalitat (tampoc en la irracionalitat), sinó en la passionalitat, oferint així un retrat de l'ésser humà com a "animal passionalis" , una criatura intermitja en la que haurien de confluir idealment raó i passió.

Lévy area for Gaussian processes: A double Wiener--Itô integral approach

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

Dinàmica de sistemes mesoscòpics amb correlacions quàntiques mitjançant la formulació de de Broglie-Bohm

Per a determinar la dinàmica espai-temporal completa d’un sistema quàntic tridimensional de N partícules cal integrar l’equació d’Schrödinger en 3N dimensions. La capacitat dels ordinadors actuals permet fer-ho com a molt en 3 dimensions. Amb l’objectiu de disminuir el temps de càlcul necessari per a integrar l’equació d’Schrödinger multidimensional, es realitzen usualment una sèrie d’aproximacions, com l’aproximació de Born–Oppenheimer o la de camp mig. En general, el preu que es paga en realitzar aquestes aproximacions és la pèrdua de les correlacions quàntiques (o entrellaçament). Per tant, és necessari desenvolupar mètodes numèrics que permetin integrar i estudiar la dinàmica de sistemes mesoscòpics (sistemes d’entre tres i unes deu partícules) i en els que es tinguin en compte, encara que sigui de forma aproximada, les correlacions quàntiques entre partícules. Recentment, en el context de la propagació d’electrons per efecte túnel en materials semiconductors, X. Oriols ha desenvolupat un nou mètode [Phys. Rev. Lett. 98, 066803 (2007)] per al tractament de les correlacions quàntiques en sistemes mesoscòpics. Aquesta nova proposta es fonamenta en la formulació de la mecànica quàntica de de Broglie– Bohm. Així, volem fer notar que l’enfoc del problema que realitza X. Oriols i que pretenem aquí seguir no es realitza a fi de comptar amb una eina interpretativa, sinó per a obtenir una eina de càlcul numèric amb la que integrar de manera més eficient l’equació d’Schrödinger corresponent a sistemes quàntics de poques partícules. En el marc del present projecte de tesi doctoral es pretén estendre els algorismes desenvolupats per X. Oriols a sistemes quàntics constituïts tant per fermions com per bosons, i aplicar aquests algorismes a diferents sistemes quàntics mesoscòpics on les correlacions quàntiques juguen un paper important. De forma específica, els problemes a estudiar són els següents: (i) Fotoionització de l’àtom d’heli i de l’àtom de liti mitjançant un làser intens. (ii) Estudi de la relació entre la formulació de X. Oriols amb la aproximació de Born–Oppenheimer. (iii) Estudi de les correlacions quàntiques en sistemes bi- i tripartits en l’espai de configuració de les partícules mitjançant la formulació de de Broglie–Bohm.