TY - JOUR
AB - We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has to be conflict-free, in the sense that in every interval I there is a color that appears exactly once in I. We present deterministic and randomized algorithms for achieving this goal, and analyze their performance, that is, the maximum number of colors that they need to use, as a function of the number n of inserted points. We first show that a natural and simple (deterministic) approach may perform rather poorly, requiring Ω(√̃) colors in the worst case. We then derive two efficient variants of this simple algorithm. The first is deterministic and uses O(log 2 n) colors, and the second is randomized and uses O(log n) colors with high probability. We also show that the O(log 2 n) bound on the number of colors used by our deterministic algorithm is tight on the worst case. We also analyze the performance of the simplest proposed algorithm when the points are inserted in a random order and present an incomplete analysis that indicates that, with high probability, it uses only O(log n) colors. Finally, we show that in the extension of this problem to two dimensions, where the relevant ranges are disks, n colors may be required in the worst case.
AU - Chent, Ke
AU - Fiat, Amos
AU - Kaplan, Haim
AU - Levy, Meital B
AU - Matoušek, Jiří
AU - Mossel, Elchanan
AU - Pach, János
AU - Sharir, Micha
AU - Smorodinsky, Shakhar
AU - Uli Wagner
AU - Welzl, Emo
ID - 2430
IS - 5
JF - SIAM Journal on Computing
TI - Online conflict-free coloring for intervals
VL - 36
ER -
TY - CONF
AB - We prove an upper bound, tight up to a factor of 2, for the number of vertices of level at most t in an arrangement of n halfspaces in R , for arbitrary n and d (in particular, the dimension d is not considered constant). This partially settles a conjecture of Eckhoff, Linhart, and Welzl. Up to the factor of 2, the result generalizes McMullen's Upper Bound Theorem for convex polytopes (the case ℓ = O) and extends a theorem of Linhart for the case d ≤ 4. Moreover, the bound sharpens asymptotic estimates obtained by Clarkson and Shor. The proof is based on the h-matrix of the arrangement (a generalization, introduced by Mulmuley, of the h-vector of a convex polytope). We show that bounding appropriate sums of entries of this matrix reduces to a lemma about quadrupels of sets with certain intersection properties, and we prove this lemma, up to a factor of 2, using tools from multilinear algebra. This extends an approach of Alon and Kalai, who used linear algebra methods for an alternative proof of the classical Upper Bound Theorem. The bounds for the entries of the h-matrix also imply bounds for the number of i-dimensional faces, i > 0, at level at most ℓ. Furthermore, we discuss a connection with crossing numbers of graphs that was one of the main motivations for investigating exact bounds that are valid for arbitrary dimensions.
AU - Uli Wagner
ID - 2431
TI - On a geometric generalization of the Upper Bound Theorem
ER -
TY - JOUR
AB - The highest densities of the two metabotropic GABA subunits, GABA B1 and GABAB2, have been reported as occurring around the glutamatergic synapses between Purkinje cell spines and parallel fibre varicosities. In order to determine how this distribution is achieved during development, we investigated the expression pattern and the cellular and subcellular localization of the GABAB1 and GABAB2 subunits in the rat cerebellum during postnatal development. At the light microscopic level, immunoreactivity for the GABAB1 and GABAB2 subunits was very prominent in the developing molecular layer, especially in Purkinje cells. Using double immunofluorescence, we demonstrated that GABAB1 was transiently expressed in glial cells. At the electron microscopic level, immunoreactivity for GABAB receptors was always detected both pre- and postsynaptically. Presynaptically, GABAB1 and GABAB2 were localized in the extrasynaptic membrane of parallel fibres at all ages, and only rarely in GABAergic axons. Postsynaptically, GABAB receptors were localized to the extrasynaptic and perisynaptic plasma membrane of Purkinje cell dendrites and spines throughout development. Quantitative analysis and three-dimensional reconstructions further revealed a progressive developmental movement of the GABAB1 subunit on the surface of Purkinje cells from dendritic shafts to its final destination, the dendritic spines. Together, these results indicate that GABAB receptors undergo dynamic regulation during cerebellar development in association with the establishment and maturation of glutamatergic synapses to Purkinje cells.
AU - Luján, Rafael
AU - Ryuichi Shigemoto
ID - 2657
IS - 6
JF - European Journal of Neuroscience
TI - Localization of metabotropic GABA receptor subunits GABAB1 and GABAB2 relative to synaptic sites in the rat developing cerebellum
VL - 23
ER -
TY - JOUR
AB - Transmembrane AMPA receptor regulatory proteins (TARPs), including stargazin/γ-2, are associated with AMPA receptors and participate in their surface delivery and anchoring at the postsynaptic membrane. TARPs may also act as a positive modulator of the AMPA receptor ion channel function; however, little is known about other TARP members except for stargazin/γ-2. We examined the synaptic localization of stargazin/γ-2 and γ-8 by immunoelectron microscopy and biochemical analysis. The analysis of sodium dodecyl sulfate-digested freeze-fracture replica labeling revealed that stargazin/γ-2 was concentrated in the postsynaptic area, whereas γ-8 was distributed both in synaptic and extra-synaptic plasma membranes of the hippocampal neuron. When a synaptic plasma membrane-enriched brain fraction was treated with Triton X-100 and separated by sucrose density gradient ultracentrifugation, a large proportion of NMDA receptor and stargazin/γ-2 was accumulated in raft-enriched fractions, whereas AMPA receptor and γ-8 were distributed in both the raft-enriched fractions and other Triton-insoluble fractions. Phosphorylation of stargazin/γ-2 and γ-8 was regulated by different sets of kinases and phosphatases in cultured cortical neurons. These results suggested that stargazin/γ-2 and γ-8 have distinct roles in postsynaptic membranes under the regulation of different intracellular signaling pathways.
AU - Inamura, Mihoko
AU - Itakura, Makoto
AU - Okamoto, Hirotsugu
AU - Hoka, Sumio
AU - Mizoguchi, Akira
AU - Fukazawa, Yugo
AU - Ryuichi Shigemoto
AU - Yamamori, Saori
AU - Takahashi, Masami
ID - 2659
IS - 1
JF - Neuroscience Research
TI - Differential localization and regulation of stargazin-like protein, γ-8 and stargazin in the plasma membrane of hippocampal and cortical neurons
VL - 55
ER -
TY - JOUR
AB - Pavlovian fear conditioning, a simple form of associative learning, is thought to involve the induction of associative, NMDA receptor-dependent long-term potentiation (LTP) in the lateral amygdala. Using a combined genetic and electrophysiological approach, we show here that lack of a specific GABAB receptor subtype, GABAB(1a,2), unmasks a nonassociative, NMDA receptor-independent form of presynaptic LTP at cortico-amygdala afferents. Moreover, the level of presynaptic GABA B(1a,2) receptor activation, and hence the balance between associative and nonassociative forms of LTP, can be dynamically modulated by local inhibitory activity. At the behavioral level, genetic loss of GABA B(1a) results in a generalization of conditioned fear to nonconditioned stimuli. Our findings indicate that presynaptic inhibition through GABAB(1a,2) receptors serves as an activity-dependent constraint on the induction of homosynaptic plasticity, which may be important to prevent the generalization of conditioned fear.
AU - Shaban, Hamdy
AU - Humeau, Yann
AU - Herry, Cyril
AU - Cassasus, Guillaume
AU - Ryuichi Shigemoto
AU - Ciocchi, Stéphane
AU - Barbieri, Samuel
AU - Van Der Putten, Herman V
AU - Kaupmann, Klemens
AU - Bettler, Bernhard
AU - Lüthi, Andreas
ID - 2660
IS - 8
JF - Nature Neuroscience
TI - Generalization of amygdala LTP and conditioned fear in the absence of presynaptic inhibition
VL - 9
ER -