Most Popular
1500 questions
24
votes
8 answers
Computing the Levenshtein distance quickly
Given a huge database of allowed words (alphabetically sorted) and a word, find the word from the database that is closest to the given word in terms of Levenshtein distance.
The naive approach is, of course, to simply compute the Levenshtein…
user3116
24
votes
1 answer
Is there a relationship between relational algebra/calculus and category theory?
I am aware of at least two different theoretical approaches for understanding relational databases: Codd's relational algebra/calculus, and category theory.
Is there any relationship between these two approaches? Are they in some sense equivalent?…
Chill2Macht
- 513
- 4
- 13
24
votes
2 answers
If machine learning techniques keep improving, what's the role of algorithmics in the future?
Let's look at the future some 30 years from now. Let's be optimistic and assume that areas related to machine learning keep developing as quickly as what we have seen in the past 10 years. That would be great, but then what would be the role of…
Jukka Suomela
- 11,500
- 2
- 53
- 116
24
votes
2 answers
Is there a direct/natural reduction to count non-bipartite perfect matchings using the permanent?
Counting the number of perfect matchings in a bipartite graph is immediately reducible to computing the permanent. Since finding a perfect matching in a non-bipartite graph is in NP, there exists some reduction from non-bipartite graphs to the…
Derrick Stolee
- 2,044
- 1
- 21
- 34
24
votes
2 answers
Is the Cheeger constant $\mathsf{NP}$-hard?
I have read in uncountably many articles that determining the Cheeger constant of a graph is $\mathsf{NP}$-hard. It seems to be a folk theorem, but I have never found either a quote or a proof for this statement. Whom should I give credit for it? In…
Delio M.
- 343
- 1
- 6
24
votes
2 answers
What is the best exact algorithm to compute the core of a graph?
A graph H is a core if any homomorphism from H to itself is a bijection. A subgraph H of G is a core of G if H is a core and there is a homomorphism from G to H.
http://en.wikipedia.org/wiki/Core_%28graph_theory%29
Given a graph G, what is the best…
Regularity
- 901
- 5
- 13
24
votes
6 answers
Statements that imply $\mathbf{P}\neq \mathbf{NP}$
This is sort of an open-ended question - for which I apologize in advance.
Are there examples of statements that (seemingly) don't have anything to do with complexity or Turing machines but the answer of which would imply $\mathbf{P}\neq…
Dominic van der Zypen
- 905
- 6
- 16
24
votes
1 answer
Is P equal to the intersection of all superpolynomial time classes?
Let us call a function $f(n)$ superpolynomial if $\lim_{n\rightarrow\infty} n^c/f(n)=0$ holds for every $c>0$.
It is clear that for any language $L\in {\mathsf P}$ it holds that $L\in {\mathsf {DTIME}}(f(n))$ for every superpolynomial time bound…
Andras Farago
- 11,396
- 37
- 70
24
votes
1 answer
The randomized query complexity of the conjoined trees problem
An important 2003 paper by Childs et al. introduced the "conjoined trees problem": a problem admitting an exponential quantum speedup that's unlike just about any other such problem that we know of. In this problem, we're given an…
Scott Aaronson
- 13,733
- 2
- 62
- 68
24
votes
2 answers
Parallel Dynamic Search
Is there a natural parallel analog to red-black trees with similar or even not-terribly-worse properties for updates while being reasonably work-efficient ?
More generally, what's the best we can do for parallel search with updates ?
Suresh Venkat
- 32,071
- 4
- 95
- 271
24
votes
4 answers
How to check if a number is a perfect power in polynomial time
The first step of the AKS primality testing algorithm is to check if the input number is a perfect power. It seems that this is a well known fact in number theory since the paper did not explain it in details. Can someone tell me how to do this in…
yzll
- 428
- 1
- 3
- 9
24
votes
3 answers
NP complete graph problems about structural properties
(This question is a bit of a "survey".)
I'm currently working on a problem where I'm trying to partition the edges of a tournament into two sets, both of which are required to fulfill some structural properties. The problem "feels" quite hard, and I…
G. Bach
- 431
- 2
- 17
24
votes
8 answers
Concise introduction to algorithms for mathematicians
I am looking for a concise introductory text on algorithms with a high ratio $$\frac{\mbox{theory covered}}{\mbox{total number of pages}}.$$ It should begin at the beginning but then progress quickly without spending too much time on real world…
Gregor
- 541
- 3
- 7
24
votes
1 answer
Sampling satisfiable 3-SAT formulas
Consider the following computational task: We want to sample a 3-SAT formula of $n$ variables (a variant: $n$ variables $m$ clauses) with respect to the uniform probability distribution, conditioned on the formula being satisfiable:
Q1: Can this be…
Gil Kalai
- 6,033
- 35
- 73
24
votes
2 answers
Is it sometimes better to not publish at all?
I hope this is not a politically incorrect question to ask, but for a PhD student who usually publishes at CCC/ITCS/ICALP (and occasionally at FOCS/STOC), could it be harmful (career-wise) to publish less significant works in less prestigious…
Belle
- 725
- 5
- 9