35
$\begingroup$

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.

Idea: each answer links to an answer on the parent site, with a brief description of what the link contains.

$\endgroup$
3
  • $\begingroup$ Moving this question to the parent site helps it to get more exposure. $\endgroup$
    – Mohammad Al-Turkistany
    Commented Jan 13, 2011 at 8:48
  • 6
    $\begingroup$ 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. $\endgroup$
    – Suresh Venkat Mod
    Commented Jan 14, 2011 at 4:48
  • 2
    $\begingroup$ 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? $\endgroup$
    – Mohammad Al-Turkistany
    Commented Feb 1, 2011 at 12:36

17 Answers 17

Reset to default
12
$\begingroup$

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.

$\endgroup$
5
  • 3
    $\begingroup$ This is the coolest example in quite a while. $\endgroup$
    – Aaron Sterling
    Commented Aug 24, 2011 at 15:45
  • $\begingroup$ Yes, it's pretty neat. A simple problem, and nice results. I smell a blog post :) $\endgroup$
    – Suresh Venkat Mod
    Commented Aug 24, 2011 at 15:53
  • 3
    $\begingroup$ 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. $\endgroup$
    – Peter Shor
    Commented Sep 11, 2011 at 5:05
  • $\begingroup$ It's a pity you can't link to a comment. $\endgroup$
    – Suresh Venkat Mod
    Commented Sep 11, 2011 at 5:06
  • 1
    $\begingroup$ @SureshVenkat you can just click on the timestamp next to the comment. $\endgroup$
    – Artem Kaznatcheev Mod
    Commented May 12, 2012 at 0:28
11
$\begingroup$

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

$\endgroup$
9
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ There are some (and more to go) NP-hard reductions shown on this site. Should we integrate them into one answer? $\endgroup$
    – Hsien-Chih Chang 張顯之
    Commented Dec 10, 2010 at 1:06
  • 1
    $\begingroup$ @Hsien-Chih: I don't think that would be helpful. $\endgroup$
    – Charles
    Commented Sep 5, 2011 at 7:00
9
$\begingroup$

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)

$\endgroup$
6
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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)

$\endgroup$
5
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Peter Shor
    Commented Dec 8, 2010 at 20:20
  • $\begingroup$ Thanks for pointing out the error. Now fixed (I hope). $\endgroup$
    – Aaron Sterling
    Commented Dec 8, 2010 at 22:45
5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Tsuyoshi Ito
    Commented Dec 10, 2010 at 4:35
  • $\begingroup$ So the direction is indeed reversed. Sorry for the misunderstanding, I'll read the proof again and modify the statement. $\endgroup$
    – Hsien-Chih Chang 張顯之
    Commented Dec 10, 2010 at 4:44
5
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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).

$\endgroup$
3
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$
    – Tsuyoshi Ito
    Commented Dec 10, 2010 at 3:03
  • $\begingroup$ @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.?" $\endgroup$
    – Hsien-Chih Chang 張顯之
    Commented Dec 10, 2010 at 3:11
  • $\begingroup$ 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. $\endgroup$
    – Tsuyoshi Ito
    Commented Dec 10, 2010 at 3:16
  • $\begingroup$ 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. $\endgroup$
    – Aaron Sterling
    Commented Dec 10, 2010 at 3:25
  • $\begingroup$ @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. $\endgroup$
    – Hsien-Chih Chang 張顯之
    Commented Dec 10, 2010 at 3:26
  • $\begingroup$ 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. $\endgroup$
    – Tsuyoshi Ito
    Commented Dec 10, 2010 at 3:46
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .