# Tag Info

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

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

### 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
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
Accepted

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

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

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

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

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

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

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

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

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

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

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

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