16
$\begingroup$

This is a placeholder question to collect instances where cstheory has been cited in papers. Hopefully as time goes in, this list will get longer.

Please answer in the format:

  • Question (and answer, if appropriate)
  • Cited in:

providing all links and citations necessary.

$\endgroup$
2
  • $\begingroup$ Curious why this was in meta rather than the main site? In particular, I'm wondering about how many papers/results had their genesis here, and I worry that posting such a question on meta would result in not much visibility. And while several of the answers here may fit the bill (eg mine - but I can't be the only one!), it's harder to offload to Google scholar. $\endgroup$
    – Joshua Grochow
    Commented Aug 17, 2020 at 15:23
  • $\begingroup$ Maybe the tag (citations) would fit here? (I do not have sufficient rep to edit on meta, so I have suggested this in a comment.) $\endgroup$
    – Martin
    Commented Aug 22, 2020 at 9:18

5 Answers 5

Reset to default
10
$\begingroup$

Instead of curating a list here (how current is this list, anyway?) we can happily delegate the work to the keeper of all data:

References to cstheory.SE on Google Scholar

$\endgroup$
1
  • $\begingroup$ nice. we were updating the list manually, but this seems to work as well. $\endgroup$
    – Suresh Venkat Mod
    Commented Sep 28, 2011 at 23:13
7
$\begingroup$

Question: How hard is unshuffling a string?

Cited in:

$\endgroup$
6
$\begingroup$

Question: Is optimally solving the n×n×n Rubik's Cube NP-hard?

Cited in: Algorithms for Solving Rubik's Cubes. Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Anna Lubiw, Andrew Winslow. arXiv:1106.5736v1

(Also pointed out in the question's answer by @Andy Drucker.)

$\endgroup$
6
$\begingroup$

Question: Post Correspondence Problem variant

Cited in: Levent Alpoge, Thomas Ang, Luke Schaeffer, Jeffrey Shallit (2011): Decidability and shortest strings in formal languages, Proc. DCFS 2011, LNCS vol. 6808, Springer. doi:10.1007/978-3-642-22600-7_5, arXiv:1103.1622

$\endgroup$
2
$\begingroup$

Question: Why is HAMILTONIAN CYCLE so different from PERMANENT?

Cited in: Grochow, J. A. Monotone Projection Lower Bounds from Extended Formulation Lower Bounds. Theory of Computing Vol. 13 Art. 18, 2017.

$\endgroup$

You must log in to answer this question.

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