As of May 31, 2023, we have updated our Code of Conduct.

New answers tagged

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 ...
Siddharth's user avatar
  • 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$ ...
Andras Farago's user avatar
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 (...
Lijie Chen's user avatar
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 ...
D.W.'s user avatar
  • 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 ...
Andras Farago's user avatar
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 ...
Joshua Grochow's user avatar

Top 50 recent answers are included