Skip to main content
4 votes

Bounded distance decoding beyond Babai

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 ...
Noah Stephens-Davidowitz's user avatar
3 votes

Hardness of LWE on not-uniform vector samples

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 ...
Geoffroy Couteau's user avatar
2 votes

Möbius values of CNF and DNF lattices of a monotone Boolean function

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)...
M.Monet's user avatar
  • 1,429
1 vote

Feature selection problem under promise

Yes. The problem of feature selection under constraints is relevant and was studied very well in multiple scenarios. You may want to look at these papers for reference. Beyond distributive fairness ...
Vidyadhar Rao's user avatar
1 vote

Why is SVP not in coNP if Gram Schmidt Orthogonalization can provide us with a lower bound of the shortest vector

This does not imply that SVP is in coNP without a proof that a basis with the necessary properties (all its GS norms are larger than $d$) actually exists.
cbright's user avatar
  • 26
1 vote

Lattice generation inside d-dimensional unit ball

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....
D.W.'s user avatar
  • 12.2k
1 vote

Upper bound on the size of a Concept Lattice (Galois Lattice)?

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{|...
Luz's user avatar
  • 427

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