Hot answers tagged

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), ...


9

Efficient CNF Simplification based on Binary Implication Graphs, Marijn Heule, Matti Jarvisalo, and Armin Biere, 2011 "This paper develops techniques for efficiently detecting and removing redundancies from CNF (conjunctive normal form) formulas based on the underlying binary clause structure (i.e., the binary implication graph) of the formulas. ...


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