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
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 ...
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 ...
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 ...
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 ...
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
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 ...
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. ...
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 ...
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 ...
Let F/E be a finite Galois extension of fields with abelian Galois group Γ. A self-dual normal basis for F/E is a normal basis with the additional property that TrF/E(g(x),h(x))=δg,h for g,h∈Γ. Bayer-Fluckiger and Lenstra h ...
We study a multiprocessor extension of the preemptive open shop scheduling problem, where the set of processors is partitioned into processor groups. We show that the makespan minimization problem is polynomially solvable for two multiprocessor groups even ...
In this paper we study an asymptotically optimal tame tower over the field with p(2) elements introduced by Garcia-Stichtenoth. This tower is related with a modular tower, for which explicit equations were given by Elkies. We use this relation to investiga ...
American Mathematical Society, P.O. Box 6248 Ms. Phoebe Murdock, Providence, Ri 02940 Usa2009
Hopf-Galois extensions of rings generalize Galois extensions, with the coaction of a Hopf algebra replacing the action of a group. Galois extensions with respect to a group G are the Hopf-Galois extensions with respect to the dual of the group algebra of ...
Let k be an algebraically closed field. Let P(X-11,...,X-nn, T) be the characteristic polynomial of the generic matrix (X-ij) over k. We determine its singular locus as well as the singular locus of its Galois splitting. If X is a smooth quasi-projective s ...
Let k be a field of characteristic /=2 and let W(k) be the Witt ring of k and L a finite extension of k. If L/k is a Galois extension, then the image of rL/k is contained in W(L)Gal(L/k) where rL/k:W(k)→W(L) is the canonical ring homomorphism. Rosenberg an ...
Extensions and variations of the basic problem of graph coloring are introduced. The problem consists essentially in finding in a graph G a k-coloring, i.e., a partition V-1,...,V-k of the vertex set of G such that, for some specified neighborhood (N) over ...
Let k be a field of characteristic = 2, and let G be a finite group. The aim of this article is to give a cohomological criterion for the isomorphism of multiples of trace forms of G-Galois algebras over k. The proof uses results concerning multiples ...
This thesis deals with the study of G-forms and particulary the trace form of a G-Galois algebra. Let k be a field of characteristic not two. Let G be a finite group and L a G-Galois algebra over k. We define the trace form qL by qL(x, y) = TrL/k(xy) for a ...
