Most Popular
1500 questions
18
votes
4 answers
If P = BQP, does this imply that PSPACE (= IP) = AM?
Recently, Watrous et al proved that QIP(3) = PSPACE a remarkable result. This was a surprising result to myself to say the least and it set me off thinking...
I wondered what if Quantum Computers could be efficiently simulated by Classical…
Zelah 02
- 1,578
- 7
- 16
18
votes
1 answer
Lower bounds for the size of nondeterministic circuits
It is known that the minimum size of $U_2$-circuits computing the parity function exactly equals $3(n-1)$. The lower bound proof is based on the gate elimination method.
Recently, I noticed that the gate elimination method works well also for…
Hiroki Morizumi
- 689
- 1
- 6
- 11
18
votes
1 answer
Edit distance in sublinear space
What is the best known complexity for computing the exact edit distance between two strings of the same length using working space which is sublinear in the size of the input? I assume the input is stored in some read-only format. Is this a…
Simd
- 3,902
- 20
- 49
18
votes
1 answer
DAG reachability with O(n log n) space and O(log n)-time queries?
For a directed acyclic graph ${\langle}V,E{\rangle}$, is there a data structure that allows for reachability queries without requiring quadratic space or linear time? Ideally I seek an algorithm using only O(log n) space per vertex and logarithmic…
user4718
- 281
- 1
- 4
18
votes
3 answers
Examples of $\Sigma_2^p$ complete problems?
I need a list of $\Sigma_2^p$ complete languages. There are two such problems listed in the Complexity Zoo, namely:
Minimum equivalent DNF. Given a DNF formula F and integer k, is there a DNF formula equivalent to F with k or fewer occurences of…
gdiazc
- 419
- 3
- 11
18
votes
1 answer
Historic Relationship between Typed Lambda Calculus and Lisp?
I was having a discussion with a friend recently (who is an advocate of strongly typed languages). He made the comment:
The inventors of Lambda Calculus always intended it to be typed.
Now we can see that Church was associated with the Simply…
hawkeye
- 2,581
- 1
- 18
- 34
18
votes
1 answer
The structure of pathological instances for simplex algorithms
As far as I understand, all know deterministic pivot rules for simplex algorithms have specific inputs on which the algorithm requires exponential time (or at least not polynomial) to find the optimum. Let us call these instances 'pathological'…
Artem Kaznatcheev
- 10,251
- 12
- 74
- 174
18
votes
2 answers
Storage requirements for median selection (two passes algorithms)
In a classic paper Munro and Paterson study the problem of how much storage is required for an algorithm to find the median in a randomly sorted array. In particular they focus on the following model:
the input is read from left to right for a…
MassimoLauria
- 1,841
- 16
- 21
18
votes
2 answers
Separating words with random DFAs
One of the interesting open problems about DFAs listed in Are there any open problems left about DFAs? is the size of a DFA required to separate two strings of length $n$. I am curious if there any results about the ability of a random DFA to…
Geoffrey Irving
- 3,253
- 15
- 29
18
votes
1 answer
Splay tree potential function: why sum the logs of the sizes?
I'm teaching a course on data structures and will be covering splay trees early next week. I've read the paper on splay trees many times and am familiar with the analysis and intuition behind the data structure. However, I cannot seem to find a…
templatetypedef
- 2,242
- 17
- 26
18
votes
0 answers
Sylver Coinage Game
A game in which the players alternately name positive integers that
are not sums of previously named integers (with repetitions being allowed). The person who names 1 (so
ending the game) is the loser.
The question is: If player 1 names ‘16’, and…
user17918
18
votes
2 answers
Is the traditional analysis of Bloom filters wrong?
This paper claims that the traditional analysis of the error rate in Bloom filters is incorrect, then provides a lengthy and nontrivial analysis of the actual error rate. The linked paper was published in 2010, yet I've seen the traditional analysis…
templatetypedef
- 2,242
- 17
- 26
18
votes
2 answers
Lower bounds on Gaussian complexity
Define the Gaussian complexity of an $n \times n$ matrix to be the minimal number of elementary row and column operations required to bring the matrix into upper-triangular form. This is a quantity between $0$ and $n^2$ (via Gaussian elemination).…
Moritz
- 1,714
- 15
- 21
18
votes
2 answers
18
votes
1 answer
A good Library for testing whether a minors exists in a graph?
I would like to know if there are any free graph libraries for testing whether a specific set of minors exists in a given graph?
Hooman
- 289
- 1
- 2