# Original proofs generated on the parent site

Not a question, but I thought it would be a useful indexing tool to have a meta big-list of proofs whose first appearance "in the literature" was on this site.

• Moving this question to the parent site helps it to get more exposure. Jan 13 '11 at 8:48
• but it's a metaquestion, and should stay here. The best way is to add comments in each answer that qualifies encouraging the author to post here. Jan 14 '11 at 4:48
• Would someone post a similar post about original questions whose first appearance "in the literature" was on this site? One such example: Is it possible to find if a sequence exists in polynomial time in the following problem? Feb 1 '11 at 12:36

Peter Shor and Aryabhata provide separate arguments for why it's impossible (with linear preprocessing) to solve membership queries on an unordered set in $O(\log n)$ time in the comparison model.

• This is the coolest example in quite a while. Aug 24 '11 at 15:45
• Yes, it's pretty neat. A simple problem, and nice results. I smell a blog post :) Aug 24 '11 at 15:53
• An especially neat consequence is Yuval Filmus's observation that these proofs show you need either $Ω(n\log n)$ preprocessing comparisons or $Ω(n)$ query comparisons. Sep 11 '11 at 5:05
• It's a pity you can't link to a comment. Sep 11 '11 at 5:06
• @SureshVenkat you can just click on the timestamp next to the comment. May 12 '12 at 0:28

Luca Trevisan breaks a conjecture by Gil Kalai on the structure of the fourier transform of boolean functions.

Jukka Suomela shows the dominating set problem remains NP-complete on planar bipartite graphs of maximum degree 3, a question asked by Florent Foucaud.

• There are some (and more to go) NP-hard reductions shown on this site. Should we integrate them into one answer? Dec 10 '10 at 1:06
• @Hsien-Chih: I don't think that would be helpful. Sep 5 '11 at 7:00

By improving a known construction, Hsien-Chih Chang gives a family of $n$-state NFAs $A_n$ for which the shortest word witnessing non-universality has length $2^{(1/5-o(1))n}$, and even to $2^{(1/3-o(1))n}$. This improves upon the previously known bound of $2^{(1/75-o(1))n}$ given in by Ellul et al. (2005).

References: K. Ellul, B. Krawetz, J. Shallit, M. Wang: Regular Expressions: New Results and Open Problems. Journal of Automata, Languages and Combinatorics 10(4): 407-437 (2005)

Hsien-Chih Chang resolves a question of Jukka Suomela on Ramsey theorems for collections of sets.

Vor finds a polynomial-time algorithm for a graph traversal problem raised by Oscar Mederos.

Emanuele Viola proved that runtime bounds in P are undecidable while answering John Sidles' question.

(Eventually an earlier proof was found in Juris Hartmanis' monograph "Feasible computations and provable complexity properties" (1978), but it seems users were unaware of the monograph when the question was answered)

Bob Hearn solves an NP-hardness question posed by Jeff Erickson.

Peter Shor answers some questions he raised about refereed games with correlated semi-private coins in this answer. There are still unanswered open questions about games with uncorrelated semiprivate coins.

• Actually, the questions I answered were about refereed games with correlated semi-private coins. The ones with uncorrelated semi-private coins are the unanswered ones. Dec 8 '10 at 20:20
• Thanks for pointing out the error. Now fixed (I hope). Dec 8 '10 at 22:45

In this post, Peter Shor shows that it is impossible to approximate a max-cut on a (possibly-)negative weighted graph within a factor of 2, unless there is also an approximation algorithm with ratio better the currently best algorithm to the max-cut problem on positive weighted graphs.

• Peter showed that it is impossible to approximate the Max-Cut with possibly negative weights (with a positive total weight) within a factor of 1/2 unless the Goemans-Williamson algorithm for the usual Max-Cut with positive weights can be beaten. Dec 10 '10 at 4:35
• So the direction is indeed reversed. Sorry for the misunderstanding, I'll read the proof again and modify the statement. Dec 10 '10 at 4:44

daniello proves that each graph of treewidth at most k has a $K_{1,k}$-minor. Does treewidth $k$ imply the existence of a $K_{1,k}$ minor?

domotorp proves a tighter relation between deterministic communication complexity and protocol partition number, thus answering a question by Hermann Gruber (which had been unanswered for more than 10 months).

Yuval Filmus (with help from Mark Reitblatt) shows algorithms and hardness results for deciding "circular languages".

Chandra Chekuri shows that a generalization of min-cost flow (where the goal is to choose a low-cost set of edges to "repair" in order to reduce their cost) is NP-hard by reduction from SET COVER.

David Eppstein shows a variant of max-cut problem is NP-hard, which is asked by Aaron.

• Thanks for mentioning my answer, but my answer is not an original proof. It is a reference to a known NP-completeness result. The equivalence of the special case of the asked problem to the problem studied in the paper is just an observation. Therefore I do not think that it would be fair to the authors of the paper for me to claim that I showed that the special case is NP-complete. Dec 10 '10 at 3:03
• @Tsuyoshi: Then how if I change the phrase to "provide a connection between a special case of the problem and a known NP-complete result proved by Shamir et al.?" Dec 10 '10 at 3:11
• The current question asks original proofs, and as I said, I do not think that my answer counts as an original proof. Therefore, despite that it is nice of you to have mentioned my answer, I do not think that my answer belongs here. Dec 10 '10 at 3:16
• I'm glad we're having this discussion. I was on the fence about including the various reductions that have appeared. I've been busy, so I haven't gone back through the site at all, but I guess @Tsuyoshi's is saying that something more than a straightforward reduction is required to be listed here. I'm ok with that, but listing reductions seems ok too, because it might be useful for future articles, publicity at conferences etc. Dec 10 '10 at 3:25
• @Tsuyoshi: Ok, I'll rollback the answer. That comes up another question - what kind of proofs that count as an original one? I've never seem the relation you mentioned before, and to me that counts as original. Maybe we need a more precise definition as a standard to put some proofs into this post. Dec 10 '10 at 3:26
• Thanks for rolling it back. I see your point, but if I am not mistaken, the phrase “original proofs” usually refers to something that can be considered as a result by itself, and it has to be more than a mere observation. The distinction between a result and an observation is not always black-and-white: there are cases where it is difficult to tell which. But in my opinion, the relation between the problem commented by Jukka and the Cluster Editing problem studied in the paper is undoubtedly an observation. Maybe my answer confused you because the observation was too verbose. Dec 10 '10 at 3:46

Oleksandr Bondarenko solved a conjecture about degree sets of linear extension graphs by himself.

@mjqxxxx provided a reduction from 3-SAT to the fewest discriminating bits problem asked by @andy_fingerhut.