Most Popular
1500 questions
20
votes
1 answer
How fast can we compute the set inclusion poset of a set family?
Given a set family $\mathcal{F}$ of subsets of a universe $U$.
Let $S_1,S_2 \in \mathcal F$ and we want to answer is $S_1 \subseteq S_2$.
I am looking for a data-structure that will allow me to quickly answer this.
My application is from graph…
Martin Vatshelle
- 1,339
- 7
- 21
20
votes
2 answers
Bounded depth probability distributions
Two related questions about bounded depth computing:
1) Suppose that you start with n bits, and to start with bit i can be 0 or 1 with some probability p(i), independently. (If it makes the problem simpler we can assume that all p(i)s are 0,1, or…
Gil Kalai
- 6,033
- 35
- 73
20
votes
1 answer
How close can we get to linear multiply, add, and compare (on integers)?
Accoring to K. W. Regan's article "Connect the Stars", he mentions at the end that it is still an open problem to find a representation of integers such that the addition, multiplication, and comparision operations are computable in linear…
Matt Groff
- 2,100
- 13
- 19
20
votes
2 answers
Algorithm for 'k'' most frequently occurring numbers
I have been searching for the most efficient (streaming??) algorithm that tells me the 'k' most frequently occurring elements in a data stream at any point in time. This post: "Divide and conquer" data stream algorithms got me interested in it.
For…
dhruvbird
- 460
- 4
- 14
20
votes
2 answers
Problems between NC and P: How many have been resolved from this list?
In the paper "A Compendium of Problems Complete for P" by Greenlaw, Hoover and Ruzzo (PS) (PDF), there is a list of problems in P that are not known to be in NC and not known to be P-complete either. (This list subsumes all the open problems in the…
Robin Kothari
- 13,617
- 2
- 60
- 116
20
votes
3 answers
$\mathcal{MA}$ in terms of $\mathcal{PCP}$
The probabilistic proof system $\mathcal{PCP}[f(n),g(n)]$ is commonly referred to as a restriction of $\mathcal{MA}$, where Arthur can only use $f(n)$ random bits and can only examine $g(n)$ bits of the proof certificate sent by Merlin (see,…
Belle
- 725
- 5
- 9
20
votes
0 answers
Interesting PCP characterization of classes smaller than P?
The PCP theorem, $\mathsf{NP} = \mathsf{PCP}(\mathsf{log}\, n, 1)$, involves probabilistically checkable proofs with polynomial time verifiers, so the smallest class that can be characterized in this way (that is, $\mathsf{PCP}(0, 0)$) must be…
argentpepper
- 2,281
- 15
- 27
20
votes
1 answer
Minimum chordless odd-cycle graph completion: is it NP-hard?
The following interesting problem came up in my research recently:
INSTANCE: Graph $G(V, E)$.
SOLUTION: A chordless odd-cycle completion, defined as a superset $E'$ of the edge set $E$ so that the completed graph $G'(V, E')$ has the property that…
Gabor Retvari
- 367
- 1
- 9
20
votes
5 answers
Compiler correctness proofs
I am looking for tutorial material that covers compiler correctness proofs, preferably using denotational methods, at the level of a beginning grad student.
Alternatively, do you know of some simple compiler examples that I could use to illustrate…
Uday Reddy
- 4,806
- 30
- 39
20
votes
4 answers
Data Structure isomorphisms
Disclaimer: I am not a CS theorist.
Coming from abstract algebra, I'm used to dealing with things that are equal up to a isomorphism - but I'm having a trouble translating this concept to data structures. I first thought that straight up set…
anon
- 203
- 2
- 4
20
votes
2 answers
efficient diff algorithm for trees and Levenshtein distance
I've recently read this summary of the issues involved with doing diff between trees and it got me interested in learning what is the state of the art for this problem.
Also, suppose that between your allowed edit operations are the traditional…
lurscher
- 303
- 2
- 5
19
votes
3 answers
Shortest Equivalent CNF Formula
Let $F_1$ be a satisfiable CNF Formula with $n$ variables and $m$ clauses. Let $S_{F_1}$ be the solution space of $F_1$.
Consider the problem of determining, given $F_1$, another CNF Formula $F_2$ with the same set of variables as $F_1$, with…
Giorgio Camerani
- 6,842
- 1
- 34
- 64
19
votes
3 answers
Why has hypercomputation research died down?
I see a lot of research on hypercomputation in the 1990's, but in more recent years there seems to be little work on the topic. Is it true that research in this area has died down? If so, what could be the reasons for it? Was this area convincingly…
Velvet Ghost
- 293
- 1
- 5
19
votes
22 answers
Which algorithms are used most often in practice?
Which algorithms are used most often?
Please write a single algorithm per answer, try to keep your answer short (one or two lines).
Kaveh
- 21,577
- 8
- 82
- 183
19
votes
2 answers
Axioms for Shortest Paths
Suppose we have an undirected weighted graph $G = (V, E, w)$ (with non-negative weights). Let us assume that all shortest paths in $G$ are unique. Suppose we have these $\binom{n}{2}$ paths (sequences of unweighted edges), but do not know $G$…
ilyaraz
- 1,569
- 18
- 33