528 citations
- New York UniversityUS86 papers
- Johns Hopkins UniversityUS10 papers
- Princeton UniversityUS9 papers
- Microsoft (United States)US5 papers
- Duke UniversityUS4 papers
- Google (United States)US4 papers
- University of RochesterUS4 papers
- California Institute of TechnologyUS3 papers
- Columbia UniversityUS3 papers
- Cornell UniversityUS3 papers
- Eindhoven University of TechnologyNL3 papers
- ETH ZurichCH3 papers
6 papers · 1 filter
Simple Proofs of Classical Theorems in Discrete Geometry via the Guth--Katz Polynomial Partitioning Technique
Haim Kaplan, Jiří Matoušek, Micha Sharir
Recently Guth and Katz \cite{GK2} invented, as a step in their nearly complete solution of Erdős's distinct distances problem, a new method for partitioning finite point sets in $\…
Deterministic Random Walks on the Integers
Joshua Cooper, Benjamin Doerr, Joel Spencer +1
Jim Propp's P-machine, also known as the "rotor router model" is a simple deterministic process that simulates a random walk on a graph. Instead of distributing chips to randomly c…
Counting Connected Graphs Asymptotically
Remco van der Hofstad, Joel Spencer
We find the asymptotic number of connected graphs with vertices and edges when approach infinity, reproving a result of Bender, Canfield and McKay. We use the {\e…
Collinear Points in Permutations
J. Cooper, J. Solymosi
Consider the following problem: how many collinear triples of points must a transversal of (Z/nZ)^2 have? This question is connected with venerable issues in discrete geometry. We…
Generalized de Bruijn Cycles
Joshua N. Cooper, Ronald L. Graham
For a set of integers , we define a -ary -cycle to be a assignment of the symbols 1 through to the integers modulo so that every word appears on some translate o…
Simulating a Random Walk with Constant Error
Joshua N. Cooper, Joel Spencer
We analyze Jim Propp's P-machine, a simple deterministic process that simulates a random walk on to within a constant. The proof of the error bound relies on several estimate…