1
$\begingroup$

I'm a first year graduate student trying to explore specific topics I might be interested in researching. Currently, I enjoy algebra, probability theory, and the computability theory side of logic, and was wondering if I could find something nestled in the intersection of these fields. I know of some overlap between algebra and probability (such as probabilistic number theory or random matrices) but I was curious if there happened to be a topic involving all three. I don't know if such an intersection would even make sense- my novice brain can't imagine the depths of these fields yet- but if anyone out there happens to have experience in this space and/or has read a piece they really enjoyed (that I could feasibly digest in finite time), I would very much appreciate some pointers.

tl;dr: I'm looking for any sort of book/lecture notes/learning material that looks at probability theory and computability theory being used together to answer algebraic types of questions or algorithms (algebraic being vague, for example it could be number theory, combinatorics, discrete math, etc.)

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ Quantum Computing Since Democritus by Scott Aaronson. // Probably it would be good to make your question a little bit less open-ended.... $\endgroup$
    – Denis T
    Commented Nov 11 at 4:54
  • $\begingroup$ @DenisT Really? I thought I was being too specific, I'll add a point at the end $\endgroup$
    – modz
    Commented Nov 11 at 18:00
  • 2
    $\begingroup$ @modz: If you're a first-year graduate student, you should talk to prospective advisors for advise rather than strangers on the internet. You're much more likely to be steered towards something that is reasonable for you to work on with one of them, which should be your goal. $\endgroup$
    – Andy Putman
    Commented Nov 11 at 18:13
  • $\begingroup$ @AndyPutman I've already reached out to a professor whose work seems very interesting, I just wanted to ask here to get a broader idea of what's out there. Basically I'm just trying to explore as much of what might interest me as possible, I apologize if it came across as asking for someone to pick my thesis topic for me $\endgroup$
    – modz
    Commented Nov 11 at 18:20
  • 1
    $\begingroup$ @modz: What I'm trying to say is that even subareas of math are huge, so you have to make choices. I would never tell someone to not read things that interest them, but if you're not sure it is in your best interest to steer your reading towards things that align with the interests of the people that are available to you as advisors. That's my objection to this question: it is likely to lead to advice that however good it might be in the abstract is likely to be non-optimal for you. Plus, I think you should in general make a habit early of getting advice from the faculty in your department. $\endgroup$
    – Andy Putman
    Commented Nov 11 at 18:29

1 Answer 1

Reset to default
1
$\begingroup$

Here are a few areas of overlap for those research topics.

  • Computable model theory is a nice overlap of computability theory and algebra, since one is looking at the nature of computably effective presentations of models, often of particular well-studied algebraic theories, although just as often the examples touch on graph theory etc.

  • There is a huge and active area of work in algorithmic randomness which combines computability theory with probability. Here is a paper also connecting this with measure theory: Effective Randomness for Continuous Measures

  • There is work also combining this with model theory and algebra, by looking at zero/one laws. One part of this, for example, is to look for instances of theories of finite models, where a given statement phi becomes very likely true or very likely false in a random model as the size increases.

  • The subject of reverse mathematics also often involves computability theory in connection with the topic of the main theory, since for the optimality results, one often has to construct a model of the given theory with prescribed features, which often involve computability theoretic techniques.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I will look into these, thank you very much $\endgroup$
    – modz
    Commented Nov 11 at 18:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .