<p>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 <em>extremely hard</em> to reach the what is now looks like the &quot;obvious&quot; 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.</p>

CC BY-SA 4.0
2022-03-03T02:51:58.103Z
2022-03-03T02:51:58.103Z
Sariel Har-Peled
<p>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 <em>could</em> 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.</p>
<p>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 &quot;game&quot; this system by adding more and more results to their papers, to increase the length and technical depth.</p>
<p>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.</p>

CC BY-SA 4.0
2022-02-22T12:57:54.880Z
2022-02-22T12:57:54.880Z
anonymous_user_1234567
<p>I am confused by how the objective worth of CS theory research is assessed.</p>
<p>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 <span class="math-container">$A$</span> and <span class="math-container">$B$</span>.</p>
<p>That Theorem <span class="math-container">$A$</span> should hold is quite intuitive, yet my rigorous proof involves several presumably non-trivial steps.
Theorem <span class="math-container">$B$</span> is relevant for the field, but follows trivially from the definitions.</p>
<p>When I presented my preliminary results to some acquaintances who were knowledgeable in CS theory, they praised result <span class="math-container">$A$</span> and paid little attention to <span class="math-container">$B$</span>, making the comment <em>But this is trivial.</em> In fact, I had the impression that they didn't read much besides definitions, lemmas, theorems and proofs.</p>
<p>Later, I distilled <span class="math-container">$A$</span> and <span class="math-container">$B$</span> into two seperate papers, because they were quite different. I submitted both paper to the same journal, and the paper about <span class="math-container">$A$</span> was quickly accepted, whereas the paper about <span class="math-container">$B$</span> was rejected with the comment <em>All described results follow trivially from definition 2</em>.</p>
<p>So, my question is the following: <strong>Why does it matter in CS theory how difficult the proof of a theorem is?</strong> As a domain expert, I can say that <span class="math-container">$A$</span> and <span class="math-container">$B$</span> are equally relevant to my field. Of course, <span class="math-container">$B$</span> follows trivially from the definitions, and most theorists could have quickly solved that -- <em>but as far as I know, nobody did.</em> Arguably, the main contribution for <span class="math-container">$B$</span> 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.</p>

CC BY-SA 4.0
2022-02-21T13:21:45.920Z
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.).
holf
CC BY-SA 4.0
2022-02-21T13:38:47.790Z
Let's say the domain is biochemical data analysis. The rejected paper contained an entire section dedicated to explaining why the proposed definition is correct, making up roughly 1/3rd of the paper. I also stressed the relevance for my field in the introduction, but I did not explicitly say "some steps are trivial".
mto_19
CC BY-SA 4.0
2022-02-21T15:16:16.173Z
@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.
mathworker21
CC BY-SA 4.0
2022-02-21T18:35:08.060Z
Did you explain in the introduction that your main contribution was the definition behind Theorem B? Did you explain why Theorem B is interesting to practitioners?
Yuval Filmus
CC BY-SA 4.0
2022-02-21T18:36:31.640Z
It is often difficult to say in advance whether a definition is "good" or "important". Convincing experts to pay attention to your definition could be difficult. It's just not the focus of the field.
Yuval Filmus
CC BY-SA 4.0
2022-02-21T18:56:05.400Z
@YuvalFilmus I did not say that the definition behind theorem is my main contribution, because in my field nobody would care about the definition, but it is the theorem that has real impact. Perhaps I need to adjust my wording for theorists. But I guess this just reflects another shade of my question, namely "Why does a contribution need to be difficult to achieve? Is it not a contribution if it is simple to achieve?"
mto_19
CC BY-SA 4.0
2022-02-21T18:58:00.103Z
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.
Ryan Williams
CC BY-SA 4.0
2022-02-21T22:38:55.303Z
@RyanWilliams I'm a bit confused by your comment. It seems the OP would certainly agree with everything except possibly the last sentence of your comment. I think the OP was asking why people don't care more about interesting definitions and only about interesting proofs.
mathworker21
CC BY-SA 4.0
2022-02-23T08:47:41.217Z
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.
Saeed
CC BY-SA 4.0
2022-02-23T21:26:14.960Z
@saeed I agree with you.
Turbo
CC BY-SA 4.0
2022-02-24T02:25:58.697Z
Plenty of papers by famous authors get routinely rejected. Reviewing process is noisy. I have had simple papers accepted and rejected. Even at SOSA! Most venues are competitive and the goal should be to write a strong paper that is too good/interesting to be rejected. Of course we all need some luck too.
Chandra Chekuri
<soft-question>
Why does it matter how difficult a proof is?
mto_19
# Why does it matter how difficult a proof is?

(Asked by: username_0 on 2022-02-21)

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.

**Tags:** soft-question
> **Comments:**
> **username_1**: 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.).  
> **username_0**: Let's say the domain is biochemical data analysis. The rejected paper contained an entire section dedicated to explaining why the proposed definition is correct, making up roughly 1/3rd of the paper. I also stressed the relevance for my field in the introduction, but I did not explicitly say "some steps are trivial".  
> **username_2**: @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.  
> **username_3**: Did you explain in the introduction that your main contribution was the definition behind Theorem B? Did you explain why Theorem B is interesting to practitioners?  
> **username_3**: It is often difficult to say in advance whether a definition is "good" or "important". Convincing experts to pay attention to your definition could be difficult. It's just not the focus of the field.  
> **username_0**: @YuvalFilmus I did not say that the definition behind theorem is my main contribution, because in my field nobody would care about the definition, but it is the theorem that has real impact. Perhaps I need to adjust my wording for theorists. But I guess this just reflects another shade of my question, namely "Why does a contribution need to be difficult to achieve? Is it not a contribution if it is simple to achieve?"  
> **username_4**: 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.  
> **username_2**: @RyanWilliams I'm a bit confused by your comment. It seems the OP would certainly agree with everything except possibly the last sentence of your comment. I think the OP was asking why people don't care more about interesting definitions and only about interesting proofs.  
> **username_5**: 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.  
> **username_6**: @saeed I agree with you.  
> **username_7**: Plenty of papers by famous authors get routinely rejected. Reviewing process is noisy. I have had simple papers accepted and rejected. Even at SOSA! Most venues are competitive and the goal should be to write a strong paper that is too good/interesting to be rejected. Of course we all need some luck too.  

---

## 2 answers

### Answer by username_9 on 2022-02-22. Score: 12 | Accepted answer

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.


---

### Answer by username_8 on 2022-03-03. Score: 8

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.


---

