15,614 reputation
1189145
bio website gowers.wordpress.com
location
age
visits member for 5 years
seen Mar 16 at 23:40
Mathematics professor at Cambridge

Aug
18
awarded  Good Answer
Jul
17
awarded  Populist
Jul
8
revised Nonexistence of an approximately distance-preserving map between discrete cubes
added 779 characters in body
Jul
8
comment Nonexistence of an approximately distance-preserving map between discrete cubes
You're right about projection on to the first $n-1$ coordinates. Actually, the case that I'm really interested in is $n/2$ dimensions. In an hour or so I'll modify the question accordingly.
Jul
8
asked Nonexistence of an approximately distance-preserving map between discrete cubes
Jun
25
awarded  Excavator
Jun
25
awarded  Enlightened
Jun
22
comment Are there very strongly pseudorandom permutations?
I think I've now found a construction that does what I want.
Jun
20
comment Are there any good websites for hosting discussions of mathematical papers?
I think you can make contributions by registering directly with the site, and anybody can read it. But Google Plus is a particularly convenient way of contributing, since all you have to do is write a normal post and add the #spnetwork hashtag. In due course other social networks will be added, but Google Plus has the advantage that public posts are genuinely public.
Jun
20
comment Are there very strongly pseudorandom permutations?
Actually, scratch that -- I miscalculated the information-theoretic bound, which gives that exponentially many would be needed.
Jun
19
awarded  Nice Answer
Jun
19
awarded  Necromancer
Jun
19
comment Are there very strongly pseudorandom permutations?
I now think it may be possible to do something by composing polynomially many Feistel permutations.
Jun
19
answered Are there any good websites for hosting discussions of mathematical papers?
Jun
19
comment Are there very strongly pseudorandom permutations?
Yes. I was vague about it, but the precise requirement I would like is that $k$ should be at most a polynomial function of $n$ (or perhaps a very slightly superpolynomial function).
Jun
18
comment Are there very strongly pseudorandom permutations?
Good point -- thanks for the tip.
Jun
18
comment Are there very strongly pseudorandom permutations?
I have now found a source that seems to suggest that the Luby-Rackoff construction won't give hardness greater than $2^n$. So it looks as though a different idea would be needed. But maybe there are some different ideas out there.
Jun
18
asked Are there very strongly pseudorandom permutations?
Jun
13
comment Are there any very hard unknots?
I drew the "quotient" knot and the picture has been sitting on my desk for about a month. At first it looked hard to simplify, but then I saw that one could make a "hole" in the middle and take a chunk of knot and pass it up through the hole and back down again. This kind of global untwisting would, I think, have to be part of any unknotting procedure of the kind I fantasize about. At some point I might make the knot out of string and see whether I can indeed untie it fairly straightforwardly starting with that move.
Jun
12
awarded  Nice Answer