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 ...
- 8,616
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 ...
- 8,598
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, ...
- 11.4k
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 ...
- 3,751
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 ...
- 36.9k
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
- 27.3k
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 ...
- 6,979
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 ...
- 862
23
votes
Importance of single author papers?
In some fields (like e.g. Economics and Mathematics) single authored papers -are- a good thing to have when you go on the job market. In theoretical computer science, collaboration is much more common,...
- 9,850
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 ...
- 10.3k
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/...
- 4,788
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. ...
- 341
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 ...
- 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. ...
- 977
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 ...
- 693
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 ...
- 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 ...
- 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 ...
- 661
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 ...
- 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
...
- 11.4k
19
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 ...
- 50.9k
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....
- 10.3k
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' ...
- 11.4k
17
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 ...
- 11.4k
16
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 ...
- 28.3k
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.
- 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 ...
- 4,011
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 ...
- 2,878
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, ...
- 11.7k
16
votes
Solo single author paper vs the comfort of having you advisor on the paper?
I would encourage her to publish by herself if there is no input from the advisor (in terms of problem, ideas, etc). The advisor may not be able to do a very careful reading but it is quite common for ...
- 6,979
Only top scored, non community-wiki answers of a minimum length are eligible