bio | website | gowers.wordpress.com |
---|---|---|
location | ||
age | ||
visits | member for | 5 years |
seen | Mar 16 at 23:40 | |
stats | profile views | 30,638 |
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 |