Concept

Théorie de Galois

Publications associées (19)

Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in Multigraphs

Adam Teodor Polak, Alexandra Anna Lassota

We solve the Bin Packing problem in O^*(2^k) time, where k is the number of items less or equal to one third of the bin capacity. This parameter measures the distance from the polynomially solvable case of only large (i.e., greater than one third) items. O ...

Schloss Dagstuhl – Leibniz-Zentrum fur Informatik2022

Subgroups of elliptic elements of the Cremona group

Christian Lucius Urech

The Cremona group is the group of birational transformations of the complex projective plane. In this paper we classify its subgroups that consist only of elliptic elements using elementary model theory. This yields in particular a description of the struc ...

2021

Computer Algebraic Approach to Verification and Debugging of Galois Field Multipliers

Cunxi Yu, Maciej Jerzy Ciesielski

The paper presents a novel method to verify and debug gate-level arithmetic circuits implemented in Galois Field arithmetic. The method is based on forward reduction of the specification polynomials of the circuit in GF(2(m)) using GF(2) models of its logi ...

IEEE2018

Cohomological Invariants for G-Galois Algebras and Self-Dual Normal Bases

Eva Bayer Fluckiger

Cohomological Invariants for G-Galois Algebras and Self-Dual Normal Bases. We define degree two cohomological invariants for

G

-Galois algebras over fields of characteristic not 2, and use them to give necessary conditions for the existence of a self--dua ...

2017

Some consequences of Masser's counting theorem on elliptic curves

Valéry Aurélien Mahé

We use Masser's counting theorem to prove a lower bound for the canonical height in powers of elliptic curves. We also prove the Galois case of the elliptic Lehmer problem, combining Kummer theory and Masser's result with bounds on the rank and torsion of ...

Springer Heidelberg2017

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

Michael Christoph Gastpar, Saeid Sahraei

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) ...

Institute of Electrical and Electronics Engineers2017

Approximate Decoding for Network Coded Inter-dependent Data

Pascal Frossard, Nikolaos Thomos, Hyung Gon Park

In this paper, we consider decoding of loss tolerant data encoded by network coding and transmitted over error-prone networks. Intermediate network nodes typically perform the random linear network coding in a Galois field and a Gaussian elimination is use ...

Elsevier Science Bv2016

Erratum for “Galois algebras, Hasse principle and induction-restriction methods” (vol 16, pg 677, 2011)

Eva Bayer Fluckiger

This is a correction to [BP 11] E. Bayer-Fluckiger, R. Parimala, Galois algebras, Hasse principle and induction-restriction methods, Documenta Math. 16 (2011), 677-707. ...

Univ Bielefeld2013

The valuation criterion for normal basis generators

If L/K is a finite Galois extension of local fields, then we say that the valuation criterion VC(L/K) holds if there is an integer d such that every element x is an element of L with valuation d generates a normal basis for L/K. Answering a question of Byo ...

2012

On the use of graphs in discrete tomography

Dominique de Werra, Bernard Ries

In this tutorial paper, we consider the basic image reconstruction problem which stems from discrete tomography. We derive a graph theoretical model and we explore some variations and extensions of this model. This allows us to establish connections with s ...

2010

Cohomological Invariants for G-Galois Algebras and Self-Dual Normal Bases

Eva Bayer Fluckiger

Cohomological Invariants for G-Galois Algebras and Self-Dual Normal Bases. We define degree two cohomological invariants for

G

-Galois algebras over fields of characteristic not 2, and use them to give necessary conditions for the existence of a self--dua ...

2017