181 citations
- University of British ColumbiaCA4 papers
- University of California, BerkeleyUS4 papers
- Eindhoven University of TechnologyNL3 papers
- Hebrew University of JerusalemIL3 papers
- Charles UniversityCZ2 papers
- Courant Institute of Mathematical SciencesUS2 papers
- Microsoft Research (United Kingdom)GB2 papers
- University of California, Los AngelesUS2 papers
- University of Illinois Urbana-ChampaignUS2 papers
- Weizmann Institute of ScienceIL2 papers
- Australian National UniversityAU1 paper
- Board of the Swiss Federal Institutes of TechnologyCH1 paper
17 papers · 1 filter
Measured descent: A new embedding method for finite metrics
Robert Krauthgamer, James R. Lee, Manor Mendel +1
We devise a new embedding technique, which we call measured descent, based on decomposing a metric space locally, at varying speeds, according to the density of some probability me…
Limits of dense graph sequences
Laszlo Lovasz, Balazs Szegedy
We show that if a sequence of dense graphs has the property that for every fixed graph F, the density of copies of F in these graphs tends to a limit, then there is a natural ``lim…
The rank of connection matrices and the dimension of graph algebras
Laszlo Lovasz
Connection matrices were introduced by Freedman, Lovasz and Schrijver [1], who used them to characterize graph homomorphism functions. The goal of this note is to determine the exa…
Consensus on Transaction Commit
Jim Gray, Leslie Lamport
The distributed transaction commit problem requires reaching agreement on whether a transaction is committed or aborted. The classic Two-Phase Commit protocol blocks if the coordin…
Supersingular primes for points on
David Jao
For small odd primes , we prove that most of the rational points on the modular curve parametrize pairs of elliptic curves having infinitely many supersingular prim…
Metric structures in L_1: Dimension, snowflakes, and average distortion
James R. Lee, Manor Mendel, Assaf Naor
We study the metric properties of finite subsets of L_1. The analysis of such metrics is central to a number of important algorithmic problems involving the cut structure of weight…