Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In this paper, the authors mention that it is possible to get an $o(n^2)$-time algorithm for the nuts and bolts problem by choosing samples based on a projective plane. They also mention that a non-constructive $O(n^{1.5}\log n)$-time algorithm can be obtained (pages 2-3). They omit the details.

I am interested in understanding these approaches, although they are not optimal. Could someone please provide the details of how this is done?

share|cite|improve this question
(1) Have you asked the authors? (2) It's not clear that these algorithms are "easy"! – Jeffε Feb 11 '13 at 17:06
(1) Not yet. (2) I meant 'easier'..I've edited the question. – Plummer Feb 12 '13 at 5:10

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.