Most Popular
1500 questions
59
votes
10 answers
Provable statements about genetic algorithms
Genetic algorithms don't get much traction in the world of theory, but they are a reasonably well-used metaheuristic method (by metaheuristic I mean a technique that applies generically across many problems, like annealing, gradient descent, and the…
Suresh Venkat
- 32,071
- 4
- 95
- 271
59
votes
6 answers
Theoretical explanations for practical success of SAT solvers?
What theoretical explanations are there for the practical success of SAT solvers, and can someone give a "wikipedia-style" overview and explanation tying them all together?
By analogy, the smoothed analysis (arXiv version))for the simplex…
Joshua Grochow
- 37,260
- 4
- 129
- 228
58
votes
5 answers
What CS blogs should everyone read?
Many top notch computer science researchers and research groups) maintain active blogs that keep us updated on the latest research in the authors' fields of interest. In most cases, blog posts are easier to understand than formal papers, because…
Vivek Bagaria
- 791
- 2
- 6
- 15
57
votes
18 answers
Where and how did computers help prove a theorem?
The purposes of this question is to collect examples from theoretical computer science where the systematic use of computers was helpful
in building a conjecture that lead to a theorem,
falsifying a conjecture or proof…
Moritz
- 1,714
- 15
- 21
57
votes
10 answers
Recent advances in computer science since 2010?
Since I left school (early 2010s) a couple of recently developed techniques were widely adopted by the industry. For example,
Asymmetric numeral systems for compression (e.g. Ubuntu ships with zstd command line utility which implements ideas from…
user12344567
- 651
- 1
- 5
- 10
57
votes
13 answers
For which algorithms is there a large gap between the theoretical analysis and reality?
Two ways of analyzing the efficiency of an algorithm are
to put an asymptotic upper bound on its runtime, and
to run it and collect experimental data.
I wonder if there are known cases where there is a significant gap between (1) and (2). By this…
Radu GRIGore
- 4,796
- 30
- 69
57
votes
16 answers
What tools do you use to write papers?
What tools do you use to write
papers?
From the little experience that I have, theoreticians spend a large amount of time writing and refining papers, besides actually being creative. That is, communicating their work to other people. Maybe…
Michael
- 436
- 7
- 14
56
votes
3 answers
Surprising algorithms for counting problems
There are some counting problems which involve counting exponentially many things (relative to the size of the input), and yet have surprising polynomial-time exact, deterministic algorithms. Examples include:
Counting perfect matchings in a planar…
Ashley Montanaro
- 2,013
- 18
- 21
56
votes
9 answers
Explain P = NP problem to 10 year old
It is my first question on this site. I am taking a master's course on theory of computation. How you would explain P = NP problem to a 10 year old child and why it has such a monetary reward on it?
Your take?
I will update the question as my head…
Mohsin Hijazee
- 151
- 1
- 3
- 5
55
votes
2 answers
Can one amplify P=NP beyond P=PH?
In Descriptive Complexity, Immerman has
Corollary 7.23. The following conditions are equivalent:
1. P = NP.
2. Over finite, ordered structures, FO(LFP) = SO.
This can be thought of as "amplifying" P=NP to an equivalent statement over (presumably)…
András Salamon
- 19,000
- 3
- 64
- 150
55
votes
7 answers
For which problems in P is it easier to verify the result than to find it?
For (search versions) of NP-complete problems, verifying a solution is clearly easier than finding it, since the verification can be done in polynomial time, while finding a witness takes (probably) exponential time.
In P, however, the solution can…
Andras Farago
- 11,396
- 37
- 70
55
votes
18 answers
Most memorable CS paper titles
Following a fruitful question in MO, I thought it would be worthwhile to discuss some notable paper names in CS.
It is quite clear that most of us might be attracted to read (or at least glance at) a paper with an interesting title (at least I do so…
R B
- 9,448
- 5
- 34
- 74
55
votes
7 answers
Good examples for how to write well in TCS
I was editing a student manuscript. The student remarked that it would be nice to see examples of quality writing in published work, and I realized that I couldn't really come up with good examples off the top of my head
What are the best examples…
Suresh Venkat
- 32,071
- 4
- 95
- 271
54
votes
1 answer
Is there a gap amplification type of result for the Graph Isomorphism Problem?
Suppose $G_1$ and $G_2$ are two undirected graphs on vertex set $\{1, \dotsc, n\}$. The graphs are isomorphic if and only if there is a permutation $\Pi$ such that $G_1 = \Pi(G_2)$, or more formally, if there is a permutation $\Pi$ such that $(i,j)$…
Andre Chailloux
- 619
- 4
- 4
54
votes
5 answers
Relationship between Turing Machine and Lambda calculus?
Is there a relationship between the Turing Machine and the Lambda calculus - or did they just happen to arise about the same time?
hawkeye
- 2,581
- 1
- 18
- 34