Most Popular
1500 questions
113
votes
7 answers
Solid applications of category theory in TCS?
I've been learning a few bits of category theory. It certainly is a different way of looking at things. (Very rough summary for those who haven't seen it: category theory gives ways of expressing all kinds of mathematical behavior solely in terms of…
Ryan Williams
- 27,465
- 7
- 115
- 164
108
votes
5 answers
List of TCS conferences and workshops
I would like to ask for help in compiling a list of as many TCS-related conferences and workshops as possible. My main motivation for doing this is to plan possible blog coverage of more theory venues -- finding correspondents attending these…
Aaron Sterling
- 6,994
- 6
- 42
- 74
106
votes
6 answers
How do the state-of-the-art pathfinding algorithms for changing graphs (D*, D*-Lite, LPA*, etc) differ?
A lot of pathfinding algorithms have been developed in recent years which can calculate the best path in response to graph changes much faster than A* - what are they, and how do they differ? Are they for different situations, or do some obsolete…
BlueRaja - Danny Pflughoeft
- 1,591
- 3
- 13
- 19
104
votes
15 answers
A simple decision problem whose decidability is not known
I am preparing for a talk aimed at undergraduate math majors, and as part of it, I am considering discussing the concept of decidability. I want to give an example of a problem that we do not currently know to be decidable or undecidable. There…
Lev Reyzin
- 11,968
- 13
- 63
- 103
102
votes
41 answers
What are the recent TCS books whose drafts are available online?
Following the post What Books Should Everyone Read, I noticed that there are recent books whose drafts are available online.
For instance, the Approximation Algorithms entry of the above post cites a 2011 book (yet to be published) titled The…
Rahab
- 351
- 3
- 4
- 10
99
votes
2 answers
What is the actual time complexity of Gaussian elimination?
In an answer to an earlier question, I mentioned the common but false belief that “Gaussian” elimination runs in $O(n^3)$ time. While it is obvious that the algorithm uses $O(n^3)$ arithmetic operations, careless implementation can create numbers…
Jeffε
- 23,129
- 10
- 96
- 163
96
votes
9 answers
What would it mean to disprove Church-Turing thesis?
Sorry for the catchy title. I want to understand, what should one have to do to disprove the Church-Turing thesis? Somewhere I read it's mathematically impossible to do it! Why?
Turing, Rosser etc used different terms to
differentiate between: "what…
user200
94
votes
7 answers
What is the contribution of lambda calculus to the field of theory of computation?
I'm just reading up on lambda calculus to "get to know it". I see it as an alternate form of computation as opposed to the Turing Machine. It's an interesting way of doing things with functions/reductions (crudely speaking). Some questions keep…
PhD
- 5,305
- 5
- 25
- 40
93
votes
14 answers
What kind of mathematical background is needed for complexity theory?
I am currently an undergraduate student, bound to graduate this year. After graduation, I am considering to work towards a TCS master/PhD. I have begun wondering what fields of mathematics are considered helpful for TCS, especially (classical)…
chazisop
- 3,796
- 2
- 29
- 37
89
votes
2 answers
Was the reduction in Shor's algorithm originally discovered by Shor?
This is a "historical question" more than it is a research question, but was the classical reduction to order-finding in Shor's algorithm for factorization initially discovered by Peter Shor, or was it previously known? Is there a paper that…
user1338
85
votes
42 answers
Funny TCS-related papers etc?
What is the funniest TCS-related published work you know?
Please include only those that are intended to be funny. Works which are explicitly crafted to be intelligently humorous (rather than, say, a published collection of short jokes regarding…
Joshua Grochow
- 37,260
- 4
- 129
- 228
85
votes
20 answers
Examples of "Unrelated" Mathematics Playing a Fundamental Role in TCS?
Please list examples where a theorem from mathematics which was not normally considered to apply in computer science was first used to prove a result in computer science. The best examples are those where the connection was not obvious, but once it…
Derrick Stolee
- 2,044
- 1
- 21
- 34
84
votes
9 answers
Are research papers hard to read?
This question may not suit to here, but I couldn't find a better place to ask (it was closed in SO).
I find research papers on computer science hard to understand. Of course the subjects are complicated. But after I understand a paper usually I can…
nimcap
- 959
- 1
- 7
- 7
83
votes
5 answers
Techniques for Reversing the Order of Quantifiers
It is well-known that in general, the order of universal and existential quantifiers cannot be reversed. In other words, for a general logical formula $\phi(\cdot,\cdot)$,
$(\forall x)(\exists y) \phi(x,y) \quad \not\Leftrightarrow \quad (\exists…
Sadeq Dousti
- 16,479
- 9
- 69
- 152
81
votes
8 answers
What would a very simple quantum program look like?
In light of the announcement of the world's first programmable quantum photonic chip, I was wondering just what software for a computer that uses quantum entanglement would be like. One of the first programs I ever wrote was something like
for i = 1…
xpda
- 931
- 1
- 7
- 8