Questions tagged [soft-question]

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.

Filter by
Sorted by
Tagged with
15
votes
2answers
454 views

(How) Could we discover/analyze NP problems in the absence of the Turing model of computation?

From a purely abstract math/computational reasoning point of view, (how) could one even discover or reason about problems like 3-SAT, Subset Sum, Traveling Salesman etc.,? Would we be even able to ...
3
votes
0answers
233 views

Formal definition of Turing Completeness [closed]

Wikipedia states: In computability theory, a system of data-manipulation rules […] is said to be Turing complete or computationally universal if it can be used to simulate any single-taped Turing ...
17
votes
1answer
2k views

Advice for a mathematician trying to present a paper at a CS conference?

I am a mathematician who works primarily in the spectral theory of self-adjoint and unitary operators. Some of my research is of relevance in quantum walks, and I have one paper in particular that I ...
7
votes
1answer
309 views

How to be formal while writing papers?

I am just beginning my second year of PhD. While my advisor is largely happy with my progress and work, there seems to be a recurring point in our discussions that I need to be more formal in my ...
17
votes
2answers
2k views

Where to learn more about what Theoretical Computer Science is?

I am a graduate student in math, and theoretical computer science is a domain which I never understood what it is about because I couldn't find a good read about the topic. I want to know what this ...
7
votes
4answers
927 views

Do I have to give up the Law of the Excluded Middle in order to Learn $\lambda$-Calculus?

I know very little about what I am talking about in what follows, so I appreciate any all help in pointing out all of my mistakes -- otherwise I won't be able to learn more and advance in my knowledge ...
15
votes
4answers
4k 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 ...
7
votes
0answers
314 views

Awards, grants and fellowships for PhD students in TCS

I think that a PhD student that received some awards and fellowships has better chance to get a good postdoc position. I was wondering what awards/grants/fellowships should one consider to apply for? ...
24
votes
5answers
893 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 ...
7
votes
1answer
303 views

(Self-)citation etiquette

This is particularly pertinent to the CS culture, where competitive conferences are often the main publication unit, which are then (sometimes) followed by journal versions. Suppose that a paper was ...
12
votes
1answer
640 views

How do journals serve the TCS community?

In the past, journals were the main way scientific/mathematical discoveries were disseminated and vetted. In some areas, they still are. However, in (theoretical) computer science that role is almost ...
2
votes
2answers
136 views

Collection of failed attempts to solve X

I've been half-jokingly entertaining the idea of trying to blog about "n ways not to solve P vs NP" in the indefinite future, and in my search came across the How not to solve P=NP? question on cs....
18
votes
2answers
934 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.
42
votes
8answers
4k 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 ...
24
votes
5answers
2k views

What are some career options for someone with a computer scientist master degree?

Other than going fully academic and getting a doctorate/post-doc, or going for a more or less 'standard' job in software development, what are some other career options in the full or semi theoretical ...
14
votes
0answers
432 views

Manuel Blum's supervisory style

Manuel Blum is a well-known theoretical computer scientist and a Turing award winner. But more interestingly, he has the highest number of students who have gone on to win a Turing award (Leonard ...
4
votes
1answer
371 views

Popular Journals for Theoretical CS

Are there some popular journals in the field of theoretical CS that serve the kind of purpose that a journal like "Physics Today" does for the Physics community ?
9
votes
2answers
3k views

Difficulty of Getting into Top Graduate Program in TCS

I'm currently a sophomore interested in TCS. Recently I've been somewhat bothered by the difficulty of getting into PhD programs in the future since the selection is indeed very competitive. I looked ...
60
votes
7answers
3k views

How to shoot down your proofs

What are general guidelines for checking your proofs? I believe this is important for graduate students like me. I already know what we need to do to prove something, but you always have to check ...
17
votes
0answers
825 views

Deeper look at Algorithmica?

Russell Impagliazzo published "A Personal View of Average-Case Complexity" (preprint) back in 1995. He presented five possible worlds we could be living in, depending on how P and NP were related. The ...
3
votes
1answer
173 views

In what fields does a knowledge of formal semantics prove useful?

(If this is better for programmers SE, let me know, but I imagined you guys would have more thorough answers) I'm a mathematics major, but I have a pretty deep interest in CS (especially in compiler ...
61
votes
33answers
4k views

Small steps for better TCS conferences?

Often, when we take part in TCS conferences, we notice some little details that we wish the conference organisers would have taken care of. And when we are organising conferences, we have already ...
40
votes
1answer
2k 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 ...
16
votes
2answers
298 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
429 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 ...
66
votes
3answers
7k views

Why does Fourier analysis of Boolean functions "work"?

Over the years I have gotten used to seeing many TCS theorems proved using discrete Fourier analysis. The Walsh-Fourier (Hadamard) transform is useful in virtually every subfield of TCS, including ...
1
vote
0answers
498 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 ...
8
votes
2answers
805 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 ...
19
votes
5answers
2k views

Where can you find job postings for faculty positions in CS theory?

What are the best resources for finding job postings for faculty positions in CS theory? Is there one website or mailing list in particular that is fairly comprehensive? I currently have the ...
1
vote
2answers
2k views

Where can I find a copy of Guy Jacobson's thesis "Succinct Static Data Structures"?

I'm looking for a copy of Guy Jacobson's PhD thesis: http://dl.acm.org/citation.cfm?id=915547 but I couldn't find it so far. Does anybody know where can I access it ? I really need it. Thanks in ...
11
votes
2answers
706 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 ...
5
votes
1answer
262 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 ...
20
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" or "...
4
votes
0answers
126 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
81 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 ...
8
votes
3answers
2k views

P vs NP: Instructive example of when Brute Force search can be avoided

To be able to explain the P vs NP problem to non-mathematicians I would like to have a pedagogical example of when Brute Force-search can be avoided. The problem should ideally be immediately ...
9
votes
1answer
2k 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 ...
0
votes
0answers
306 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
209 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 halts....
11
votes
6answers
3k 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 ...
9
votes
1answer
3k 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? ...
7
votes
4answers
636 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 ...
14
votes
1answer
2k 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 Simply-...
3
votes
3answers
607 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 ...
13
votes
2answers
1k 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 ...
0
votes
1answer
354 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 ...
15
votes
1answer
625 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 ...
2
votes
2answers
212 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 assumptions,...
8
votes
5answers
857 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 ...
9
votes
1answer
576 views

Technical article vs. research paper

Being a professional software engineer, i have seen a lot of really interesting technical work, many of it is published as technical articles in technical journals and websites like http://www.drdobbs....

1 2 3
4
5
8