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 [integer-lattice]

The tag has no usage guidance.

1
vote
0answers
7 views

Size of solutions in integer programming

Given a linear integer program $Ax\leq b$ with $A\in\mathbb Z^{m\times n}$ and $b\in\mathbb Z^m$ known is there a polynomial time algorithm to give tight upper bounds for $\log_2\|x\|_\infty$ and $\...
0
votes
1answer
94 views

On polytope lattice points

Given a convex polytope let the width of the polytope be $d$ and the farthest euclidean distance between any points in the polytope be $e$. Denote $\mathcal P(a,c)$ to be the set of convex polytopes ...
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$...
8
votes
1answer
261 views

Ajtai's Proof of Theorem 1 in 'Generating Hard Instances of Lattice Problems'

My question pertains to the proof of Ajtai's main theorem in his groundbreaking 1996 paper, Generating hard instances of lattice problems, which indicates a connection between worst-case hard and ...
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 $...
1
vote
0answers
92 views

Complexity for computing weighted number of paths on integer lattice

Our input is a $(n+1)\times (n+1)$ table filled with some value (integer) for each leftmost and bottom cell $l_i,b_i$ as in the figure. We wish to compute the value of all upper and rightmost cells $...
15
votes
1answer
1k views

Solving a linear diophantine equation approximately

Consider the following problem: Input: a hyperplane $H = \{ \mathbf{y} \in \mathbb{R}^n: \mathbf{a}^T\mathbf{y} = {b}\}$, given by a vector $\mathbf{a} \in \mathbb{Z}^n$ and $b \in \mathbb{Z}$ in ...
1
vote
1answer
262 views

Most optimal parallel method for calculating the integral of a 2D function

I posted already this question to SO but got no answer so I try it now here: In some crunching number program, I have a function which can be just 1 or 0 in three dimensions. I do not know in advance ...
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 ...
25
votes
1answer
728 views

Random self-avoiding lattice cycle within a given bounding box

In connection with the Slither Link puzzle, I've been wondering: Suppose that I have an $n\times n$ grid of square cells, and I want to find a simple cycle of grid edges, uniformly at random among all ...
12
votes
2answers
707 views

What is the pathwidth of the 3D-grid (mesh or lattice) with sidelength k?

I asked this question some weeks ago at mathoverflow, but I got no reply. Here, by 3D-grid of sidelength $k$ I mean the graph $G=(V,E)$ with $V= \{1,\ldots,k\}^3$ and $E=\{( (a,b,c) ,(x,y,z) ) \mid |...
9
votes
3answers
823 views

Tree decomposition for planar graphs

First asked on math.SE with no replies. Suppose I have a planar graph, with a planar embedding, how do I find tree decomposition? What is the optimal tree decomposition of a $d$-by-$d$ square grid? ...
10
votes
2answers
499 views

Complexity of hidden polygon puzzle on square grids?

Hiroimono is a popular $NP$-complete puzzle. I'm interested in the computational complexity of a related puzzle. The problem is: Input: Given a set of points on on a $n$x$n$ square grid and ...