bio | website | gowers.wordpress.com |
---|---|---|
location | ||
age | ||
visits | member for | 5 years, 6 months |
seen | Apr 17 at 10:31 | |
stats | profile views | 32,003 |
Mathematics professor at Cambridge
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 |
Jun 6 |
awarded | Favorite Question |
May 24 |
awarded | Popular Question |
May 9 |
comment |
Are there any very hard unknots?
Thank you for this example. It's quite interesting as it is in some sense a "product" of smaller knots. I tried replacing the bundles of strands (most of the time four strands) by a single strand and obtained a picture of a knot that I can't instantly see to be the unknot, though I did find a local way of reducing the number of crossings. If this "quotient" knot is not the unknot, then it's a very interesting example. |
Mar 30 |
awarded | Good Answer |
Mar 29 |
comment |
What can be proved about the Ramanujan conjecture using elementary means?
I don't mind complex analysis, but I'm wondering whether a "non-structural" proof is possible. Without saying precisely what I mean by that, I would say that modular forms are on the wrong side of the boundary. |