Skip to main content
Share Your Experience: Take the 2024 Developer Survey

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
9 votes
1 answer
183 views

algebraic topology in distributed computing

I have just discovered the paper of M. Herlihy and N. Shavit on the use of algebraic topology methods in TCS and distributed computing in particular. Now I am wondering if there is any further work ...
timtombobjohn's user avatar
6 votes
1 answer
248 views

How stringent is the peer review process of ECCC exactly?

Apologies for the soft question. ECCC (the Electronic Colloquium on Computational Complexity), on its website (ECCC), says it is a compromise between the negligible peer review of ArXiv and the long ...
Tejas's user avatar
  • 369
4 votes
1 answer
248 views

What is the 'P=NP?' building?

I remember that I read somewhere some years ago that they've built a computing building with the 'P=NP?' question built in it from bricks so that they later have the option to rearrange these bricks ...
domotorp's user avatar
  • 14k
9 votes
0 answers
147 views

Resources on how to write good TCS papers

I am looking for good resources on how to write papers, which could be useful for graduate students in TCS. The internet seems to be full with style books, papers, and online talks on the subject, but ...
Or Meir's user avatar
  • 5,615
6 votes
1 answer
187 views

What online talks should everyone watch? [duplicate]

In the past 4-5 years or so, partly owing to COVID, more and more talks have been uploaded to YouTube. In the same spirit as this question by Ryan Williams almost 14 years ago: What papers should ...
Tejas's user avatar
  • 369
5 votes
1 answer
349 views

How does one "understand" complexity theory?

There's a famous quote by Bob Thomason about Grothendieck that he tried to understand algebraic geometry whilst everyone else was super-fixated on trying to prove theorems. Complexity theory, as one ...
Tejas's user avatar
  • 369
3 votes
2 answers
338 views

What are some "who ordered that?" moments in theoretical computer science?

I was recently listening to Sean Carroll's interview with Scott Aaronson, and the two of them briefly talked about surprises in their respective fields (theoretical and particle physics, and ...
20 votes
2 answers
4k views

Why isn't TheoretiCS very popular yet?

(My question is probably badly formulated, sorry for this.) TheoretiCS is an overlay journal in Theoretical CS (hence charge-free and in full open access), launched two years ago. From my point of ...
sparusaurata's user avatar
-4 votes
1 answer
153 views

If I want to end math, where should I start?

I'm a PhD in math, but I'm not good. I'm familiar with Riemannian geometry, a little partial differential equations, and a little algebraic topology. And the other undergraduate courses of math (I ...
Enhao Lan's user avatar
4 votes
2 answers
362 views

Where should I apply for MS in CS if I want to get admitted for Phd in TCS

I'm currently finishing my bachelor's degree of Computer Science and I'm really interested in Computational Complexity Theory and Analysis and design of Algorithms. As far as I know, if I do not have ...
Marinovsky's user avatar
57 votes
10 answers
18k views

Recent advances in computer science since 2010?

Since I left school (early 2010s) a couple of recently developed techniques were widely adopted by the industry. For example, Asymmetric numeral systems for compression (e.g. Ubuntu ships with ...
7 votes
0 answers
182 views

Project management

What book or MOOC would you recommend on work organisation / management of academic research projects? (Does not have to be academic project management specifically, but as close as possible)
Tatiana Starikovskaya's user avatar
6 votes
2 answers
632 views

NP-complete problems where the inputs are prime numbers

Are there (well?) known NP-complete problems where the input(s) is(are) a(some) prime number(s), with complexity measured relative to the binary length of the input number(s)? I am thinking there are ...
EGME's user avatar
  • 161
7 votes
2 answers
1k views

Problems in NP with non-trivial certificate

For all NP-complete problems I can think about, the problem statement says very clearly how to test a certificate. I'm looking for interesting problems with NP which have non-trivial certificates. I ...
Command Master's user avatar
9 votes
3 answers
1k views

Solo single author paper vs the comfort of having you advisor on the paper?

My partner is a very bright theoretical CS student. Recently she proved a pretty significant result that she is aiming to submit for SODA. In addition, the paper was done completely without her ...
user3508551's user avatar
  • 1,153
3 votes
0 answers
63 views

What are some practical applications of inductive-inductive types?

By "practical applications" I mean in usual programming/industry. I am particularly interested in cases where the inductive-inductive types cannot be easily replaced by inductive-recursive ...
Fernando Chu's user avatar
14 votes
4 answers
2k views

Where is the model theory in programming language theory?

I have a background in mathematical logic and am trying to learn some programming language theory. In the syntax of, say, first-order logic, one of the first distinctions you learn about is between ...
Siddharth's user avatar
  • 851
2 votes
0 answers
69 views

Open Quantum Analogs to Classical Problems

I am looking for interesting examples of complexity-theoretic and cryptographic problems where we have a significant amount of knowledge about the classical version of the problem, but we have no ...
SAS's user avatar
  • 121
2 votes
2 answers
228 views

Resources for hoodie design related to theoretical CS [closed]

I have to design a hoodie for my computer science batch, and I want it to be related to Theoretical computer science. I don't want to slap on some text with HTML-like angle brackets, but actually want ...
Mr.HiggsBoson's user avatar
1 vote
1 answer
315 views

Are there 'poision-pill' research questions in TCS?

I intend to double major in CS/Math and go to grad school for TCS. I have some - unorthodox - research ideas I would like to pursue for grad school. At the very least, they are interdisciplinary (...
wonderinghuh's user avatar
4 votes
1 answer
252 views

Does double majoring with math in undergrad help one grasp TCS topics more easier?

I'm a CS major. However, a lot of TCS topics seem to be in the realm of pure math. Should I add a math major to complement understanding and for a future career in TCS?
wonderinghuh's user avatar
18 votes
2 answers
989 views

Why does it matter how difficult a proof is?

I am confused by how the objective worth of CS theory research is assessed. In the last year, I had been working on formalizing some tasks from a different research field in cs theoretic terms, i.e. ...
mto_19's user avatar
  • 291
23 votes
1 answer
963 views

FOCS virtual fee $600

I'm not sure this is on topic here, but probably can be best answered by this community, so I'm posting it as a soft-question. Due to the pandemic, FOCS 2021 will be a virtual conference. Most ...
1 vote
1 answer
175 views

Graph associated to a mathematical statement (for the purpose of zero-knowledge proofs)

I'll preface this question by saying I have very little (zero!) knowledge of theoretical computer science, and this post is a genuine attempt to understand something, even if at an intuitive level, ...
Emilio Ferrucci's user avatar
7 votes
1 answer
681 views

Which universities in the U.S. are doing research in type theory?

The question is meant to be broad in that recommendations with mentions of the particular areas within type theory research are greatly appreciated. Also, the research need not be conducted in ...
Alvaro Pintado's user avatar
1 vote
0 answers
69 views

Decision tree vs. pebble game lower bounds

This question concerns two types of lower bounds. In a pebbling lower bound, we are concerned with the complexity of constructing the output from the input. For example, if the only way we could ...
Siddharth's user avatar
  • 851
7 votes
3 answers
1k views

Is it right to ask a TCS researcher about the real life application of the problem she/he is working on?

I have attended a decent number of TCS conferences. It is good that researchers solve difficult problems. However, I am often interested in the reason why a problem is interesting in the first place. ...
Inuyasha Yagami's user avatar
1 vote
0 answers
159 views

I think I may have discovered a new algorithm for a common problem. Now what?

I was trying to solve a common problem the other week and upon checking Stackoverflow there was a solution, but it just seemed like there should be a better way to do it. I thought about it for a ...
Erick Weber's user avatar
16 votes
6 answers
5k views

Can theoretical computer science be applied in social sciences?

I'm very new to this field - technically not in it but want to be. I'm very early in my academic career (sophomore at a community college) but decided that I want to add a math major along with my ...
wonderinghuh's user avatar
16 votes
3 answers
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, ...
Inuyasha Yagami's user avatar
3 votes
2 answers
283 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 ...
Coreman's user avatar
  • 33
22 votes
2 answers
1k 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 ...
Inuyasha Yagami's user avatar
4 votes
0 answers
120 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 ...
templatetypedef's user avatar
16 votes
4 answers
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. ...
Joe Shmo's user avatar
  • 301
-1 votes
1 answer
160 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 ...
kate's user avatar
  • 109
4 votes
0 answers
178 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 ...
Matthieu Latapy's user avatar
3 votes
2 answers
158 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
Hao S's user avatar
  • 228
1 vote
1 answer
196 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’ ...
Fahim's user avatar
  • 19
5 votes
1 answer
543 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 ...
user13251577's user avatar
3 votes
1 answer
527 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 ...
frafle's user avatar
  • 33
1 vote
1 answer
157 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?
Turbo's user avatar
  • 12.9k
16 votes
2 answers
627 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 ...
Proof-From-The-Book's user avatar
4 votes
1 answer
198 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 ...
Artem Kokorin's user avatar
4 votes
1 answer
259 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 ...
raycosine's user avatar
  • 203
35 votes
10 answers
4k 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 result (...
Inuyasha Yagami's user avatar
17 votes
5 answers
3k 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 ...
Inuyasha Yagami's user avatar
4 votes
1 answer
436 views

Online TCS Seminars

I want to have a list of online seminars that holds now. So far I know only about TCS+(https://www.tcsplus.org/) seminars. I would like to ask if there are other TCS seminars.
9 votes
0 answers
158 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 ...
oek's user avatar
  • 91
29 votes
1 answer
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 ...
Bhishmaraj's user avatar
11 votes
4 answers
2k 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 ...
user1729's user avatar
  • 221

1
2 3 4 5
9