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
20
votes
7answers
27k views

Universities for Quantum Computing / Information?

Which universities have a strong quantum computing curriculum, and offer some type of quantum computing/information courses/research? The aim here is to collect a useful list for someone considering ...
20
votes
5answers
2k views

Version control for collaboration (with word-level diffs)?

Most papers are now written collaboratively, and collaborators are often located in different places. I have always used version control systems for my documents and code, and have also found version ...
20
votes
3answers
565 views

What is the right theoretical model to design algorithms for current and upcoming high performance computers

This question is similar to a more general question for what is the right theoretical model of a computer to design algorithm and data structures in. Here, I ask specifically about current high ...
20
votes
1answer
2k 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.
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 ...
19
votes
2answers
3k views

Is a PhD in TCS the best way towards achieving a career in industrial research?

My idea of a dream career is a career in industrial research, where one gets to tackle problems which are challenging, and also have a practical usage. To that end, is pursuing a PhD in TCS (I'm ...
19
votes
4answers
7k views

Abstract algebra for Theoretical Computer Scientists

I have a reasonable undergrad math education but have never been 100% comfortable with abstract algebra (the mathematics of groups, rings, fields etc. ). I think this was partly as I needed to see ...
19
votes
1answer
4k views

Choosing a research topic using game theory

This recent game theory question got me thinking (this is a tangent, of course): Is it possible to efficiently optimize a personal strategy for choosing research questions to work on using game theory?...
18
votes
6answers
3k views

Should experts in TCS charge money to read proofs that P != NP?

It's well-known that there are tons of amateurs--myself included--who are interested in the P vs. NP problem. There are also many amatuers--myself still included--who have made attempts to resolve ...
18
votes
5answers
1k views

Simple and practical deterministic algorithm, complicated running time

Very often, if the running time of an algorithm is a complicated expression, the algorithm itself is also complicated and impractical. Each of the cube roots and $\log \log n$ factors in the ...
18
votes
4answers
1k views

Applications of Complexity Theory

Complexity theory seems to capture something fundamental about the structure of the universe, in that it formalizes the intuitive notion that some problems are harder than others. Scott Aaronson ...
18
votes
3answers
732 views

How to talk about theory

I realize this might be a contentious question, but this seemed like the right place to ask. Please redirect me if not. The background is that I am a "practitioner" (PhD student, I don't study CS ...
18
votes
2answers
921 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.
18
votes
2answers
1k views

The motivation for using Karp-reductions in the theory of $\mathcal{NP}$-completeness

The notion of polynomial time reductions (Cook reductions) is an abstraction of a very intuitive concept: efficiently solving a problem by using an algorithm for a different problem. However, in the ...
18
votes
1answer
1k views

What is the status of fuzzy logic for TCS in 2011?

I am reviewing the Handbook of Nature-Inspired and Innovative Computing for SIGACT News. It's a very interesting read. Each chapter, though, has the flavor, "This is my research area, and damn it's ...
17
votes
9answers
2k views

Is there any book on the philosophical implications of Theoretical Computer Science?

I find some books about computers, but all of them are about technology. I want something more linked to theory.
17
votes
7answers
1k views

Pointers for CS applications of logic

I'm a grad student in math with a solid background in logic. I've taken a year-long graduate course in logic together with graduate courses on finite model theory and another on forcing and set theory....
17
votes
1answer
1k 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 ...
17
votes
1answer
913 views

The TOC Blog Aggregator is Offline

I apologise if this is off-topic. It seems that the domain name has expired. I hope some member(s) of the community here (I am not one) may know who was the administrator/owner of that site. It was ...
17
votes
2answers
677 views

Importance of ACM/IEEE in TCS conference

Recently I was in an ACM supported conference. During the banquet, the conference organizers told us about the future and past of the conference. They told us that during the 2010 edition of the ...
16
votes
4answers
1k views

When are more publications less?

Are there cases where extra publications can hurt your record? This is avoiding the obvious cases where you publish incorrect, or controversial results. Also avoiding the case of finite-time: you ...
16
votes
3answers
10k views

Graduate studies (PhD) in CS Theory vs. Applied Math

Given most American universities only accept applications in only one field, I'm trying to figure out what are the advantages/disadvantages of applying to a CS theory program vs an applied math ...
16
votes
7answers
2k views

Research data organization

This is a question in the spirit of this one where I answered that it is important to keep track of what you have done something, why you have done it and what is not working. I personally use ...
16
votes
2answers
448 views

Publishing short and simple results

I have a manuscript that has been conference-rejected 3 times up to this point. Just to clear things up, I am by no means a senior researcher but I am not a junior who cannot judge the strength of my ...
16
votes
2answers
295 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. ...
16
votes
0answers
735 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 ...
15
votes
10answers
3k views

Intractability of NP-complete problems as a principle of physics?

I'm always intrigued by the lack of numerical evidence from experimental mathematics for or against the P vs NP question. While the Riemann Hypothesis has some supporting evidence from numerical ...
15
votes
6answers
7k views

Quantum computing project ideas

I'm undergraduate computer science student and I'm currently planning for my graduation project. I need some ideas in quantum computing field. any help?
15
votes
5answers
1k views

Examples of pedantry in TCS

Larry Wasserman has a recent post where he talks about the "p-value police". He makes an interesting point (all emphasis mine) (the premise in italics that I added, and his response below it): The ...
15
votes
2answers
1k 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 ...
15
votes
2answers
424 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 ...
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 ...
15
votes
1answer
2k views

Algorithms Design and Complexity - How to think in that 'way'?

My question is a general one: How do I start thinking in terms of Algorithm Design and Complexity? I am going to take a Graduate Course in Algorithm Design. I had enrolled in it earlier but dropped it ...
15
votes
1answer
590 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 ...
14
votes
7answers
1k views

Mathematical analysis and computational complexity?

computational complexity involves large amounts of Combinatorics and number theory, some ingridiences from stochastics, and an emerging amount of algebra. However, being a analysist, I wonder whether ...
14
votes
6answers
7k views

Advice for Graduate School in Computer Science

I am looking for some advice and feedback. Background: I am an undergraduate mathematics student, with an interest in theoretical computer science (computational complexity, graph theory, ...
14
votes
2answers
581 views

Proof assistant usage in complexity theory research?

Considering the topics covered at a conference like STOC, are any algorithm or complexity researchers actively using COQ or Isabelle? If so, how are they using it in their research? I assume most ...
14
votes
2answers
1k views

Resources for mathematicians hoping to learn more computer science

Background: I'm coming to the end of my masters degree in Mathematics and will be starting a PhD in Logic in August. The more logic I study, the more theoretical computer science I am exposed to, e.g....
14
votes
1answer
3k 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 ...
14
votes
1answer
397 views

Algebraic topology for termination proofs

I'm reading about various ways in which termination proofs of software verifiers are built: ad-hoc methods that detect recursions, term-rewriting, synthesis of lexicographic orderings... From the ad-...
14
votes
0answers
419 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 ...
14
votes
0answers
279 views

First use of sans serif for complexity classes

(Apologies for the triviality of this question; nevertheless, it's been bugging me and presumably people here will be able to answer it...) It seems that it has become popular in recent years to ...
13
votes
3answers
4k views

How to write a negative review for a conference paper?

This is related to the general question of "How do I referee a paper?". I am reviewing a paper for a conference, and this paper should be rejected, because it is not significant enough for publication ...
13
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-...
13
votes
4answers
4k views

Interesting results in TCS which are easily explainable to programmers without technical background

Suppose you're meeting with programmers who have taken some professional programming courses (/ self thought) but didn't study a university level math. In order to show them the beauty of TCS, I'd ...
13
votes
3answers
622 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 ...
13
votes
1answer
848 views

How can I use my computational theory and analysis powers for the greater good?

Outside of academia, what are the uses of my 'powers'? What can I do other than teaching and publishing papers? Where all can I apply my powers? For the sake of argument: Please assume I have a PhD ...
13
votes
2answers
3k views

What are current open problems in compiler theory?

Compiler theory seems to be a pretty vetted subject. What are some open problems or current research happening in the field?
13
votes
1answer
208 views

Dialogue writing style & Yuri Gurevich's imaginary student: Quisani

Recently, while I was looking for more sources of crossing sequence in computational complexity theory, I came across the article "Is Randomness 'Native' to Computer Scientist?" written by M. Ferbus-...
13
votes
4answers
1k views

Alan Turing Documentaries

To celebrate Alan Turing 100th birthday, I want to watch a documentary about his life. However, there are several documentaries to choose from. Which documentary about Alan Turing is your favorite? ...

1 2
3
4 5
8