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 ...


39

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 ...


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 ...


24

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 ...


17

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

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

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

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

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.


6

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 Mathematical Structures in Computer Science. I can also think of some journals which are owned by you know who, so not mentionable.


6

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 $A^n$. For example, the Kannan-Lipton Orbit Problem asks, given two vectors $s,t\in \mathbb Q^d$, whether there exists $n$ such that $A^ns=t$. These types of ...


5

You can subscribe to the RSS of ArXiv, and you can keep track of which papers are getting accepted to the relevant conferences.


5

Not standard topics, no. And sorry, I have no general overview. However, I would have a look at the PhD thesis of Klaus Reinhardt for at least a picture of the various families that live in this area. See page 64 for a diagram of the zoo. Motivated by Petri Nets with inhibitor arcs Reinhardt studies priority multicounters with restrictions on when to do ...


5

here is a new collaborative online Latex editor called WriteLatex that looks promising, as a near one-stop shop for many scientific writing needs/requirements. works on mobile has realtime preview easy/private sharing finds latex errors allows add on latex libraries/styles cloud storage the coauthor John Hammersley posted an announcement in tcs se meta ...


5

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 addition, I read some papers published in Algorithmica. Also, just giving a reference, I find a link to some journals related to Discrete Mathematics (particularly ...


4

it occurred to me that 1sthand accounts might be helpful, but those seem to be somewhat rare in CS (as opposed to eg mathematics, biographical/ memoir-like writing etc). here are two online refs that address the question & may be helpful. they are more aimed at PhD student life & CS oriented but most will carry to professor level research (other than ...


4

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/


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