Post-Doctoral Research Visit F/M Multipoint evaluation and spatial subdivisions
Type de contrat : Fixed-term contract
Niveau de diplôme exigé : PhD or equivalent
Fonction : Post-Doctoral Research Visit
Contexte et atouts du poste
The INRIA team Gamble is part of the INRIA Nancy Grand Est research center and also of the department Algorithms, Computation, Geometry and Image of the LORIA laboratory of Université de Lorraine.
Classical computational geometry usually deals with linear objects in a Euclidean setting and when other situations happen, curved objects are typically linearized and non-Euclidean spaces are locally approximated by Euclidean spaces. The goals of the Gamble team are to address such limitations of classical computational geometry.
Mission confiée
The goal of this postdoc is to study questions that are relevant both to discrete and computational geometry and to computer algebra, by combining combining classical methods and recent developments from both fields.
As an example, consider the typical problem, underlying several questions in computational geometry and computer algebra, is semi-algebraic range counting: given a set P of n points and a set F of polynomials, count the number of pair (f,p) ∈ F × P such that f(p) > 0. Consider for instance the case where the points are in ℝ2 and the polynomials are bivariate. On one hand, recent results in computational geometry show that if F consists of n polynomials of constant degrees, then it is possible to do it in O(n4/3) operations [1]. On the other hand, results in computer algebra based on a completely different set of tools show that if F is reduced to a single polynomial of degree n1/2, then the problem can be solved in O(n1.334) operations [2]. Is it possible to combine these two sets of tools to obtain better bounds? Or could we obtain lower bounds for those problems, in the spirit of the recent lower bounds obtained for selialgebraic range reporting problems [3]?
State of the art
The main tools from computational geometry that we will consider are cuttings [4, Ch. 4 and 6] and their algebraic generalization [5]. Initially, cuttings were introduced to allow divide-and-conquer algorithms in geometry. For example, given n lines in the plane and a parameter 0 < ε < 1, a ε−cutting is a triangulation of ℝ2 such that each triangle contains at most εn lines.
In computer algebra, the main tools used for fast bivariate polynomial evaluation are based on fast matrix multiplication [6, Ch. 12]. This tool was used to compute the modular composition of polynomials [7], and later extended to evaluate a bivariate polynomial on multiplie points [2].
An important data structure underlying these approaches is the biclique partition. Given a subset S of a product of sets F × P, a biclique partition of S is a union of pairwise distinct subsets Si ⊂ S of the form Fi × Pi ⊂ F × P such that S = ∪iSi. This kind of data structure appears notably in several geometric incidence and algebraic rigidity problems. Such problems include bounding the number of line intersections, or bounding the number of intersection of an algebraic surface with a Cartesian product [8].
Principales activités
The candidate will study the recent results on semi-algebraic-relational queries to try and narrow the gaps between upper and lower bounds. They will try to improve asymptotic bounds on related problems in computational geometry and computer algebra, and to compare and combine the methods from both fields.
Depending on the interests of the candidate, the postdoc can open up in a number of directions. For example, these problems are naturally studied in the Real RAM model of computation, but a comparison to the word-RAM model is relevant (in particular, it would be interesting to inspect the frontier between the classes NP and ETR, if any). Other possiblities include, but are not limited to, investigating from a computer algebra standpoint problems in dicrete and computational geometry where polynomials play a key role (e.g. the various phenomena of algebraic rigidity that arise in incidence geometry, semi-algebraic graphs arising from geometry, certain LP-type optimization problems, etc.).
Compétences
Academic background: Ph.D. in computer science or mathematics.
Required knowledge and skills: algorithms in discrete and computational geometry.
Avantages
- Subsidized meals
- Partial reimbursement of public transport costs
- Leave: 7 weeks of annual leave + 10 extra days off due to RTT (statutory reduction in working hours) + possibility of exceptional leave (sick children, moving home, etc.)
- Possibility of teleworking (after 6 months of employment) and flexible organization of working hours
- Professional equipment available (videoconferencing, loan of computer equipment, etc.)
- Social, cultural and sports events and activities
- Access to vocational training
- Social security coverage
Rémunération
2788 € gross/month
Informations générales
- Thème/Domaine : Algorithmics, Computer Algebra and Cryptology
- Ville : Villers lès Nancy
- Centre Inria : Centre Inria de l'Université de Lorraine
- Date de prise de fonction souhaitée : 2024-09-01
- Durée de contrat : 2 years
- Date limite pour postuler : 2024-04-28
Attention: Les candidatures doivent être déposées en ligne sur le site Inria. Le traitement des candidatures adressées par d'autres canaux n'est pas garanti.
Consignes pour postuler
Sécurité défense :
Ce poste est susceptible d’être affecté dans une zone à régime restrictif (ZRR), telle que définie dans le décret n°2011-1425 relatif à la protection du potentiel scientifique et technique de la nation (PPST). L’autorisation d’accès à une zone est délivrée par le chef d’établissement, après avis ministériel favorable, tel que défini dans l’arrêté du 03 juillet 2012, relatif à la PPST. Un avis ministériel défavorable pour un poste affecté dans une ZRR aurait pour conséquence l’annulation du recrutement.
Politique de recrutement :
Dans le cadre de sa politique diversité, tous les postes Inria sont accessibles aux personnes en situation de handicap.
Contacts
- Équipe Inria : GAMBLE
-
Recruteur :
Moroz Guillaume / Guillaume.Moroz@inria.fr
A propos d'Inria
Inria est l’institut national de recherche dédié aux sciences et technologies du numérique. Il emploie 2600 personnes. Ses 215 équipes-projets agiles, en général communes avec des partenaires académiques, impliquent plus de 3900 scientifiques pour relever les défis du numérique, souvent à l’interface d’autres disciplines. L’institut fait appel à de nombreux talents dans plus d’une quarantaine de métiers différents. 900 personnels d’appui à la recherche et à l’innovation contribuent à faire émerger et grandir des projets scientifiques ou entrepreneuriaux qui impactent le monde. Inria travaille avec de nombreuses entreprises et a accompagné la création de plus de 200 start-up. L'institut s'efforce ainsi de répondre aux enjeux de la transformation numérique de la science, de la société et de l'économie.