64 votes

Single author papers against my advisor's will?

As a department chair, I can say you aren't alone. These situations come up all too often. Please do reach out to your department chair, graduate program director or grad student ombudsperson if your ...
Lance Fortnow's user avatar
45 votes

Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?

To complete the other answers: I think that Turing Machine are a better abstraction of what computers do than finite automata. Indeed, the main difference between the two models is that with finite ...
Denis's user avatar
  • 8,843
34 votes

Recent advances in computer science since 2010?

Deriving fast JIT compilers from interpreters. It has long been known, that, in principle, compilers can be derived from interpreters in a mechanical way. This is a special case of partial evaluation, ...
32 votes
Accepted

Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?

There are two approaches when considering this question: historical that pertains to how concepts were discovered and technical which explains why certain concepts were adopted and others abandoned or ...
chazisop's user avatar
  • 3,796
31 votes
Accepted

Where to learn more about what Theoretical Computer Science is?

First, "theoretical computer science" means different things to different people. I think for most users on this site, a historical caricature (which reflects some modern sociological tendencies) is ...
Joshua Grochow's user avatar
30 votes
Accepted

Is there any book on the philosophical implications of Theoretical Computer Science?

Try the 50+ page essay "Why Philosophers Should Care About Computational Complexity" https://arxiv.org/abs/1108.1791
Ryan Williams's user avatar
28 votes

Single author papers against my advisor's will?

You should switch advisors. Since you are independently writing papers and have a track record, it should be possible to find a fair-minded theory advisor in a different technical area who is willing ...
Chandra Chekuri's user avatar
27 votes

Why isn't TheoretiCS very popular yet?

Disclaimer: I'm managing editor for TheoretiCS. It is true that TheoretiCS is not as well known as it may be in some research areas within Theoretical Computer Science. But in many respects it is ...
Nathanaël Fijalkow's user avatar
25 votes

Turing award papers

Yes, it happens that the work that merits the Turing award was pioneered or introduced in a single very influential paper. Sometimes, this is even explicitly the reason for the award. For example, in ...
Caleb Stanford's user avatar
23 votes
Accepted

Correcting a conference paper error in the journal version

I think it is very helpful to point out if and where previous results are erroneous. I've done this myself (more times than I would have liked to). My style is to state the correct result, and in ...
Aryeh's user avatar
  • 10.5k
23 votes
Accepted

Sources of open problems?

Here's a partial list of collections of open problems in TCS, broadly construed. Note that a collection of "major open problems" exists already on this site: http://cstheory.stackexchange.com/...
Huck Bennett's user avatar
  • 4,868
22 votes

Writing a paper as a single author in 1st person singular

I am not a native English speaker, but I don't think this is important here. The appropriate thing is not what an English professor or a poet suggests, but what is standard in the particular field. ...
Christian Matt's user avatar
22 votes

Any fundamental papers in TCS which were found to be incorrect/wrong later?

One example is the claimed proof of the Gilbert-Pollak conjecture on the Steiner ratio, which appears in FOCS'90, and Algorithmica. The conjecture is now considered open. Another examples include a ...
Yixin Cao's user avatar
  • 2,560
21 votes
Accepted

Writing a paper as a single author in 1st person singular

The pronoun used is not in reference to the author or authors but about the reader, about the audience. We is used to include the reader in the process of discovering and understanding the result. ...
Logan Mayfield's user avatar
21 votes

Algorithms Careers

A friend of mine works on the combinatorics of Sturmian words, and did so for years. A Sturmian word is typically obtained from a straight line drawn on a lattice: whenever the line crosses an ...
Matthieu Latapy's user avatar
20 votes

How do journals serve the TCS community?

The process of journal reviewing shakes out bugs. Conference reviewers tend not to look at papers with a fine-tooth comb; the program committee process gives them too many papers to review in too ...
David Eppstein's user avatar
20 votes
Accepted

Advice for a mathematician trying to present a paper at a CS conference?

First and foremost, stay on time. Usually, at conferences you are supposed to talk for a very limited amount of time, e.g. 25 minutes including 5 for questions. In such slot you will not be able to ...
chi's user avatar
  • 668
20 votes

Is parameterized complexity going to be the future of complexity theory?

Predicting the future is nigh impossible, especially so for cutting-edge research. I don't think anyone predicted how much impact deep learning is now having or that cryptography would be taken over ...
Thomas's user avatar
  • 2,803
20 votes
Accepted

Why do TCS papers have author names in alphabetical order of their surnames?

The American Mathematical Society has released a statement (pdf link) about the commonly accepted practice of listing authors in alphabetical order in mathematics. Their reasoning applies, in my ...
Ilkka Törmä's user avatar
20 votes

Any fundamental papers in TCS which were found to be incorrect/wrong later?

The very influential Karp, Vazirani, Vazirani paper on online bipartite matching turned out to have a mistake in one lemma (see here for details) that was only discovered close to two decades after ...
gov's user avatar
  • 341
20 votes

Recent advances in computer science since 2010?

Low precision floating point data types. Historically, most programming used the IEEE 754 Standard for Floating-Point Arithmetic. Simplifying a great deal, IEEE 754 floats (64 bits version) give you ...
19 votes

Reviewing a paper and found a better solution

I don’t think there’s a clear protocol. I’ve seen referees generously offer improvements. I’ve seen authors offer coauthorship for those improvements. I’ve seen the referee accept or decline the offer....
Aryeh's user avatar
  • 10.5k
19 votes

Recent advances in computer science since 2010?

Liquid types. Introduced in [1], and refined in multiple follow-up papers. Liquid types can be seen as a form of dependent types that break with traditional type theory which is keen to have 'nice' ...
18 votes
Accepted

(How) Could we discover/analyze NP problems in the absence of the Turing model of computation?

You may wish to look at cost semantics for functional languages. These are various computational complexity measures for functional languages that do not pass through any kind of Turing machine, RAM ...
Andrej Bauer's user avatar
  • 28.9k
18 votes

What is the "question" that programming language theory is trying to answer?

The overall purpose of PLT is to make industrial software engineering (in a general sense) cheaper (also in a general sense), through optimising the most important tool (programming languages) and ...
Martin Berger's user avatar
16 votes

Do I have to give up the Law of the Excluded Middle in order to Learn $\lambda$-Calculus?

To me, your question seems analogous to saying "I've heard that non-Euclidean geometry requires me to give up Euclid's fifth axiom, which is very useful in many mathematical contexts." You don't have ...
Alexis's user avatar
  • 261
16 votes

Is there any book on the philosophical implications of Theoretical Computer Science?

Quantum Computing Since Democritus by Scott Aaronson is the closest match I can think of. I don't think there is a single book completely devoted to philosophical implications of TCS.
Gustav Nordh's user avatar
  • 1,047
16 votes

Any fundamental papers in TCS which were found to be incorrect/wrong later?

There is some sort of "meta-flaw" pointed out by the following paper: SOS is not obviously automatizable, even approximately. R. O'Donnell. ITCS '17. Roughly speaking, it turns out that constant ...
Mahdi Cheraghchi's user avatar
16 votes

Why most of the top TCS conferences are not double-blind?

This is not an answer to the question but too long for a comment by 1253 characters. STACS 2021 used light double blind review. We used easychair for it, which provides some functionality for double ...
Markus Bläser's user avatar
16 votes
Accepted

Can theoretical computer science be applied in social sciences?

I won't say it is impossible, but to me it seems... challenging at best. Social science deals with the behavior of humans, and humans are complex. TCS deals with mathematics and computer algorithms, ...
D.W.'s user avatar
  • 12.1k

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