Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

6
votes
0answers
87 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
138 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
138 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
290 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
30 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 ...
0
votes
0answers
9 views

Python3: Distance between rectangles keep changing. Please help! [migrated]

(python3)Creating rectangles with equal distance between them but with random heights and widths. However the distance between them is not fixed and changes. Can someone help? Thank you! import ...
10
votes
3answers
420 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
246 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
288 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
102 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 ...
7
votes
3answers
211 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
180 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 ...
6
votes
1answer
202 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
41 views

None-monotone submodular function examples

What are some interesting example of non-monotone submodular functions beside cut, directed cut in graphs?
10
votes
1answer
998 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
295 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
687 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
209 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 ...
13
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
287 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
153 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 ...
3
votes
2answers
134 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
239 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
219 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
158 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
0answers
230 views

soft question - What university for Theoretical Computer Science

I need a piece of advice about my next year at university. I know this forum is for solving problems, but I've seen some questions that deal with this topic tagged with "soft-question". Before ...
5
votes
1answer
256 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 ...
7
votes
0answers
155 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 ...
8
votes
2answers
577 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!...
8
votes
0answers
206 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
98 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
365 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 ...
7
votes
0answers
279 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 ...
24
votes
2answers
628 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 ...
12
votes
1answer
820 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 $\...
22
votes
5answers
2k views

Writing a paper as a single author in 1st person singular

I am writing papers in theoretical computer science sometimes being a nonanonymous single author. Earlier, I used the 1st person plural in such papers, e.g.: We will show that the complexity ...
3
votes
0answers
221 views

Is putting articles on arXiv or alternatives, before peer review, generally acceptable?

How common is it to place articles on arXiv or similar sites before publishing in a peer-reviewed journal? I'm trying to get a feel for what my chances are, of publishing in a journal if I put an ...
15
votes
2answers
357 views

(How) Could we discover/analyze NP problems in the absence of the Turing model of computation?

From a purely abstract math/computational reasoning point of view, (how) could one even discover or reason about problems like 3-SAT, Subset Sum, Traveling Salesman etc.,? Would we be even able to ...
3
votes
0answers
147 views

Formal definition of Turing Completeness [closed]

Wikipedia states: In computability theory, a system of data-manipulation rules […] is said to be Turing complete or computationally universal if it can be used to simulate any single-taped Turing ...
25
votes
1answer
662 views

Proof refutation: Amateur reviews of ambitious CoRR papers

I guess that I read too many ambitious CoRR papers. The problem is that those papers are not peer reviewed, but often sound interesting and pass basic plausibility checks. Or maybe they don't, and I ...
17
votes
1answer
1k views

Advice for a mathematician trying to present a paper at a CS conference?

I am a mathematician who works primarily in the spectral theory of self-adjoint and unitary operators. Some of my research is of relevance in quantum walks, and I have one paper in particular that I ...
7
votes
1answer
272 views

How to be formal while writing papers?

I am just beginning my second year of PhD. While my advisor is largely happy with my progress and work, there seems to be a recurring point in our discussions that I need to be more formal in my ...
14
votes
2answers
1k views

Where to learn more about what Theoretical Computer Science is?

I am a graduate student in math, and theoretical computer science is a domain which I never understood what it is about because I couldn't find a good read about the topic. I want to know what this ...
6
votes
4answers
442 views

Do I have to give up the Law of the Excluded Middle in order to Learn $\lambda$-Calculus?

I know very little about what I am talking about in what follows, so I appreciate any all help in pointing out all of my mistakes -- otherwise I won't be able to learn more and advance in my knowledge ...
8
votes
0answers
275 views

Awards, grants and fellowships for PhD students in TCS

I think that a PhD student that received some awards and fellowships has better chance to get a good postdoc position. I was wondering what awards/grants/fellowships should one consider to apply for? ...
6
votes
1answer
225 views

(Self-)citation etiquette

This is particularly pertinent to the CS culture, where competitive conferences are often the main publication unit, which are then (sometimes) followed by journal versions. Suppose that a paper was ...
11
votes
1answer
381 views

How do journals serve the TCS community?

In the past, journals were the main way scientific/mathematical discoveries were disseminated and vetted. In some areas, they still are. However, in (theoretical) computer science that role is almost ...
2
votes
2answers
132 views

Collection of failed attempts to solve X

I've been half-jokingly entertaining the idea of trying to blog about "n ways not to solve P vs NP" in the indefinite future, and in my search came across the How not to solve P=NP? question on cs....
39
votes
10answers
14k views

Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?

Real computers have limited memory and only a finite number of states. So they are essentially finite automata. Why do theoretical computer scientists use the Turing machines (and other equivalent ...
14
votes
0answers
376 views

Manuel Blum's supervisory style

Manuel Blum is a well-known theoretical computer scientist and a Turing award winner. But more interestingly, he has the highest number of students who have gone on to win a Turing award (Leonard ...