New answers tagged cc.complexity-theory
0
votes
Can Lexicographic BFS be implemented in logspace?
It is not clear that the OP meant lexicographic BFS. The OP let (paraphrasing) $u_1$ be $v_1$, and the next elements $u_2$, $u_3$, etc., of the output, be the neighbors of $v_1$ according to the input ...
- 693
16
votes
Accepted
Why the "balanced vs constant function" problem is not a proof that P ≠ BPP?
It is true that if the function $f$ is given by an oracle, then a randomized algorithm is exponentially faster than any deterministic algorithm. With an oracle function, however, this is not a $BPP$ ...
- 11.1k
2
votes
Fine-grained average-case derandomization
There are some recent works on this topic, for example [DMOZ20], [CT21a], and [CT21b].
For worst-case derandomization: following [DMOZ20], [CT21a] showed that under plausible hardness assumption (...
- 151
6
votes
Priority queue implementation with both find-min and delete-min $o(\log n)$
It is trivial to build a heap where insert takes $O(n)$ time and find-min and delete-min take $O(1)$ time: simply store all the numbers in a linked list in sorted order.
It is not possible to build a ...
- 11.3k
8
votes
Complexity class of optimization problems whose fractional relaxation is polynomial-time solvable
The answer to the second question is no. Here is an example when the integer-output optimization problem is polynomial-time solvable, yet its fractional relaxation is NP-complete:
In complements of ...
- 11.1k
2
votes
Accepted
Perm and Det mod $2^k$ - I
I don't think so. Theorem 5.1 of the linked paper shows that, for any fixed k, permanent mod $2^k$ is $\mathsf{\oplus L}$-complete. (I believe the same is true for det mod $2^k$.) So it won't be in a ...
- 36.4k
Top 50 recent answers are included