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.
415
questions
2
votes
1
answer
2k
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 ...
- 831
11
votes
4
answers
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....
user887
7
votes
3
answers
795
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 ...
- 1,868
26
votes
4
answers
2k
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 ...
- 7,615
6
votes
0
answers
1k
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 ...
- 61
15
votes
2
answers
2k
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....
- 253
1
vote
2
answers
432
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.
- 137
5
votes
0
answers
122
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 ...
- 151
7
votes
0
answers
550
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 ...
13
votes
1
answer
923
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,305
-6
votes
1
answer
168
views
Do irrational numbers contain an infinite number of (or all possible) 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 ...
- 89
9
votes
1
answer
446
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 ...
- 2,044
8
votes
3
answers
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 ...
- 153
26
votes
6
answers
3k
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 ...
- 975
21
votes
4
answers
8k
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 ...
- 333
24
votes
2
answers
3k
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 ...
- 725
1
vote
2
answers
187
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 clustering....
- 111
11
votes
1
answer
802
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 ...
- 568
-2
votes
1
answer
308
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 ...
- 113
32
votes
7
answers
10k
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}$ ...
- 4,828
28
votes
6
answers
3k
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 ...
- 32.5k
8
votes
1
answer
434
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 ...
- 279
11
votes
3
answers
633
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 ...
- 4,031
18
votes
7
answers
1k
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 theory....
32
votes
15
answers
13k
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 ...
user887
4
votes
2
answers
2k
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 ...
- 1,591
2
votes
1
answer
239
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 ...
- 644
18
votes
2
answers
2k
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 ...
- 725
3
votes
1
answer
3k
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' ...
- 5,305
12
votes
0
answers
480
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 ...
- 87
28
votes
5
answers
62k
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 ...
- 647
55
votes
7
answers
4k
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 ...
14
votes
0
answers
301
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 ...
- 2,013
4
votes
4
answers
545
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 ...
- 309
24
votes
4
answers
2k
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 ...
- 21.6k
21
votes
4
answers
695
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 ...
- 383
69
votes
3
answers
8k
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 ...
user887
8
votes
1
answer
586
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 ...
- 251
4
votes
2
answers
518
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 https://cstheory.meta.stackexchange.com/a/359/6133 )
Question similar -> ...
4
votes
1
answer
244
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 ...
- 1,117
-5
votes
1
answer
2k
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?
- 11k
21
votes
1
answer
3k
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 ...
- 319
51
votes
8
answers
5k
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 ...
- 8,951
9
votes
3
answers
585
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 ...
39
votes
3
answers
2k
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 (http://qwiki.stanford.edu/index.php/...
- 5,496
15
votes
5
answers
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 ...
36
votes
8
answers
11k
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, ...
13
votes
4
answers
2k
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?
...
6
votes
0
answers
293
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 http://www.cs.princeton.edu/~rs/talks/AofA2AC....
- 61
6
votes
1
answer
476
views
Is it considered OK to email authors to inquire about their paper while subreviewing their paper for a conference?
More generally, how do you reconcile questions that you may have about the paper's technical material?
- 61