Correspondance de Galois | EPFL Graph Search

En mathématiques, une correspondance de Galois antitone est une généralisation, pour deux ordres partiels quelconques, de la correspondance entre sous-corps d'une extension galoisienne et sous-groupes de son groupe de Galois. Une correspondance de Galois isotone se définit de façon analogue, en inversant l'ordre sur le deuxième ensemble. Cette notion est reliée à celle d'opérateur de clôture. Correspondance antitone Soient m_1:P\to Q et m_2:Q\to P des fonctions définies sur deux ensembles ordonnés (P,\le_P) et (Q,\le_Q). On vérifie facilement l'équivalence des deux définitions suivantes. Première définition : (m_1,m_2) est une correspondance de Galois antitone si m_1 et m_2 sont décroissantes et si m_2\circ m_1 et m_1\circ m_2 sont extensives, c.-à-d. vérifient (pour tout élément p de P et tout élément q de Q) : :p\le_Pm_2(m_1(p))\qquad\text{et}\qquad

On the Construction of Galois Towers

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 investigate its Galois closure. Along the way, we obtain information about the structure of the Galois closure of X-0(p(n)) over X-0(p(r)), for integers 1 < r < n and prime p and the Galois closure of other modular towers (X-0(p(n)))n.

American Mathematical Society, P.O. Box 6248 Ms. Phoebe Murdock, Providence, Ri 02940 Usa2009

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 some groups of rational points on an elliptic curve.

Springer Heidelberg2017

The One-Way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness

Moran Feldman, Ashkan Norouzi Fard, Ola Nils Anders Svensson, Rico Zenklusen

We consider the classical problem of maximizing a monotone submodular function subject to a cardinality constraint, which, due to its numerous applications, has recently been studied in various computational models. We consider a clean multi-player model that lies between the offline and streaming model, and study it under the aspect of one-way communication complexity. Our model captures the streaming setting (by considering a large number of players), and, in addition, two player approximation results for it translate into the robust setting. We present tight one-way communication complexity results for our model, which, due to the above-mentioned connections, have multiple implications in the data stream and robust setting. Even for just two players, a prior information-theoretic hardness result implies that no approximation factor above 1/2 can be achieved in our model, if only queries to feasible sets, i.e., sets respecting the cardinality constraint, are allowed. We show that the possibility of querying infeasible sets can actually be exploited to beat this bound, by presenting a tight 2/3-approximation taking exponential time, and an efficient 0.514-approximation. To the best of our knowledge, this is the first example where querying a submodular function on infeasible sets leads to provably better results. Through the above-mentioned link to the robust setting, both of these algorithms improve on the current state-of-the-art for robust submodular maximization, showing that approximation factors beyond 1/2 are possible. Moreover, exploiting the link of our model to streaming, we settle the approximability for streaming algorithms by presenting a tight 1/2 + epsilon hardness result, based on the construction of a new family of coverage functions. This improves on a prior 1 - 1/e + epsilon hardness and matches, up to an arbitrarily small margin, the best known approximation algorithm.

ASSOC COMPUTING MACHINERY2020

The One-Way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness

Moran Feldman, Ashkan Norouzi Fard, Ola Nils Anders Svensson, Rico Zenklusen

ASSOC COMPUTING MACHINERY2020