Carmin.tv

Mathématiques
et Interactions

Merci de nous donner votre avis pour que nous puissions améliorer votre expérience !
Not Only Scalar Curvature Seminar
74 videos

Not Only Scalar Curvature Seminar

Geometric structures and discrete group actions / Structures géométriques et actions de groupes discrets
4 videos

Geometric structures and discrete group actions / Structures géométriques et actions de groupes discrets

Misha Gromov : Mathematical Description of Biological Structures
4 videos

Misha Gromov : Mathematical Description of Biological Structures

Applications of NonCommutative Geometry to Gauge Theories, Field Theories, and Quantum Space-Time / Applications de la Géométrie Non Commutative aux Théories de Jauge, à la Théorie des Champs et aux Espaces-Temps Quantiques
5 videos

Applications of NonCommutative Geometry to Gauge Theories, Field Theories, and Quantum Space-Time / Applications de la Géométrie Non Commutative aux Théories de Jauge, à la Théorie des Champs et aux Espaces-Temps Quantiques

Toutes les collections
CIMPA
CIRM
IHES
IHP
LMR
SMF
Tous les instituts
2016 - T1 - WS2 - Fundamental inequalities and lower bounds theme

Collection 2016 - T1 - WS2 - Fundamental inequalities and lower bounds theme

Organisateur(s) Green Larsen, Kasper ; Hassibi, Babak ; Kerenidis, Iordanis ; Yeung, Raymond
Date(s) 15/02/2016 - 26/02/2016
URL associée https://web.archive.org/web/20221228152146/http://iss.bu.edu/bobak/csnexus//inequalities.html
00:00:00 / 00:00:00
34 51

Rectangle inequalities for data structure lower bounds

De Yitong Yin

The richness lemma is a classic rectangle-based technique for asymmetric communication complexity and cell-probe lower bounds. The technique was enhanced by the Patrascu-Thorup’s direct-sum approach to prove higher cell-probe lower bounds. In this talk, I will give an improved richness lemma which generalizes the previous ones and may support even higher cell-probe lower bounds. Combined with the isoperimetric inequalities, we give an Ω(d) cell-probe lower bound for the nearest neighbor search problem when the data structure is of linear size.

Informations sur la vidéo

  • Date de publication 14/03/2016
  • Institut IHP
  • Licence CC BY-NC-ND
  • Langue Anglais
  • Format MP4

Domaine(s)

Codes MSC

Dernières questions liées sur MathOverflow

Pour poser une question, votre compte Carmin.tv doit être connecté à mathoverflow

Poser une question sur MathOverflow




Inscrivez-vous

  • Mettez des vidéos en favori
  • Ajoutez des vidéos à regarder plus tard &
    conservez votre historique de consultation
  • Commentez avec la communauté
    scientifique
  • Recevez des notifications de mise à jour
    de vos sujets favoris
Copyright Carmin.tv 2025
En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies pour améliorer votre expérience. En savoir plus sur notre politique de confidentialité.
Accepter
Donner son avis