52

Is this a common situation that a researchers notices that her idea is not going to work after considerable amount of work? Yes. But as you get more experienced, you're able to "fail fast" - learn how to test the idea quickly to see if it passes a 'smell test'. What do you do when you realized that an approach you had in mind is not going to work ...


38

This is very common, and certainly frustrating. Here is my advice: Don't wait until you have a complete result to start writing. Maintain a TeX document with formal descriptions of your problem, proofs of preliminary lemmas, etc. as you go. It is easy to convince yourself that something is true and overlook simple mistakes if you are holding the argument ...


38

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 some hard but uninteresting problem in a technical area. That being said, of course solving an open problem is really good for academic credentials. But that's ...


24

I like to give my students Keshav's "How to Read a Paper" (ACM DL)(PDF). He outlines some pretty effective strategies. In general, I'd say practice makes perfect and you just have be very patient with the process. Try different strategies and just keep reading and re-reading the paper until it makes sense. If you have to read and re-read one paragraph for ...


23

I think the overall goal of PL theory is to lower the cost of large-scale programming by way of improving programming languages and the techincal ecosystem wherein languages are used. Here are some high-level, somewhat vague descriptions of PL research areas that have received sustained attention, and will probably continue to do so for a while. Most ...


15

Simon Peyton Jones has an excellent web page devoted not only to advice on writing introductions, but whole papers, and there is a cool video as well. On page 18 of his slides he says that the purpose of an introduction is to: Describe the problem. State your contributions. He then goes on for a while to explain what precisely that means in pracrtice. But ...


14

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 contribution, especially if it offers new insights.


13

Regarding topics There are different type of issues that may be considered theoretical computer science. The important word here is "theoretical" (as we all have some idea of what computer science deals with). Understanding the word theoretical is not so obvious. For a long time I took it to mean mathematical, as opposed for example to "hacking". I learned ...


12

Let me list some assumptions which limit the programming language research. These are hard to break away from because they feel like they are an essential part of what programming languages are about, or because exploring alternatives would be "not programming language design anymore". With each assumption I list its limiting effects. Programs are syntactic ...


12

I think this is a type of "educational snowball effect". The academics writing the papers have "snowballed" so much information about their subject, that when they write their paper, they speak entirely in terms of their subject. Any given sentence in that paper, however, might make mention of several other research topics that you have no idea about. For ...


12

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


12

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 authors for a clarification, as Noam suggested in the comments. If the authors confirm that it's indeed a mistake, you can indicate that in the paper (cite it ...


11

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 = EXP. The main issue is that you can't do self-reference for time-bounded machines since you can't simulate and stay within the time bound.


10

Edit: It's been 2+ years so I'm updating the answer. Every year the Notices of the AMS publishes a list of math journals and their backlogs, turnaround times, etc. Here are some of the previous articles: Nov 2009, Nov 2010, Nov 2011, Nov 2012, Nov 2013. Based on the Nov 2013 article, here are some CS Journals and their median submission to final acceptance ...


10

This should be perfectly acceptable if it is framed as an exposition article. There is a long tradition of expository articles in mathematics (one example that comes to mind is Thurston's exposition of a method developed by Conway to determine if the plane can be tiled by a given shape, see here). Just make sure that the abstract and the introduction convey ...


10

Normal research papers are written primarily for other researchers, typically people in the same field, who are also at the cutting edge of research themselves. It is not surprising that they are hard to understand for normal professionals. Some top researchers do know that a wide readership is a prize to be sought and develop skills to write in such a way ...


10

The excellent answers so far have left out one reason that I think is critical to both understanding and publishing papers: the reviewers are not really the eventual audience. A paper's reviewers are generally experts in the sub-field, and experts on the topic if possible. A paper's readership are generally newcomers, or are only passingly familiar with the ...


10

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

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 should delve into, since easy problems have likely been solved already, and harder problems are hard ;) One suggestion is to take known communication lower ...


10

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/Polymath_Project#Problems_solved. As such, you would have to pick a problem of this nature in CS. The only one that comes immediately to mind is improving the ...


8

Usually the main idea of a paper is simple. However it is often the case that the translation from the simple idea to mathematically rigorous proofs adds quite a bit of minor technical details, which contribute to the difficulty of understanding the paper. If you ask an author to explain their result in person, they are often able to do so pretty efficiently ...


8

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 really look like research papers in form; I mostly can't really tell if their technical content could be made into a paper because I'm not an expert in the field, ...


8

In one sense, browsing this site will tell you the kinds of questions theoretical computer scientists think about (at a low level). At a very high level, theoretical computer scientist ask questions about the mathematical foundations of computation: what can we compute ? how can we compute it ? How fast ? what happens when we have limited resources to ...


8

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 interview entitled "Good Proofs are Proofs that Make us Wiser" about Hilbert and his list: This year’s International Congress is the last ICM in this century. Do ...


8

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 to have similar BibTex-ready websites: see http://proceedings.mlr.press/. For instance, going to the abstract of a randomly chosen paper from ICML'15: ICLR ...


7

Depending on what you want to do with it, a possible alternative is to just fold it into the work you're doing, i.e. recapitulate the results, with clear attribution, but inside your work. The results in Szelepcsenyi's paper don't seem to take up too much space to do this with a journal paper. It'd be a bad idea with a conference paper. Of course if you're ...


7

There are some nice answers by others. I just want to add a few points: Don't panic! Usually, you expect to be graduated sooner than the average students because you think that you are smarter than most of them. Fast graduation doesn't mean you are better than others. Longer graduation time doesn't mean you are weaker that others. You are working on totally ...


7

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 randomized pivoting rules, due to Friedmann, Hansen, and Zwick. The lower bounds rely on lower bounds for policy iteration algorithms for parity games, which are ...


6

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 introductory survey lists four open problems, two of which are also in the KN textbook: (KN 2.10) Is it true that $D(f) \le O(\log \chi(f))$? Here $\chi(f)$ is the ...


6

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.


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