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.
13
votes
4answers
332 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 ...
3
votes
0answers
157 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 ...
9
votes
2answers
201 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, ...
-4
votes
0answers
45 views
Start using SAT Solvers [migrated]
What i actually want to do is to turn a math problem ,i have to solve,to a Boolean Satisfiability problem and solve it using a SAT Solver.
I wonder if someone knows any manual,guide or anything that ...
1
vote
2answers
292 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.
-2
votes
1answer
138 views
Can the human mind be efficiently simulated by a Turing machine ? [closed]
Can the human mind be efficiently simulated by a Turing machine ? If not , Can we consider a quantum computational model ? Is it possible that there are NP hard problems that can't be solved by a ...
5
votes
0answers
80 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 ...
5
votes
0answers
172 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
376 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
85 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
328 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
440 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 ...
24
votes
6answers
1k 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 ...
15
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 ...
12
votes
1answer
1k 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 ...
0
votes
0answers
279 views
Is This Experience Possible Before Grad School? [closed]
I'm currently a research assistant in a neuroscience lab at MIT and I'm considering pursuing a PhD in theoretical computer science or math. The RAs in my lab who want to eventually become ...
1
vote
2answers
90 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 ...
5
votes
1answer
149 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
177 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 ...
17
votes
5answers
2k 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}$ ...
15
votes
5answers
569 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 ...
7
votes
1answer
230 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 ...
7
votes
3answers
384 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 ...
13
votes
7answers
485 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 ...
23
votes
13answers
2k views
Complex analysis in theoretical computer science
There are many applications of real analysis in theoretical computer science, covering property testing, communication complexity, PAC learning, and many other fields of research. However, I can't ...
1
vote
1answer
185 views
List of TCS conferences along with important dates
I saw that there is a post with a List of TCS conferences. However, this does not list important dates like conference date, submission deadline etc. Is there any post or website which maintains these ...
2
votes
1answer
175 views
Recent fundamental results in algorithms? [closed]
I dont know if this question belong to this forum, but I will ask it anyway
To your opinions, what are the most recent fundamental results in the field of algorithms ? [Results that can be taught in ...
14
votes
2answers
366 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 ...
22
votes
3answers
829 views
Ecology and evolution through the algorithmic lens
The study of ecology and evolution is becoming increasingly more mathematical, but most of the theoretical tools seem to be coming from physics. However, in many cases the problems have a very ...
1
vote
1answer
201 views
What are some good references for mathematical optimization for the layman?
I've been getting myself involved with this topic and would like to read more to gain a conceptual understanding of the various techniques and what each one is trying to achieve and their 'idea' ...
11
votes
0answers
439 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 ...
0
votes
3answers
452 views
To what extent is “advanced mathematics” needed/useful in A.I. research?
I am currently studying mathematics. However, I don't think I want to become a professional mathematician in the future. I am thinking of applying my knowledge of mathematics to do research in ...
38
votes
6answers
1k views
Good examples for how to write well in TCS
I was editing a student manuscript. The student remarked that it would be nice to see examples of quality writing in published work, and I realized that I couldn't really come up with good examples ...
11
votes
0answers
207 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 ...
3
votes
4answers
398 views
TCS Research Frontier with Huge Practical and Industrial Impact on our Society
While CS theorists pursue the beauty and unity of their mathematical theories, their results can have a practical and industrial impact.
As we know, P versus NP is often talked about with its ...
21
votes
4answers
1k views
Handbook of advanced data structures
I am looking for a book on advanced data structures that goes beyond what is covered in standard textbooks like Cormen, Leiserson, Rivest, and Stein's "Introduction to Algorithms".
A book that can be ...
20
votes
4answers
480 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 ...
38
votes
2answers
2k 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 ...
4
votes
1answer
209 views
Papers on Prolog-like languages without closed world assumption (CWA)
Prolog execution process may be seen as a search that model scientific search for a proof of a proposition. At the same time, real world scientific search greatly differs from Prolog search in the ...
4
votes
2answers
403 views
How to do organize papers, urls and other TCS related resources?
This question is a try of making
Do you use any article organizers? question suitable for TCS (as suggested in meta answer http://meta.cstheory.stackexchange.com/a/359/6133 )
Question similar -> ...
4
votes
1answer
225 views
Surveys in other languages than English
Where can I find surveys in languages than English ?
If the question is found to be interesting (it could be usefull for graduated students who are not fluent in English for instance), it would be ...
-5
votes
1answer
238 views
why is a Turing machine defined as a 5-tuple? [closed]
[Edited to provide better context.]
In a comment on meta, JɛffE suggested that this would be a good topic for a question to ask here.
why is a Turing machine defined as a 5-tuple?
21
votes
1answer
873 views
What are some careers in theoretical computer science that do not require a PhD?
I am an undergraduate, and have recently come to terms with the fact that I may not have the intellect to do research in theoretical computer science, or be able to be admitted into and complete a PhD ...
33
votes
8answers
2k views
Are there non-constructive algorithm existence proofs?
I remember I might have encountered references to problems that have been proven to be solvable with a particular complexity, but with no known algorithm to actually reach this complexity.
I struggle ...
9
votes
3answers
461 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 ...
31
votes
3answers
940 views
Is there a backup/replacement for the Complexity Zoo?
This is a non-technical question, but certainly relevant for the TCS community. If considered inappropriate, feel free to close.
The Complexity Zoo webpage ...
15
votes
5answers
929 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 ...
23
votes
8answers
3k views
Alan Turing's Contributions to Computer Science
Alan Turing, one of the pioneers of (theoretical) computer science, made many seminal scientific contributions to our field, including defining Turing machines, the Church-Turing thesis, ...
11
votes
3answers
408 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
0answers
275 views
Formula in common: How to search for same/similar equations in other knowledge domains?
In a recent presentation by Sedgewick, he recounts in 1977 Flajolet noticed that they had a formula in common, both in different domains (see slide 4 in ...
