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

16
votes
3answers
1k 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
65 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
69 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
455 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
191 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
200 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
618 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
198 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? ...
9
votes
1answer
775 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 ...
5
votes
1answer
296 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
366 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
186 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
316 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
570 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 ...
17
votes
1answer
367 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 ...
0
votes
0answers
53 views

Proof for a subpart for the painter's problem

I've been looking at the painters problem here: http://leetcode.com/2011/04/the-painters-partition-problem-part-ii.html I'm trying to formally prove that this function, on which the algorithm is ...
20
votes
5answers
623 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
125 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
220 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
333 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
464 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
268 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
302 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
177 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
341 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
516 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
76 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
151 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
76 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 ...
28
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 ...
31
votes
3answers
1k 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 ...
13
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
120 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
446 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
500 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 ...
1
vote
1answer
371 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 ...
50
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
644 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
627 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 ...
36
votes
5answers
14k 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 ...
2
votes
1answer
134 views

Faithful functors vs forgetful functors: exact category-theoretic defs?

In category theory, a functor between two categories $C,D$ is a map $F$ that assigns to each object (resp. morphism) $x$ of $C$ a corresponding object (resp. morphism) $F(x)$ of $D$ by respecting the ...
13
votes
1answer
417 views

How to write the introduction of a research paper?

Apologies if this is too broad a question for this forum, but I'm interested in specific tactics and tips that researchers (in TCS) use to write the introduction of a research paper.
4
votes
2answers
227 views

TCS oriented refs/survey on group theoretic word problem

The word problem for groups was shown to be Turing-complete in 1955 but has many decidable subcases. This problem arose more in mathematical group theory than in theoretical computer science, but now ...
33
votes
7answers
3k views

What do you do when you cannot make progress on the problem you have been working on?

I am a 2nd year graduate student in theory. I have been working on a problem for the last year (in graph theory/algorithms). Until yesterday I thought I am doing well (I was extending a theorem from a ...
0
votes
1answer
251 views

Mathematics degree for Theoretical Computer Science? [closed]

I want to go to grad school in theoretical computer science. I don't like programming. I am in France. Should I pursue a bachelors in math or in computer science?
64
votes
7answers
22k views

What is the contribution of lambda calculus to the field of theory of computation?

I'm just reading up on lambda calculus to "get to know it". I see it as an alternate form of computation as opposed to the Turing Machine. It's an interesting way of doing things with ...