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
12
votes
7answers
1k views

Interdisciplinary topics between control theory and theoretical computer science

I am in my second year in a MSc that doesn't relate too much with TCS though I wish it would. It's basically about control theory, signals and systems and I took classes in advanced systems (robust, ...
12
votes
6answers
734 views

What is a really good problem to get your hands dirty in computational-geometry?

Computational geometry is an area I find pretty interesting, and I'd like to devote about a month or two to a project that will introduce me to this and help me learn key concepts. What is a good way ...
12
votes
4answers
878 views

How to be more “theory-minded”?

Apologies in advance for this a soft question which has no closed, correct answer. This is probably the best forum to ask my question. I am a third year graduate student in theory group of a top-15 ...
12
votes
2answers
957 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 ...
12
votes
3answers
6k 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 ...
12
votes
0answers
309 views

What percentage of SODA papers are galactic algorithms?

Consider papers published in major theoretical CS conferences during the last 5 year, where the main result is that there exists an algorithm with some time or space complexity to solve some problem. ...
12
votes
0answers
474 views

Looking for a quotation by Edsger Dijkstra

In one of his papers Edgser Dijkstra makes a statement like: "What we consider to be the standard case is one case among many exceptional cases only it occurs more often " or something along such ...
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 ...
11
votes
6answers
1k views

What is the point of calling $\lambda$-calculus an algebra?

What is the difference of calling $\lambda$-calculus an algebra instead of a calculus? I raise this question because I read somewhere the line "$\lambda$-calculus is not a calculus but an algebra" (...
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....
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 ...
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
973 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 ...
11
votes
3answers
731 views

Why do TCS papers have author names in alphabetical order of their surnames?

I am currently doing a Ph.D. in Theoretical Computer Science, and any research paper I encountered so far has the author's names in alphabetical order of their surnames. For example consider the most ...
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!...
11
votes
3answers
576 views

Proofs found by computer

In 1996, a long-standing open problem was solved by a computer; namely, that Robbins algebra and Boolean algebra are the same. The proof was found by an automated theorem prover. Moreover, the known ...
11
votes
3answers
603 views

Feel dissatisfied after each submission

I am a third year graduate student at a "top-20" university who works on fine-grained complexity (lots of playing with 3-SUM, OV and the usual popular hardness conjectures). I have been fairly ...
11
votes
1answer
889 views

Correcting a conference paper error in the journal version

In a conference paper, in order to prove the $\mathsf{NP}$-completeness of a problem, I wrote the stupid sentence "It is clear that the problem is in $\mathsf{NP}$. So we will prove that it is $\...
11
votes
1answer
558 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 ...
11
votes
1answer
977 views

What is the “question” that programming language theory is trying to answer?

I've been interested in various topics like Combinatory Logic, Lambda Calculus, Functional Programming for a while and have been studying them. However, unlike the "Theory of Computation" which ...
11
votes
1answer
648 views

How do database aggregations form a monoid?

On cs.stackexchange I asked about the algebird scala library on github, speculating on why they might need an abstract algebra package. The github page has some clues: Implementations of Monoids ...
11
votes
2answers
689 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 ...
11
votes
2answers
272 views

Exhibits for a Museum of Computing

All of the computer-related museums and exhibits I'm aware of seem to only cover the history of computing machinery, but nothing on topics of computer science. You are involved in the creation of a ...
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 ...
10
votes
8answers
3k views

What math courses should I take to prepare for a CS masters or PhD?

I'm a self-taught professional programmer. I am pretty good at it (Ruby, Unix, Clojure, Java, Objective-C), but now I'm thinking of taking it to the next level by maybe applying for a masters or PhD ...
10
votes
4answers
745 views

How to know if X and Y have coauthored?

Is there any tool where one can figure out if two people have coauthored or not? Like the tool where one can figure out somebody's Erdos _number_ .
10
votes
3answers
1k views

How easy is it to switch the area of research in CS (going from M.Tech to PhD)?

I'm faced with a rather tough dilemma :- I had completed M.Tech in CS 2 years back, completing my dissertation in the field of VLSI Testing. While I liked my work, I don't wish to go back to pursue ...
10
votes
3answers
495 views

Is it beneficial to regularly read papers outside your field?

What do you think about regularly reading papers outside one's own field, even those which are not related to his area? My intuition is that it can give a totally different perspective or technique ...
10
votes
1answer
1k views

Is parameterized complexity going to be the future of complexity theory?

I am a research scholar who works in Algorithms and Complexity theory, I use parameterized complexity to some extent. To me it appears that researchers in parameterized complexity are very active (I ...
10
votes
7answers
1k views

Are there pre-doc positions in TCS?

Are there positions for recently graduated bachelor or masters students with a record of research to work as a researcher before committing to their PhD? TCS has a culture of post-doc positions for ...
10
votes
2answers
623 views

Motivating Talk on Foundations of Cryptography

This question is in the same vein as inspirational talk for final year high school pupils. My Ph.D. advisor asked me to give an inspirational talk for new M.Sc. students. The subject is foundations of ...
10
votes
3answers
338 views

Introductory notes on parallelization, in particular patterns of problems and algorithms

I am looking for online available Lecture notes or other resources that give a good introduction into parallel programming, just like parallel analog of basic classes in computer science. My focus is ...
10
votes
1answer
660 views

PhD Development; Literature Review Tactics

Not sure if correct area, but here goes. Starting a PhD in Trust and Reputation Management in Communications networks (lots of graph theory, probabilistic analysis, etc), and have lots of reading ...
10
votes
2answers
347 views

Are linear feedback shift registers being generally discouraged by cryptologists?

Katz and Lindell mention in their book that LFSR have been horrible as basis for pseudorandom generators, and advocate that they are not used anymore (well, they also recommend that people use block ...
10
votes
0answers
197 views

Relatively low ambitious frontiers

What are some of the current "relatively" low ambitious frontiers for MA/PhD thesis in complexity theory class separations/containment or quantum computing? For example: In the draft version of Arora ...
9
votes
2answers
2k views

The average number of annual publications for CS postdocs

What is the average number of publications (including conference proceedings), per year, for CS postdoctoral researchers in the US? What are the ways to find out or estimate this number?
9
votes
5answers
3k views

How do you decide when you have enough research results to write a paper and to which journal you submit the paper

In some research area in CS we got some very interesting results. Now we are thinking about publishing them. In the group we are, the philosophy is to publish inmediately small things in conference ...
9
votes
1answer
865 views

About switching from a computer scientist to a mathematician

What is the possibility for a computer scientist to change his field into a pure mathematician ? and what's the most smooth way to do it ? any examples for people who could make it ?
9
votes
6answers
14k views

What is the best text of computation theory/theory of computation?

In University we used the Sipser text and while at the time I understood most of it, I forgot most of it as well, so it of course didn't leave all to great of an impression. I borrowed that book and ...
9
votes
3answers
559 views

Submitting other people's work to the arXiv

This is a soft question aimed at establishing what people think is the professional best-practise for submitting unoriginal work on the arXiv. There is a draft of an article [1] by Robert ...
9
votes
4answers
1k views

How do conference proceedings add to academic prestige?

I come from mathematics and, for whatever reason, am trying to publish in theoretical computer science. I'm still trying to understand the role of conference proceedings, and I have two specific ...
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 ...
9
votes
2answers
2k 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 ...
9
votes
1answer
564 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....
9
votes
1answer
426 views

Understanding the talks in Conferences and Workshops

I am a graduate student from India. I am very much interested in attending the Workshops, conferences, and invited lecturers given by prominent professors. At the end of the talk as usual some people ...
9
votes
1answer
412 views

Is there a relationship between computational complexity theory and complex systems theory?

Computational complexity theory classifies problems according to their inherent difficulty. Complex systems theory addresses systems that exhibit behaviours that do not obviously arise from the ...
9
votes
1answer
348 views

How do you remember parameters?

I'm currently doing research in pseudorandomness, which involves a zoo of wonderful objects such as pseudorandom generators, randomness extractors, expander graphs, etc. I find it a fascinating topic, ...
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 ...
8
votes
3answers
2k views

What kind of mathematical background is needed for graph theory?

It is going to be the first time for me to learn graph theory. What kind of mathematical background do I need to prepare master theses about this subject in following years? Which subjects should be ...
8
votes
5answers
751 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 ...

1 2 3
4
5
8