A soft question is a question (possibly subjective) about the field of theoretical computer science as opposed to being a question in theoretical computer science.

learn more… | top users | synonyms

9
votes
4answers
2k views

Theoretical computer science self-study resources for programmers

I am a pretty proficient software engineer, but I don't know much theory. I want to learn more theory. Particular topics that I am interested in are: computational complexity, formal languages, and ...
37
votes
1answer
1k views

Importance of single author papers?

I'm a fourth year PhD student in theoretical computer science. I'd like to stay in academia, so I'm thinking about how best to advance my career. Obviously the best way to do that is write lots of ...
14
votes
2answers
238 views

Recent TCS publications with philosophical aspects

Many computer science publications from the 1950s and 1960s contain fascinating philosophical speculations on the nature of the mind and the meaning of information in relation to the physical world. ...
1
vote
1answer
157 views

The most applicable areas in Theoretical Computer Science [closed]

I just wanted to know areas in common to Theoretical Computer Science which have a lot of carrer prospects outside of academia. I specifically wanted to know because I am interested in almost all ...
1
vote
0answers
104 views

NP Complete Problems - Book References - Reductions and Use Cases? [closed]

What are the best self contained Books that mainly serve the purpose of: Demonstrating NP Complete Reductions (other than Garey and Johnson, which mainly lists the problems as NP complete, and ...
5
votes
1answer
170 views

Is education for research-based CS at odds with that of industrial CS?

I'm an undergraduate strongly interested (well, this is a hunch) in theoretical CS and all things mathematical. While I'd like to devote my time to participating in research opportunities and learning ...
9
votes
2answers
543 views

Massive online collaboration for solving open problem in theoretical computer science

In Polymath projects a large group work on an open problem. What kind of problems seem to work best in this framework? Are there any good candidates for a polymath project in theoretical computer ...
19
votes
3answers
2k views

Who introduced nondeterministic computation?

I have two historical questions: Who first described nondeterministic computation? I know that Cook described NP-complete problems, and that Edmonds proposed that P algorithms are "efficient" ...
4
votes
0answers
77 views

major applied focuses of different proof assistants

Currently, what are the major applied focuses (if any applications can be deserved such a distinction) of different proof assistants, such as the following? If there are significant differences ...
1
vote
0answers
73 views

“conservative approximate Set Cover”?

We are given a lattice graph $L$, embedded on the plane, and a certain "shape" (a connected, acyclic subgraph $S$ of $L$). The task is to approximately cover $L$ with translated, rotated and flipped ...
7
votes
1answer
1k views

Did Stephen Cook see the significance of showing that SAT is NP-Hard before actually proving it?

If I understand correctly, to prove that problem $A$ is NP hard, you need to pick all possible problems $B_{i}$ that are in NP and then prove that they reduce to $A$ by using a polynomial time ...
9
votes
3answers
469 views

Is there algorithmic mathematical analysis?

There are algorithmic graph theory/number theory/combinatorics/information theory/game theory. Is there algorithmic mathematical analysis? According to wiki, mathematical analysis includes the ...
0
votes
0answers
206 views

What is the difference between a TCS PhD thesis and Computer Science experimental PhD thesis?

I'm doing my PhD in computer science, namely theoretical computer science and currently waiting for my VIVA. I think one of my examiner is an experimental person, how can I convince her that my work ...
2
votes
0answers
203 views

What one bit of computable information would you most like to know? [closed]

If you could ask one computational yes/no question, what would it be? To be precise, you get to specify a Turing machine (in a convenient language) and an oracle will tell you whether or not it ...
10
votes
6answers
642 views

Are there any topics in theoretical CS that are more about pure math?

I am a graduate student in theoretical computer science, and in particular, approximation algorithms. I find now that I am more interested in pure math (I can say this because I seem to have enjoyed ...
-1
votes
1answer
245 views

Why study type theory?

After reading the literature on type theory (especially the constructive kind - CTT) I'm left wondering "why" should one study type theory, specifically within the confines of "computing" in general? ...
10
votes
1answer
899 views

Why was there a need for Martin-Löf to create intuitionistic type theory?

I've been reading up on Intuitionistic Type Theory (ITT) and it does make sense. But what I'm struggling to understand is "why" was it created in the first place? Intuitionistic Logic (IL) and ...
6
votes
2answers
391 views

How would a theory of computation course that culminated in lambda-calculus as “the” model of computation, instead of Turing machines, look like?

Currently, our ToC (Theory of Computation) courses are designed with the following progression of topics: Finite automata and regular languages Pushdown automata and context-free languages Turing ...
1
vote
3answers
383 views

Why is lambda calculus so “function” oriented?

I've always had this question nagging at me subconsciously but have never been able to intuitively grasp it. Why does $\lambda$-calculus have a functional notation? Why is everything a function? It ...
0
votes
1answer
202 views

Electrical engineering student interested in Theoretical computer science

I am sophomore studying electrical engineering and I have immense interest in pure mathematics and theoretical computer science. I have studied abstract algebra ,real analysis and little bit of ...
12
votes
1answer
346 views

Why was Schönfinkel's work on eliminating “bound variables” in logic so crucial?

AFAIK, The first evidence of using higher order functions goes back to Schönfinkel's 1924 paper: "On the Building Blocks of Mathematical Logic" - where he allowed one to pass functions as ...
8
votes
2answers
595 views

How exactly does lambda calculus capture the intuitive notion of computability?

I've been trying to wrap my head around the what, why and how of $\lambda$-calculus but I'm unable to come to grips with "why does it work"? "Intuitively" I get the computability model of Turing ...
18
votes
1answer
612 views

Constraint satisfaction problem (CSP) vs. satisfiability modulo theory (SMT); with a coda on constraint programming

Does someone dare to attempt to clarify what's the relation of these fields of study or perhaps even give a more concrete answer at the level of problems? Like which includes which assuming some ...
20
votes
5answers
639 views

Curious about computer-assisted NP-completeness proofs

In the paper "THE COMPLEXITY OF SATISFIABILITY PROBLEMS" by Thomas J. Schaefer, the author has mentioned that ...
2
votes
2answers
143 views

Reference on cryptography methods

I'm looking for a good reference, possibly a survey, on the different types of cryptography methods. As far as I understand, the security of a cryptographic method depends on some hardness ...
4
votes
0answers
229 views

Faculty hiring differences between US and UK/Germany [closed]

This question contains some great answers on how to get a job. I wonder whether there are some significant differences if I will be looking for a position in Europe (in particular, UK and Germany) as ...
2
votes
1answer
415 views

Some good Theoretical Computer Science Journals

I have been doing some work in Theoretical Computer Science(especially related to algorithms), and I wanted the publish some of my findings. Can someone please suggest some good journals or ...
10
votes
3answers
486 views

Uses of $\infty$-categories in TCS

I'm not a theoretical computer scientist. I'm a stable homotopy theorist using $\infty$-categories. I've seen applications of category theory and topos theory to theoretical computer science, and I ...
1
vote
1answer
284 views

How difficult is it to work on mathematics problems as a computer science graduate student?

I am interested in problems typically tackled in theoretical computer science departments as well as seperate problems found in mathematics departments. Both would be more proof based. Is it easy to ...
8
votes
5answers
328 views

Are there any schools with researchers interested in cellular automata?

I have been working on an independant project focusing on cellular automata and was wondering if this might be something that I could continue on in graduate school somewhere. I've seen some ...
-2
votes
1answer
179 views

who found out Theory of Computer Science? [closed]

who first started to analyse computers theoretically ? who gave birth to Theory of Computation ?
7
votes
4answers
381 views

Explaining computer science algorithms/concepts/ideas using metaphors

Recently I found an interesting algorithm book entitled 'Explaining Algorithms Using Metaphors' (Google books) by Michal Forišek and Monika Steinová. "Good" metaphors help people understand and even ...
13
votes
2answers
533 views

Long-Standing Conjectures later trivially proved by an implication

I'd like to know if there have been conjectures that have long been unproven in TCS, that were later proven by an implication from another theorem, that may have been easier to prove.
-1
votes
1answer
77 views

The Arrow of Time in a Non-Physical Realm [closed]

Could there be a logically consistent theory supporting the transmission of non-physical information to a point in time previous to the time it was sent using a computer network (quantum theory, etc)? ...
4
votes
0answers
168 views

What makes for a good paper abstract?

I am writing a paper for a TCS conference and wondering what the community's opinion is on how abstracts in TCS should be written, good practices, or rules of thumb. I thought that I had read enough ...
40
votes
16answers
10k views

Most memorable CS paper titles

Following a fruitful question in MO, I thought it would be worthwhile to discuss some notable paper names in CS. It is quite clear that most of us might be attracted to read (or at least glance at) a ...
0
votes
1answer
81 views

Talk for K-12 Students + General Audience Reference Request

I will be giving talks about general topics in CS, and want to hit on TCS as well. The talks will be given to K-12 schools, so not all of them will be seniors who may go to an undergraduate program at ...
29
votes
10answers
4k views

Algebra oriented branch of theoretical computer science

I have a very strong base in algebra, namely commutative algebra, homological algebra, field theory, category theory, and I am currently learning algebraic geometry. I am a math major with an ...
32
votes
3answers
2k views

How to find interesting research problems

Despite several years of classes, I'm still at a loss when it comes to choosing a research topic. I've been looking over papers from different areas and spoken with professors, and I'm beginning to ...
15
votes
5answers
2k views

What are some good introductory books on type theory?

I'm recently studying Haskell and programming languages. Could someone recommend some books on type theory?
5
votes
0answers
119 views

What is the significance of regarding the mutual exclusion problem as a problem of physics?

In the description of his own paper "On Interprocess Communication" [Distributed Computing 1, 2 (1986), 77-101], Leslie Lamport wrote Most computer scientists regard synchronization problems, such ...
0
votes
0answers
133 views

introduction to spectral geometry

In the paper Belkin, Mikhail, and Partha Niyogi. "Laplacian eigenmaps and spectral techniques for embedding and clustering." In NIPS, vol. 14, pp. 585-591. 2001 The ...
4
votes
4answers
478 views

TCS conferences for undergraduate students?

I have noticed that ICFP has a student volunteer program and research program that accepts undergraduate students and POPL have the Programming Language Mentoring Workshop, so I was wondering if there ...
10
votes
3answers
2k views

What does research in theoretical computer science involve?

I am trying to understand what is involved in theoretical computer science research. What do theoretical computer scientists do? I know a significant time is spent on teaching, supervising graduate ...
7
votes
0answers
515 views

Why is single authorship so common among breakthrough papers in computer science?

Looking at the list of important papers in computer science one notices that the majority are authored by a single author. Those include classic papers of Turing, Shannon, Karp and Cook. Cook's solo ...
0
votes
1answer
394 views

Which areas of TCS are better for a math bachelor?

I am graduating from mathemetics bachelor program and I've been accepted for masters degree in mathematics. But I am not sure to pursue math, hence I am looking for other field I can do research. I am ...
51
votes
10answers
5k views

Are there any open problems left about DFAs?

After studying deterministic finite state automata (DFA) in undergrad, I felt they are extremely well understood. My question is whether there is something we still don't understand about them. I ...
13
votes
1answer
815 views

Careers for theoretical computer scientists

What are the typical careers for theoretical computer scientists (people with graduate degree in theoretical computer science)? What kind of industries and institutions look for theoretical computer ...
0
votes
1answer
633 views

Are aspects of the 20 questions game ambitious enough for graduate research?

I am finishing a masters program this year and I'm interested in doing a Ph.D. in the field of Artificial Intelligence. I have an idea I've been tinkering with for a while, but some people have told ...
39
votes
5answers
16k views

What CS blogs should everyone read?

Many top notch computer science researchers and research groups) maintain active blogs that keep us updated on the latest research in the authors' fields of interest. In most cases, blog posts are ...