Most Popular
1500 questions
34
votes
11 answers
Concepts in theoretical CS that would be approachable ages 8-14
Guessing it's unlikely a common question, but wondering if anyone has seen material that was clearly made to address this audience in a meaningful way.
blunders
- 443
- 5
- 7
33
votes
2 answers
"Steve's class": origin of SC
We "know" that $\mathsf{SC}$ is named for Steve Cook and $\mathsf{NC}$ is named for Nick Pippenger. If I'm not mistaken, Steve Cook named NC in honor of Nick Pippenger, and I was told that the reverse is true as well. However, I wasn't able to find…
Suresh Venkat
- 32,071
- 4
- 95
- 271
33
votes
5 answers
Complexity of applying a permutation in-place
To my surprise, I was not able to find papers about this - probably searched the wrong keywords.
So, we've got an array of anything, and a function $f$ on its indices; $f$ is a permutation.
How do we reorder the array according to $f$ with memory…
jkff
- 8,941
- 3
- 23
- 33
33
votes
7 answers
Algorithmic lens in the social sciences
Looking at questions through the algorithmic lens (i.e. from an algorithmic or complexity point of view) has become useful in disciplines outside of the 'standard domain' of computer science. In particular CS has made an impact on biology through…
Artem Kaznatcheev
- 10,251
- 12
- 74
- 174
33
votes
2 answers
Cohomological approach to boolean complexity
A few years ago, there was some work by Joel Friedman relating lower circuit bounds to Grothendieck cohomology (see papers: http://arxiv.org/abs/cs/0512008, http://arxiv.org/abs/cs/0604024). Has this line of thought brought any new insights into…
Marcin Kotowski
- 2,806
- 19
- 25
33
votes
4 answers
What are the differences between logical relations and simulations?
I'm a beginner working on methods proving program equivalence. I've read a few papers about defining logical relations or simulations to prove two programs are equivalent. But I am quite confused about these two techniques.
I only know logical…
Hongjin Liang
- 431
- 4
- 5
33
votes
5 answers
Programming languages for efficient computation
It is impossible to write a programming language that allows all machines that halt on all inputs and no others. However, it seems to be easy to define such a programming language for any standard complexity class. In particular, we can define a…
Artem Kaznatcheev
- 10,251
- 12
- 74
- 174
33
votes
12 answers
Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient
This is somewhat of a meta-cstheory question, and is more historical in nature. What are some good examples of problems for which the literature followed the develpment below:
The original algorithms, despite being hopelessly intractable (e.g.…
TedThomson
- 331
- 3
- 4
33
votes
0 answers
Is BPP= P known for ANY uniform model of computation?
Many believe that BPP $=$ P "should" hold for Turing machines. We even have some "witnesses" for this: otherwise some "strange" things would happen; see e.g. this paper by Implagliazzo and Wigderson.
But the proof of BPP $=$ P remains still
not in…
Stasys
- 6,765
- 29
- 54
33
votes
2 answers
What functions can System F not compute?
In this wikipedia article on Turing Completeness it states that:
The untyped lambda calculus is Turing complete, but many typed lambda calculi, including System F, are not. The value of typed systems is based in their ability to represent most…
Mike H-R
- 383
- 3
- 9
33
votes
1 answer
Constraint satisfaction problem (CSP) vs. satisfiability modulo theory (SMT); with a coda on constraint programming
Does someone dare to attempt to clarify what's the relation of these fields of study or perhaps even give a more concrete answer at the level of problems? Like which includes which assuming some widely accepted formulations. If I got this correctly,…
the gods from engineering
- 481
- 4
- 9
33
votes
9 answers
Randomized algorithm that "looks" deterministic?
Is there an interesting example of a randomized algorithm for a search problem that always outputs the same (correct) answer, regardless of its internal randomness, but which exploits the randomness so that its expected running time is better than…
arnab
- 7,000
- 1
- 38
- 55
33
votes
12 answers
Algebra oriented branch of theoretical computer science
I have a very strong base in algebra, namely
commutative algebra,
homological algebra,
field theory,
category theory,
and I am currently learning algebraic geometry.
I am a math major with an inclination to switch to theoretical computer science.…
spaceman_spiff
- 481
- 4
- 6
33
votes
4 answers
Does a noisy version of Conway's game of life support universal computation?
Quoting Wikipedia, "[Conway's Game of Life] has the power of a universal Turing machine: that is, anything that can be computed algorithmically can be computed within Conway's Game of Life."
Do such results extend to noisy versions of Conway's Game…
Gil Kalai
- 6,033
- 35
- 73
33
votes
2 answers
When does "X is NP-complete" imply "#X is #P-complete"?
Let $X$ denote a (decision) problem in NP and let #$X$ denote its counting version.
Under what conditions is it known that "X is NP-complete" $\implies$ "#X is #P-complete"?
Of course the existence of a parsimonious reduction is one such condition,…
Tyson Williams
- 4,258
- 2
- 23
- 44