Most Popular
1500 questions
21
votes
3 answers
Is it hard to find optimal addition chains?
An addition chain is a sequence of positive integers $(x_1, x_2, \dots, x_n)$ where $x_1 = 1$ and each index $i\ge 2$, we have $x_i = x_j + x_k$ for some indices $1\le j,k < i$. The length of the addition chain is $n$; the target of the addition…
Jeffε
- 23,129
- 10
- 96
- 163
21
votes
3 answers
Good practices for writing algorithms
This is about how effectively we can express an algorithm at hand. I need this for my undergraduate teaching.
I understand there is no such thing as standard way of writing a pseudo code. Different authors follow different conventions.
It would be…
user3162
- 709
- 5
- 12
21
votes
2 answers
Computing the Cheeger constant: feasible for which classes?
Computing the Cheeger constant of a graph, also known as the isoperimetric constant
(because it is essentially a minimum area/volume ratio), is known to be NP-complete.
Generally it is approximated. I am interested to learn if exact polynomial…
Joseph O'Rourke
- 3,753
- 23
- 41
21
votes
1 answer
Consensus clustering using set union
I've already posted this question a while ago on MathOverflow, but to the best of my knowledge it is still open, so I'm reposting it here in the hope that someone might have heard of it.
Problem statement
Let $P$, $Q$ and $R$ be three partitions…
Anthony Labarre
- 3,264
- 1
- 25
- 33
21
votes
1 answer
FPT vs W[P] - Parameterized Complexity
In parametrized complexity, $\mathsf{FPT} \subseteq \mathsf{W}[1]$ $\subseteq \mathsf{W}[2]$ $\subseteq \ldots \subseteq \mathsf{W}[P]$. It is conjectured that each of the containments is proper.
If $\mathsf{FPT}=\mathsf{W}[P]$ then…
Uéverton dos santos souza
- 213
- 1
- 6
21
votes
4 answers
Which results in complexity theory make essential use of uniformity?
A complexity class separation proof uses uniformity of complexity classes essentially if the proof does not prove the result for nonuniform version, for example proofs based on diagonalization (like time and space hierarchy theorems) make essential…
Kaveh
- 21,577
- 8
- 82
- 183
21
votes
2 answers
Are edge-vertex graphs of polytopes (decent) expanders?
This question is inspired by the polynomial Hirsch conjecture (PHC). Given a $n$-facet polytope $P$ in $\mathbb R^d$, is the spectral gap of its edge-vertex graph (call it $G$) lower bounded by $\Omega(1/\mathrm{poly}(n))$? Note that the cycle graph…
Srivatsan Narayanan
- 531
- 2
- 9
21
votes
4 answers
Do the undecidable attributes of P pose an obstruction to deciding P versus NP? (answer: maybe)
Five linked questions are asked, and a single integrated answer is hoped-for:
Q1: Do there exist languages $L$ that are recognized solely by those Turing machines in $P$ whose runtime exponents are undecidable?
Q2: Can examples of these Turing…
John Sidles
- 1,536
- 1
- 12
- 28
21
votes
3 answers
space-bounded TMs and oracles
In general, the query-tape for an oracle counts towards the space-complexity of a TM. However, it seems plausible to allow a write-only oracle-tape (such as is used in L-space reductions).
Is such a construction useful? Does it yield any…
Jeremy Hurwitz
- 433
- 3
- 7
21
votes
3 answers
Why can Lambda Calculus not represent some combinators?
This paper suggests that there are combinators (representing symbolic computations) that can not be represented by the Lambda calculus (if I understand things correctly):
hawkeye
- 2,581
- 1
- 18
- 34
21
votes
1 answer
What is the most general structure on which matrix product verification can be done in $O(n^2)$ time?
In 1979, Freivalds showed that verifying matrix products over any field can be done in randomized $O(n^2)$ time. More formally, given three matrices A, B, and C, with entries from a field F, the problem of checking whether AB = C has a randomized…
Robin Kothari
- 13,617
- 2
- 60
- 116
21
votes
10 answers
What are examples of recent relatively simple 'toolbox algorithms'?
Taking an introduction to algorithms course, one encounters quicksort, minimal spanning tree, Dijkstra, Ford–Fulkerson algorithm etc.
There are also several relatively standard data structures, such as hash maps or prefix-trees, etc. which are not…
Per Alexandersson
- 412
- 3
- 8
21
votes
2 answers
How good is the Huffman code when there are no large probability letters?
The Huffman code for a probability distribution $p$ is the prefix code with the minimum weighted average codeword length $\sum p_i \ell_i$, where $\ell_i$ is the length of the $i$th codword. It is a well-known theorem that the average length per…
Peter Shor
- 24,763
- 4
- 93
- 133
21
votes
6 answers
Difference between theory and practice of security and cryptography?
What interesting differences are there between theory and practice of security and cryptography?
Most interesting will of course be examples that suggest new avenues for theoretical research based on practical experience :).
Answers might include…
Joshua Grochow
- 37,260
- 4
- 129
- 228
21
votes
2 answers
Decidability of diophantine equations over {=, +, gcd}
It is well-known that polynomial diophantine equations are undecidable (Hilbert's 10th problem): that is, given a quantifier-free formula over the language $\{=, +, \cdot, 1\}$ (of equality, addition, multiplication, and the constant $1$), with free…
Caleb Stanford
- 872
- 5
- 15