40 votes
Accepted

How to find interesting research problems

I strongly disagree with the "find a list of open problems" approach. Usually open problems are quite hard to make progress on, and I'm thoroughly unconvinced that good research is done by tackling ...
  • 13.3k
14 votes
Accepted

Is an NP-hardness proof of an NP-hard problem considered a contribution?

There are venues that are interested by elegant proofs of existing results, see for instance the Symposium on Simplicity in Algorithms. So yes, in some cases an elegant proof can be considered as a ...
  • 1,645
13 votes
Accepted

Is it a bad idea to critique someone's paper in my first publication?

I think the same standards apply, regardless of whether it's your 1st or 100th publication. If you think you've found a mistake in a published paper, a common courtesy is to first contact the paper's ...
  • 10.1k
12 votes
Accepted

Good books on parser theory?

One book that I can recommend is D. Grune, C. J. H. Jacobs, Parsing Techniques: a Practical Guide.
11 votes

"Berman-Hartmanis Conjecture Separates NP From All Super-Poly. DTIME Classes" -- Worthy of arXiv.org?

I'm glad you are interested in complexity but there are some issues in your paper. Your techniques relativize and there is an oracle relative to which the Berman-Hartmanis conjecture is true and NP = ...
10 votes

Research problems in communication complexity

I'll start with answers to your general questions, then give one nice open problem with applications towards circuit complexity. It's hard to say what areas a new communication complexity researcher ...
10 votes

What do you do when you cannot make progress on the problem you have been working on?

In How to Solve It, Pólya advises: "If you can't solve a problem, then there is an easier problem you can solve: Find it."
10 votes
Accepted

Massive online collaboration for solving open problem in theoretical computer science

Polymath projects seems to succeed when a breakthrough happens, and one is trying to optimize the result of the breakthrough or come up with simpler or better proof. See https://en.wikipedia.org/wiki/...
9 votes

What is the best place to get BibTeX entries for ICLR and other machine learning papers?

For NeurIPS (previously NIPS), the NeurIPS website itself is a good source: look for a paper, go to its page, and click on the "BibTex" link. Here is a random sample (!): ICML, COLT, and JMLR appear ...
  • 4,361
9 votes

When should one start looking at existing results in theoretical CS?

Scenario 1: You spend several months tinkering around with colorings, not reading any literature. After many failed attempts you finally discover one that works. Before you can write a paper about it, ...
  • 26.8k
8 votes

Technical article vs. research paper

Thanks for the question; I had similar questions few years ago, before starting in research (I'm not necessarily assuming that's your case). I've looked at a couple of the links, and they don't ...
  • 2,019
8 votes

How to find interesting research problems

David Hilbert is a renowned mathematician. He put forth a list of 23 unsolved problems at the International Congress of Mathematicians in Paris in 1900. I just want to quote part of Yuri Manin ...
  • 121
7 votes

Are there any intersections between Theory A and Theory B?

One cool example of work that straddles things that are typically considered theory A and things typically considered theory B are the lower bounds on the running time of the simplex algorithm with ...
6 votes

Research problems in communication complexity

Several long-standing key open problems are in the Kushilevitz and Nisan textbook (see also the list of errata which mentions that Open Problem 8.6 was solved by Dietzfelbinger). Razborov's 2011 ...
6 votes
Accepted

How to evaluate and compare the performance of algorithms in practice?

I believe what you're looking for is the field of Experimental Algorithmics. There is a text by McGeoch, an ACM Journal, and a previous question on this site that provides a reading list for the field....
6 votes
Accepted

Where do people publish/submit their work on type theory?

You can follow the activities of the EUTypes network, and see what meeting are organized. The list of events is growing nicely. As for journals, I can think of Logical Methods in Computer Science and ...
  • 26.8k
6 votes
Accepted

What is the best place to get BibTeX entries for ICLR and other machine learning papers?

As an update, I noticed that DBLP has added ICLR to tracking as of today. Now it has ICLR papers and their bibtex available at https://dblp.uni-trier.de/db/conf/iclr/
6 votes

Some good Theoretical Computer Science Journals

Apart from top conferences mentioned by @usul, I think Journal of the ACM (JACM) is a top journal in computer science, which also includes many excellent theoretical computer science papers. In ...
6 votes

Are there any intersections between Theory A and Theory B?

One example (from my research field) is analysis of dynamical systems: in a (linear) dynamical system, you are given a matrix $A\in {\mathbb Q}^{d\times d}$ and you reason about various properties of $...
  • 5,271
3 votes

Are research papers hard to read?

Another reason why papers are often hard to read is because the authors have usually just figured out the result and don't have much hindsight or time to digest what they did. When you write a paper, ...
  • 7,485
3 votes

Good books on parser theory?

If you want to learn about the theory of parsers, I recommend volume 1 of this classic book: Aho, Alfred V.; Ullman, Jeffrey D., The theory of parsing, translation, and compiling, Prentice-Hall (1972)...
3 votes

What would you advise someone who wants to do research as a hobby?

As already said, it is very difficult due to time, background, money and discipline. Generally, if you are able to make a contribution to the field, in principle you would get a PhD and could work as ...
3 votes

How should I perform research as an Undergraduate

Yes, ask your professor to give you a problem that you may solve as an undergraduate. You can also look for publications that say that the problems are appropriate for undergraduates. I think that a ...
3 votes
Accepted

How to generate Skolem function in practice

First of all there are two Skolem transformations, one replaces universal quantifiers and preserves validity, the other one replaces existential quantifiers and preserves satisfiability of the formula....
3 votes

Can theoretical computer science be combined with mechanism and information design and applications in financial markets

This depends on whether the CS department you are studying at has somebody working in this field. Some of them (at least three of the top ten in the U.S.) do, and some of them don't, and some of them ...
2 votes

Is there research on algorithmic design patterns?

There are many general techniques and meta-theorems. Unlike software engineering, in TCS we don't want to repeat things similar to what the others did, we want to create something new or solve an ...
  • 3,430
2 votes

Massive online collaboration for solving open problem in theoretical computer science

If a massively online collaboration is set up, then it should try to focus on problems with a reasonable chance of success. The three classical construction problems of antiquity are known as "...
2 votes

Are there any intersections between Theory A and Theory B?

As far as I understand it, linear logic and "implicit complexity theory" use tools that are often found in Theory B (type theory, theory of programming languages, etc.) to capture and study complexity ...
2 votes

Are patents good sources for academic research?

Are patents good sources for academic research? In general, a clear NO. Typically, patents are intentionally written in a diffuse language to cover as much ground as possible (without incuring the ...
  • 91
2 votes

Areas of research and open problems in functional programming

The computational implications of homotopy type theory & higher type theory. Homotopy type theory was invented and developed by a group of computer scientists and mathematicians as a new ...
  • 1,125

Only top scored, non community-wiki answers of a minimum length are eligible