Episciences.org
Not a member yet
6707 research outputs found
Sort by
On a decomposition of -adic Coxeter orbits
No full textWe analyze the geometry of some -adic Deligne--Lusztig spaces introduced in [Iva21] attached to an unramified reductive group overa non-archimedean local field. We prove that when is classical, basic and Coxeter, decomposes as a disjoint union of translates ofa certain integral -adic Deligne--Lusztig space. Along the way we extendsome observations of DeBacker and Reeder on rational conjugacy classes ofunramified tori to the case of extended pure inner forms, and prove a loopversion of Frobenius-twisted Steinberg's cross section.Comment: \'Epijournal de G\'eom\'etrie Alg\'ebrique, Volume 7 (2023), Article no. 1
Embedding phylogenetic trees in networks of low treewidth
No full textGiven a rooted, binary phylogenetic network and a rooted, binary phylogenetictree, can the tree be embedded into the network? This problem, called\textsc{Tree Containment}, arises when validating networks constructed byphylogenetic inference methods.We present the first algorithm for (rooted)\textsc{Tree Containment} using the treewidth of the input network asparameter, showing that the problem can be solved in timeand space
Dependent Type Refinements for Futures
No full textType refinements combine the compositionality of typechecking with theexpressivity of program logics, offering a synergistic approach to programverification. In this paper we apply dependent type refinements to SAX, afutures-based process calculus that arises from the Curry-Howard interpretationof the intuitionistic semi-axiomatic sequent calculus and includes unrestrictedrecursion both at the level of types and processes. With our type refinementsystem, we can reason about the partial correctness of SAX programs,complementing prior work on sized type refinements that supports reasoningabout termination. Our design regime synthesizes the infinitary proof theory ofSAX with that of bidirectional typing and Hoare logic, deriving some standardreasoning principles for data and (co)recursion while enabling informationhiding for codata. We prove syntactic type soundness, which entails a notion ofpartial correctness that respects codata encapsulation. We illustrate ourlanguage through a few simple examples.Comment: 15 pages, MFPS 202
A Robust Version of Heged\H{u}s's Lemma, with Applications
No full textHeged\H{u}s's lemma is the following combinatorial statement regardingpolynomials over finite fields. Over a field of characteristic and for a power of , the lemma says that any multilinear polynomial of degree less than that vanishes at allpoints in of some fixed Hamming weight must alsovanish at all points in of weight . This lemma was used byHeged\H{u}s (2009) to give a solution to \emph{Galvin's problem}, an extremalproblem about set systems; by Alon, Kumar and Volk (2018) to improve thebest-known multilinear circuit lower bounds; and by Hrube\v{s}, Ramamoorthy,Rao and Yehudayoff (2019) to prove optimal lower bounds against depth-threshold circuits for computing some symmetric functions. In this paper, we formulate a robust version of Heged\H{u}s's lemma.Informally, this version says that if a polynomial of degree vanishes atmost points of weight , then it vanishes at many points of weight . Weprove this lemma and give three different applications.Comment: Published in STOC 2020. Changed affiliation in v2. v3: Revised in accordance with comments from referees for TheoretiC
You Actually Look Twice At it (YALTAi): using an object detection approach instead of region segmentation within the Kraken engine
No full textLayout Analysis (the identification of zones and their classification) is the first step along line segmentation in Optical Character Recognition and similar tasks. The ability of identifying main body of text from marginal text or running titles makes the difference between extracting the work full text of a digitized book and noisy outputs. We show that most segmenters focus on pixel classification and that polygonization of this output has not been used as a target for the latest competition on historical document (ICDAR 2017 and onwards), despite being the focus in the early 2010s. We propose to shift, for efficiency, the task from a pixel classification-based polygonization to an object detection using isothetic rectangles. We compare the output of Kraken and YOLOv5 in terms of segmentation and show that the later severely outperforms the first on small datasets (1110 samples and below). We release two datasets for training and evaluation on historical documents as well as a new package, YALTAi, which injects YOLOv5 in the segmentation pipeline of Kraken 4.1
Efficient Evaluation of Arbitrary Relational Calculus Queries
No full textThe relational calculus (RC) is a concise, declarative query language.However, existing RC query evaluation approaches are inefficient and oftendeviate from established algorithms based on finite tables used in databasemanagement systems. We devise a new translation of an arbitrary RC query intotwo safe-range queries, for which the finiteness of the query's evaluationresult is guaranteed. Assuming an infinite domain, the two queries have thefollowing meaning: The first is closed and characterizes the original query'srelative safety, i.e., whether given a fixed database, the original queryevaluates to a finite relation. The second safe-range query is equivalent tothe original query, if the latter is relatively safe. We compose ourtranslation with other, more standard ones to ultimately obtain two SQLqueries. This allows us to use standard database management systems to evaluatearbitrary RC queries. We show that our translation improves the time complexityover existing approaches, which we also empirically confirm in both realisticand synthetic experiments
Noncommutative Algebra and Representation Theory: Symmetry, Structure & Invariants
No full textThis is an abridged version of our Habilitation thesis. In these notes, weaim to summarize our research interests and achievements as well as motivatewhat drives our work: symmetry, structure and invariants. The paradigmaticexample which permeates and often inspires our research is the Weyl algebra.Comment: This is a survey paper with no proof
La science dérange-t-elle les managers ?: Retour sur la construction, la diffusion et la réception des savoirs dans la distribution d’articles et de services sportifs
No full textIn France, under the Anti-Discrimination Act of 16th November 2001, "no person may be excluded from a recruitment procedure (...) on the grounds of (...) age (...) gender (...) or physical appearance". Yet despite the existence of this anti-discrimination law, discrimination in recruitment persists. Seven surveys carried out over the last fifteen years have shed light on the sociological mechanisms that contribute to discrimination on these three grounds in a sector of activity that offers a major source of jobs for students of Sport and Exercise Sciences programmes (STAPS) - companies trading in sports goods and services in large and/or medium-sized self-service retail outlets, such as Décathlon, Sport 2000, Intersport, etc. The results have been the subject of publications and research reports, but the conduct of research in this field, which is 'sensitive’ in many ways, deserved to be developed independently, particularly in terms of the ambivalent attitude of managers towards science in this sector. Encouraged by calls for introspection and the gains offered by reflexivity in sport social sciences of sport, this account of an investigation makes it possible to look back on experiences in the field, both successful and unsuccessful, and to open a reflection on the circulation of knowledge in so-called sports distribution. Examining the context, the researcher's identity and the possible instrumentalization of her scientific work helps to explain the difficult construction of areas of favourable interest between scientists and managers in this sector of activity. Analysis of the perseverance and renunciations made on the scientific front in turn reveals the obstacles to the translation and restitution of the knowledge produced. Finally, the way in which managers seize - or fail to seize - the knowledge produced and make use of it - or fail to make use of it - reveals the mechanisms that explain the practical fortunes and misfortunes of the knowledge produced in sports management.En France, depuis la loi du 16 novembre 2001 relative à la lutte contre les discriminations, « aucune personne ne peut être écartée d’une procédure de recrutement (…) en raison (…) de son âge (…) de son sexe (…) et de son apparence physique ». Pourtant, et malgré l’existence de ce cadre législatif antidiscriminatoire, les discriminations à l’embauche persistent. Sept enquêtes menées depuis plus d’une quinzaine d’années ont permis de mettre au jour les mécanismes sociologiques qui contribuent aux processus de discrimination selon ces trois motifs dans un secteur d’activités qui constitue un gisement d’emplois pour les étudiants issus des Sciences et Techniques des Activités Physiques et Sportives (STAPS) - les entreprises pratiquant le commerce d’articles et de services sportifs dans des grandes et/ou moyennes surfaces de vente, sous la forme du libre-service, comme Décathlon, Sport 2000, Intersport, etc. Les résultats produits ont fait l’objet de publications et de communications scientifiques, mais la conduite de recherches sur ce terrain en plusieurs points « sensible » méritait un développement autonome, notamment sur la position ambivalente des managers de ce secteur d’activités à l’égard de la science. Encouragé par les appels à l’introspection et les gains offerts par la réflexivité en sciences sociales du sport, ce récit d’enquête permet de revenir a posteriori sur les expériences de terrain, heureuses ou malheureuses, et d’ouvrir la réflexion sur la circulation des savoirs dans la distribution dite sportive. L’examen du contexte, de l’identité de la chercheuse et de l’instrumentalisation possible de son travail scientifique permet d’expliquer la construction difficile de zones d’intéressement favorables entre les scientifiques et les managers de ce secteur d’activités. L’analyse des entêtements et des renoncements opérés sur le plan scientifique dévoile à son tour les obstacles à la traduction et à la restitution des savoirs produits. Enfin, la manière dont les managers se saisissent - ou non - des savoirs produits et en font - ou non - usage, permet de révéler les mécanismes qui expliquent les fortunes et infortunes pratiques des savoirs produits en management du sport
Exponentials as Substitutions and the Cost of Cut Elimination in Linear Logic
No full textThis paper introduces the exponential substitution calculus (ESC), a newpresentation of cut elimination for IMELL, based on proof terms and building onthe idea that exponentials can be seen as explicit substitutions. The idea initself is not new, but here it is pushed to a new level, inspired by Accattoliand Kesner's linear substitution calculus (LSC). One of the key properties ofthe LSC is that it naturally models the sub-term property of abstract machines,that is the key ingredient for the study of reasonable time cost models for the-calculus. The new ESC is then used to design a cut eliminationstrategy with the sub-term property, providing the first polynomial cost modelfor cut elimination with unconstrained exponentials. For the ESC, we also proveuntyped confluence and typed strong normalization, showing that it is analternative to proof nets for an advanced study of cut elimination
EpiSearch. Identifying Ancient Inscriptions in Epigraphic Manuscripts
No full textAbstractEpigraphic documents are an essential source of evidence for our knowledge of the ancient world. Nonetheless, a significant number of inscriptions have not been preserved in their material form. In fact, their texts can only be recovered thanks to handwritten materials and, in particular, the so-called epigraphic manuscripts. EpiSearch is a pilot project that explores the application of digital technologies deployed to retrieve the epigraphic evidence found in these sources. The application of Handwritten Text Recognition (HTR) to epigraphic manuscripts is a challenging task, given the nature and graphic layout of these documents. Yet, our research shows that, even with some limits, HTR technologies can be used successfully.