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
30
votes
2answers
856 views

Proof refutation: Amateur reviews of ambitious CoRR papers

I guess that I read too many ambitious CoRR papers. The problem is that those papers are not peer reviewed, but often sound interesting and pass basic plausibility checks. Or maybe they don't, and I ...
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
304 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 ...
15
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
877 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 ...
7
votes
0answers
308 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? ...
7
votes
1answer
295 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
622 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....
43
votes
10answers
16k views

Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?

Real computers have limited memory and only a finite number of states. So they are essentially finite automata. Why do theoretical computer scientists use the Turing machines (and other equivalent ...
14
votes
0answers
429 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
366 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 ...
16
votes
0answers
804 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 ...
15
votes
4answers
3k 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 ...
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
297 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
416 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
471 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
258 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 ...
11
votes
2answers
701 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 ...
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
124 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
78 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 ...
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 ...
11
votes
4answers
1k 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
303 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
2k 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? ...
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-...
8
votes
2answers
784 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 ...
3
votes
3answers
595 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
347 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
615 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 ...
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 ...
32
votes
1answer
4k 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 ...
23
votes
5answers
888 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
197 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,...
4
votes
0answers
272 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 ...
6
votes
1answer
3k 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 ...
13
votes
3answers
626 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
369 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
820 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
199 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
619 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 ...
18
votes
2answers
930 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
93 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)? ...
6
votes
0answers
423 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 ...

1 2
3
4 5
8