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
16
votes
4answers
4k views

Reviewing a paper and found a better solution

I was reviewing a paper of a double-blind conference (ML/AI-based conference). The authors improved the approximation bounds for some special instances of a problem. To understand their proof better, ...
2
votes
2answers
219 views

How to acknowledge answers of TCS in the paper?

I am researcher in a company from last 5 years. I have received few answers on Theoretical Computer Science stack exchange regarding my current research work. They are not the main part of the paper ...
15
votes
1answer
688 views

Why most of the top TCS conferences are not double-blind?

I have found that the most notable TCS conferences like FOCS, STOC, SODA, and ICALP are single-blind. That is the authors do not know the identity of reviewers; however, the reviewers know the ...
4
votes
0answers
81 views

Simple randomized priority queue matching the Fibonacci heap time bounds?

Since the Fibonacci heap was developed, many other priority queues have been invented with equivalent time bounds and a simpler design (e.g. hollow heaps, quake heaps, etc.). Many classical worst-case ...
4
votes
0answers
182 views

What kind of research can be considered publishable for undergraduate or graduate students (MSc level)

I'am currently doing a non-research Dipl.Eng (Engineering Diploma in French school system equivalent to MSc) in Computer Science. The courses I am currently taking are software oriented, there's an ...
16
votes
4answers
3k views

Algorithms Careers

I’ve been writing software for a living for a number of years now. I have graduate background in mathematics and I am wondering whether knowledge of higher algorithms is utilized anywhere in industry. ...
-1
votes
1answer
129 views

Do theoretical computer scientists work more with proving theorems, or work more with data?

As theoretical computer scientists, do you work more with proving theorems, or do you work more with data? According to How to Criticize Computer Scientists, computer scientists can be divided into ...
4
votes
0answers
151 views

The graph of problem reductions

A classical approach to study the complexity of a problem $P$ is to efficiently reduce a well known problem $P'$ to $P$, thus showing that $P$ is at least as difficult as $P'$. The TCS literature ...
3
votes
2answers
133 views

Looking for some lecture videos on logic, models of computation and computational complexity/tcs fundamentals [closed]

Looking for some lecture videos (introductory level) on logic, models of computation as well as computational complexity/ other theoretical computer science fundamentals
1
vote
1answer
140 views

What math courses should I revisit to prepare for a CS Ph.D. (Reinforcement learning and Game Theory)?

I am planning to join a CS Ph.D. program in 6 months. My topics of research will be in the area of Reinforcement Learning and Game Theory. Even though I have a good grasp of these two topics’ ...
6
votes
1answer
268 views

Advice on undergraduate research

I am a junior in college who is very interested in doing some sort of REU/research internship in theoretical computer science this summer, as I would like to get research experience before potentially ...
3
votes
1answer
265 views

Which are the best universities for a DPhil/PhD in proof theory and automated reasoning?

I'm an undergraduate student studying computer science and I'm interested in doing a PhD after I graduate. I would like to do research in proof theory and automated reasoning, specifically in ...
1
vote
1answer
143 views

Publishing by showing falsity of existing results [closed]

Is it valid to publish a minor result related to computer science complexity theory and classes that disproves and falsifies an existing result? Would that be a valid and respectable endeavor?
16
votes
2answers
480 views

Publishing short and simple results

I have a manuscript that has been conference-rejected 3 times up to this point. Just to clear things up, I am by no means a senior researcher but I am not a junior who cannot judge the strength of my ...
3
votes
1answer
152 views

Formal theory about explaining algorithms

There is a lot of algorithms written in formal languages, but I have never seen any formal system which target is to explain or give a rationale behind an algorithm. It seems that when constructing ...
4
votes
1answer
213 views

Should one study undergrad TCS materials before taking grad-level ones? (soft question)

I am a 1st year PhD student. I got a bachelor's degree in CS but I didn't start learning TCS systematically until this year. This dumb question came to me when I opened an undergrad complexity lecture ...
32
votes
9answers
3k views

Any fundamental papers in TCS which were found to be incorrect/wrong later?

I am asking this question out of curiosity. I recently encountered this well-known paper on (published in 2009): the hardness_of_Euclidean_kmeans The paper showed that the previous NP-hardness ...
15
votes
5answers
2k 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 ...
4
votes
1answer
206 views

Online TCS Seminars

I want to have a list of online seminars that holds now. So far I know only about TCS+(https://sites.google.com/site/plustcs/) seminars. I would like to ask if there are other TCS seminars.
8
votes
0answers
137 views

How to succeed in remote TCS research as undergraduate

I am participating in a remote summer research program in theoretical computer science due to the current pandemic. I recognize that given the current situation, it may be harder to collaborate with ...
28
votes
1answer
1k views

Are there any public synchronous discussion forums (slack, discord, etc.) for TCS

I'm a 2nd year masters student studying theoretical CS (algorithms to be precise). I would like to know if there are any public synchronous discussion groups (slack, discord, etc.) for TCS. CSTheory ...
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 ...
6
votes
1answer
317 views

Is the basis of parity functions the only orthonormal basis for Boolean functions?

Is there another orthonormal basis of functions for Boolean functions? Or, more specifically, besides the parity functions, is there another explicit function (which is common and has a name) that can ...
10
votes
4answers
762 views

What podcast should everybody listen to?

This list was inspired by the lists: What are the popular science books that inspire TCS? What Books Should Everyone Read? What papers should everyone read? What videos should everybody watch? I don'...
3
votes
1answer
88 views

What is 'circuit problem' mentioned in Kempe-Kitaev-Regev's local hamiltonian problem paper

I have been going through Kempe-Kitaev-Regev's paper The Complexity of the Local Hamiltonian Problem. In the first paragraph of page 3, the authors point out that: To the best of our knowledge, ...
1
vote
1answer
174 views

Analytic Number theory in TCS [closed]

Are there any applications of analytic number theory in TCS?
5
votes
0answers
128 views

Program size versus program running time

Short "naive" question: Is it true that faster algorithms require longer programs ? Given a decision problem $A$ and a reasonable model of computation, there can be many ways (algorithms) ...
5
votes
0answers
168 views

What research is being done in classical complexity theory?

As far as I'm aware, classical complexity theory is being replaced by more recent forms of complexity theory, such as communication complexity and quantum complexity. What happened to results such as ...
0
votes
1answer
155 views

Diving straight into “research” versus studying broadly as an undergrad (soft question)

I'm nearing the end of my first year as an undergraduate and am very confident that I want to pursue a PhD in TCS. Fortunately because I quickly realized what I'm interested in and have a solid ...
13
votes
0answers
357 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. ...
1
vote
0answers
18 views

Sorting using comparisons that are not simple mappings of simple comparisons

The Python language has a sort(x) function that sorts a list based on the intrinsic comparison operator associated with the type of the elements of its input list x. One can also provide a cmp ...
4
votes
0answers
92 views

Status of the Junta Problem (soft question)

Does the learning theory community in general believe that juntas can be learned in polynomial time? The naive algorithm works in quasi-polynomial time. MOS's paper shows how to solve the junta ...
13
votes
1answer
265 views

Dialogue writing style & Yuri Gurevich's imaginary student: Quisani

Recently, while I was looking for more sources of crossing sequence in computational complexity theory, I came across the article "Is Randomness 'Native' to Computer Scientist?" written by M. Ferbus-...
4
votes
1answer
194 views

What are the criteria for inviting conference papers (e.g. SODA) for special issue?

This is mostly for some immigration related document that I am trying to write and want to reference an online link which mentions that only a select few papers are invited for special issue for SODA ...
21
votes
1answer
1k views

Turing award papers

I was wondering if there are individual publications that have led their authors to win the Turing Prize or if the Turing Prize is the result of a lifetime's work and multiple publications and results....
3
votes
0answers
112 views

Metrics for modelling convergence in the lambda-calculus

I wonder if there have been efforts to reconcile the measure approach to termination and Scott's domain theory or other topological models of computation. In other words, can we translate this measure ...
4
votes
0answers
202 views

Advice for new grad student [closed]

I'm a first year PhD student in a CS department at what some would probably consider a mid-tier university. I've been reading from Vershynin's High-Dimensional Probability and been trying to learn ...
1
vote
2answers
155 views

Are patents good sources for academic research?

I'm a freshman Master's student in Computer Science and I need to write a paper for my Operating System class. While looking through research articles using google scholar I found that a lot results ...
2
votes
0answers
160 views

Quantum advantage beyond the black-box model

Question Aaronson wrote in his thesis that “essentially all quantum algorithms that we know today—from Shor’s algorithm, as discussed previously, to Grover’s algorithm, to the quantum adiabatic ...
5
votes
1answer
251 views

Site with collection of exercises in TCS?

Is there a website with a large collection of exercises for theoretical computer science, sorted by topics? I know that many exercises can be found in different textbooks, I'm looking for an online ...
7
votes
3answers
708 views

How to efficiently read the theoretical computer science research papers?

I am a computer science graduate student works in theory. The general advice is to go through the paper and then in the second or third round try to understand the detail. Read the abstract, ...
2
votes
0answers
149 views

Book recommendation treewidth

I am searching for a good book (or survey paper) on treewidth. I would be delighted if the book/paper surveys multiple approaches to treewidth (eg: structural, algorithmic, `language-theoretic') and ...
7
votes
0answers
177 views

Tortoise and hare algorithms

Consider the problem: Given an array $a[0..n]$ where $n\ge 1$ and $a[i]\in [n]$ for all $i=0,\ldots,n$ find two indices $s\neq t$ so that $a[s] = a[t]$. This problem has a stunning solution running ...
2
votes
1answer
252 views

How far has computer science moved past Knuth's TAoCP, if at all? [closed]

The seminal book The Art of Computer Programming got its start in 1968. I have been finding references to it in many literature reviews, apparently there are many problems for which a review by Knuth ...
2
votes
0answers
266 views

Is Combinatory Logic (CL) still relevant for programming language theory?

I've been reading up on R. Smullyan's "To Mock a Mockingbird" and Hindley's "Lambda-Calculus and Combinators: An Introduction". I've even read Schonfinkel's 1924 paper introducing the idea of ...
11
votes
1answer
2k 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 ...
40
votes
4answers
5k views

Single author papers against my advisor's will?

I am a third year PhD student in an area of theoretical CS that would like advice for a difficult situation with my advisor. My advisor is not involved in my research projects at all. In particular, ...
5
votes
1answer
422 views

What type of mathematical problems interesting for TCS researchers?

I am Ph.D student (about to graduate) in TCS. I have worked on some problems. I have been able to publish few research paper. There are many research problems in mathematics as well in TCS. I am sure ...
2
votes
1answer
249 views

What are CS blogs for puzzles/games?

I am looking for blogs which contains recent progress on puzzles/games (Algebraic and Combinatorial) etc. like Soduko, latin square etc. I come across a list on TCS What CS blogs should everyone read?,...
7
votes
1answer
224 views

Where do people publish/submit their work on type theory?

Besides the most common venues (perhaps POPL, ICFP, LICS and FSCD), where else are papers on type theory commonly published? Especially, I'm looking for more "pure mathematical" venues/journals which ...

1
2 3 4 5
8