Tag Info

9

Yes, assuming you want both $f_1(x)$ and $f_2(x)$ with integer coefficients. One of the reasons why LLL is so popular is precisely because it gives a polynomial time algorithm to factor polynomials with integer coefficients. For an excellent introduction, I recommend C. Yap's "Fundamental Problems in Algorithmic Algebra" (available online, for free), ...

8

If you look at the original paper by Lenstra, Lenstra, and Lovasz, you will see the following applications: factoring univariate polynomials over the rationals (the motivation for developing LLL basis reduction) efficient version of Dirichlet's classical diophantine approximation theorem: for rationals $a_1, \ldots, a_n$ and $\epsilon$, find in polynomial ...

7

It's fixed-parameter tractable in the natural parameter, the distance. So if two trees have distance $k$ you can find the distance in time polynomial + $f(k)$ for some function $f$. The proof is a kernelization that produces a kernel of size $O(k)$ so putting that together with the naive method of finding a shortest path in the flip graph gives time singly ...

3

I realize that this is a very late reply, but the answer is yes. You can get an approximation factor of $2^{C n \log \log n/\log n}$ for any constant $C$ in polynomial time. In fact, you can do this with Babai's algorithm together with better preprocessing than LLL. Unfortunately, I don't know of a great write up for this specific fact. The main point is ...

3

Since you are specifically interested in $q=2$, I will focus on this case in my answer. A note on your choice of tags: you tagged your question with "lattice" and "lattice-theory"; however, your question seems much more closely related to questions in coding theory. I elaborate below. A good starting point is to observe that LPN with matrix $A$ reduces to ...

2

OK so, more than one year later, here is the answer to this. We'll see Boolean valuations $\nu$ as the set of variables that are mapped to $1$. We can show that $\mu_\text{cnf}(\hat{0},\hat{1}) = (-1)^k \mu_\text{dnf}(\hat{0},\hat{1}) = \sum_{\nu \models \phi} (-1)^{|\nu|}$. In the literature, the quantity $\sum_{\nu \models \phi} (-1)^{|\nu|}$ is also ...

1

In general, even telling whether any such point exists is hard; it is equivalent to the Shortest Vector Problem (SVP), and it is conjectured that there is no polynomial-time algorithm for this problem.

1

As told in the previous comments, $min\{2^{|O|}, 2^{|A|}\}$ is a correct upper bound. When the parameter $R$ is also available, we can improve the upper bound to $min\{2^{|O|}, 2^{|A|}, 2^{1+\sqrt{|R|}}\}$

Only top voted, non community-wiki answers of a minimum length are eligible