# Applications of Probability Theory to Coding/Cryptography Theory

I'm looking to do a PhD in probability, with my project(s) having applications to for example the following (non-exhaustive).

1. Coding theory: eg algorithms for sending data quickly which can be decoded rapidly with a high probability of correct decoding, including error correction (with high probability) codes; also more general information theory

2. Cryptography: similar to above, but ways of securely encrypting given a key and then decrypting with high probability of success given the key but with very low probability of success without the key

3. Computer science more generally: fast algorithms for sampling (eg Markov mixing)

I'm after some advice as to possible topics/projects that I could consider in this field. Most of what I've looked at only uses very basic probability (eg discrete conditioning on events); this isn't what I'm lookin for. I'm interested in the PhD being in probability, but with above applications. I did probability for Part III, so this is the level of probability I want to use. (Yes, I realise real research isn't quoting/proving theorems that other people have used, but hopefully this is clear what I'm meaning.) It should include, for example, hitting/mixing times of random walks, maybe the odd martingale, even maybe some percolation. Another example might be to do with showing concentration results.

If people have any suggestions, then I'd very very interested in hearing about them. Thank you.

Lastly, hopefully this is on topic. If you have any advice how to make it more on topic, then please let me know... preferably without being too rude ;)

• You may want to look at the work of e.g. Jelani Nelson and Mary Wootters (IIRC, concentration of measure and chaining play a big role there). Also, asking on cstheory.SE may be more relevant (?). – Clement C. Nov 14 '16 at 15:52
• Thanks for your response; I shall have a look. Your comment also reminded me of putting in about concentration results. Regarding CS though, I did think about that, but the point is that it's a probability PhD. The work should have applications to the above, but in the end be rigorous, pure probability theory. I've added CS as a tag... – Sam OT Nov 14 '16 at 15:58
• Oh, the results they use I was thinking of are pure probability -- they come up in CS, when analyzing randomized algorithms or probabilistic arguments. – Clement C. Nov 14 '16 at 16:40
• Ah, sorry, I was meaning "regarding [posting on] CS[theory.SE]". Thank you for your comments, I'll have a thorough look at them. (Other people's comments are still welcome!) – Sam OT Nov 14 '16 at 17:41

The most important issue I see here is to get yourself ready for a PhD program in probability. Depending on what is available in your current program, presumably an undergraduate major in mathematics, you should consider the following. Make sure you really know calculus through multiple integration and and infinite series. Take a course in real analysis. Learn something about measure theory. Take a mathematical statistics course (or at least a statistics course with a calculus prerequisite). Find out what Bayesian statistics is. And a course in linear algebra would certainly be useful.

Look at the web sites of departments to which you might feasibly be admitted; some of them give specifics of the background they want applicants to have.

You will be exposed to a lot of new ideas and possibilities in a PhD program in probability. The CS related fields you mention are changing so rapidly and progress in them is tightly held and not always public information, that it might not be possible for you to prepare yourself for those fields now. It is entirely possible that your objectives will change as you progress towards your PhD in probability. So my suggestions along lines of the CS topics you mention are more tentative and possibly not as important as my suggestions on preparing for the probability PhD.

Of course, you should take obviously relevant courses in computer science. Some less obvious possibilities are number theory, group theory, and quantum mechanics. Learn to use a statistical programming package/language such as R or Python (with Scripy)--data management, standard statistical analysis, simulation (e.g., permutation tests, bootstrapping, stochastic processes, maybe even Gibbs sampling).

Outside of coursework, try to keep current in developments in various kinds of artificial intelligence, and proposals for making the Internet more secure. You may find out more about these things by reading the New York Times than from CS courses. (Generally speaking, it is a real struggle for colleges and universities to keep current with developing trends in CS because the non-academic job market for potential faculty members is so active.) Much of the innovation in these areas is going on at places like Google and Facebook in the private sector and NSA in the government sector, and you may only be able to get miscellaneous rumors, hints, and clues about the most important developments.

Personal note: All of that said, I went off to a PhD program in probability and statistics out a first rate undergrad program, but with only a one-quarter course out of Feller's probability book to give me a clue what I was getting into. I did survive, and over 50 years later I'm still learning stuff. So I can't say planning is everything. Being at the right place at the right time is important and unpredictable. (But never having the curiosity to be anywhere interesting any of the time is clearly not an optimal strategy.)

• Thank you for your extensive answer, but I'm afraid you've kind of missed the point! :( -- I've done Cambridge undergraduate and then Part III, where I specialised in probability! My understanding of your response is that you think I'm, say, a first or second year undergraduate. In hindsight, maybe I should have been clearer! Also, I'm looking at theoretical CS. I do know some R, but this isn't really important. – Sam OT Dec 24 '16 at 20:04
• Instead of the stuff you've been suggesting, I'm thinking of more specific CS-related probability stuff. The main thing that I know about is fast sampling, say determining mixing times. Thank you for your time, though! :) – Sam OT Dec 24 '16 at 20:06
• For a first year undergraduate, or even a second year, your advice looks very good though! – Sam OT Dec 24 '16 at 20:07