Most Popular
1500 questions
54
votes
11 answers
If you could rename dynamic programming...
If you could rename dynamic programming, what would you call it?
Jack
- 447
- 5
- 14
54
votes
5 answers
What kind of answer does TCS want to the question "Why do neural networks work so well?"
My Ph.D. is in pure mathematics, and I admit I don't know much (i.e. anything) about theoretical CS. However, I have started exploring non-academic options for my career and in introducing myself to machine learning, stumbled across statements such…
Neuling
- 649
- 6
- 3
54
votes
2 answers
What are the outstanding questions in purely functional data structures?
This question is inspired by another question about what's new in PFDS since the publication of Okasaki's book in 1998.
I'll start with two questions I have:
Is there a purely functional set data structure that approaches the speed of hash tables?…
jbapple
- 11,184
- 2
- 29
- 50
54
votes
21 answers
Dinner-table description of theoretical computer science?
I'm often asked what a theoretical computer scientist does. It would be great to have some nice responses to this question. I tend to fall back to technical jargon and people's eyes usually glaze over at this point.
What does a theoretical…
András Salamon
- 19,000
- 3
- 64
- 150
54
votes
3 answers
Rigorous security proof for Wiesner's quantum money?
In his celebrated paper "Conjugate Coding" (written around 1970), Stephen Wiesner proposed a scheme for quantum money that is unconditionally impossible to counterfeit, assuming that the issuing bank has access to a giant table of random numbers,…
Scott Aaronson
- 13,733
- 2
- 62
- 68
53
votes
3 answers
How to find interesting research problems
Despite several years of classes,
I'm still at a loss when it comes to choosing a research topic.
I've been looking over papers from different areas and
spoken with professors, and
I'm beginning to think this is the wrong approach.
I've read…
al92
- 683
- 6
- 6
53
votes
1 answer
A combinatorial version for the polynomial Hirsch conjecture
Consider $t$ disjoint families of subsets of {1,2,…,n}, ${\cal F}_1,{\cal F_2},\dots {\cal F_t}$ .
Suppose that
(*)
For every $i \lt j \lt k$
and every $R \in {\cal F}_i$, and $T \in {\cal F}_k$,
there is $S \in {\cal F}_j$ which contains $R \cap…
Gil Kalai
- 6,033
- 35
- 73
52
votes
4 answers
Why do we consider log-space as a model of efficient computation (instead of polylog-space) ?
This might be a subjective question rather than one with a concrete answer, but anyway.
In complexity theory we study the notion of efficient computations. There are classes like $\mathsf{P}$ stands for polynomial time, and $\mathsf{L}$ stands for…
Hsien-Chih Chang 張顯之
- 7,638
- 4
- 44
- 83
52
votes
6 answers
Complexity of the simplex algorithm
What is the upper bound on the simplex algorithm for finding a solution to a Linear Program?
How would I go about finding a proof for such a case?
It seems as though the worst case is if each vertex has to be visited that is it $O(2^n)$. However in…
shuttle87
- 637
- 1
- 5
- 5
52
votes
3 answers
Shallow versus Deep Embeddings
When encoding a logic into a proof assistant such as Coq or Isabelle, a choice needs to be made between using a shallow and a deep embedding. In a shallow embedding logical formulas are written directly in the logic of the theorem prover, whereas in…
Dave Clarke
- 16,666
- 3
- 60
- 106
52
votes
20 answers
NP-hard problems on trees
Several optimization problems that are known to be NP-hard on general graphs are trivially solvable in polynomial time (some even in linear time) when the input graph is a tree. Examples include minimum vertex cover, maximum independent set,…
Shiva Kintali
- 10,578
- 41
- 74
51
votes
4 answers
What are the best current lower bounds on 3SAT?
What are the best current lower bounds for time and circuit depth for 3SAT?
Joe Fitzsimons
- 13,675
- 47
- 91
51
votes
4 answers
Is finding the minimum regular expression an NP-complete problem?
I am thinking of the following problem:
I want to find a regular expression that matches a particular set of strings (for ex. valid email addresses) and doesn't match others (invalid email addresses).
Suppose by regular expression we mean some…
László Kozma
- 1,336
- 1
- 10
- 16
51
votes
8 answers
Are there non-constructive algorithm existence proofs?
I remember I might have encountered references to problems that have been proven to be solvable with a particular complexity, but with no known algorithm to actually reach this complexity.
I struggle wrapping my mind around how this can be the case;…
jkff
- 8,941
- 3
- 23
- 33
51
votes
9 answers
Best Upper Bounds on SAT
In another thread, Joe Fitzsimons asked about "the best current lower bounds on 3SAT."
I'd like to go the other way: What's the best current upper bounds on 3SAT? In other words, what is the time complexity of the most efficient SAT solver?
In…
Sadeq Dousti
- 16,479
- 9
- 69
- 152