- #1

- 1,064

- 782

I am interested in complexity theory, and have been watching the whole "Big Data" scene with interest (and ignorance). I googled "Complexity and Big Data" and the result seems to be something called PAC learning.

I have some undergraduate background in Theory of Computation (including Automata and complexity) and a little bit of Combinatorics and Graph Theory. I have a career background in I.T. and some programming skills, and generally a good intuition and draw towards computer science, though I've never studied it formally, save from a purely mathematical perspective.

This coming semester I will be taking (graduate courses) Algebra II, Algebraic Automata Theory, and mathematical logic and foundations. (Which all nicely tie together)

I'm a bit away from a thesis but I don't want to wait to get started researching. I'd like it to be something mathematically satisfying, yet have some connection to something that is happening right now. Machine learning is a fascinating area that is very "now."

We have some people doing theoretical comp sci in the math department, so I have my eye on a couple of people for potential advisors and are in contact with them. So I will keep that up. In the meantime, just poking around on my own. I want to come to them with an informed idea.

So, can somebody tell me about PAC learning, what the 'questions' are in this field, or any other connections between machine learning, big data, complexity, etc.? Is this a good starting point for a topic?

Apologies if my question is uninformed or vague, but I'm at the necessarily naive first step...

Regards,

Dave K