# 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. – Sasho Nikolov Jun 27 '18 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 '18 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. – András Salamon Jun 27 '18 at 19:56
• This advice seems relevant here. – Jeffε Jun 29 '18 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.