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.

learn more… | top users | synonyms

-8
votes
0answers
38 views

What did Turing call Turing Machines? [on hold]

I hope he didn't go with the uninspired "Turing Machines."
0
votes
0answers
22 views

Video lectures on type systems [migrated]

For my job, I need to pick up a working understanding of the implementation of type systems (in particular, how to write typing rules based on a design document). I've been given a copy of Types and ...
0
votes
0answers
62 views

Graph database indexing

Graph databases are usually defined as index-free adjacency and that applies mostly to many current implementations - for example Neo4j - My question is: Is there are any references or papers with ...
0
votes
0answers
80 views

introduction to spectral geometry

In the paper Belkin, Mikhail, and Partha Niyogi. "Laplacian eigenmaps and spectral techniques for embedding and clustering." In NIPS, vol. 14, pp. 585-591. 2001 The ...
4
votes
4answers
274 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 ...
9
votes
3answers
797 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 ...
7
votes
0answers
440 views

Why is single authorship so common among breakthrough papers in computer science?

Looking at the list of important papers in computer science one notices that the majority are authored by a single author. Those include classic papers of Turing, Shannon, Karp and Cook. Cook's solo ...
1
vote
1answer
302 views

Which areas of TCS are better for a math bachelor?

I am graduating from mathemetics bachelor program and I've been accepted for masters degree in mathematics. But I am not sure to pursue math, hence I am looking for other field I can do research. I am ...
42
votes
8answers
4k views

Are there any open problems left about DFAs?

After studying deterministic finite state automata (DFA) in undergrad, I felt they are extremely well understood. My question is whether there is something we still don't understand about them. I ...
13
votes
1answer
443 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 ...
0
votes
1answer
420 views

Are aspects of the 20 questions game ambitious enough for graduate research?

I am finishing a masters program this year and I'm interested in doing a Ph.D. in the field of Artificial Intelligence. I have an idea I've been tinkering with for a while, but some people have told ...
23
votes
4answers
8k views

What CS blogs should everyone read?

Many top notch computer science researchers and research groups) maintain active blogs that keep us updated on the latest research in the authors' fields of interest. In most cases, blog posts are ...
2
votes
1answer
110 views

Faithful functors vs forgetful functors: exact category-theoretic defs?

In category theory, a functor between two categories $C,D$ is a map $F$ that assigns to each object (resp. morphism) $x$ of $C$ a corresponding object (resp. morphism) $F(x)$ of $D$ by respecting the ...
10
votes
1answer
287 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.
3
votes
2answers
129 views

TCS oriented refs/survey on group theoretic word problem

The word problem for groups was shown to be Turing-complete in 1955 but has many decidable subcases. This problem arose more in mathematical group theory than in theoretical computer science, but now ...
32
votes
7answers
3k 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 ...
0
votes
1answer
189 views

Mathematics degree for Theoretical Computer Science? [closed]

I want to go to grad school in theoretical computer science. I don't like programming. I am in France. Should I pursue a bachelors in math or in computer science?
57
votes
6answers
20k views

What is the contribution of lambda calculus to the field of theory of computation?

I'm just reading up on lambda calculus to "get to know it". I see it as an alternate form of computation as opposed to the Turing Machine. It's an interesting way of doing things with ...
8
votes
1answer
435 views

Connections between the Erdos Discrepancy Problem and (Theoretical) CS?

Recently there have been some new results on computer-based experimental study of the Erdos Discrepancy Problem (EDP) (via SAT solvers, cited below). This problem has been cited and studied by several ...
2
votes
1answer
177 views

How to become a Theoretical Computer Scientist [closed]

I am a computer science graduate from India. I have worked in a reputed software company for 10 months only to discover that my area of interest is something else. So I resigned from there and I am ...
5
votes
1answer
143 views

Interesting programs on small machines

I am teaching a course and have a tiny implementation of a counter-style machine that has the following instructions and two registers, r0 & r1 ...
12
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 ...
2
votes
3answers
571 views

Does anyone know of online video courses (in english) on randomness in theoretical computer science?

I have found some video courses like this one but they are all in russian or other languages I don't understand. I'll like to know if anyone has come across lectures (courses) of this kind which are ...
1
vote
0answers
489 views

How to find interesting algorithms to implement?

I am not a researcher in algorithms (I am a college freshman). I would like to implement an interesting recent algorithm from a data structure/algorithms paper. How can find a good algorithms paper ...
1
vote
2answers
206 views

Foundational textbook(s) for Complexity and Computability on Real Numbers

It would be extremely helpful if someone can suggest foundational textbooks on Recursive Analysis (Computability over Reals) which explains connections between Computability and the Topological ...
3
votes
0answers
255 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 ...
3
votes
3answers
463 views

Why do theoreticians in CS use multiple-letter variables?

This is a "dual" question of a popular post on math.se. Some mathematical objects in computational complexity theory have multiple-letter names. Complexity classes such as $\mathbf{BPP}$ have an ...
5
votes
0answers
218 views

Being a theoretician at a business university?

I'm currently on the job market and I've seen some open faculty positions in computer science at a business university (which is quite reputable among its kind). While the job opening doesn't ...
2
votes
1answer
204 views

What are the open ended questions for an CS Undergraduate to think about? [closed]

What can be a possible open ended research topics in Computational Complexity (or something equally fun), for an undergraduate to think about? [I am planning to take up something fun, however my ...
8
votes
4answers
893 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, ...
6
votes
3answers
581 views

What is the importance of a TCS researcher in a mostly applied CS department?

Stating the title in another way, how to convince a strong applied CS department that a theorist would be a better choice than one more applied computer scientist? I understand that it is natural for ...
17
votes
4answers
898 views

When does (or should) Theoretical CS care about intuitionistic proofs?

From what I understand (which is very little, so please correct me where I err!), theory of programming languages is often concerned with "intuitionistic" proofs. In my own interpretation, the ...
5
votes
0answers
410 views

What should I do to switch from math department to cs to research tcs topics?

This can be a very weird question, but I haven't seen the same situation with mine in this forum, so I'd like to put this. Let me introudce my situation first. I'm now a math student of master ...
10
votes
2answers
634 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, ...
1
vote
2answers
389 views

How do top researchers keep track new results in datastructures

Is there any twitter or some feed,which constantly sends new results which are being published to your mail.
5
votes
0answers
109 views

conceptual tools for illustrating types of computation?

From time to time I come across concepts in programming that take a certain number of exposures to grasp. Things like: tail calls, futures, monads, coroutines, closures, call/cc. The common theme is ...
6
votes
0answers
337 views

Does a depth knowledge on theory of computation helps to be a better practitioner

I would like to know whether knowledge of the theory of computation can help you to be a better practitioner. Is it enough to obtain some depth of knowledge of algorithms and data structures, or would ...
11
votes
1answer
586 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 ...
-5
votes
1answer
117 views

Do irrational number contain infinate/every patterns of sequences? [closed]

I guess the question is "does an 'infinite' number of patterns imply 'every' number of patterns?" For instance, if you could quickly calculate the decimal sequence of π, could you not (in ...
10
votes
1answer
377 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 ...
4
votes
2answers
575 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 ...
25
votes
6answers
2k views

Can one return to a TCS research job after an excursion to a non-research industry job?

I have heard from some senior researchers in theoretical computer science that working in a non-research industry job, even just for a few years, will kill your career as a TCS researcher. However I ...
17
votes
4answers
2k 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 ...
24
votes
2answers
2k views

Is it sometimes better to not publish at all?

I hope this is not a politically incorrect question to ask, but for a PhD student who usually publishes at CCC/ITCS/ICALP (and occasionally at FOCS/STOC), could it be harmful (career-wise) to publish ...
1
vote
2answers
141 views

Classic parallel clustering algorithms

I'm starting a research about parallel clustering. I see a ton of articles on this topic, so that I don't know where to start. I'd like to get familiar with classic methods of parallelizing ...
7
votes
1answer
290 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 ...
-2
votes
1answer
227 views

Good exploit to explore for an undergraduate research paper [closed]

I am looking to write a research paper for an undergraduate class in security. I'd like to explore the details of a security attack that's happened within the last ~15 years (within the last 5 years ...
25
votes
7answers
5k views

Should we consider $\mathsf{P} \neq \mathsf{NP}$ a law of nature?

Many experts believe that the $\mathsf{P} \neq \mathsf{NP}$ conjecture is true and use it in their results. My concern is that the complexity strongly depends on the $\mathsf{P} \neq \mathsf{NP}$ ...
17
votes
6answers
1k 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 ...
8
votes
1answer
272 views

Recent Probabilistic Methods in Combinatorics and its appplications to Complexity Theory

I read the famous book by Alon and Spencer on the probabilistic method in combinatorics. Is there a survey or lecture notes on recent advances and relationships with the following complexity ...