18
$\begingroup$

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. providing proper definitions, proving bounds etc. In the end, I came up with two proper theorems that are relevant in my research field. Let's call them $A$ and $B$.

That Theorem $A$ should hold is quite intuitive, yet my rigorous proof involves several presumably non-trivial steps. Theorem $B$ is relevant for the field, but follows trivially from the definitions.

When I presented my preliminary results to some acquaintances who were knowledgeable in CS theory, they praised result $A$ and paid little attention to $B$, making the comment But this is trivial. In fact, I had the impression that they didn't read much besides definitions, lemmas, theorems and proofs.

Later, I distilled $A$ and $B$ into two seperate papers, because they were quite different. I submitted both paper to the same journal, and the paper about $A$ was quickly accepted, whereas the paper about $B$ was rejected with the comment All described results follow trivially from definition 2.

So, my question is the following: Why does it matter in CS theory how difficult the proof of a theorem is? As a domain expert, I can say that $A$ and $B$ are equally relevant to my field. Of course, $B$ follows trivially from the definitions, and most theorists could have quickly solved that -- but as far as I know, nobody did. Arguably, the main contribution for $B$ was the definition that implied the theorem--which, by the way, was quite hard to come up with--but nobody seemed to care about that.

Improve this question
$\endgroup$
11
  • 2
    $\begingroup$ Was it a general venue or a venue specialized in your domain? If the scope of the venue is too general, then you may end up with reviewers that are not familiar with the internals of your domain and it will be easier for them to judge the complexity of the proofs than the relevance of the results. It is also important to stress it in your introduction and to insist on why, despite the simple proof, it is a contribution (by e.g., comparing with previous work, stressing why a definition is more than it seems etc.). $\endgroup$
    – holf
    Commented Feb 21, 2022 at 13:21
  • 4
    $\begingroup$ @mto_19 This is not an answer to your question, but usually a good way to show that Theorem B is useful despite being trivial to prove is to use it to prove nontrivial things. I don't mind a culture that 'forces' people to give evidence that what they claim is important is in fact important. $\endgroup$
    – mathworker21
    Commented Feb 21, 2022 at 15:16
  • 10
    $\begingroup$ I think if you replace "difficult" with "interesting" you will understand your question better. People want to read something interesting, using an idea or two they haven't seen or thought before. Ideas/proofs that look trivial at first can definitely lead to something interesting; these are not the same notion. If a theorem is immediate from a definition then it's perhaps not very interesting, the definition is what's potentially interesting. Maybe there are more theorems like this you can derive from your definition, which you can use to point back to the interestingness of the definition. $\endgroup$
    – Ryan Williams
    Commented Feb 21, 2022 at 18:58
  • 3
    $\begingroup$ I've found many reviewers at TCS jealous. They cannot accept that one comes up with easy solutions for interesting problems, so they tend to reject by providing most nonsense responses. On the other hand, if you already made a big name for yourself or have a good network supporting you, then you can publish your simple proofs in top conferences and journals and then people will call it "elegant"! If anyone disagrees, I can show simple proofs that were already known (at least the idea) or are even wrong but accepted in top venues when they are written by so-called top researchers in the field. $\endgroup$
    – Saeed
    Commented Feb 23, 2022 at 8:47
  • 3
    $\begingroup$ @saeed I agree with you. $\endgroup$
    – Turbo
    Commented Feb 23, 2022 at 21:26

2 Answers 2

Reset to default
12
$\begingroup$

I believe this is a consequence of the small number of papers that get accepted at top-notch conferences, such as STOC or FOCS. For example, it is often the case that for a certain sub-area (like proof complexity or distributed algorithms) only 5 or 10 papers can be accepted but there are 20 or more papers that could be accepted. Hence, a tie-breaker is needed and, more often than not, the paper with the most intricate/complicated proof is picked. This sets the bar for many venues and extends to lower-tier conferences and journals.

This is also corroborated by the fact that many TCS conferences reject your paper, even when it has very good scores (e.g., having a single accept and two weak accepts is often not good enough to get the paper accepted). I also know of people who try to "game" this system by adding more and more results to their papers, to increase the length and technical depth.

I think this is quite detrimental to the community and to its outreach to other areas of computer science. The only way out that I could imagine would be to significantly increase the sizes of the conferences but many important people are against it.

Improve this answer
$\endgroup$
8
$\begingroup$

It is very hard to judge the quality of a paper, especially when you do math - what is once understood becomes so much easier than before. We have many cases where it was extremely hard to reach the what is now looks like the "obvious" ideas used. And yet, we need to judge - so people use the hardness of a proof as a proxy for the quality of a work/paper, but nobody really believes in this measure. It is just in many cases we have nothing better to use. This is doubly true if you are trying to judge the quality of a paper that is on a problem/subfield you never worked on before.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.