bio | website | gowers.wordpress.com |
---|---|---|
location | ||
age | ||
visits | member for | 5 years, 10 months |
seen | May 22 at 10:59 | |
stats | profile views | 32,855 |
Mathematics professor at Cambridge
Oct
20 |
awarded | Yearling |
Oct
8 |
awarded | Nice Question |
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? |