Most Popular
1500 questions
80
votes
14 answers
Uses of algebraic structures in theoretical computer science
I'm a software practitioner and I'm writing a survey on algebraic structures for personal research and am trying to produce examples of how these structures are used in theoretical computer science (and to a lesser degree, other sub-fields of…
GEL
- 903
- 1
- 8
- 8
76
votes
9 answers
Are runtime bounds in P decidable? (answer: no)
The question asked is whether the following question is decidable:
Problem Given an integer $k$ and Turing machine $M$ promised to be in P, is the runtime of $M$ ${O}(n^k)$ with respect to input length $n$ ?
A narrow answer of "yes", "no", or…
John Sidles
- 1,536
- 1
- 12
- 28
75
votes
4 answers
Why is 2SAT in P?
I've come across the polynomial algorithm that solves 2SAT. I've found it boggling that 2SAT is in P where all (or many others) of the SAT instances are NP-Complete. What makes this problem different? What makes it so easy (NL-Complete - even easier…
Guy
- 1,205
- 1
- 9
- 8
75
votes
9 answers
Powerful Algorithms too complex to implement
What are some algorithms of legitimate utility that are simply too complex to implement?
Let me be clear: I'm not looking for algorithms like the current asymptotic optimal matrix multiplication algorithm (Coppersmith-Winograd), which is reasonable…
Elliot JJ
- 745
- 2
- 8
- 12
75
votes
14 answers
Applications of topology to computer science
I'd like to write a survey on the applications of Topology in Computer
Science. I plan to cover the history of topological ideas in Computer
Science and also highlight a few current developments. It would be
extremely helpful if anyone could give…
Ben
- 871
- 1
- 7
- 5
72
votes
12 answers
How important is knowing how to program for TCS?
Coming from a more mathematical background, I never really learned how to code.
I am starting a PhD in TCS and many people were surprised by how little I knew about programming (and about computer in general). I can write algorithms in pseudo-code,…
Gopi
- 1,655
- 16
- 21
72
votes
13 answers
Common false beliefs in theoretical computer science
This post is inspired by the one in MO: Examples of common false beliefs in mathematics.
Since the site is designed for answering research level questions, examples like $\mathsf{NP}$ stands for non-polynomial time should be not on the list.…
Hsien-Chih Chang 張顯之
- 7,638
- 4
- 44
- 83
71
votes
17 answers
Polynomial-time algorithms with huge exponent/constant
Do you know sensible algorithms that run in polynomial time in (Input length + Output length), but whose asymptotic running time in the same measure has a really huge exponent/constant (at least, where the proven upper bound on the running time is…
Joris
- 454
- 5
- 7
71
votes
7 answers
Which interesting theorems in TCS rely on the Axiom of Choice? (Or alternatively, the Axiom of Determinacy?)
Mathematicians sometimes worry about the Axiom of Choice (AC) and Axiom of Determinancy (AD).
Axiom of Choice: Given any collection ${\cal C}$ of nonempty sets, there is a function $f$ that, given a set $S$ in ${\cal C}$, returns a member of…
Ryan Williams
- 27,465
- 7
- 115
- 164
70
votes
5 answers
The origin of the notion of treewidth
My question today is (as usual) a bit silly; but I would request you to kindly consider it.
I wanted to know about the genesis and/or motivation behind the treewidth concept. I sure understand that it is used in FPT algorithms, but I do not think…
Akash Kumar
- 1,973
- 16
- 27
69
votes
10 answers
Are there any open problems left about DFAs?
After studying deterministic finite state automata (DFA) in undergrad, I felt they are extremely well understood. My question is whether there is something we still don't understand about them. I don't mean generalisations of DFAs but the original…
Canadian goose
- 612
- 6
- 10
69
votes
3 answers
Why does Fourier analysis of Boolean functions "work"?
Over the years I have gotten used to seeing many TCS theorems proved using discrete Fourier analysis. The Walsh-Fourier (Hadamard) transform is useful in virtually every subfield of TCS, including property testing, pseudorandomness, communication…
user887
68
votes
7 answers
Are $PSPACE$-complete problems inherently less tractable than $NP$-complete problems?
Currently, solving either a $NP$-complete problem or a $PSPACE$-complete problem is infeasible in the general case for large inputs. However, both are solvable in exponential time and polynomial space.
Since we are unable to build nondeterministic…
Alex ten Brink
- 4,680
- 25
- 48
68
votes
17 answers
Applications of TCS to classical mathematics?
We in TCS often use powerful results and ideas from classical mathematics (algebra, topology, analysis, geometry, etc.).
What are some examples of when it has gone the other way around?
Here are some I know of (and also to give a flavor of the…
Joshua Grochow
- 37,260
- 4
- 129
- 228
67
votes
3 answers
How do I referee a paper?
Updated below
We all know the critical importance of peer-review. It is the main form of quality control and feedback on research. However, to an early-stage researcher (like me), it can sometimes be a confusing system/process.
Accordingly, there…
RJK
- 1,952
- 1
- 19
- 27