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

0
votes
1answer
46 views

Quantum Computing & Ray Tracing Rendering Engines

As a non-expert in any of these fields, but out of interest, I have been looking into basic concepts of quantum computing. And I was wondering, taking the concept of ray tracing and rendering engines, ...
-4
votes
0answers
50 views

Is Software Consist Weight [closed]

i am confuse about that Is software consist Weight or not? Regards, Arif
0
votes
0answers
54 views

Expressive enough to talk about Turing machines / Peano arithmetic?

In answering a question about Gödel and Church-Turing: The relation of Gödel's Incompleteness Theorems to the Church-Turing Thesis Andrej Bauer offered "a philosophical answer that may ...
1
vote
1answer
207 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 ...
6
votes
4answers
227 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
157 views

who found out Theory of Computer Science? [closed]

who first started to analyse computers theoretically ? who gave birth to Theory of Computation ?
4
votes
1answer
140 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 ...
12
votes
2answers
442 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
69 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)? ...
3
votes
0answers
108 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 ...
36
votes
16answers
9k views

Most memorable CS paper titles

Following a fruitful question in MO, I thought it would be worthwhile to discuss some notable paper names in CS. It is quite clear that most of us might be attracted to read (or at least glance at) a ...
0
votes
1answer
61 views

Talk for K-12 Students + General Audience Reference Request

I will be giving talks about general topics in CS, and want to hit on TCS as well. The talks will be given to K-12 schools, so not all of them will be seniors who may go to an undergraduate program at ...
28
votes
10answers
4k views

Algebra oriented branch of theoretical computer science

I have a very strong base in algebra, namely commutative algebra, homological algebra, field theory, category theory, and I am currently learning algebraic geometry. I am a math major with an ...
27
votes
3answers
800 views

How to find interesting research problems

Despite several years of classes, I'm still at a loss when it comes to choosing a research topic. I've been looking over papers from different areas and spoken with professors, and I'm beginning to ...
13
votes
5answers
2k views

What are some good introductory books on type theory?

I'm recently studying Haskell and programming languages. Could someone recommend some books on type theory?
5
votes
0answers
109 views

What is the significance of regarding the mutual exclusion problem as a problem of physics?

In the description of his own paper "On Interprocess Communication" [Distributed Computing 1, 2 (1986), 77-101], Leslie Lamport wrote Most computer scientists regard synchronization problems, such ...
0
votes
0answers
77 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
96 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
326 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 ...
10
votes
3answers
1k 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
465 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
330 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 ...
47
votes
9answers
5k 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
477 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
616 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 ...
27
votes
5answers
11k 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
120 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 ...
13
votes
1answer
352 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
131 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
212 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?
59
votes
7answers
21k 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
449 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
252 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
144 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
592 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
627 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
225 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
275 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
470 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
219 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
227 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 ...
9
votes
4answers
950 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, ...
7
votes
3answers
614 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 ...
18
votes
4answers
936 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
440 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
661 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
393 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
112 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 ...