The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
0answers
15 views

Liveness constraints as monotone functions

I have two question regarding an example from Michael I. Schwartzbach's lecture notes on Static Analysis. The paper defines and describes some properties of lattices and then uses static analysis to ...
1
vote
0answers
62 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
204 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 ...
10
votes
0answers
195 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
75 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
62 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
112 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
192 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
212 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
176 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. ...
16
votes
1answer
522 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
162 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 ...
13
votes
3answers
498 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
169 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 ...
16
votes
4answers
553 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 ...