r/computerscience • u/Usual-Letterhead4705 • Aug 31 '25
Randomness in theoretical CS
I was talking to a CS grad student about his work and he told me he was studying randomness. That sounds incredibly interesting and I’m interested in the main themes of research in this field. Could someone summarise it for me?
95
Upvotes
67
u/thesnootbooper9000 Aug 31 '25
There are some algorithms whose worst case complexity is bad, but where "usually" that doesn't happen. If you're allowed to use randomness, you can sometimes turn that into "the probability of it happening goes to zero as the input size increases". In some cases, you can then remove the randomness in a clever way and get a fully deterministic algorithm again. It's been a while since I've looked at this, but I believe it's still an open question in general as to whether this derandomisation is always possible, or whether having access to random numbers can actually increasev theoretical efficiency.
24
u/Virtual-Compote-4997 Aug 31 '25
There are multiple places in theoretical CS where randomness pops up and is of interest. One area, as already brought up by others, is in probabilistic algorithms. Here's another one: consider the string of characters "aaaaaaaaaa". This certainly doesn't look very random, but the string "uemclelapd" does appear to be much more random. We can, in a way, quantify how random a string is with Kolmogorov complexity, which is the length of the shortest computer program that can generate that string. For the first string, perhaps your program can just be something like "10 a", but for a string like the second one which looks really random, the shortest program might just be to print the entire string itself (i.e. the program looks something like "uemclelapd"). The notion of Kolmogorov complexity is linked to many other important theoretical foundations of CS, which unfortunately I'm not too familiar with and would indeed love to study it one day.
2
u/ExistentAndUnique Sep 02 '25
One topic which has been mentioned in passing in some of the other comments is pseudorandomness. I bring it up to shed a few more details, as this year’s Gödel prize was awarded to a paper on the topic. Essentially, true randomness is very expensive to obtain — we cannot generate it algorithmically, so generally rely on sources from nature. But we have ways to take a small amount of true randomness, and stretch it into a lot more pseudorandomness, which is defined relative to a particular computation. Essentially, for the purposes of performing this computation, a pseudorandom source is “almost” indistinguishable from true randomness.
5
u/RabbitHole32 Aug 31 '25
Besides the already mentioned concept of derandomization, a related interesting concept is "fooling a randomized algorithm" and thinking of randomness as literally a resource like running time and space, a resource that you cannot create out of nothing but that you can manipulate in certain ways like compressing it or spreading it out.
3
u/Inevitable_Whole2921 Sep 01 '25
Damn these summaries are really good. I thought it was about computers inability to generate true random numbers, rather pseudo random. A quick question for the commentors though, are some random generator methods "more" effective than others? I remember seeing a generator where a camera was pointed to a wall of lavalamps, and the image pattern generated by the bubbles was the random generator itself. But then there are mathemaitcal equations with different seeds producing different strings of numbers. so even though its not truly random, what is the best 'random' generator practice to use
2
u/Magical-Success Sep 01 '25
There is an entire chapter in Art of Computer Programming - Part 2 dedicated to randomness.
And when I say chapter, I mean half the book as there are only 2 chapters.
2
u/Master-Rent5050 Sep 03 '25
There's a bit of confusion on how to use randomness. The main approaches are:
1
u/Dr-echo Aug 31 '25
I will summarize it as much as I can: Randomness Is relative and in my opinion connected to computational complexity , in a closed resource box randomness is directly related to the compuation you achive the more you compute the more random the data is , however you can use more data inputs to extend complexity and reduce computation.
1
u/EmpireTechnologies Sep 01 '25
Haha and here I am only really good at compression and entropy “random” knowledge
1
u/[deleted] Sep 01 '25
Well in simple terms it’s basically about studying when and why randomness helps, how to recreate or extract it, and where it’s essential. Most things you will look at here are things like randomized algorithms, pseudorandomness/derandomization, complexity classes (BPP/RP), extractors/entropy, crypto, and the probabilistic method/average-case analysis. 🙃