Geometric Considerations in Lattice Programming

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Geometric properties of lattice quantum gravity in two dimensions are studied numerically via Monte Carlo on Euclidean Dynamical Triangulations. A new computational method is proposed to simulate gravity coupled with fermions, which allows the study of int ...

We give a construction of an efficient one-out-of-many proof system, in which a prover shows that he knows the pre-image for one element in a set, based on the hardness of lattice problems. The construction employs the recent zero-knowledge framework of Ly ...

We show that a constant factor approximation of the shortest and closest lattice vector problem in any l(p)-norm can be computed in time 2((0.802 + epsilon)n). This matches the currently fastest constant factor approximation algorithm for the shortest vect ...

We study the elliptic curves given by y(2) = x(3) + bx + t(3n+1) over global function fields of characteristic 3 ; in particular we perform an explicit computation of the L-function by relating it to the zeta function of a certain superelliptic curve u(3) ...

An oblivious linear function evaluation protocol, or OLE, is a two-party protocol for the function f (x) = ax + b, where a sender inputs the field elements a, b, and a receiver inputs x and learns f (x). OLE can be used to build secret-shared multiplicatio ...

We propose a new approach for normalization and simplification of logical formulas. Our approach is based on algorithms for lattice-like structures. Specifically, we present two efficient algorithms for computing a normal form and deciding the word problem ...

We start this short note by introducing two remarkable mathematical objects: the E8E8 root lattice Lambda8Lambda8 in 8-dimensional Euclidean space and the Leech lattice Lambda24Lambda24 in 24-dimensional space. These two lattices stand out among their lat ...

An integer program (IP) is a problem of the form

\min \{f(x) : \, Ax = b, \ l \leq x \leq u, \ x \in \Z^n\}

, where

A \in \Z^{m \times n}

b \in \Z^m

l,u \in \Z^n

, and

f: \Z^n \rightarrow \Z

is a separable convex objective function. The problem o ...

The advent of the quantum computer makes current public-key infrastructure insecure. Cryptography community is addressing this problem by designing, efficiently implementing, and evaluating novel public-key algorithms capable of withstanding quantum comput ...

In a seminal work, Micciancio and Voulgaris (SIAM J Comput 42(3):1364-1391, 2013) described a deterministic single-exponential time algorithm for the closest vector problem (CVP) on lattices. It is based on the computation of the Voronoi cell of the given ...

This thesis explores various approaches of studying the long-range colour order of antiferromagnetic SU(N) Heisenberg models with the linear flavour-wave theory (LFWT). The LFWT is an extension of the well-known SU(2) spin-wave theory to SU(N), and this se ...

In a seminal work, Micciancio & Voulgaris (2010) described a deterministic single-exponential time algorithm for the Closest Vector Problem (CVP) on lattices. It is based on the computation of the Voronoi cell of the given lattice and thus may need exponen ...

The worst-case hardness of finding short vectors in ideals of cyclotomic number fields (Ideal-SVP) is a central matter in lattice based cryptography. Assuming the worst-case hardness of Ideal-SVP allows to prove the Ring-LWE and Ring-SIS assumptions, and t ...

The security of public-key cryptography relies on well-studied hard problems, problems for which we do not have efficient algorithms. Factorization and discrete logarithm are the two most known and used hard problems. Unfortunately, they can be easily solv ...

A particular instance of the shortest vector problem (SVP) appears in the context of compute-and-forward. Despite the NP-hardness of the SVP, we will show that this certain instance can be solved in complexity order O(nψlog(nψ)) , where ψ=sqrt(P ||h||^2+1) ...

Motivated by recent experimental progress in the context of ultra-cold multi-colour fermionic atoms in optical lattices, this thesis investigates the properties of the antiferromagnetic SU(N) Heisenberg models with fully antisymmetric irreducible represent ...

The unique shortest vector problem on a rational lattice is the problem of finding the shortest non-zero vector under the promise that it is unique (up to multiplication by -1). We give several incremental improvements on the known hardness of the unique s ...

The Learning With Error problem (LWE) is becoming more and more used in cryptography, for instance, in the design of some fully homomorphic encryption schemes. It is thus of primordial importance to find the best algorithms that might solve this problem so ...

In this paper, we present a heuristic algorithm for solving exact, as well as approximate, shortest vector and closest vector problems on lattices. The algorithm can be seen as a modified sieving algorithm for which the vectors of the intermediate sets lie ...

Compute-and-Forward is an emerging technique to deal with interference. It allows the receiver to decode a suitably chosen integer linear combination of the transmitted messages. The integer coefficients should be adapted to the channel fading state. Optim ...

Geometric Considerations in Lattice Programming

Chat with Graph Search

Hausdorff dimension of fermions on a random lattice

BLOOM: Bimodal Lattice One-out-of-Many Proofs and Applications

Approximate CVPp in time 2(0.802n)

On the Mordell-Weil lattice of y(2) = x(3) + bx plus t(3n+1) in characteristic 3

Efficient protocols for oblivious linear function evaluation from ring-LWE

Formula Normalizations in Verification

Almost impossible E_8 and Leech lattices

New Results in Integer and Lattice Programming

Synthesis of Flexible Accelerators for Early Adoption of Ring-LWE Post-quantum Cryptography

On compact representations of Voronoi cells of lattices

Linear Flavour-Wave Theory of SU(N) Lattice Models with Arbitrary Irreducible Representations

On compact representations of Voronoi cells of lattices

Short Stickelberger Class Relations and Application to Ideal-SVP

LPN in Cryptography : an Algorithmic Study

Polynomially Solvable Instances of the Shortest and Closest Vector Problems With Applications to Compute-and-Forward

A variational investigation of the SU(N) Heisenberg model in antisymmetric irreducible representations

Improved hardness results for unique shortest vector problem

Better Algorithms for LWE and LWR

A sieve algorithm based on overlattices

Compute-and-Forward: Finding the Best Equation