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
6
votes
0answers
143 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
192 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
83 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
520 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 ...
32
votes
4answers
4k 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
382 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
192 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
202 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
533 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 ...
2
votes
2answers
874 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
317 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
229 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
81 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
89 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
764 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
130 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
664 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
165 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
190 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
151 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
325 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
59 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
450 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
258 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
311 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
117 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
235 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
204 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
224 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
44 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
327 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?
11
votes
4answers
777 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
237 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
300 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
163 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
150 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
365 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
298 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
175 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
268 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 ...
5
votes
0answers
161 views

Is E.M Luks algorithm for trivalent graph isomorphism parallelizable?

It is still open whether also Luks’ efficient GI algorithm for graphs with bounded degree is parallelizable i.e. NC. I get this from the survey "On Graph Isomorphism for Restricted Graph Classes" by ...
7
votes
2answers
722 views

Sources of open problems?

I'm wondering if there are some known sources of open TCS problems? I'm a junior studying math/CS and would like to know of some accessible problems that I could start thinking about! Thanks so much!...
7
votes
0answers
212 views

Low barrier to entry Computational Complexity problems

I could use some help navigating which areas of Computational Complexity (e.g. CCC, STOC topics) require the least amount of background knowledge to get involved in basic research. I am looking to ...
3
votes
0answers
99 views

Notion of “total work” of a problem?

I apologize in advance if this question is outside the scope of this Exchange community; if so, perhaps someone can point me in the right direction. I am curious if there is a theoretical notion of "...
14
votes
2answers
454 views

Proof assistant usage in complexity theory research?

Considering the topics covered at a conference like STOC, are any algorithm or complexity researchers actively using COQ or Isabelle? If so, how are they using it in their research? I assume most ...
6
votes
0answers
295 views

What is the current status of Acta Informatica?

Almost everybody knows the journal Acta Informatica. Some really important publications appeared there over the years. Upon looking on the website of the journal I noticed the following: Number of ...
23
votes
2answers
670 views

If machine learning techniques keep improving, what's the role of algorithmics in the future?

Let's look at the future some 30 years from now. Let's be optimistic and assume that areas related to machine learning keep developing as quickly as what we have seen in the past 10 years. That would ...
11
votes
1answer
845 views

Correcting a conference paper error in the journal version

In a conference paper, in order to prove the $\mathsf{NP}$-completeness of a problem, I wrote the stupid sentence "It is clear that the problem is in $\mathsf{NP}$. So we will prove that it is $\...