# How to come up with an non-trivial idea in theoretical computer science?

I am a PhD student working in theoretical computer science. I have read the research papers of many researcher and I have seen many tools and mathematics they use for designing an algorithm. For example see this research paper [Primality in P]. I would not say this research paper is based on one or two ideas but it is based upon many ideas which requires serious mathematics. I am struggling to come up with those kind of ideas from couple of years. I have worked on one problem for many months, but there is nothing non-trivial coming into my mind. All the ideas which have come into my mind till now are trivial and of very little use to theoretical computer science researchers. I am wondering how to come up with a machinery which will enable me to generate non-trivial results.

Question : How to come up with a non-trivial idea in theoretical computer science? I know there are different meanings to the word "non-trivial idea". For me, it is something publishable and interesting to the theoretical computer science community. I have seen some research papers in which they define few (mathematical) terms then design the algorithm using the defined terms. I wondering how to come up with such things.

One advice I have got from my research friends and seniors is to read the research papers carefully and read the mathematics (theorems and proofs) very carefully, try to do the proofs on your own and try to extend them.

• As Aryeh points out, this is better discussed with your advisor than with the internet. They can steer you clear of dead ends, suggest things to try, guide you as you learn the basic tools, point out what's missing in prior work. Remember that one of the authors of Primality in P was an experienced researcher who knew the problem very well. Jun 27, 2018 at 13:33
• I wonder if you set your bar too high. Good research is rarely transformative or totally new machinery. Often it comes from understanding your problem deeply to the point where you stumble on the small, even "trivial" idea that shows why something is true; then you find that writing it up properly takes 30 pages. Do this several times on closely related problems and you may see machinery emerge (hopefully metaphorically).
– usul
Jun 27, 2018 at 13:54
• Huge oak trees grow from little acorns. Most PhD theses I've seen have grown out of small insights or results for extremely restricted cases, which were then slowly extended over many months. Jun 27, 2018 at 19:56
• This advice seems relevant here. Jun 29, 2018 at 12:30

1. Almost certainly there are lists of open problems in your particular subfield. Find them and read them. Although it's rather unlikely you will be able to solve these problems --- at least right away ---, use them as a starting point. Can you solve some particular cases? Can you solve a less general problem? Can you show a more general problem is computationally difficult?

2. Read what other people are doing. This means making a list of the conferences and journals in your area, and devoting at least an hour a day to reading papers in them. There is no need to understand everything at once. Try to familiarize yourself with the general themes, then pick one or two papers that seem interesting or fundamental and immerse yourself in them. Study the techniques and proofs. Can you apply them to similar or related problems? Work out specific examples in detail, to the extent possible.

3. When reading any result, ask yourself: are all the hypotheses necessary? What if the hypotheses are weakened or strengthened? Are the bounds really optimal? If only an upper bound is proved, can you prove a matching lower bound?

I am going to try and answer this with my limited experience. Disclaimer I am just a senior phd candidate myself.

The question you are asking is by no means a trivial one nor are you the only one wondering about it. Every single phd student, in almost any field, that preceded us and that will succeed us, has/will wonder the same. So, as a first piece of advice: If you feel lost, you are not alone!

My academic journey has lead me to believe a somewhat unpopular opinion; an experienced advisor can be sufficient but is not a necessary ingredient in this process. Surely, having someone to gradually introduce you to an area with questions and tasks of increasing difficulty, and provide sufficient support and guidance throughout the process can help come up with your own questions. Of course, in most cases that is outside of our control.

Although, I do believe it's not necessary. Some of the first original ideas and results I came up with were a product of discussing problems and concepts with other phd students in my group. Bouncing ideas back and forth, attending conferences all together and discussing the presentations and results, having weekly "Theory Seminars", etc. To me, the group of your fellow phd students is almost as important as the advisors themselves. But again, this is a parameter of your environment and not necessarily in your control.

So, what is in your control? I think the biggest value-for-time if you are stuck in the no-mans land, is to read. From the consensus most influential papers of your area to surveys and recent results. Any chance you get, keep building on to that picture in your head of what your area looks like; what are the biggest challenges, what are the most valuable tools, who are the key people whose work you need to follow. It's a slow and tedious process and you have to read a lot of papers, sometimes to even identify the influential ones, but do it. Make sure you read the papers at your own pace, but as your peers have advised you, make sure you understand them (yes, that includes - by definition - the theorems and proofs). Once you have read enough papers and painted your picture ornate, you will start noticing the small, and as you go along larger, "holes" that you can slowly fill with your questions and hopefully answers.

Finally, as anyone who has written any paper ever will tell you, you don't just magically start writing a paper. The whole process is a product of a lot of reading, a lot of trial and error, and a lot of writing and editing. I too have felt at times overwhelmed when reading a paper and truly wondered how, or even if, I would ever be able to come up with a result of the same quality, but don't think about it that way. Start small and keep going. Just remember that when you are reading a paper and it feels daunting you are consuming, in a few minutes, work that was a product of probably hundreds and hundreds of hours.

I am sorry I don't know much about your field, so I can't provide specific advice, but these are my thoughts. Please take them with a grain of salt, as I believe we are on the same boat. Good luck!

• "an experienced advisor is a sufficient but not necessary ingredient in this process", did you mean "...is a necessary but not sufficient ingredient..."?
– user34637
Jun 29, 2018 at 19:09
• Oh I see, you could make sense of it that way too, just would twist the meaning. But what I meant to say is that “an experienced advisor can be sufficient but is not necessary”. I’ll edit it to fix Jun 29, 2018 at 19:15

Here is a suggestion: look for open problems in your field that interests you. Try to reformulate the problem in different representations especially non-standard ones. Try to combine different ideas, theorems, and results from different related fields to build tools to attack your problem. Formulate conjectures and try proving them (or design an algorithm and prove its correctness).

It's a generic question so I'm going to give a generic answer: Speak with your academic adviser! You do have one, right? Are you familiar with his/her research projects? Do any of them interest you? If none do, perhaps you should look for a different adviser...