Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more

New answers tagged

5 votes

Can we approximate the number of words accepted by an NFA?

And now there is a faster FPRAS: https://arxiv.org/abs/2312.13320
Umang's user avatar
  • 111
4 votes

Reference request: finite field computation over the Word-RAM model

Looks like Lemma 2.6 from https://arxiv.org/abs/2403.20326 answers my question. Constant time addition and multiplication are possible over $\mathbb{F}_q$ in the Word-RAM model, provided you first ...
Naysh's user avatar
  • 686
0 votes

Positive cut algorithm on bipartite graphs with negative weights

Theorem 1. The problem is NP-hard. The proof is by reduction from the NP-hard Sparsest Cut problem. For Sparsest Cut, the input is a connected undirected graph $G=(V, E)$ and a budget $\lambda > 0$....
Neal Young's user avatar
  • 10.8k

Top 50 recent answers are included