96

$\lambda$-calculus has two key roles. It is a simple mathematical foundation of sequential, functional, higher-order computational behaviour. It is a representation of proofs in constructive logic. This is also known as the Curry-Howard correspondence. Jointly, the dual view of $\lambda$-calculus as proof and as (sequential, functional, higher-order) ...


63

Here is my point of view, which I learned from Guy Kindler, though someone more experienced can probably give a better answer: Consider the linear space of functions $f: \{0,1\}^n\to\mathbb{R}$, and consider a linear operator of the form $\sigma_w$ (for $w\in\{0,1\}^n$), that maps a function $f(x)$ as above to the function $f(x+w)$. In many of the questions ...


60

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 institution has one. We want to know when our faculty are behaving badly and often we can help.


57

I do not want to sound condescending, but the math you are studying at the undergraduate and even graduate level courses is not advanced. It is the basics. The title of your question should be: Is "basic" math needed/useful in AI research? So, gobble up as much as you can, I have never met a computer scientist who complained about knowing too much math, ...


57

Strassen's statement needs to be put into context. This was an address to an audience of mathematicians in 1986, a time when many mathematicians did not have a high opinion of theoretical computer science. The complete statement is For some of you it may seem that the theories discussed here rest on weak foundations. They do not. The evidence in favor of ...


56

Here is one problem described in the book "A second course in formal languages and automata theory" by Shallit. Let $u$ and $v$ be two distinct words with $|u|=|v|=n$. What is the size of the smallest DFA that accepts $u$ but rejects $v$, or vice versa? Robson, in his paper "Separating strings with small automata" in 1989 proved an upper bound $O(n^{...


55

Theoretical computer science is a broad field and the importance of programming depends on what you do in TCS. I will mention two ways in which programming can help you, without implying that these are the only ways. First, if you design algorithms for problems of practical importance, implementing your algorithms and making the code available to others ...


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


47

I feel compelled to cite Doron Zeilberger on this: Opinion 37: Programming is Even More Fun Than Proving, and, More Importantly It Gives As Much, If Not More, Insight and Understanding. Read the opinion, it's full of gems (btw he tends to be deliberately provocative). For example, "The best way to understand something is to teach it. But even better then ...


47

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 differences are largely in how each approach structures information about the exploration of the search space. My working analogy is that SAT is machine code, while the ...


44

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 automata, we expect to treat data that is bigger than the state space, and Turing Machine are a model for the other way around (state space >> data) by making the ...


42

Here's a very simple decision problem about DFA's. Given a DFA M, does M accept the base-2 representation of at least one prime number? Currently, we don't even know if this problem is recursively solvable. If it is recursively solvable, and we had an algorithm for it, we could resolve the longstanding open problem about whether there are any Fermat ...


41

It might come as no surprise, but there is a substantial overlap between cstheory Q&A power-users and the blogosphere. We even had a dedicated blog for a while, with some great posts but it fell into disuse. However, I thought I would list some of the blogs run by our top 38 users that have had new posts since 2012: David Eppstein's 0xDE: graph-theory ...


40

I was just referred to this question by graduate students that, in my opinion, were far too influenced by the answers. So let me start with two generic advises. To the aspiring scientist: Don't assign too much weight to any answer on such matters, and don't assume that a small and highly non-random sample represents the common views among senior (or non-...


39

The Černý conjecture is still open and important. It is about DFAs that have a synchronizing word (a word with the property that two copies of the automaton started in different states always end up in the same state as each other after both processing the word), and asks whether (for $n$-state automata) the length of the shortest such word is always at most ...


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


37

I did a survey on Twitter about this a while back, results here. A few of my favorites: Parametric Polymorphism through Runtime Sealing, or, Theorems for Low, Low Prices! by Jacob Matthews and Amal Ahmed, ESOP 2008 DOI:10.1007/978-3-540-78739-6_2 F-ing Modules by Andreas Rossberg, Claudio Russo, and Derek Dreyer, TLDI 2010 Cons should not cons its arguments ...


35

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


33

You can be a quite successful theoretical computer scientist without programming. For a few people, programming is quite difficult, and if you are one of them you shouldn't despair and switch fields. However, for most math and computer science graduate students, learning to program is not particularly difficult, and is a skill which is very useful. You ...


33

There's another answer that no one has really brought up. Programming can actually lead to interesting theory. A lot of the recent developments in hashing (especially tabulation hashing) are motivated not by theoretical concerns per se, but by the fact that the theoretically optimal algorithms aren't that great in practice. This of course is something you ...


33

Consider the function (taken from here) $\qquad \displaystyle f(n) = \begin{cases} 1 & 0^n \text{ occurs in the decimal representation of } \pi \\ 0 & \text{else}\end{cases}$ Despite the looks, $f$ is computable by the following argument. Either $0^n$ occurs for every $n$ or there is a $k$ so that $0^k$ occurs but $0^{k+1}$ does not. We do not ...


32

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 even forgotten. Historically, the Turing Machine is perhaps the most intuitive model of several developed trying to answer the Entscheidungsproblem. This is ...


31

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 Decision Problems, 1959. Rabin's Turing Award citation also suggests that Rabin and Scott introduced nondeterministic machines.


30

I used to like quirky titles when I started out in computer science but got bored eventually. Some authors manage to write titles that are clever, memorable and relevant but most attempts at funny titles results in unnecessarily long, uninformative and kludgy phrases that I find difficult to remember and look up. There are papers like Pnueli's The Temporal ...


29

Talk to people, even if they are scary big names. Attend all the keynote/invited presentations. Attend the talks most relevant to you. Don't be afraid to ask questions. Attend the social events, meet other graduate students, have fun. Talk enthusiastically about your research. Make sure you have a 1 minute pitch describing your work, plus a 5 minute ...


29

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 that there is "Theory A" and "Theory B" (with no implied order relation between them): Theory A consists of the theory of algorithms, complexity theory, ...


28

No. Publish. The only things that would be actively harmful to your career would be publishing most of your papers in third-tier venues (strongly suggesting that you have mostly third-tier results), or publishing anything in a fake/scam conference (strongly suggesting that you are either dangerously uninformed or a scammer yourself).


28

Software Foundations by Benjamin C. Pierce would be a good place to start. It would be a make a good precursor to his Types and Programming Languages. There is also Simon Thompson's Type Theory and Functional Programming and Girard's Proofs and Types.


27

I did not know of these until recently. 1) The LU decomposition of a matrix is due to Turing! Considering how fundamental LU decomposition is, this is one contribution that deserves to be highlighted and known more widely (1948). 2) Turing was the first to come up with a "paper algorithm" for chess. At that point, the first digital computers were still ...


27

Let me disagree with the other responses. While there are clearly notable examples of people who can transition to industry and back (see other answers), going to a non-research industrial position, even for a couple years, will make it very hard to return to academia, unless you're already very famous. The reason is not because academics look down on ...


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