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
4
votes
1answer
130 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 ...
20
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....
4
votes
0answers
167 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
140 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
120 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
192 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
2answers
316 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
111 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
167 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
210 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 ...
1
vote
0answers
122 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 ...
9
votes
1answer
608 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
393 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
201 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
209 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 ...
12
votes
3answers
551 views

Feel dissatisfied after each submission

I am a third year graduate student at a "top-20" university who works on fine-grained complexity (lots of playing with 3-SUM, OV and the usual popular hardness conjectures). I have been fairly ...
4
votes
2answers
1k views

What to do as a Theoretical computer science PhD student in a free time?

I am a mid-stage theoretical computer science student. Although I have a busy schedule, I still have a one or one a half hour in a day which I devote to reading and solving the question given Jeff ...
6
votes
2answers
369 views

Is getting post-doc difficult in theoretical computer science with few published papers? [closed]

I am a Ph.D student ( expected to graduate in few months ) works in computational mathematics. In my PhD, I have published just couple of research papers. I am willing to go for a post-doc( US, Europe,...
-2
votes
1answer
248 views

Graduate school for CS theory?

I am currently studying a bachelor's in (joint honours) Mathematics and Computer Science in the UK. I am intrigued by the sorts of problems present in theoretical computer science and I want to ...
1
vote
1answer
85 views

Cryptography protocols using graph problem instances

I personally am only aware of basic examples of public key cryptography and I haven't studied cryptography yet. I'm curious if there are circumstances in cryptography where using problem instances ...
4
votes
0answers
91 views

Naming an algorithm after a copyrighted object

In machine learning, it is common to give algorithms quirky names. What happens if you think you've found a name that's actually quite fitting for an algorithm (catchy, descriptive, etc) -- but turns ...
17
votes
1answer
818 views

The TOC Blog Aggregator is Offline

I apologise if this is off-topic. It seems that the domain name has expired. I hope some member(s) of the community here (I am not one) may know who was the administrator/owner of that site. It was ...
1
vote
0answers
137 views

How to write algorithms?

Reading research articles in theoretical computer science, I noticed that people often describe their algorithms in an enumerative way (i.e., they enumerate the steps of their algorithm and use "go to"...
18
votes
3answers
680 views

How to talk about theory

I realize this might be a contentious question, but this seemed like the right place to ask. Please redirect me if not. The background is that I am a "practitioner" (PhD student, I don't study CS ...
9
votes
0answers
169 views

Relatively low ambitious frontiers

What are some of the current "relatively" low ambitious frontiers for MA/PhD thesis in complexity theory class separations/containment or quantum computing? For example: In the draft version of Arora ...
1
vote
0answers
208 views

Automated theorem proving PhD

I'm looking for a university where I can do doctoral studies in automated theorem proving / computational algebra. Any ideas? Thank you!
4
votes
1answer
154 views

What is the etiquette of naming concepts after people?

There is a concept introduced by other researchers that I use in my work, and IMO it is appropriate to rename it to honor the inventors. Is it considered normal to just go ahead and name it like that ...
8
votes
1answer
329 views

Is it a bad idea to critique someone's paper in my first publication?

I am currently facing a situation that I am not sure how to handle. Basically, there is this problem $A$. Problem $A$ has been a hot topic in the past $5$ years. Last year, a paper was published in ...
1
vote
1answer
72 views

Soft Truth Values in the PSL model

This might sound like a trivial question. But since am starting out with my research in an area that is entirely new to me, I would really appreciate it if someone could kindly elucidate what Soft ...
10
votes
3answers
457 views

Is it beneficial to regularly read papers outside your field?

What do you think about regularly reading papers outside one's own field, even those which are not related to his area? My intuition is that it can give a totally different perspective or technique ...
13
votes
0answers
269 views

Algebraic topology for termination proofs

I'm reading about various ways in which termination proofs of software verifiers are built: ad-hoc methods that detect recursions, term-rewriting, synthesis of lexicographic orderings... From the ad-...
-2
votes
3answers
318 views

Algorithms with run-time $O(n\log \log n)$ [closed]

I am looking for the list of problems with runtime $O(n\log \log n)$, where $n$ is the size of the input. I tried to search on internet but did not able to find any.
1
vote
1answer
120 views

When we say a parameter is good for a problem?

I am studying parameterized complexity. I have seen few parameterized algorithm for problems like vertex cover, feedback vertex set etc. I have difficulty in determining when a parameter is said to be ...
5
votes
3answers
242 views

What are interesting algorithmic questions for groups in table representation?

I am currently reading about research problems in nilpotent groups ( assume table representation ). As we know that solvable group isomorphism is known to be in the (almost ) intersection of $\mathcal{...
1
vote
2answers
212 views

If only pathological cases of NP-hard problems are difficult to solve, then why isn't NP-hard defined to only include those pathological cases?

NP-hard problems are not used in cryptography, because they are believed to be computationally-intractable in the worst case but are not computationally-intractable in the average case. Is there a ...
5
votes
1answer
238 views

Are there works on “quantum parametrized complexity”?

I am a research scholar who works in Algorithms and Complexity theory, I use parameterized complexity to some extent. I don't know if researchers in quantum complexity have started using ...
2
votes
0answers
45 views

None-monotone submodular function examples

What are some interesting example of non-monotone submodular functions beside cut, directed cut in graphs?
9
votes
1answer
1k views

Is parameterized complexity going to be the future of complexity theory?

I am a research scholar who works in Algorithms and Complexity theory, I use parameterized complexity to some extent. To me it appears that researchers in parameterized complexity are very active (I ...
5
votes
1answer
346 views

How should I perform research as an Undergraduate

Are there distinct fields or types of problems which have contributions that are realistic to achieve for an undergraduate?
12
votes
4answers
804 views

How to be more “theory-minded”?

Apologies in advance for this a soft question which has no closed, correct answer. This is probably the best forum to ask my question. I am a third year graduate student in theory group of a top-15 ...
4
votes
1answer
245 views

The Maxwell's Demon and Computer Science

What is the best source -in terms of quality- that would explain the argument that uses computations concepts to demonstrate that the Maxwell's Demon does not break the second law of thermodynamics? I ...
15
votes
9answers
2k views

Is there any book on the philosophical implications of Theoretical Computer Science?

I find some books about computers, but all of them are about technology. I want something more linked to theory.
1
vote
4answers
310 views

Is Biological Computation a theme covered by the Theoretical Computer Science?

I want to say computation realized by biological systems themselves. I'm not talking about bio-inspired algorithms, or applications in computation using living systems. This question is more about an ...
4
votes
1answer
166 views

How often is the ECCC queue cleared?

I wanted to know as to how often are the submissions for ECCC cleared? Or do we know when is the next set of uploads going to be made on that site? Unlike arxiv where I know when my paper will go ...
2
votes
2answers
154 views

Suggested approach to cover data structure literature

I am not sure if this question is odd topic or too broad, but I have been wondering about this for a long time, and I would very much appreciate any valuable inputs. As a new grad student working on ...
2
votes
1answer
416 views

Computability Theory prerequisites

What are the prerequisite disciplines for Computability theory? How much is Theory of Computation, Automata Theory, etc and how hard would it be studying it without those prerequisites?
3
votes
0answers
355 views

Book Recommendations for a General Introduction to (Theoretical) Computer Science

After perusing the web and cstheory.stackexchange in particular, I've come across many different wonderful resources in Computer Science - from Sipser's "Introduction to the Theory of Computation" to ...
4
votes
1answer
177 views

Have fixed parameter integer program algorithms ever been implemented for research use?

Have any fixed parameter integer programming algorithms described in Integer programming with a fixed number of variables been implemented? Is there a reference code that researchers can use?
2
votes
1answer
278 views

Is Isomorphism of bounded degree hyper-graphs in P?

Informally, hypergraph is a generalization of a graph in which an edge can join any number of vertices. A hyper graph G=(V,E) is a two tuple, where $V$ is the set of vertices and $E$ is a set contain ...