63
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,546
54
votes
Constraint satisfaction problem (CSP) vs. satisfiability modulo theory (SMT); with a coda on constraint programming
SAT, CP, SMT, (much of) ASP all deal with the same set of combinatorial optimisation problems.
However, they come at these problems from different angles and with different toolboxes.
These ...
- 18.8k
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,223
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,731
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.3k
30
votes
Accepted
Who introduced nondeterministic computation?
I have always seen the notion of nondeterminism in computation attributed to Michael Rabin and Dana Scott. They defined nondeterministic finite automata in their famous paper Finite Automata and Their ...
- 18.1k
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
- 26.7k
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,764
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 ...
- 852
24
votes
Accepted
Why was there a need for Martin-Löf to create intuitionistic type theory?
Very briefly: the simply-typed $\lambda$-calculus does not have dependent types. Dependent types were proposed by de Bruijn and Howard who wanted to extend the Curry-Howard correspondence from ...
- 10.6k
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,820
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.2k
22
votes
Accepted
Curious about computer-assisted NP-completeness proofs
As for question 2, there are at least two examples of $NP$-completeness proofs that involve computer-assistant.
Erickson and Ruskey provided a computer-aided proof that Domino Tatami Covering is NP-...
- 20.7k
22
votes
Accepted
How exactly does lambda calculus capture the intuitive notion of computability?
You're in good company. Kurt Gödel criticized $\lambda$-calculus (as well as his own theory of general recursive functions) as not being a satisfactory notion of computability on the grounds that it ...
- 27.6k
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
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,533
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
Why study type theory?
Type theories in which every type is inhabited are far from being useless. True enough, through the eyes of logic they are inconsistent, but there are other things in life apart from logic.
A general ...
- 27.6k
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. ...
- 967
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,793
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
19
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 ...
- 331
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.2k
18
votes
Accepted
Is there algorithmic mathematical analysis?
Check out
the Computability and Complexity in Analysis network. Quote:
The topics of interest include foundational work on various models and approaches for describing computability and complexity ...
- 4,445
18
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.5k
17
votes
Accepted
Why was Schönfinkel's work on eliminating "bound variables" in logic so crucial?
TL;DR. The metamathematics of binding are subtle: they seem trivial but aren't — whether you deal with (higher-order) logics or 𝜆-calculus. They're so subtle that binding representations form an open ...
- 2,029
17
votes
Accepted
Did Stephen Cook see the significance of showing that SAT is NP-Hard before actually proving it?
First of all, Cook actually showed that the problem of whether a logical expression is a tautology is $\mathbb{NP}$-complete under Cook reductions. The proof however works by replacing them with Karp ...
- 3,731
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 ...
- 27.6k
Only top scored, non community-wiki answers of a minimum length are eligible