@article{11762, abstract = {In this paper, we describe six algorithmic problems that arise in web search engines and that are not or only partially solved: (1) Uniformly sampling of web pages; (2) modeling the web graph; (3) finding duplicate hosts; (4) finding top gainers and losers in data streams; (5) finding large dense bipartite graphs; and (6) understanding how eigenvectors partition the web.}, author = {Henzinger, Monika H}, issn = {1944-9488}, journal = {Internet Mathematics}, number = {1}, pages = {115--123}, publisher = {Internet Mathematics}, title = {{Algorithmic challenges in web search engines}}, doi = {10.1080/15427951.2004.10129079}, volume = {1}, year = {2004}, } @inproceedings{11801, abstract = {Web search engines have emerged as one of the central applications on the internet. In fact, search has become one of the most important activities that people engage in on the Internet. Even beyond becoming the number one source of information, a growing number of businesses are depending on web search engines for customer acquisition. In this talk I will brief review the history of web search engines: The first generation of web search engines used text-only retrieval techniques. Google revolutionized the field by deploying the PageRank technology – an eigenvector-based analysis of the hyperlink structure- to analyze the web in order to produce relevant results. Moving forward, our goal is to achieve a better understanding of a page with a view towards producing even more relevant results. Google is powered by a large number of PCs. Using this infrastructure and striving to be as efficient as possible poses challenging systems problems but also various algorithmic challenges. I will discuss some of them in my talk.}, author = {Henzinger, Monika H}, booktitle = {2th Annual European Symposium on Algorithms}, isbn = { 3540230254}, issn = {1611-3349}, location = {Bergen, Norway}, pages = {3}, publisher = {Springer Nature}, title = {{Algorithmic aspects of web search engines}}, doi = {10.1007/978-3-540-30140-0_2}, volume = {3221}, year = {2004}, } @inproceedings{11800, abstract = {Web search engines have emerged as one of the central applications on the Internet. In fact, search has become one of the most important activities that people engage in on the the Internet. Even beyond becoming the number one source of information, a growing number of businesses are depending on web search engines for customer acquisition. The first generation of web search engines used text-only retrieval techniques. Google revolutionized the field by deploying the PageRank technology – an eigenvector-based analysis of the hyperlink structure – to analyze the web in order to produce relevant results. Moving forward, our goal is to achieve a better understanding of a page with a view towards producing even more relevant results.}, author = {Henzinger, Monika H}, booktitle = {31st International Colloquium on Automata, Languages and Programming}, issn = {1611-3349}, location = {Turku, Finland}, pages = {3}, publisher = {Springer Nature}, title = {{The past, present, and future of web search engines}}, doi = {10.1007/978-3-540-27836-8_2}, volume = {3142}, year = {2004}, } @inproceedings{11859, abstract = {In this article we describe the approach taken by the first web search engines, discuss the state of the art, and present some of the challenges for the future.}, author = {Henzinger, Monika H}, booktitle = {SPIE Proceedings}, issn = {0277-786X}, location = {San Jose, CA, United States}, pages = {23 -- 26}, publisher = {Society of Photo-Optical Instrumentation Engineers}, title = {{The past, present, and future of web information retrieval}}, doi = {10.1117/12.537534}, volume = {5296}, year = {2004}, } @article{11877, abstract = {The World Wide Web provides a unprecedented opportunity to automatically analyze a large sample of interests and activity in the world. We discuss methods for extracting knowledge from the web by randomly sampling and analyzing hosts and pages, and by analyzing the link structure of the web and how links accumulate over time. A variety of interesting and valuable information can be extracted, such as the distribution of web pages over domains, the distribution of interest in different areas, communities related to different topics, the nature of competition in different categories of sites, and the degree of communication between different communities or countries.}, author = {Henzinger, Monika H and Lawrence, Steve}, issn = {1091-6490}, journal = {Proceedings of the National Academy of Sciences}, number = {suppl_1}, pages = {5186--5191}, publisher = {Proceedings of the National Academy of Sciences}, title = {{Extracting knowledge from the World Wide Web}}, doi = {10.1073/pnas.0307528100}, volume = {101}, year = {2004}, } @article{12658, abstract = {[1] During the ablation period 2001 a glaciometeorological experiment was carried out on Haut Glacier d'Arolla, Switzerland. Five meteorological stations were installed on the glacier, and one permanent automatic weather station in the glacier foreland. The altitudes of the stations ranged between 2500 and 3000 m a.s.l., and they were in operation from end of May to beginning of September 2001. The spatial arrangement of the stations and temporal duration of the measurements generated a unique data set enabling the analysis of the spatial and temporal variability of the meteorological variables across an alpine glacier. All measurements were taken at a nominal height of 2 m, and hourly averages were derived for the analysis. The wind regime was dominated by the glacier wind (mean value 2.8 m s−1) but due to erosion by the synoptic gradient wind, occasionally the wind would blow up the valley. A slight decrease in mean 2 m air temperatures with altitude was found, however the 2 m air temperature gradient varied greatly and frequently changed its sign. Mean relative humidity was 71% and exhibited limited spatial variation. Mean incoming shortwave radiation and albedo both generally increased with elevation. The different components of shortwave radiation are quantified with a parameterization scheme. Resulting spatial variations are mainly due to horizon obstruction and reflections from surrounding slopes, i.e., topography. The effect of clouds accounts for a loss of 30% of the extraterrestrial flux. Albedos derived from a Landsat TM image of 30 July show remarkably constant values, in the range 0.49 to 0.50, across snow covered parts of the glacier, while albedo is highly spatially variable below the zone of continuous snow cover. These results are verified with ground measurements and compared with parameterized albedo. Mean longwave radiative fluxes decreased with elevation due to lower air temperatures and the effect of upper hemisphere slopes. It is shown through parameterization that this effect would even be more pronounced without the effect of clouds. Results are discussed with respect to a similar study which has been carried out on Pasterze Glacier (Austria). The presented algorithms for interpolating, parameterizing and simulating variables and parameters in alpine regions are integrated in the software package AMUNDSEN which is freely available to be adapted and further developed by the community.}, author = {Strasser, Ulrich and Corripio, Javier and Pellicciotti, Francesca and Burlando, Paolo and Brock, Ben and Funk, Martin}, issn = {0148-0227}, journal = {Journal of Geophysical Research: Atmospheres}, keywords = {Paleontology, Space and Planetary Science, Earth and Planetary Sciences (miscellaneous), Atmospheric Science, Earth-Surface Processes, Geochemistry and Petrology, Soil Science, Water Science and Technology, Ecology, Aquatic Science, Forestry, Oceanography, Geophysics}, number = {D3}, publisher = {American Geophysical Union}, title = {{Spatial and temporal variability of meteorological variables at Haut Glacier d'Arolla (Switzerland) during the ablation season 2001: Measurements and simulations}}, doi = {10.1029/2003jd003973}, volume = {109}, year = {2004}, } @article{1456, abstract = {We study the space of L2 harmonic forms on complete manifolds with metrics of fibred boundary or fibred cusp type. These metrics generalize the geometric structures at infinity of several different well-known classes of metrics, including asymptotically locally Euclidean manifolds, the (known types of) gravitational instantons, and also Poincaré metrics on ℚ-rank 1 ends of locally symmetric spaces and on the complements of smooth divisors in Kähler manifolds. The answer in all cases is given in terms of intersection cohomology of a stratified compactification of the manifold. The L2 signature formula implied by our result is closely related to the one proved by Dai and more generally by Vaillant and identifies Dai's τ-invariant directly in terms of intersection cohomology of differing perversities. This work is also closely related to a recent paper of Carron and the forthcoming paper of Cheeger and Dai. We apply our results to a number of examples, gravitational instantons among them, arising in predictions about L2 harmonic forms in duality theories in string theory.}, author = {Tamas Hausel and Hunsicker, Eugénie and Mazzeo, Rafe R}, journal = {Duke Mathematical Journal}, number = {3}, pages = {485 -- 548}, publisher = {Duke University Press}, title = {{Hodge cohomology of gravitational instantons}}, doi = {10.1215/S0012-7094-04-12233-X}, volume = {122}, year = {2004}, } @article{1464, abstract = {The moduli space of stable vector bundles on a Riemann surface is smooth when the rank and degree are coprime, and is diffeomorphic to the space of unitary connections of central constant curvature. A classic result of Newstead and Atiyah and Bott asserts that its rational cohomology ring is generated by the universal classes, that is, by the Kunneth components of the Chern classes of the universal bundle. This paper studies the larger, non-compact moduli space of Higgs bundles, as introduced by Hitchin and Simpson, with values in the canonical bundle K. This is diffeomorphic to the space of all connections of central constant curvature, whether unitary or not. The main result of the paper is that, in the rank 2 case, the rational cohomology ring of this space is again generated by universal classes. The spaces of Higgs bundles with values in K(n) for n > 0 turn out to be essential to the story. Indeed, we show that their direct limit has the homotopy type of the classifying space of the gauge group, and hence has cohomology generated by universal classes. 2000 Mathematics Subject Classification 14H60 (primary), 14D20, 14H81, 32Q55, 58D27 (secondary). }, author = {Tamas Hausel and Thaddeus, Michael}, journal = {Proceedings of the London Mathematical Society}, number = {3}, pages = {632 -- 658}, publisher = {Oxford University Press}, title = {{Generators for the cohomology ring of the moduli space of rank 2 higgs bundles}}, doi = {10.1112/S0024611503014618}, volume = {88}, year = {2004}, } @article{1963, abstract = {The mechanism coupling electron transfer and proton pumping in respiratory complex I (NADH-ubiquinone oxidoreductase) has not been established, but it has been suggested that it involves conformational changes. Here, the influence of substrates on the conformation of purified complex I from Escherichia coli was studied by cross-linking and electron microscopy. When a zero-length cross-linking reagent was used, the presence of NAD(P)H, in contrast to that of NAD+, prevented the formation of cross-links between the hydrophilic subunits of the complex, including NuoB, NuoI, and NuoCD. Comparisons using different cross-linkers suggested that NuoB, which is likely to coordinate the key iron-sulfur cluster N2, is the most mobile subunit. The presence of NAD(P)H led also to enhanced proteolysis of subunit NuoG. These data indicate that upon NAD(P)H binding, the peripheral arm of the complex adopts a more open conformation, with increased distances between subunits. Single particle analysis showed the nature of this conformational change. The enzyme retains its L-shape in the presence of NADH, but exhibits a significantly more open or expanded structure both in the peripheral arm and, unexpectedly, in the membrane domain also.}, author = {Mamedova, Aygun A and Holt, Peter J and Carroll, Joe D and Leonid Sazanov}, journal = {Journal of Biological Chemistry}, number = {22}, pages = {23830 -- 23836}, publisher = {American Society for Biochemistry and Molecular Biology}, title = {{Substrate-induced conformational change in bacterial complex I}}, doi = {10.1074/jbc.M401539200}, volume = {279}, year = {2004}, } @article{209, author = {Timothy Browning and Heath-Brown, Roger}, journal = {Inventiones Mathematicae}, number = {3}, pages = {553 -- 573}, publisher = {Unknown}, title = {{Equal sums of three powers}}, doi = {10.1007/s00222-004-0360-9}, volume = {157}, year = {2004}, } @article{2308, abstract = {It is widely believed that the inflammatory events mediated by microglial activation contribute to several neurodegenerative processes. Alzheimer's disease, for example, is characterized by an accumulation of β-amyloid protein (Aβ) in neuritic plaques that are infiltrated by reactive microglia and astrocytes. Although Aβ and its fragment 25-35 exert a direct toxic effect on neurons, they also activate microglia. Microglial activation is accompanied by morphological changes, cell proliferation, and release of various cytokines and growth factors. A number of scientific reports suggest that the increased proliferation of microglial cells is dependent on ionic membrane currents and in particular on chloride conductances. An unusual chloride ion channel known to be associated with macrophage activation is the chloride intracellular channel-1 (CLIC1). Here we show that Aβ stimulation of neonatal rat microglia specifically leads to the increase in CLIC1 protein and to the functional expression of CLIC1 chloride conductance, both barely detectable on the plasma membrane of quiescent cells. CLIC1 protein expression in microglia increases after 24 hr of incubation with Aβ, simultaneously with the production of reactive nitrogen intermediates and of tumor necrosis factor-α (TNF-α). We demonstrate that reducing CLIC1 chloride conductance by a specific blocker [IAA-94 (R(+)-[(6,7-dichloro-2-cyclopentyl-2,3-dihydro-2-methyl-1-oxo-1H-inden-5yl)-oxy] acetic acid)] prevents neuronal apoptosis in neurons cocultured with Aβ-treated microglia. Furthermore, we show that small interfering RNAs used to knock down CLIC1 expression prevent TNF-α release induced by Aβ stimulation. These results provide a direct link between Aβ-induced microglial activation and CLIC1 functional expression.}, author = {Gaia Novarino and Fabrizi, Cinzia and Tonini, Raffaella and Denti, Michela A and Malchiodi, Albedi F and Lauro, Giuliana M and Sacchetti, Benedetto and Paradisi, Silvia and Ferroni, Arnaldo and Curmi, Paul M G and Breit, Samuel N and Mazzanti, Michele}, journal = {Journal of Neuroscience}, number = {23}, pages = {5322 -- 5330}, publisher = {Society for Neuroscience}, title = {{Involvement of the intracellular ion channel CLIC1 in microglia-mediated β-amyloid-induced neurotoxicity}}, doi = {10.1523/JNEUROSCI.1170-04.2004}, volume = {24}, year = {2004}, } @article{2356, abstract = {Recent experimental and theoretical work has shown that there are conditions in which a trapped, low-density Bose gas behaves like the one-dimensional delta-function Bose gas solved years ago by Lieb and Liniger. This is an intrinsically quantum-mechanical phenomenon because it is not necessary to have a trap width that is the size of an atom - as might have been supposed - but it suffices merely to have a trap width such that the energy gap for motion in the transverse direction is large compared to the energy associated with the motion along the trap. Up to now the theoretical arguments have been based on variational - perturbative ideas or numerical investigations. In contrast, this paper gives a rigorous proof of the one-dimensional behavior as far as the ground state energy and particle density are concerned. There are four parameters involved: the particle number, N, transverse and longitudinal dimensions of the trap, r and L, and the scattering length a of the interaction potential. Our main result is that if r/L → 0 and N → ∞ the ground state energy and density can be obtained by minimizing a one-dimensional density functional involving the Lieb-Liniger energy density with coupling constant ∼ a/r 2. This density functional simplifies in various limiting cases and we identify five asymptotic parameter regions altogether. Three of these, corresponding to the weak coupling regime, can also be obtained as limits of a three-dimensional Gross-Pitaevskii theory. We also show that Bose-Einstein condensation in the ground state persists in a part of this regime. In the strong coupling regime the longitudinal motion of the particles is strongly correlated. The Gross-Pitaevskii description is not valid in this regime and new mathematical methods come into play.}, author = {Lieb, Élliott H and Robert Seiringer and Yngvason, Jakob}, journal = {Communications in Mathematical Physics}, number = {2}, pages = {347 -- 393}, publisher = {Springer}, title = {{One-dimensional behavior of dilute, trapped Bose gases}}, doi = {10.1007/s00220-003-0993-3}, volume = {244}, year = {2004}, } @article{2355, abstract = {The BMV conjecture for traces, which states that Tr exp(A - λB) is the Laplace transform of a positive measure, is shown to be equivalent to two other statements: (i) The polynomial λ → Tr(A + λB) p has only non-negative coefficients for all A, B ≥ 0, p ∈ ℕ and (ii) λ → Tr(A + λB)-p is the Laplace transform of a positive measure for A, B ≥ 0, p > 0.}, author = {Lieb, Élliott H and Robert Seiringer}, journal = {Journal of Statistical Physics}, number = {1-2}, pages = {185 -- 190}, publisher = {Springer}, title = {{ Equivalent forms of the Bessis-Moussa-Villani conjecture}}, doi = {10.1023/B:JOSS.0000019811.15510.27}, volume = {115}, year = {2004}, } @article{2360, abstract = {An optical lattice model developed that is similar to the Bose-Hubbard model to describe the transition between Bose-Einstein condensation (BEC) and a Mott insulator state was analyzed. It was found that the system was a hard core lattice gas at half of the maximum density and the optical lattice was modeled by a periodic potential of strength λ. It was also observed that the interparticle interaction was essential for this transition that occurred even in the ground state. The results show that all the essential features could be proved rigorously such as the existence of BEC for small λ and its suppression for a large λ.}, author = {Aizenman, Michael and Lieb, Élliott H and Robert Seiringer and Solovej, Jan P and Yngvason, Jakob}, journal = {Physical Review A - Atomic, Molecular, and Optical Physics}, number = {2}, pages = {023612 -- 1--0236121--2}, publisher = {American Physical Society}, title = {{Bose-Einstein quantum phase transition in an optical lattice model}}, doi = {10.1103/PhysRevA.70.023612}, volume = {70}, year = {2004}, } @inbook{2417, author = {Lovász, László and Vesztergombi, Katalin and Uli Wagner and Welzl, Emo}, booktitle = {Towards a Theory of Geometric Graphs}, editor = {Pach, János}, pages = {139 -- 148}, publisher = {American Mathematical Society}, title = {{Convex quadrilaterals and k-sets }}, doi = {10.1090/conm/342}, volume = {342}, year = {2004}, } @article{2426, abstract = {We introduce the adaptive neighborhood graph as a data structure for modeling a smooth manifold M embedded in some Euclidean space ℝ d. We assume that M is known to us only through a finite sample P ⊂ M, as is often the case in applications. The adaptive neighborhood graph is a geometric graph on P. Its complexity is at most min{2O(k)n, n2}, where n = P and k = dim M, as opposed to the n[d/2] complexity of the Delaunay triangulation, which is often used to model manifolds. We prove that we can correctly infer the connected components and the dimension of M from the adaptive neighborhood graph provided a certain standard sampling condition is fulfilled. The running time of the dimension detection algorithm is d20(k7 log k) for each connected component of M. If the dimension is considered constant, this is a constant-time operation, and the adaptive neighborhood graph is of linear size. Moreover, the exponential dependence of the constants is only on the intrinsic dimension k, not on the ambient dimension d. This is of particular interest if the co-dimension is high, i.e., if k is much smaller than d, as is the case in many applications. The adaptive neighborhood graph also allows us to approximate the geodesic distances between the points in P.}, author = {Giesen, Joachim and Uli Wagner}, journal = {Discrete & Computational Geometry}, number = {2}, pages = {245 -- 267}, publisher = {Springer}, title = {{Shape dimension and intrinsic metric from samples of manifolds}}, doi = {10.1007/s00454-004-1120-8}, volume = {32}, year = {2004}, } @article{2425, abstract = {A finite set N ⊂ Rd is a weak ε-net for an n-point set X ⊂ Rd (with respect to convex sets) if N intersects every convex set K with |K ∩ X| ≥ εn. We give an alternative, and arguably simpler, proof of the fact, first shown by Chazelle et al., that every point set X in Rd admits a weak ε-net of cardinality O(ε-dpolylog(1/ε)). Moreover, for a number of special point sets (e.g., for points on the moment curve), our method gives substantially better bounds. The construction yields an algorithm to construct such weak ε-nets in time O(n ln(1/ε)).}, author = {Matoušek, Jiří and Uli Wagner}, journal = {Discrete & Computational Geometry}, number = {2}, pages = {195 -- 206}, publisher = {Springer}, title = {{New constructions of weak ε-nets}}, doi = {10.1007/s00454-004-1116-4}, volume = {32}, year = {2004}, } @misc{2461, author = {Sauer, Michael and Friml, Jirí}, booktitle = {Development}, number = {23}, pages = {5774 -- 5775}, publisher = {Company of Biologists}, title = {{The Matryoshka dolls of plant polarity}}, doi = {10.1242/dev.01463}, volume = {131}, year = {2004}, } @article{2642, abstract = {In the hippocampal CA1 region, metabotropic glutamate subtype 1 (mGluR1) receptors have been implicated in a variety of physiological responses to glutamate, which include modulation of synaptic transmission and plasticity, as well as neuronal excitability and synchronization. The mGluR1α isoform is characteristically expressed only by nonprincipal cells, and it is particularly enriched in somatostatin (SS -containing interneurons in stratum oriens-alveus. Anatomical and physiological data have indicated the presence of mGluR1α in several distinct classes of interneurons with their somata located also in strata pyramidale, radiatum, and lacunosum moleculare. Each different interneuron subtype, as defined by functionally relevant criteria, including input/output characteristics and expression of selective molecular markers, subserves distinct functions in local hippocampal circuits. We have investigated which of the different CA1 interneuron classes express mGluR1α by immunofluorescent labeling, combining antibodies to mGluR1α, calcium-binding proteins, and neuropeptides, and by intracellular labeling in vitro. Several types of interneuron that are immunopositive for mGluR1α each targeted different domains of pyramidal cells and included (1) O-LM interneurons, found to coexpress both SS and parvalbumin (PV); (2) interneurons with target selectivity for other interneurons, expressing vasoactive intestinal polypeptide (VIP) and/or the calcium-binding protein calretinin; (3) procholecystokinin-immunopositive interneurons probably non-basket and dendrite-targeting; and (4) an as-yet unidentified SS-immunoreactive but PV-immunonegative interneuron class, possibly corresponding to oriensbistratified cells. Estimation of the relative proportion of mGluR1α-positive interneurons showed 43%, 46%, and 30% co-labeling with SS, VIP, or PV, respectively. The identification of the specific subclasses of CA1 interneurons expressing mGluR1α provides the network basis for assessing the contribution of this receptor to the excitability of the hippocampus.}, author = {Ferraguti, Francesco and Cobden, Philip M and Pollard, Marie and Cope, David W and Ryuichi Shigemoto and Watanabe, Masahiko and Somogyi, Péter}, journal = {Hippocampus}, number = {2}, pages = {193 -- 215}, publisher = {Wiley-Blackwell}, title = {{Immunolocalization of metabotropic glutamate receptor 1α (mGluR1α) in distinct classes of interneuron in the CA1 region of the rat hippocampus}}, doi = {10.1002/hipo.10163}, volume = {14}, year = {2004}, } @article{2639, abstract = {Vesicular glutamate transporter type 3 (VGLUT3) containing neuronal elements were characterized using antibodies to VGLUT3 and molecular cell markers. All VGLUT3-positive somata were immunoreactive for CCK, and very rarely, also for calbindin; none was positive for parvalbumin, calretinin, VIP or somatostatin. In the CA1 area, 26.8 ± 0.7% of CCK-positive interneuron somata were VGLUT3-positive, a nonoverlapping 22.8 ± 1.9% were calbindin-positive, 10.7 ± 2.5% VIP-positive and the rest were only CCK-positive. The patterns of coexpression were similar in the CA3 area, the dentate gyrus and the isocortex. Immunoreactivity for VGLUT3 was undetectable in pyramidal and dentate granule cells. Boutons colabelled for VGLUT3, CCK and GAD were most abundant in the cellular layers of the hippocampus and in layers II-III of the isocortex. Large VGLUT3-labelled boutons at the border of strata radiatum and lacunosum-moleculare in the CA1 area were negative for GAD, but were labelled for vesicular monoamine transporter type 2, plasmalemmal serotonin transporter or serotonin. No colocalization was found in terminals between VGLUT3 and parvalbumin, vesicular acetylcholine transporter and group III (mGluR7a,b; mGluR8a,b) metabotropic glutamate receptors. In stratum radiatum and the isocortex, VGLUT3-positive but GAD-negative boutons heavily innervated the soma and proximal dendrites of some VGLUT3- or calbindin-positive interneurons. The results suggest that boutons coexpressing VGLUT3, CCK and GAD originate from CCK-positive basket cells, which are VIP-immunonegative. Other VGLUT3-positive boutons immunopositive for serotonergic markers but negative for GAD probably originate from the median raphe nucleus and innervate select interneurons. The presumed amino acid substrate of VGLUT3 may act on presynaptic kainate or group II metabotropic glutamate receptors.}, author = {Somogyi, Jozsef and Baude, Agnès and Omori, Yuko and Shimizu, Hidemi and El-Mestikawy, Salah and Fukaya, Masahiro and Ryuichi Shigemoto and Watanabe, Masahiko and Somogyi, Péter}, journal = {European Journal of Neuroscience}, number = {3}, pages = {552 -- 569}, publisher = {Wiley-Blackwell}, title = {{GABAergic basket cells expressing cholecystokinin contain vesicular glutamate transporter type 3 (VGLUT3) in their synaptic terminals in hippocampus and isocortex of the rat}}, doi = {10.1111/j.0953-816X.2003.03091.x}, volume = {19}, year = {2004}, }