Most Popular
1500 questions
19
votes
3 answers
Reader, Writer monads
Let $C$ be a CCC. Let $(\times)$ be a product bifunctor on $C$. As Cat is CCC, we can curry $(\times)$:
$curry (\times) : C \rightarrow(C \Rightarrow C)$
$curry (\times) A = \lambda B. A \times B$
Functor category $C \Rightarrow C$ has usual…
beroal
- 557
- 3
- 12
19
votes
2 answers
Can we decide whether a permanent has a unique term?
Suppose we are given an n by n matrix, M, with integer entries. Can we decide in P whether there is a permutation $\sigma$ such that for all permutations $\pi\ne\sigma$ we have $\Pi M_{i\sigma(i)}\ne \Pi M_{i\pi(i)}$?
Remarks. One can of course…
domotorp
- 13,931
- 37
- 93
19
votes
5 answers
(False?) proof for computability of a function?
Consider $f(n)$, a function that returns 1 iff $n$ zeros appear consecutively in $\pi$. Now someone gave me a proof that $f(n)$ is computable:
Either for all n, $0^n$ appears in $\pi$, or there is a m s.t. $0^m$ appears in $\pi$ and $0^{m+1}$ does…
Mike B.
- 749
- 6
- 13
19
votes
1 answer
Is there a geometrical picture for adiabatic quantum computation?
In adiabatic quantum computation (AQC), one encodes the solution to an optimization problem in the ground state of a [problem] Hamiltonian $H_p$. To get to this ground state, you start in an easily coolable initial (ground) state with Hamiltonian…
hadsed
- 431
- 2
- 10
19
votes
5 answers
Fast treewidth algorithms
I would like to compute the treewidth of a graph. There are really good heuristics for other NP-hard graph problems such as VF2 for subgraph isomorphism, with code available in igraph for example. I have tried them on my graphs and I find they run…
Simd
- 3,902
- 20
- 49
19
votes
7 answers
Books/Lecture Notes on Parametrized Complexity
I would like to learn about Parametrized Complexity (both on the algorithmic side and on the hardness side). What books/lecture notes can I read on this subject?
Igor Shinkar
- 1,927
- 11
- 21
19
votes
4 answers
Checking if all products of a set of matrices eventually equal zero
I am interested in the following problem: given integer matrices $A_1,A_2, \ldots, A_k$ decide if every infinite product of these matrices eventually equals the zero matrix.
This means exactly what you think it does: we will say the set of matrices…
robinson
- 775
- 4
- 13
19
votes
1 answer
Count the number of spanning trees fast
Let $t(G)$ denote the number of spanning trees in a graph $G$ with $n$ vertices. There is an algorithm that computes $t(G)$ in $O(n^3)$ arithmetic operations. This algorithm is to compute $\frac{1}{n^2} \det(J + Q)$, where $Q$ is the Laplacian of…
user197284
- 605
- 3
- 11
19
votes
4 answers
How to obtain the unknown values $a_i,b_j$ given an unordered list of $a_i-b_j\mod N$?
Can anyone help me with the following problem?
I want to find some values $a_i,b_j$ (mod $N$) where $i=1,2,…,K, j=1,2,…,K $ (for example $K=6$), given a list of $K^2$ values that correspond to the differences $a_i-b_j\pmod N$ (for example $N=251$),…
a guest
- 193
- 1
- 4
19
votes
2 answers
Runtime of Grover's algorithm
What is the time complexity (not query complexity) of Grover's algorithm? It seems clear to me that it is $\Omega(\log(N) \sqrt{N})$ since there are $\Omega(\sqrt{N})$ iterations and each iteration requires use of the reflection operation which in…
Dan Stahlke
- 493
- 2
- 8
19
votes
11 answers
Are there any problems whose best known algorithm has run time $O\left(\frac{f(n)}{\log n}\right)$
I've never seen an algorithm with a log in the denominator before, and I'm wondering if there are any actually useful algorithms with this form?
I understand lots of things that might cause a log factor to be multiplied in the run time, e.g.…
Mike Izbicki
- 1,073
- 7
- 15
19
votes
0 answers
To what extent MSO = WS1S, when adding relations?
[This question has been asked on MathOverflow with no luck a month ago.]
Let me first clarify my definitions. For a word $w \in \Sigma^*$, with $\Sigma =\{a_1,
\ldots, a_n\}$, I define two structures:
$\mathbb{N}(w) = \langle \mathbb{N}, <,…
Michaël Cadilhac
- 3,946
- 22
- 39
19
votes
2 answers
What is the space complexity of calculating Eigenvalues?
I am looking for a survey paper or a book covering results
about the space complexity of common linear algebra operations
such as matrix rank, eigenvalues calculation, etc.
I stress the "space complexity" part meaning work space complexity,
rather…
gil
- 323
- 1
- 6
19
votes
4 answers
Why is the consensus problem so important in distributed computing?
In distributed computing, the consensus problem seems to be one of the central topics which has attracted intensive research. In particular, the paper "Impossibility of Distributed Consensus with One Faulty Process" received the 2001 PODC…
hengxin
- 2,329
- 1
- 17
- 32
19
votes
2 answers
What are the limits of total functional programming?
What are the limitations of total functional programming? It is not Turing-complete, but still supports a large subset of the possible programs. Are there important constructs that you could write in a Turing-complete language, but not in a total…
Matthijs Steen
- 423
- 4
- 8