I am finishing a masters program this year and I'm interested in doing a Ph.D. in the field of Artificial Intelligence.

I have an idea I've been tinkering with for a while, but some people have told me that it is not ambitious enough for Ph.D.-level research. I'm not sure if this is because the TCS community already knows all there is to know about it or because I have failed to express myself adequately (bad sales pitch). Based on what I could find online, not all that much has been done.

So, I am going to describe what I thought about doing and I would like to ask if you think this is a promising start idea and if it has the potential to lead to something graduate-level worthy.

I want to research efficient and reliable ways to implement a distributed system that can identify entities based on data collected from its users. To give a concrete example of this, I am going to use the 20 questions game.

Existing implementations of this can be found at http://www.20q.net/ and http://www.akinator.com/ however these are closed: no official details whatsoever on how they do it exist anywhere that I can find (subquestion: in general, if someone does something but does not publish how it's done, how worthy is (much) later research that explains how it can be done?).

There are also no details on the required processing power (performance can easily be seen to be very good, although also hard to quantify exactly - is this because they're smart about whatever it is they do or because they run the site on supercomputers?) and the reliability (how often they guess right, under what circumstances etc.) of these systems.

Of course, one can say "use neural networks", "use bayesian classifiers", "use KNN", "use this special form of decision trees: ____", but how well will these work (is it that obvious that they even will?), how exactly they need to be implemented to work efficiently and reliably, how they can be implemented in a distributed manner that is accesible and cheap (for example, if they could be implemented efficiently using widely-used relational databases such as MySQL, that would be great), how they can be tailored to learn from user inputs and probably other factors seem to be up for research.

The problem is more complicated than it seems I feel, because players can also lie, and you'll notice akinator will guess right in many of those cases as well - so it's not so easy as using a decision tree. As for the other approaches, many questions arise as well, such as scalability, reliability and exact mechanics that are provably best (or at least better than most others) for this specific problem.

At first, based on what I read online, the problem did not seem too complicated, but when I thought and learned more about what people were suggesting, I quickly started to find various flaws. Then I started to write code and noticed even more potential shortcomings, so now I feel that the problem has a lot more that can be learned from it than trivial implementations of various existing concepts.

Does this have any potential or should I start looking someplace else entirely?

  • 4
    $\begingroup$ There is a lot of interesting work in the theory community on search in the presence of errors. See for example this paper and the references in it: cs.bu.edu/~gacs/papers/liars.pdf. $\endgroup$ Commented Apr 21, 2014 at 2:48
  • $\begingroup$ BTW do not take my comment above as an answer to your question in either direction. $\endgroup$ Commented Apr 21, 2014 at 2:51
  • 1
    $\begingroup$ I think it would be good to extract the main points of the question and express it more generally so it can be useful for others also. $\endgroup$
    – Kaveh
    Commented Apr 21, 2014 at 3:18
  • $\begingroup$ I suspect the difficulty with building these 20q websites is getting enough data (i.e. descriptions of millions of things). The actual learning and computing is probably not that difficult once you have that. $\endgroup$
    – Thomas
    Commented Apr 21, 2014 at 3:42
  • 10
    $\begingroup$ This is the usual reason a Ph.D student has an advisor: to answer questions precisely of this form. $\endgroup$ Commented Apr 21, 2014 at 3:59

1 Answer 1


A PhD thesis should have references to the published literature and should be extending results in that literature. So it is important to be able to say, these serious researchers did something but we do something they either were not able to do, or at least did not think of doing or did not have time to do, but would want to do.

  • $\begingroup$ Yes, of course. Right now, my ability to scour what has already been done in this direction is limited (Google doesn't really point to anything, or maybe I'm using it wrong and I don't have access to any journals). I would probably have references to neural networks and machine learning papers, exactly which I don't know yet. I am asking if 1. Someone has already done exactly this and there's nothing for me to do anymore and 2. If this is ambitious enough - a PhD should contribute something significant in some way, it can't be something trivial - this feels significant to me, but is it? $\endgroup$
    – IVlad
    Commented Apr 20, 2014 at 22:23
  • 1
    $\begingroup$ I think the significance depends on what your results are. What are you hoping to be able to conclude about this problem? $\endgroup$
    – Thomas
    Commented Apr 21, 2014 at 4:08
  • $\begingroup$ @Thomas - that there is a provably good (either mathematically or empirically - in the case that I build such a system, get people to use it and usage stats will prove it) way to implement such a system using the techniques and specs I mentioned. $\endgroup$
    – IVlad
    Commented Apr 21, 2014 at 16:06
  • 5
    $\begingroup$ Just building a system is arguably not a significant research contribution, and it is certainly not a theoretical computer science research contribution. $\endgroup$
    – Jeffε
    Commented May 23, 2014 at 13:58

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.