# David Eppstein

Irvine, California

ics.uci.edu/~eppstein

Age: 50

I'm a professor of computer science at the University of California, Irvine, working on graph algorithms and computational geometry.
 2d awarded Nice Answer Dec 5 comment Computing the convex hull of lattice pointsMostly right, but I don't know where you get your bound of $O(n\log M)$ on the number of word operations for integer sorting. When $M$ is large that is worse even than standard comparison sorting algorithms. The number of word operations is as given in my answer: $O(n(1+\frac{\log M}{\log n}))$ or $O(n\sqrt{\log\log n})$. And the orientation tests involve multiplications, so they're a little more than $O(\log M\log\log M)$ per test. Dec 4 comment Fundamental Cycles of a graphsYes, a largest set, and they're all trees iff they all have exactly $n-1$ edges. Dec 4 comment Fundamental Cycles of a graphsThe subsets of edges that do not include any cycles form the independent sets of a matroid. The subsets of edges that don't include all of the unique edges of some cycle form the independent sets of a different matroid. When you have two matroids on the same elements, you can find the largest set that's independent for both of them, in polynomial time. If this set is a tree, you've solved the problem, and if not there is no solution. Dec 4 comment Computing the convex hull of lattice pointsWell, true, but the same reasoning shows that the bit complexity of convex hulls is the same as the bit complexity of sorting, plus $O(n)$ orientation tests, up to constant factors. I was more addressing the part of the question that asked: what can you gain by assuming the inputs are integers? Dec 3 revised Computing the convex hull of lattice pointsadd summary sentence Dec 3 comment Computing the convex hull of lattice pointsI have clarified the sorting order. I mean linear in $n$, without any logs or other factors. Dec 3 revised Computing the convex hull of lattice pointsadded 273 characters in body Dec 3 answered Computing the convex hull of lattice points Nov 29 answered Fundamental Cycles of a graphs Nov 28 revised Labeling vertices in a graphadded 173 characters in body Nov 28 answered Labeling vertices in a graph Nov 28 comment Labeling vertices in a graphIt is polynomial, and when it exists the labeling is unique (up to permutation and flipping of the bits of the labels and insertion/deletion of bits that are the same for all vertices). So solving it for fixed $k$ is not any harder: just find the labeling and then test whether it uses $k$ or fewer bits. The NP-complete problem is a different one where you have to preserve adjacency but not nonadjacency nor distances. Nov 28 comment Fundamental Cycles of a graphsThis looks easy enough to be a homework question. Any motivation for why you're asking? Nov 26 comment expressing $\log(\left \lfloor x \right \rfloor!)$ in terms of zeta-zerosSo, to clarify, you want to reverse the order of nested summation and still get something meaningful? Nov 26 comment expressing $\log(\left \lfloor x \right \rfloor!)$ in terms of zeta-zerosIn what way is plugging in the explicit formula into the sum not already an expression in terms of zeta zeros? Nov 24 comment Primes $p$ for which $pk+1$ is prime for small $k$ (or approximating Sophie Germain)Yes, I agree. I was just describing how our two questions resemble each other, but the papers that answer one also answer the other apparently. Through the reference you gave me, I also found R. C. Baker and G. Harman. Shifted primes without large prime factors. Acta Arith. 83(4):331–361, 1998, which has a stronger bound on $k$ (in terms of the largest prime factor of $p-1$, they show it is infinitely often at least $p^{0.677}$). Nov 23 comment Primes $p$ for which $pk+1$ is prime for small $k$ (or approximating Sophie Germain)Thanks! Yes, this is very similar to your earlier question — I am looking for large prime factors of $p-1$, while you are looking for large prime factors of $p+1$. Nov 23 asked Primes $p$ for which $pk+1$ is prime for small $k$ (or approximating Sophie Germain) Nov 23 comment Hamiltonian MatroidsDid you try scholar.google.com/… ? It seems to answer your question "yes": there is literature (about 8 papers) on this. Or did you have a more specific question that these papers don't answer?