Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [lattice]

The tag has no usage guidance.

1
vote
1answer
101 views

Lattice generation inside d-dimensional unit ball

I am interested to know if there is a standard algorithm for generating all the lattice points inside the $d$-dimensional unit ball (with respect to the $\ell_2$-norm). The brute force approach is to ...
5
votes
0answers
128 views

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

Let $\phi$ be a monotone Boolean function on a set of variables $\langle k \rangle := \{0,\ldots,k\}$ such that $\phi$ depends on all the variables in $\langle k \rangle$ (that is, for every variable $...
7
votes
0answers
152 views

A class of functions on a lattice that are easy to optimize

Let $({\cal P}(X),\subseteq)$ be the subset lattice for a finite set $X$. Consider a function $f:{\cal P}(X)\to \mathbb{R}$ with the following property: Given any element $I_0\in {\cal P}(X)$, there ...
6
votes
1answer
125 views

Bounded distance decoding beyond Babai

Consider a full-rank lattice in $\mathbb{R}^n$. Let $\lambda_1$ be the length of the shortest nonzero vector. Given a vector in $\mathbb{R}^n$ we wish to find the nearest lattice vector, as measured ...
2
votes
1answer
102 views

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

A context is a tuple $(O, A, R)$ where $O$ is the set of objects, $A$ the set of attributes and $R \subseteq O\times A$ is a relation. For $o \in O$ and $a \in A$ we read $oRa$ as the object $o$ ...
6
votes
0answers
259 views

On the shortest vector problem (is it $NP$-complete?)

Ajtai has shown that shortest vector problem is $NP$-hard by using randomized reduction from subset sum. Has this been derandomized?
8
votes
0answers
159 views

Simplified lattices

Consider the following question: Let $N$ be some large prime number, and suppose we are given $n$ uniformly independent samples $g_i$ from $0...,N-1$. Think of $N$ as being exponentially large in $n$...
1
vote
0answers
50 views

partitioning boolean lattice into the smallest number of chains

As a result of the Dilowrth's theorm we know that the Boolean Lattic can be partitioned into $\dbinom{n}{n/2}$ chains and it is the smallest number of such chains. Another question regarding that, ...
2
votes
1answer
144 views

Algorithms for tree rotation

What is the fastest known algorithm(s) for finding a minimal sequence of tree rotations that transform given trees $A$ to $B$ (each with $n$ unlabeled nodes)? Equivalently, how can we find a shortest ...
12
votes
0answers
118 views

Is it #P-hard to compute the number of antichains of a distributive lattice?

An antichain of a poset $(P, <)$ is a subset of pairwise incomparable elements, namely, a subset $A \subseteq P$ such that there are no $x, y \in A$ with $x < y$. By a result of Provan and Ball, ...
2
votes
0answers
84 views

Completeness of the quotient of the power set lattice of a partial order induced by the Hoare pre-order

Let $(P,\le)$ be a partially ordered set and $\preceq$ the Hoare pre-order on its subsets, i.e. for $X,Y\subseteq P$, $X\preceq Y$ iff $\forall x\in X:\exists y\in Y:x\le y$. Let $\sim$ be the ...
5
votes
0answers
238 views

Less known graphical representations of Boolean functions

A Boolean function $f: \{0, 1\}^n \rightarrow \{0, 1\}$ admits a canonical graphical representation in terms of a reduced ordered binary decision diagram (ROBDDs or BDDs for short). There are other ...
1
vote
0answers
91 views

Nearly-uniformally sampling lattice points from a basis that lie on the interior of a polytope

Definitions: Consider a polytope $P \subset \mathbb{R}^n$ with a nonempty interior to be $P : \{x \in \mathbb{R}^n | Ax \le B\}$ for appropriate real $n \times m$ matrix $A$ and $m \times 1$ vector $...
4
votes
2answers
256 views

Lattice-based algorithms in practice

Are there any applications of lattice-based algorithms other than those in cryptography and integer programming? Could someone state a few papers where the primary algorithms use lattice-based LLL ...
3
votes
1answer
339 views

Factoring with LLL when the form of the factors is given

Given a degree $2k$ reducible polynomial $$f(x)=\sum_{i=0}^{2k}a_ix^i\in\Bbb Z[x]$$ with $$\text{gcd}(a_{2k},\dots,a_0)=1$$ that is known to be of the form $f_1(x)f_2(x)$ with $\text{deg}\big(...
10
votes
0answers
376 views

Illustrative Examples of Tarski's Fixed Point Theorems

I have come across many informal examples that provide a physical illustration for Brouwer's fixed point theorem (some due to Brouwer himself). A person walks from the bottom of a hill to the top. ...
4
votes
0answers
84 views

Computing a frontier set for some Boolean-valued function in a lattice?

Assume that we have a non-empty finite lattice $(L,\leq)$ and a monotone Boolean-valued function $f : L \rightarrow \mathbb{B}$ (i.e, for every $x,y \in L$, if $f(x)=\mathbf{true}$ and $x \leq y$, ...
3
votes
0answers
83 views

Closest Vector Problem with sparse basis and target vector

The Closest Vector Problem (and related problems) is random self-reducible and in general is NP-Hard, making it a useful tool in cryptography research and post-quantum public key crypto. For a variety ...
5
votes
1answer
158 views

CNF Rule hierarchy discovery

This is bothering me for some time. Consider that I have a set of CNF formulae: $F_1 = \left( A \lor B \lor C \right) \land \left( C \lor D \lor E \right) \land \left( B \lor F \lor G \right)$ $F_2 =...
8
votes
2answers
287 views

Sufficient conditions to guarantee unique fixpoint (not unique least/greatest fixpoint) for monotone functions on complete lattice

Tarski's fixpoint theorem states, that the fixpoints of a monotone operator on a complete lattice is a complete lattice. By consequence, we have a unique greatest fixpoint and unique least fixpoint ...
11
votes
2answers
258 views

On $n$ dimensional manifolds and lattices

EDIT (By Tara B): I'd still be interested in a reference to a proof of this, as I had to prove it myself for my own paper. I'm looking for the proof of Theorem 4 that appears in this paper: An ...
1
vote
1answer
275 views

2D grid placement problem

Data for the problem: 2D grid(lattice) of size NxN n nodes placed on the grid:node_1,node_2,…node_n Each of nodes contain some data: a. node_i is presented by 3 parameters (x_i,y_i,t_i) b. ...
17
votes
1answer
641 views

A topological space related to SAT: is it compact?

The Satisfiability problem is, of course, a fundamental problem in theoretical CS. I was playing with one version of the problem with infinitely many variables. $\newcommand{\sat}{\mathrm{sat}} \...
1
vote
0answers
218 views

The Number of Short Vectors in a Lattice [closed]

Given a lattice $L = \bigoplus_{i=1}^{m} \mathbb{Z}v_i$ (the $v_i$ are linearly independent vectors in $\mathbb{R}^n$) and a number $c > 0$, can one quickly compute or find a good estimate on the ...
15
votes
3answers
704 views

Edit distance between two partitions

I have two partitions of $[1 \ldots n]$ and am looking for the edit distance between them. By this, I want to find the minimal number of single transitions of a node into a different group that are ...
2
votes
0answers
193 views

Turing Machine which generates order on the set of its states

The Turing machine (TM) is an abstract model for effective implementation of (finite algorithmic) calculation. TM is defined over some alphabet of symbols L and reading data performs a finite sequence ...
17
votes
4answers
677 views

Applications of metric structures on posets/lattices in theoryCS

Since the term is overloaded, a brief definition first. A poset is a set $X$ endowed with a partial order $\le$. Given two elements $a,b \in X$, we can define $x \vee y$ (join) as their least upper ...