Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Imperial mathematician scoops $3M Breakthrough Prize

imperial.ac.uk

Post reply on HN
Print view View original

101–110 of 111 posts

Re: Imperial mathematician scoops $3M Breakthrough Prize

#101

Post by chrisseaton »

yaseer wrote: post #44
leoc wrote: post #36

Earlier quoted context omitted.

Britain has a whole clutch of universities which are global research powerhouses but are scorned as boring redbricks (or whatever) by most of the locals and unheard of to most people internationally.

'...unheard of to most people internationally.' Taking this point further, I note there's a huge Anglo-Saxon bias in the prestige of Universities. I don't know why this is. I say this having studied at Oxford and Cambridge and noticed how 'unfair' it was that many French and German universities had undergraduate bodies with even higher selection standards, yet few people internationally would have heard of them. It s…

> many French and German universities had undergraduate bodies with even higher selection standards

I've heard that this is because the French and Germans often split institutions into teaching and research, so their teaching institutions look crap to outsiders because they're not doing any research.

Re: Imperial mathematician scoops $3M Breakthrough Prize

#102

Post by redis_mlc »

wombat23 wrote: post #24
redis_mlc wrote: post #9

Earlier quoted context omitted.

FYI: How Stanford University handles that now is that they have a new subdivision on campus, and chosen professors are given title to a nice house. When they move later, they are given the assessed profit of any rise in house value over the years. This was necessary because house prices in Palo Alto are in the $2+ million range, which is not affordable to profs, and prevents them from the normal housing ladder invest…

it's kinda scary that the go-to personal investment plan is based on a leveraged buy & sell with the implied promise that things perpetually increase in value.

You are feigning surprise at a common practise that goes back hundreds of years in most countries?

Re: Imperial mathematician scoops $3M Breakthrough Prize

#103

Post by proto-n »

ChrisLomont wrote: post #100
mikorym wrote: post #90

Oh, it's actually called the Breakthrough Prize . I thought perhaps three of the Millennium problems had been solved, and the apocalypse were here. BTW, for those interested in P=NP and not so much in the direct mathematical research, one interesting way to approach is via hash functions. If we had P=NP, then hash functions would be more easily invertible (eh, left or right invertible). I think in polynomial time. So…

P,NP, and the invertability of most hash functions are not related, as far as is known. Most one-way functions of use are not known to be NP hard or NP complete, so having P=NP or P != NP would not affect currently widely used hash functions. https://en.wikipedia.org/wiki/One-way_function https://www.quora.com/Is-cryptographic-hash-inversion-believ...

While not NP complete, reverting a hash function is in NP(), so it is very much affected if P=NP.

() Ok obviously it can't be in NP as it's not a decision problem, but asking "is there a preimage starting with 1, with 1A, etc." _is_ in NP. From the it's trivial to generate a preimage in P.

Re: Imperial mathematician scoops $3M Breakthrough Prize

#104

Post by ChrisLomont »

proto-n wrote: post #103
ChrisLomont wrote: post #100

Earlier quoted context omitted.

P,NP, and the invertability of most hash functions are not related, as far as is known. Most one-way functions of use are not known to be NP hard or NP complete, so having P=NP or P != NP would not affect currently widely used hash functions. https://en.wikipedia.org/wiki/One-way_function https://www.quora.com/Is-cryptographic-hash-inversion-believ...

While not NP complete, reverting a hash function is in NP( ), so it is very much affected if P=NP. ( ) Ok obviously it can't be in NP as it's not a decision problem, but asking "is there a preimage starting with 1, with 1A, etc." _is_ in NP. From the it's trivial to generate a preimage in P.

Inverting hash functions isn’t in NP, except that it’s constant time, so it’s also trivially in P. Thus P=NP is irrelevant. It’s just the constant is large. Since each common hash function is fixed size, inverting them is fixed size.

For a problem to be of interest regarding the P=NP question, the problem needs to have arbitrarily large size. 3-SAT can be arbitrary sized, thus is a candidate to ask if it’s NP hard, complete, etc. If we consider 3-SAT with fixed, bounded size, then 3-SAT is constant time.

For example, inverting SHA-512 requires at most on order of 2^512 ops to invert. This is constant time, not even polynomial time.

So no, hashing is not generally affected by P=NP.

Re: Imperial mathematician scoops $3M Breakthrough Prize

#105

Post by agent008t »

dogma1138 wrote: post #21
agent008t wrote: post #8

Earlier quoted context omitted.

Which actually made me wonder - where/how do London academics live? I find it hard to imagine them commuting for hours from the suburbs - it does not seem very consistent with an academic life - but I do not see them being able to afford to live near their universities either.

The same way that everyone else does; buying a 1.5M 2 bed flat in Zone 1 isn’t possible on UK tech salaries either, even if you reach the top tiers for UK tech pay which usually tops at around £125K base you aren’t buying central London properties either.

But then who is buying them? I see plenty of young families that seemingly live in those 1.5M zone 1-2 houses and flats, and many do not appear to be renting (although maybe they are? But not like renting is THAT much cheaper either).

Re: Imperial mathematician scoops $3M Breakthrough Prize

#106

Post by mikorym »

ChrisLomont wrote: post #104
proto-n wrote: post #103

Earlier quoted context omitted.

While not NP complete, reverting a hash function is in NP( ), so it is very much affected if P=NP. ( ) Ok obviously it can't be in NP as it's not a decision problem, but asking "is there a preimage starting with 1, with 1A, etc." _is_ in NP. From the it's trivial to generate a preimage in P.

Inverting hash functions isn’t in NP, except that it’s constant time, so it’s also trivially in P. Thus P=NP is irrelevant. It’s just the constant is large. Since each common hash function is fixed size, inverting them is fixed size. For a problem to be of interest regarding the P=NP question, the problem needs to have arbitrarily large size. 3-SAT can be arbitrary sized, thus is a candidate to ask if it’s NP hard, c…

Chris, I am a bit over my head usually with P=NP, since it's not my area and I have to warp it before it is.

One question I would have on your comment is: What kind of proof or counterexample for P ?= NP would in fact influence our study of hash functions? This is a subjective question of course, but essentially I am wondering what approach to P ?= NP might introduce new mathematics that indeed would have something to say about hash functions.

Re: Imperial mathematician scoops $3M Breakthrough Prize

#107

Post by gdy »

mellosouls wrote: post #58
protomolecule wrote: post #27

Earlier quoted context omitted.

They are all related to a single award -- 2019 (special) for supergravity.

They are just examples - and intended as counter to the "ignorant" accusation which implies there was no truth to the idea of criticism.

Fair enough.

Re: Imperial mathematician scoops $3M Breakthrough Prize

#108

Post by ChrisLomont »

mikorym wrote: post #106
ChrisLomont wrote: post #104

Earlier quoted context omitted.

Inverting hash functions isn’t in NP, except that it’s constant time, so it’s also trivially in P. Thus P=NP is irrelevant. It’s just the constant is large. Since each common hash function is fixed size, inverting them is fixed size. For a problem to be of interest regarding the P=NP question, the problem needs to have arbitrarily large size. 3-SAT can be arbitrary sized, thus is a candidate to ask if it’s NP hard, c…

Chris, I am a bit over my head usually with P=NP, since it's not my area and I have to warp it before it is. One question I would have on your comment is: What kind of proof or counterexample for P ?= NP would in fact influence our study of hash functions? This is a subjective question of course, but essentially I am wondering what approach to P ?= NP might introduce new mathematics that indeed would have something t…

>What kind of proof or counterexample for P ?= NP would in fact influence our study of hash functions?

None. Hash functions are almost all O(1) to invert, that is, constant time. It's just we designed that constant to be prohibitively large.

And hash functions are not generally based on NP hard problems - they're based on bit mixing, which for all common hash functions are completely orthogonal to the question of P and NP.

Quantum computing, via Grover's algorithm, did impact hash functions one and all, since it allows searching N unstructured items in O(sqrt(N)) time, while classical computers require O(N) time. But this simply turns a 512 bit hash into a 256 bit hash, still intractable.

Again, however, this has nothing to do with P?=NP.

For a problem to be changed by P?=NP, since most think P != NP, that problem must be in NP/P, and hash functions are not (almost ever, and no common ones) from that class of problems. Also the problem has to part of an infinite family of such problems with unbounded sizes. Hash functions again are not in this class.

Of course, it may be that we can build computers in the future with closed timelike loops (CTL), in which case all problems are constant time, and that may prove for that class of machines that the complexity hierarchy collapses, but that is a long time off, if ever. We may be able to build machines that exploit topological quantum field theories (TQFTs) some day, like in Friedman's work, and again, that may break things, but again that is a long time off, if ever.

I'd personally bet on P!=NP being a fundamental law of physics, built into the fabric of the universe, in the It from Bit idea from Wheeler and others. I think this is becoming more and more the mainstream science belief, as the universe is looking more and more like computation.

Re: Imperial mathematician scoops $3M Breakthrough Prize

#109

Post by dash2 »

jkaptur wrote: post #74
dash2 wrote: post #12

Earlier quoted context omitted.

One thing I learned: he did his work while at Warwick. Warwick is kind of under-estimated among UK universities. It's reasonably well-run (which makes it almost unique), regularly hires smart people, and doesn't have the Brideshead Revisited hangover of Oxbridge.

I don't quite follow what you mean by "Brideshead Revisited hangover" - from Wikipedia, it seems like it roughly means "nostalgia for the age of English aristocracy"?

That's about right. Think candlelit dinners with lots of claret, terribly clever undergraduates writing terribly clever 1500-word essays on their PPE course, the gentleman amateur.... Things that were great in the 19th century and have now become parodies of themselves.

Re: Imperial mathematician scoops $3M Breakthrough Prize

#110

Post by room271 »

asib wrote: post #98
room271 wrote: post #56

Earlier quoted context omitted.

Ha I agree with the broad point, but as someone who (used to until Covid) commute from South London to Kings Cross everyday, this doesn't seem true timewise until you live quite far South in London. And I live a 15 minute walk from a tube station. Having said that, I agree with the sentiment!

Tooting -> Kings X is 49 minutes according to citymapper. Cambridge -> Kings X is a 48 minute train. I personally wouldn't consider Tooting to be deep south, but maybe we have different definitions. I have a friend who lives near Kingston, it's roughly an hour commute for him.

I don't know how City Mapper is getting that number to be honest. TFL gives 35 minutes, and that includes 5 minutes for walking out the tube at Kings Cross.

The trick is you have to change at Stockwell onto the Victoria Line.

Nb. I did almost this journey every day pre-lockdown and the numbers are accurate for me at least.

Post reply on HN