Computer Scientist Wins Turing Award for Seminal Work on Randomness (arstechnica.com) 31
Computational scientist and mathematician Avi Wigderson of the Institute for Advanced Study (IAS) in Princeton has won the 2023 A.M. Turing Award. From a report: The prize, which is given annually by the Association for Computing Machinery (ACM) to a computer scientist for their contributions to the field, comes with $1 million thanks to Google. It is named in honor of the British mathematician Alan Turing, who helped develop a theoretical foundation for understanding machine computation. Wigderson is being honored "for foundational contributions to the theory of computation, including reshaping our understanding of the role of randomness in computation and for his decades of intellectual leadership in theoretical computer science." He also won the prestigious Abel Prize in 2021 for his work in theoretical computer science -- the first person to be so doubly honored.
It's not just about the award. (Score:5, Informative)
He’s made sure the field’s going to keep on breaking new ground for years. Fresh ideas, new perspectives, all of that’s blooming thanks to Wigderson’s help in bringing up new talent.
A shout-out to the huge impact he’s had on the entire discipline.
Re: (Score:1, Funny)
Re: (Score:2)
Well sure, but aside from that, what has he ever done for us?
I protest! (Score:5, Funny)
This award was just randomly assigned!
John Von Neumann quote (Score:2)
Anyone who attempts to generate random numbers by deterministic means is, of course, living in a state of sin.
Re: (Score:1)
Yes, but it's more fun that way. As they say, brunettes get into heaven, but blonds get into everything else.
Re: (Score:3)
Anyone who attempts to generate random numbers by deterministic means is, of course, living in a state of sin.
As Avi pointed out, Von Neumann did not follow his own advice.
Re: (Score:3)
Except that it wasn't advice but a disclaimer. Curiously, though, the original context [lanl.gov] ties in to the topic of derandomisation:
Advanced Lateral Kerfliggening, 3d. Ed. (Score:3, Interesting)
From TFA:
"While computers are fundamentally deterministic systems, researchers discovered in the 1970s that they could enrich their algorithms by letting them make random choices during computation in hopes of improving their efficiency. And it worked. It was easier for computer scientists to start with a randomized version of a deterministic algorithm and then "de-randomize" it to get an algorithm that was deterministic."
"In 1994, Wigderson co-authored a seminal paper on hardness versus randomness with Noam Nisan, demonstrating that as useful as randomness can be, it is not a necessity."
That's all very vague. Who were those researchers in the 1970's? What domain, exactly, were they researching? How does one write the "randomized version" of an algorithm, and how does one subsequently "de-randomize" it?
Re: (Score:3, Interesting)
From TFA:
"While computers are fundamentally deterministic systems,"
When you start with a wrong premise, the rest that follows is suspect.
Your computer has nondeterministic instructions by design. It is not in any way "fundamentally deterministic". It's made of electronics. Electronics has noise. Electrical noise is nondeterministic.
Re: (Score:3)
"Your computer has nondeterministic instructions by design."
Okay, I'll bite. I'm working on a laptop with an Intel i7 processors. Please elaborate what machine language instructions it has that are nondeterministic.
Re: Advanced Lateral Kerfliggening, 3d. Ed. (Score:4, Informative)
Re: (Score:2)
Okay, good enough. I didn't know they were packing entropy generators on microchips these days.
Re: (Score:2)
Re: (Score:2)
Somehow you missed the entire point. You are discussing how to provide cryptographically secure sources of entropy to a random number generator. This guy is a mathematician who studies the role of using some sort of randomness (which might not really be random to the standards of cryptography) to improve the performance of heuristics and algorithms in solving real world problems. And it doesn't matter if the sources of entropy he uses are truly random. Its about when making a guess is better than comput
Re: (Score:2)
Re: (Score:3)
Avi does awesome work. His papers, particularly on multiple input entropy extractors have solved fundamental problems in RNG design (and my job is RNG design, so I care).
Here is a very good and accessible talk he gave that covers some essential aspects of his research : https://www.youtube.com/watch?... [youtube.com]
His work covers both domains you mentioned. On randomized algorithms, he established important principles about what is possible. On cryptographically secure sources of nondeterministic randomness, his BIW pa
Re: (Score:2)
Re: (Score:3)
I've spent the past 16 years deep in the tarpit of RNG design. The book in my sig is one of the results, along with the RNGs that are common in today's CPUs.
I can't complain - it's kept me gainfully employed. But I'd really like to work on something else for a change.
Re: (Score:3)
The i810 RNG was a slower noisy VCO sampling a fast oscillator. This is fine, albeit slow. However it did not scale well to modern small feature size silicon. We replaced it with a differential feedback metastable source which is fast and reliable and has been all Intel CPUs since 2011. This is the noise source behind the RdRand and RdSeed instructions that have an SP800-90A,B,C based design generating the random numbers.
Re: (Score:2)
not good at all, it completely misses the point. an instruction to create a random value is deterministic in that it is expected to specifically produce a random value. everything else in a cpu and its instruction set is deterministic and the hardware is engineered with tolerances large enough to satisfy that requirement. when (conventional) computers (or instructions) exhibit nondeterministic behavior that's never "by design", that's just a bug.
going deeper, i would surmise that even that instruction's int
Re: Advanced Lateral Kerfliggening, 3d. Ed. (Score:4, Interesting)
"going deeper, i would surmise that even that instruction's internal process is fully deterministic too,"
Nope. The noise source is (subject to quantum physics) nondeterministic. Data from this source goes through a cryptographic entropy extractor. For RdRand there is a DRBG that follows, to give you fast, secure random numbers and for RdSeed you get full entropy random numbers, which are limited by the speed of the source and so isn't as fast as RdRand.
Quantum physics does not answer to question as to whether or not the universe is nondeterministic. It certainly look nondeterministic but we don't know if they is actual nondeterminism or ignorance of a deeper process.
For more stuff on this, maybe check out the book in my sig.
Re: (Score:2)
"Your computer has nondeterministic instructions by design."
Okay, I'll bite. I'm working on a laptop with an Intel i7 processors. Please elaborate what machine language instructions it has that are nondeterministic.
RdRand and RdSeed.
Re: (Score:2)
Remember the Pentium Floating Point fiasco? THAT's what happens when your processor behaves non-deterministically!
Re: (Score:2)
No, components in your computer are subject to forces that are non deterministic, but the entire *purpose* of a processor is to be deterministic. To perform all instructions consistently, and repeatably, and to return the "correct" to an instruction every time.
Remember the Pentium Floating Point fiasco? THAT's what happens when your processor behaves non-deterministically!
You are wrong. The purpose of a computer is to compute and be useful. To that purpose, computers have nondeterministic instructions. In X86 CPUs they are RdRand and RdSeed. RISC-V has equivalent instructions. ARM is a bit of a mess, but various ARM providers have various RNG solutions on chip. If your computer was deterministic, it would never be able to perform a secure Diffie Hellman key setup, or generate a secure private key.
Re: (Score:2)
"Your computer has nondeterministic instructions by design."
-1, true but useless
Normal human being understand that these usages of "deterministic" are modified by "correctly and intentionally functioning". What you are describing is called a "fault".
Re: (Score:2)
Nope. It would be a fault if the nondeterministic instructions were in fact deterministic. The security of your communications depends on those instructions being nondeterministic. Otherwise your adversary could guess your key.
Re: (Score:1)
Who were those researchers in the 1970's? What domain, exactly, were they researching? How does one write the "randomized version" of an algorithm, and how does one subsequently "de-randomize" it?
All corporate buzz words used to keep him employed
Re: Advanced Lateral Kerfliggening, 3d. Ed. (Score:4)
Re: (Score:3)
"That's all very vague."
No, it's a summary. Did you think the entire research space was going to fit into two paragraphs?
Much worse in mathematics (Score:2)
Us computer guys are only looking for random rational numbers, since that's all a computer can create or store, since it doesn't have infinite bytes.
Worse, nearly all numbers are transcendental and not calculable, so there's no way at all to pick a random number from the field of Reals.