Nous rejoindre

Revues

Informatique et mathématiques appliquées

ARIMA

[Revue africaine de recherche en informatique et mathématiques appliquées]

ARIMA

Revue africaine de recherche en informatique et mathématiques appliquées

La Revue africaine de recherche en informatique et mathématiques appliquées (ARIMA) est née en 2002 d’une collaboration scientifique Nord/Sud menée dans le sillage des activités du Colloque africain pour la recherche en informatique et mathématiques appliquées (CARI). La revue publie au fil de l’eau, en français et en anglais, les résultats de recherche issus de ces coopérations.

  • Directeur de la publication : Maurice Tchuenté
  • Rédacteurs en chef : Nabil Gmati ; Mathieu Roche ; Maurice Tchuenté ; Bruce Watson
  • Type de support : électronique
  • Périodicité : au fil de l’eau
  • Année de création : 2002
  • Date de mise en ligne sur Episciences : 2016
  • eISSN : 1638-5713
  • Disciplines : informatique et mathématiques appliquées
  • Langues de la publication : anglais, français
  • Procédure d’évaluation : évaluation en simple aveugle
  • Licence CC BY 4.0
  • Éditeur : African Society in Digital Science
    • Adresse postale : Department of Mathematics and Computer Science, Faculty of Science, University of Dschang, P.O. Box 96 Dschang
    • Pays : Cameroun
  • Contact : arima AT episciences.org
Voir le site

Derniers articles

Vers une plateforme sémantique pour l'apprentissage adaptatif et collaboratif en ligne

Dans le monde de la formation en ligne, les systèmes d'apprentissage ont cherché à proposer un contenu adapté à tout utilisateur selon son profil.Cette adaptation a comme objectif général de permettre à l'apprenant de tirer le meilleur parti du contenu exposé des ressources d'apprentissage.Cependant, du point de vue de la collaboration entre apprenants selon l'adaptation au profil des apprenants, cette adaptation n'a pas été suffisamment explorée comme un aspect important du processus d'apprentissage en ligne.L'adaptation va permettre de grouper des utilisateurs de profil similaire ou très proche pour apprendre en harmonie tout en gardant la motivation et l'engagement nécessaire afin d'augmenter le taux de réussite des apprenants. Cet état de fait doit permettre aussi de réutiliser certains parcours d'apprentissage avec de bons taux de réussite pour de futures recommandations aux utilisateurs ayant le même profil. Dans cet article, nous mettons l'accent sur cet aspect et proposons un système d'apprentissage qui recommande des parcours d'apprentissage adaptés au profil des utilisateurs et qui permet un apprentissage collaboratif des utilisateurs de façon synchrone. Après un tour d'horizon de l'existant dans le domaine de l'apprentissage adaptatif en ligne, nous proposerons une architecture pour le pilotage de ce type d'apprentissage adaptatif collaboratif. Cette solution est fondée sur des ontologies et orchestrée par un système multi-agents. Ce dernier est responsable du pilotage des parcours d'apprentissage, de la recommandation de parcours en mode collaboratif ou non par le biais d'une communication entre les différents agents intervenants et de la gestion des événements captés par le système.
Sabeima, Massra
10 janvier 2023
Lire l'article

Amélioration de la visite de classe de l'enseignement technique : intégration d'un dispositif de médiation

L’amélioration des pratiques de l’enseignant est portée par la visite de classe effectuée par le conseil pédagogique. Cet article présente l’intégration d’un système de partage de document comme un dispositif de médiation dans la visite de classe. Ce système de partage permet d’améliorer les interactions entre l’enseignant et le conseil pédagogique sur l’élaboration des principaux documents pédagogiques relatif à la visite de classe. L’expérimentation a été réalisée avec le service de partage de documents Google Drive sur une population constituée d’une quinzaine d’enseignants et de trois encadreurs pédagogiques de l’enseignement technique. Les résultats ont montré une amélioration de la qualité pédagogique de la visite de classe et une amélioration de la communication entre l’enseignant et l’encadreur pédagogique. Il ressort de cette étude que l’enseignant devient moins stressé et il sollicite beaucoup plus le conseil pédagogique que lorsqu’il n’utilise pas ce dispositif.
Ouédraogo, Frédéric,
30 septembre 2022
Lire l'article
Informatique et mathématiques appliquées

DMTCS

[Discrete Mathematics & Theoretical Computer Science]

DMTCS

Discrete Mathematics & Theoretical Computer Science

Discrete Mathematics & Theoretical Computer Science (DMTCS) est une revue à comité de lecture créée en 1997. Adossée à l’association DMTCS, elle publie au fil de l’eau des articles de recherche en anglais, dans les domaines des mathématiques discrètes et de l’informatique théorique, en particulier à l’intersection de ces deux disciplines.

  • Directeur de la publication : Jens Gustedt
  • Rédacteurs/trices en chef : Jørgen Bang-Jensen ; Michael Drmota ; Isabelle Guérin Lassous; Jens Gustedt ; Mihyun Kang ; Anca Muscholl ; Hadas Shachnai
  • Type de support : électronique
  • Périodicité : au fil de l’eau
  • Année de création : 1997
  • Date de mise en ligne sur Episciences : 2016
  • eISSN : 1365-8050
  • Disciplines : mathématiques, informatique
  • Langues de publication : anglais
  • Procédure d’évaluation : simple aveugle
  • Licence CC BY 4.0
  • Éditeur : association DMTCS
    • Adresse postale : c/o Jens Gustedt, 67A avenue Jean-Jaurès, 67100 Strasbourg
    • Pays : France
  • Contact : dmtcs AT episciences.org
Voir le site

Derniers articles

Several Roman domination graph invariants on Kneser graphs

This paper considers the following three Roman domination graph invariants on Kneser graphs: Roman domination, total Roman domination, and signed Roman domination. For Kneser graph $K_{n,k}$, we present exact values for Roman domination number $\gamma_{R}(K_{n,k})$ and total Roman domination number $\gamma_{tR}(K_{n,k})$ proving that for $n\geqslant k(k+1)$, $\gamma_{R}(K_{n,k}) =\gamma_{tR}(K_{n,k}) = 2(k+1)$. For signed Roman domination number $\gamma_{sR}(K_{n,k})$, the new lower and upper bounds for $K_{n,2}$ are provided: we prove that for $n\geqslant 12$, the lower bound is equal to 2, while the upper bound depends on the parity of $n$ and is equal to 3 if $n$ is odd, and equal to $5$ if $n$ is even. For graphs of smaller dimensions, exact values are found by applying exact methods from literature.
Zec, Tatjana
26 mai 2023
Lire l'article

Rainbow vertex pair-pancyclicity of strongly edge-colored graphs

An edge-colored graph is \emph{rainbow }if no two edges of the graph have the same color. An edge-colored graph $G^c$ is called \emph{properly colored} if every two adjacent edges of $G^c$ receive distinct colors in $G^c$. A \emph{strongly edge-colored} graph is a proper edge-colored graph such that every path of length $3$ is rainbow. We call an edge-colored graph $G^c$ \emph{rainbow vertex pair-pancyclic} if any two vertices in $G^c$ are contained in a rainbow cycle of length $\ell$ for each $\ell$ with $3 \leq \ell \leq n$. In this paper, we show that every strongly edge-colored graph $G^c$ of order $n$ with minimum degree $\delta \geq \frac{2n}{3}+1$ is rainbow vertex pair-pancyclicity.
Zhao, Peixue
16 mai 2023
Lire l'article
Informatique et mathématiques appliquées

ENTICS

[Electronic Notes in Theoretical Informatics and Computer Science]

ENTICS

Electronic Notes in Theoretical Informatics and Computer Science

ENTICS, Electronic Notes in Theoretical Informatics and Computer Science, créée en 2022, publie, au fil de l’eau en anglais, des actes de conférences et de workshops en informatique théorique.

  • Directeur de la publication : Bruno Sportisse
  • Rédacteur en chef : Michael Mislove
  • Type de support : électronique
  • Périodicité : au fil de l’eau
  • Année de création : 2022
  • Date de mise en ligne sur Episciences : 2023
  • eISSN : 2969-2431
  • Disciplines : informatique théorique
  • Langue de publication : anglais
  • Procédure d’évaluation : simple aveugle
  • Licence CC BY 4.0
  • Éditeur : Inria
    • Adresse postale : Domaine de Voluceau Rocquencourt – B.P. 105 78153 Le Chesnay Cedex
    • Pays : France
  • Contact : entics AT episciences.org
Voir le site

Derniers articles

The sheaf representation of residuated lattices

The residuated lattices form one of the most important algebras of fuzzy logics and have been heavily studied by people from various different points of view. Sheaf presentations provide a topological approach to many algebraic structures. In this paper, we study the topological properties of prime spectrum of residuated lattices, and then construct a sheaf space to obtain a sheaf representation for each residuated lattice.
Zhang, Huarong
21 mars 2023
Lire l'article

A Hofmann-Mislove theorem for $c$-well-filtered spaces

The Hofmann-Mislove theorem states that in a sober space, the nonempty Scott open filters of its open set lattice correspond bijectively to its compacts saturated sets. In this paper, the concept of $c$-well-filtered spaces is introduced. We show that a retract of a $c$-well-filtered space is $c$-well-filtered and a locally Lindel\"{o}f and $c$-well-filtered $P$-space is countably sober. In particular, we obtain a Hofmann-Mislove theorem for $c$-well-filtered spaces.
Zhang, Liping
21 mars 2023
Lire l'article
Informatique et mathématiques appliquées

FI

[Fundamenta Informaticae]

FI

Fundamenta Informaticae

Fondée en 1977, Fundamenta Informaticae est une revue scientifique à comité de lecture couvrant tous les domaines de l’informatique, avec un accent particulier sur les fondements théoriques. La revue est publiée dans la série IV des Annales Societatis Mathematicae Polonae, par la Société mathématique polonaise.

  • Directeur de la publication : Prof. Jacek Miękisz
  • Rédacteur en chef : Damian Niwiński
  • Type de support : papier et électronique
  • Périodicité : 5 à 6 volumes par an
  • Année de création : 1977
  • Date de mise en ligne sur Episciences : 2020
  • eISSN : 1875-8681
  • Disciplines : informatique
  • Langues de publication : anglais
  • Procédure d’évaluation : simple aveugle
  • Licence CC BY 4.0
  • Éditeur : Polish Mathematical Society
    • Adresse postale : ul. Śniadeckich 8, 00-656 Warszawa
    • Pays : Pologne
  • Contact : fi AT episciences.org
Voir le site

Derniers articles

Structural Liveness of Immediate Observation Petri Nets

We look in detail at the structural liveness problem (SLP) for subclasses of Petri nets, namely immediate observation nets (IO nets) and their generalized variant called branching immediate multi-observation nets (BIMO nets), that were recently introduced by Esparza, Raskin, and Weil-Kennedy. We show that SLP is PSPACE-hard for IO nets and in PSPACE for BIMO nets. In particular, we discuss the (small) bounds on the token numbers in net places that are decisive for a marking to be (non)live.
Jancar, Petr
18 avril 2023
Lire l'article

Cost Automata, Safe Schemes, and Downward Closures

In this work we prove decidability of the model-checking problem for safe recursion schemes against properties defined by alternating B-automata. We then exploit this result to show how to compute downward closures of languages of finite trees recognized by safe recursion schemes. Higher-order recursion schemes are an expressive formalism used to define languages of finite and infinite ranked trees by means of fixed points of lambda terms. They extend regular and context-free grammars, and are equivalent in expressive power to the simply typed $\lambda Y$-calculus and collapsible pushdown automata. Safety in a syntactic restriction which limits their expressive power. The class of alternating B-automata is an extension of alternating parity automata over infinite trees; it enhances them with counting features that can be used to describe boundedness properties.
Barozzini, David
18 avril 2023
Lire l'article
Informatique et mathématiques appliquées

JDMDH

[Journal of Data Mining and Digital Humanities]

JDMDH

Journal of Data Mining and Digital Humanities

Créé en 2014, le Journal of Data Mining and Digital Humanities (JDMDH) se situe à l’intersection de la fouille des données et des humanités numériques. Les articles publiés, en anglais ou en français, concernent aussi bien l’extraction et la gestion des connaissances (analyse des réseaux, extraction d’information, web sémantique, analyse des préférences, apprentissage automatique) que les sciences humaines et sociales (historiques, politiques, linguistiques, sociologiques, géographiques, de la communication et de l’archivage) à l’ère du numérique.

  • Directeur de la publication : Bruno Sportisse
  • Rédacteurs en chef : Richi Nayak ; Laurent Romary ; Nicolas Turenne
  • Type de support : électronique
  • Périodicité : au fil de l’eau
  • Année de création : 2014
  • Date de mise en ligne sur Episciences : 2014
  • eISSN : 2416-5999
  • Disciplines : sciences humaines et sociales, humanités numériques, text mining
  • Langues de publication : anglais, français
  • Procédure d’évaluation : simple aveugle
  • Licence CC BY 4.0
  • Éditeur : Inria
    • Adresse postale : Domaine de Voluceau Rocquencourt – B.P. 105 78153 Le Chesnay Cedex
    • Pays : France
  • Contact : jdmdh AT episciences.org
Voir le site

Derniers articles

From exemplar to copy: the scribal appropriation of a Hadewijch manuscript computationally explored

This study is devoted to two of the oldest known manuscripts in which the oeuvre of the medieval mystical author Hadewijch has been preserved: Brussels, KBR, 2879-2880 (ms. A) and Brussels, KBR, 2877-2878 (ms. B). On the basis of codicological and contextual arguments, it is assumed that the scribe who produced B used A as an exemplar. While the similarities in both layout and content between the two manuscripts are striking, the present article seeks to identify the differences. After all, regardless of the intention to produce a copy that closely follows the exemplar, subtle linguistic variation is apparent. Divergences relate to spelling conventions, but also to the way in which words are abbreviated (and the extent to which abbreviations occur). The present study investigates the spelling profiles of the scribes who produced mss. A and B in a computational way. In the first part of this study, we will present both manuscripts in more detail, after which we will consider prior research carried out on scribal profiling. The current study both builds and expands on Kestemont (2015). Next, we outline the methodology used to analyse and measure the degree of scribal appropriation that took place when ms. B was copied off the exemplar ms. A. After this, we will discuss the results obtained, focusing on the scribal variation that can be found both at the level of individual words and n-grams. To this end, we use machine learning to identify the most distinctive features that separate manuscript A from B. Finally, we look at possible diachronic trends in the appropriation by B's scribe of his exemplar. We argue that scribal takeovers in the exemplar impacts the practice of the copying scribe, while transitions to a different content matter cause little to no effect.
Haverals, Wouter
20 avril 2023
Lire l'article

Artificial colorization of digitized microfilms: a preliminary study

A lot of available digitized manuscripts online are actually digitized microfilms, a technology dating back from the 1930s. With the progress of artificial colorization, we make the hypothesis that microfilms could be colored with these recent technologies, testing InstColorization. We train a model over an ad-hoc dataset of 18 788 color images that are artificially gray-scaled for this purpose. With promising results in terms of colorization but clear limitations due to the difference between artificially grayscaled images and "naturaly" greyscaled microfilms, we evaluate the impact of this artificial colorization on two downstream tasks using Kraken: layout analysis and text recognition. Unfortunately, the results show little to no improvements which limits the interest of artificial colorization on manuscripts in the computer vision domain.
Clérice, Thibault
12 avril 2023
Lire l'article
Informatique et mathématiques appliquées

JIPS

[Journal d’Interaction Personne-Système]

JIPS

Journal d’Interaction Personne-Système

Créé en 2008 par l’Association francophone d’interaction humain-machine, le Journal d’Interaction Personne-Système (JIPS) succéda à la Revue d’Interaction Homme-Machine (RIHM) elle-même fondée en 1997 et active jusqu’en 2007 (devenant ensuite la Revue des Interactions Humaines Médiatisées).
JIPS a cessé de paraître en avril 2022 ; les articles publiés restent accessibles sur le site de la revue.

  • Directrice de la publication : Sophie Dupuy-Chessa
  • Type de support : électronique
  • État de la collection : 2010-2020
  • Année de création : 2008
  • Date de mise en ligne sur Episciences : 2008
  • eISSN : 2418-1838
  • Disciplines : informatique, ingénierie, technologies, sciences cognitives
  • Langues de publication : anglais, français
  • Licence CC BY 4.0
  • Éditeur : Association Francophone d’Interaction Homme-Machine (AFIHM)
    • Adresse postale : 385 rue de la Bibliothèque, 38041 Grenoble Cedex
    • Pays : France
  • Contact : presidence AT afihm.org
Voir le site

Derniers articles

Processus de changement de comportement : états, transitions et déterminants du comportement

Si le but et les garde-fous éthiques de la persuasion sont aujourd’hui bien compris, la littérature est abondante et les analyses critiques multiples, sans qu’un langage de comparaison n’ait été défini. Cet article propose les concepts d’états, de transitions et de déterminants pour caractériser les travaux de la littérature et ainsi en faciliter la compréhension et la comparaison. L’opérationnalisation de ce cadre ouvre des perspectives intéressantes au domaine.
Fenicio, Alessandro
08 février 2021
Lire l'article

L’adaptation pour une persuasion durable

Persuader est difficile ; persuader sur la durée l’est encore plus. Nous explorons l’adaptation pour apporter de la variété et de la pertinence à la persuasion et ainsi pallier l’usure de l’efficacité des messages persuasifs. Le cas d’étude est TILT, un dispositif persuasif pour la régulation du temps d’usage du smartphone. La persuasion de TILT s’appuie sur le principe d’auto-surveillance. L’expérimentation démontre la pertinence de l’adaptation du message persuasif comme renfort de l’efficacité du principe d’auto-surveillance dans le temps.
Foulonneau, Anthony
22 janvier 2021
Lire l'article
Informatique et mathématiques appliquées

LMCS

[Logical Methods in Computer Science]

LMCS

Logical Methods in Computer Science

Logical Methods in Computer Science (LMCS) publie au fil de l’eau des articles de recherche en anglais sur des domaines théoriques et pratiques de l’informatique impliquant des méthodes logiques, prises dans un sens large. Créée en 2014, la revue est éditée par Logical Methods in Computer Science e.V., une organisation à but non lucratif dont le but est de faciliter la diffusion des résultats scientifiques relatifs à la logique en informatique.

  • Directeur de la publication : Lars Birkedal
  • Rédacteur en chef : Stefan Milius
  • Type de support : électronique
  • Périodicité : au fil de l’eau
  • Année de création : 2014
  • Date de mise en ligne sur Episciences : 2015
  • eISSN : 1860-5974
  • Disciplines : informatique, méthodes logiques
  • Langues de publication : anglais
  • Procédure d’évaluation : simple aveugle
  • Licence CC BY 4.0
  • Éditeur : Logical Methods in Computer Science e.V.
    • Pays : Allemagne
  • Contact : lmcs AT episciences.org
Voir le site

Derniers articles

Adding Negation to Lambda Mu

We present $\cal L$, an extension of Parigot's $\lambda\mu$-calculus by adding negation as a type constructor, together with syntactic constructs that represent negation introduction and elimination. We will define a notion of reduction that extends $\lambda\mu$'s reduction system with two new reduction rules, and show that the system satisfies subject reduction. Using Aczel's generalisation of Tait and Martin-L\"of's notion of parallel reduction, we show that this extended reduction is confluent. Although the notion of type assignment has its limitations with respect to representation of proofs in natural deduction with implication and negation, we will show that all propositions that can be shown in there have a witness in $\cal L$. Using Girard's approach of reducibility candidates, we show that all typeable terms are strongly normalisable, and conclude the paper by showing that type assignment for $\cal L$ enjoys the principal typing property.
van Bakel, Steffen
25 mai 2023
Lire l'article

Enumerating Independent Linear Inferences

A linear inference is a valid inequality of Boolean algebra in which each variable occurs at most once on each side. In this work we leverage recently developed graphical representations of linear formulae to build an implementation that is capable of more efficiently searching for switch-medial-independent inferences. We use it to find four `minimal' 8-variable independent inferences and also prove that no smaller ones exist; in contrast, a previous approach based directly on formulae reached computational limits already at 7 variables. Two of these new inferences derive some previously found independent linear inferences. The other two (which are dual) exhibit structure seemingly beyond the scope of previous approaches we are aware of; in particular, their existence contradicts a conjecture of Das and Strassburger. We were also able to identify 10 minimal 9-variable linear inferences independent of all the aforementioned inferences, comprising 5 dual pairs, and present applications of our implementation to recent `graph logics'.
Das, Anupam
19 mai 2023
Lire l'article
Informatique et mathématiques appliquées

MNA

[Mathematical Neuroscience and Applications]

MNA

Mathematical Neuroscience and Applications

Créée en 2021, la revue Mathematical Neuroscience and Applications (MNA) s’intéresse à la modélisation et à l’analyse mathématique dans tous les domaines des neurosciences, c’est-à-dire l’étude du système nerveux et de ses dysfonctionnements. Elle est la continuité du Journal of Mathematical Neuroscience (2011-2021), précédemment publié chez Springer. La revue accueille des articles en langue anglaise.

  • Directeur de la publication : Olivier Faugeras
  • Rédacteur en chef : Olivier Faugeras
  • Type de support : électronique
  • Périodicité : annuelle
  • Année de création : 2021
  • Date de mise en ligne sur Episciences : 2021
  • eISSN : 2801-0159
  • Disciplines : mathématiques, neurosciences
  • Langues de publication : anglais
  • Procédure d’évaluation : simple aveugle
  • Licence CC BY 4.0
  • Contact : mna AT episciences.org
Voir le site

Derniers articles

On the long time behaviour of single stochastic Hodgkin-Huxley neurons with constant signal, and a construction of circuits of interacting neurons showing self-organized rhythmic oscillations

The stochastic Hodgkin-Huxley neurons considered in this paper replace time-constant deterministic input $a dt$ of the classical deterministic model by increments $\vartheta dt + dX_t$ of a stochastic process: $X$ is Ornstein-Uhlenbeck with volatility $\sigma>0$ and backdriving force $\tau>0$, and we call $\vartheta>0$ the signal. We have ergodicity and strong laws of large numbers for various functionals of the process, and characterize 'quiet behaviour' and 'regular spiking' as events whose probability depends on the parameters $(\tau,\sigma)$ and on the signal $\vartheta$. The notions of quiet behaviour and regular spiking allow for a construction of circuits of interacting stochastic Hodgkin-Huxley neurons, combining excitation with inhibition according to a bloc structure along the circuit, on which self-organized rhythmic oscillations can be observed.
Höpfner, Reinhard
30 janvier 2023
Lire l'article

Theoretical study of the emergence of periodic solutions for the inhibitory NNLIF neuron model with synaptic delay

Among other models aimed at understanding self-sustained oscillations in neural networks, the NNLIF model with synaptic delay was developed almost twenty years ago to model fast global oscillations in networks of weakly firing inhibitory neurons. Periodic solutions were numerically observed in this model, but despite its intensive study by researchers in PDEs and probability, there is up-to-date no analytical result on this topic. In this article, we propose to approximate formally these solutions by a Gaussian wave whose periodic movement is described by an associate delay differential equation (DDE). We prove the existence of a periodic solution for this DDE and we give a rigorous asymptotic result on these solutions when the connectivity parameter $b$ goes to $-\infty$. Lastly, we provide heuristic and numerical evidence of the validity of our approximation.
Ikeda, Kota
26 octobre 2022
Lire l'article
Informatique et mathématiques appliquées

TheoretiCS

TheoretiCS

Créée en 2021, TheoretiCS couvre tous les domaines de l’informatique théorique (Theoretical Computer Science, TCS). Effort conjoint de la communauté TCS, la revue est publiée par la Fondation TheoretiCS, une organisation à but non lucratif située en Allemagne. La revue publie au fil de l’eau des travaux de recherche en anglais incluant des versions révisées et étendues d’articles de conférences.

  • Directeur de la publication : Thomas Schwentick
  • Rédacteurs en chef : Javier Esparza ; Uri Zwick
  • Type de support : électronique
  • Périodicité : au fil de l’eau
  • Année de création : 2021
  • Date de mise en ligne sur Episciences : 2021
  • eISSN : 2751-4838
  • Disciplines : informatique théorique
  • Langue de publication : anglais
  • Procédure d’évaluation : simple aveugle
  • Licence CC BY 4.0
  • Éditeur : TheoretiCS Foundation e.V.
    • Adresse postale : c/o Thomas Schwentick – Schillingstr. 23, D-44139 Dortmund
    • Pays : Allemagne
  • Contact : theoretics AT episciences.org
Voir le site

Derniers articles

Fully Dynamic Connectivity in $O(\log n(\log\log n)^2)$ Amortized Expected Time

Dynamic connectivity is one of the most fundamental problems in dynamic graph algorithms. We present a randomized Las Vegas dynamic connectivity data structure with $O(\log n(\log\log n)^2)$ amortized expected update time and $O(\log n/\log\log\log n)$ worst case query time, which comes very close to the cell probe lower bounds of Patrascu and Demaine (2006) and Patrascu and Thorup (2011).
Huang, Shang-En
02 mai 2023
Lire l'article

A Robust Version of Hegedűs's Lemma, with Applications

Heged\H{u}s's lemma is the following combinatorial statement regarding polynomials over finite fields. Over a field $\mathbb{F}$ of characteristic $p > 0$ and for $q$ a power of $p$, the lemma says that any multilinear polynomial $P\in \mathbb{F}[x_1,\ldots,x_n]$ of degree less than $q$ that vanishes at all points in $\{0,1\}^n$ of some fixed Hamming weight $k\in [q,n-q]$ must also vanish at all points in $\{0,1\}^n$ of weight $k + q$. This lemma was used by Heged\H{u}s (2009) to give a solution to \emph{Galvin's problem}, an extremal problem about set systems; by Alon, Kumar and Volk (2018) to improve the best-known multilinear circuit lower bounds; and by Hrube\v{s}, Ramamoorthy, Rao and Yehudayoff (2019) to prove optimal lower bounds against depth-$2$ 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 $o(q)$ vanishes at most points of weight $k$, then it vanishes at many points of weight $k+q$. We prove this lemma and give three different applications.
Srinivasan, Srikanth
01 mars 2023
Lire l'article