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.

  • $\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$ – Anirbit Jul 1 '17 at 23:42
  • $\begingroup$ Try oracle results. $\endgroup$ – Philip White Jul 2 '17 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 Jul 3 '17 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 Jul 3 '17 at 4:07
  • $\begingroup$ I personally think deep nets is much more than just its machine learning application. $\endgroup$ – Anirbit Jul 3 '17 at 19:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.