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
38
votes
14answers
24k views

How practical is Automata Theory?

There is always a way for application in topics related to theoretical computer science. But textbooks and undergraduate courses usually don't explain the reason that automata theory is an important ...
62
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 ...
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 ...
30
votes
19answers
8k views

Beautiful results in TCS

Recently, a friend of mine (working in TCS) mentioned in a conversation that "he wanted to see/know all (or as much as possible) of the beautiful results in TCS in his lifetime". This kind of made me ...
44
votes
5answers
1k views

Casual tours around proofs

Today Ryan Williams posted an article on the arXiv (previously appeared in SIGACT News) containing a less technical version of his recent ACC lower bound technique. My question is not about the ...
21
votes
9answers
14k views

What is the recommended software for drawing data structures such as graphs and trees?

When putting together results, it's often desirable to have some professional looking diagrams, rather than diagrams put together in MS Paint. What is the standard for drawing data structures?
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 ...
27
votes
2answers
9k views

How to publish a paper?

Being a software engineer for the most part of my life I have absolutley no idea how to start with publishing an "academic" kind of paper. During my latest research I've found an interesting algorithm ...
20
votes
7answers
26k 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 ...
34
votes
11answers
4k views

Concepts in theoretical CS that would be approachable ages 8-14

Guessing it's unlikely a common question, but wondering if anyone has seen material that was clearly made to address this audience in a meaningful way.
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 ...
46
votes
11answers
4k views

If you could rename dynamic programming…

If you could rename dynamic programming, what would you call it?
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
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?...
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....
37
votes
5answers
2k views

When should you say what you know?

What should you do when you see a question raised in public, say here on stack-exchange, that you know the answer to, because you are looking into as part of current research project? For example, I ...
37
votes
3answers
5k views

Extended Church-Turing Thesis

One of the most discussed questions on the site has been What it Would Mean to Disprove the Church-Turing Thesis. This is partly because Dershowitz and Gurevich published a proof of the Church-Turing ...
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 ...
26
votes
5answers
2k views

Long-lasting errors in computer science

This is my first question on the cstheory stack, so don't be too rude if I'm violating etiquette somehow ) As we know, in mathematics even famous mathematicians, superstars and geniuses are doing ...
24
votes
6answers
2k views

How should I think about proof nets?

In his answer to this question, Stephane Gimenez pointed me to a polynomial-time normalization algorithm for proofs in linear logic. The proof in Girard's paper uses proof nets, which are an aspect of ...
6
votes
3answers
2k views

Mathematical background needed for pursuing a PhD in TCS [duplicate]

Possible Duplicate: What kind of mathematical background is needed for complexity theory? I'm a final year undergrad and I'm looking to pursue a PhD in theoretical computer science in the long ...
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 ...
11
votes
2answers
1k views

Sources of open problems?

I'm wondering if there are some known sources of open TCS problems? I'm a junior studying math/CS and would like to know of some accessible problems that I could start thinking about! Thanks so much!...
37
votes
7answers
3k views

What is the oldest open problem in TCS?

This problem is inspired by this MO question, which I thought was very interesting. What is the oldest open problem in TCS? Clearly this question needs some clarification. First, what is TCS? ...
24
votes
1answer
4k views

Major mistakes in accepted FOCS/STOC papers [closed]

Have you come across an occasion like that in the past? Well, there is a possibility for everything but I would like to know how realistic this incidence can be. I am referring to serious mistakes ...
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 ...
5
votes
3answers
433 views

What podcast should everybody listen to?

This list was inspired by the lists: What are the popular science books that inspire TCS? What Books Should Everyone Read? What papers should everyone read? What videos should everybody watch? I don'...
21
votes
4answers
656 views

Language and automata textbook, free or low cost?

I'll be teaching a standard undergraduate class on languages and automata next semester, and would prefer to use a legitimate free or low-cost text. Any suggestions? I love the Sipser text but the ...
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?
10
votes
5answers
3k views

Automata Theory / Formal Language Thesis Topic

Hey All, I'm currently trying to find a solid masters thesis topic pertaining to some branch of automata theory or related to formal languages. I'm trying to generate some good ideas for what an ...
6
votes
5answers
3k views

How to make a paper stronger?

After reading this question and David's answer I thought a more general question asking for tips would be useful. So how can authors make (and write) a paper stronger?
31
votes
1answer
757 views

Eilenberg's rational hierarchy of nonrational automata & languages — where is it now?

In the preface to his very influential books Automata, Languages and Machines (Volumes A, B), Samuel Eilenberg tantalizingly promised Volumes C and D dealing with "a hierarchy (called the rational ...
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 ...
11
votes
5answers
3k views

How to find a specific research topic to concentrate on?

I recently started my masters course. Last semester I took courses from different disciplines like networks, software engineering, architecture, etc. Recently, after taking an advanced course in ...
4
votes
2answers
744 views

What are the prospects of research in database field?

I have been working with database management systems, and would like to focus on research in this very area some day. I was having a look at the various research labs around the world, ...
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.
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? ...
4
votes
4answers
804 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 ...
7
votes
2answers
1k views

Deciding between different PhD programs

Edited Version What are the main characteristics and qualities that you would consider if you were going to choose a PhD program in theoretical computer science (or related areas) today (based on ...
6
votes
0answers
510 views

How fundamental is undecidability? [closed]

What does it mean that some problem is undecidable? For instance the halting problem. Does it mean that humans can never invent a new technique that always decides whether a turing machine will halt?...
3
votes
1answer
426 views

What is “distributed computing” as a field of computer science?

I think it's field that studies distributed systems as described at http://en.wikipedia.org/wiki/Distributed_computing. There are distributed systems such as clusters and grids on top of this field. ...
11
votes
3answers
780 views

Where do I turn for help with research/publishing?

I have been developing a SAT algorithm for a while, and have reached a point where I'd like to share it. I don't know many people in computer science, and I'm not sure exactly where to turn. I'm ...
11
votes
4answers
2k views

Author ordering in TCS papers

While the rule of thumb is that in TCS papers the authors are ordered alphabetically, there are some notable counterexamples that comes to mind, wherein the authors are ordered in a different way, e.g....
7
votes
5answers
555 views

What is a substantial contribution to software design, with respect to authorship?

Background I am a biologist. I wrote and am about to submit a manuscript that describes a statistical analysis of computer model; it is a statistical methods and modeling paper. After my manuscript ...
4
votes
1answer
284 views

Consequences of Polynomial & QuasiPolynomial time algorithms for UP, FewP and CoC=P

I have came up with two alternate universe scenarios that I need some help figuring out the outcome of. Thank you in advance. There exists two complexity classes $\mathsf{A}$ and $\mathsf{B}$. By ...

1
2