7
$\begingroup$

I could use some help navigating which areas of Computational Complexity (e.g. CCC, STOC topics) require the least amount of background knowledge to get involved in basic research. I am looking to focus on such topics to get momentum in thinking about Computational Complexity research problems. Are there exercises in particular texts that are good warm up or moderately hard problems in those topics to get started?

I have studied most topics in CS, the basics of applied math/calculus, introductory combinatorics, and introductory information theory. I have not studied linear algebra, abstract algebra, probability. I am happy to learn more about each topic gradually, but I am looking for some initial area in complexity that requires few of those topics, to get a foothold in understanding some topic deeply.

Improve this question
$\endgroup$
5
  • $\begingroup$ May I suggest deep nets? :) Questions are very easy to state but there doesnt seem to be any finite set of techniques that will always be helpful to answer even the most basic sounding questions. $\endgroup$
    – Student
    Commented Jul 1, 2017 at 23:42
  • $\begingroup$ Try oracle results. $\endgroup$
    – user1338
    Commented Jul 2, 2017 at 17:36
  • $\begingroup$ I don't like machine learning or streaming/big data focused problems generally. I started looking at oracle results. $\endgroup$
    – nish2575
    Commented Jul 3, 2017 at 4:06
  • $\begingroup$ I am also debating simply implementing various randomized algorithms and studying their properties, as a really simple first step. $\endgroup$
    – nish2575
    Commented Jul 3, 2017 at 4:07
  • $\begingroup$ I personally think deep nets is much more than just its machine learning application. $\endgroup$
    – Student
    Commented Jul 3, 2017 at 19:05

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.