The lattice tag has no wiki summary.
3
votes
0answers
45 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 ...
0
votes
0answers
40 views
Is SVP in Lattices equivalent with decoding random linear codes problem in terms of hardness?
Is there any equivalence (reduction) of the Decoding of random linear codes problem which the McEliece cryptosystem is based with the SVP problem where recent lattice base cryptography put its ...
5
votes
1answer
89 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
138 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 ...
10
votes
2answers
191 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
129 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. ...
12
votes
1answer
408 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
148 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 ...
11
votes
3answers
410 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
158 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 ...
15
votes
4answers
483 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 ...
