Join us

Journals

Informatics and Applied Mathematics

ARIMA

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

ARIMA

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

The Revue africaine de recherche en informatique et mathématiques appliquées (ARIMA) was born in 2002 from a North/South scientific collaboration carried out in the wake of the activities of the African Colloquium for Research in Computer Science and Applied Mathematics (Colloque africain pour la recherche en informatique et mathématiques appliquées, CARI). The journal publishes the research results of these collaborations in French and English on an ongoing basis.

  • Director of publication: Maurice Tchuenté
  • Editor-in-chief: Nabil Gmati ; Mathieu Roche ; Tayou Djamegni Clémentin
  • Medium: electronic
  • Frequency: continuous
  • Date created: 2002
  • Date of publication on Episciences: 2016
  • eISSN: 1638-5713
  • Subjects: Computer Science and Applied Mathematics
  • Languages of publication: English, French
  • Review process: single blind peer review
  • CC BY 4.0 licence
  • Publisher: African Society in Digital Science
    • Address: Department of Mathematics and Computer Science, Faculty of Science, University of Dschang, P.O. Box 96 Dschang
    • Country: Cameroon
  • Contact: arima AT episciences.org
See website

Latest articles

Synthèse multi-cible des systèmes de contrôle-commande à l'aide de l'approche IDM

Le GRAFCET est un puissant langage de modélisation graphique pour la spécification de contrôleurs dans des systèmes à événements discrets. Il prend en compte des structures hiérarchiques ainsi que des contraintes structurelles et sémantiques.Ici, nous proposons d'utiliser un modèle de spécification GRAFCET dans une approche d'ingénierie dirigée par les modèles (IDM) pour la synthèse multi-cible de systèmes de contrôle commande embarqués basés sur des microcontrôleurs.Dans cette approche, un métamodèle GRAFCET est associé à un métamodèle microcontrôleur, lequel caractérise les fonctionnalités de la plateforme spécifique microcontrôleur à considérer lors de la génération de code.Ce métamodèle GRAFCET proposé prend en compte la modélisation des expressions pour faciliter la vérification du modèle et une interprétation facile des événements GRAFCET ainsi que des contraintes de temps. Les règles de transformation utiles à la génération de code pour des microcontrôleurs C-programmables sont ensuite présentées.Comme application, nous présentons une plateforme basée sur Eclipse EMF, Object Constraint Language (OCL) et le moteur de génération de code Acceleo.
Nzebop Ndenoka, Gérard
April 09, 2025
Read article

Prise en compte du temps et des catégories d'item dans l'estimation des influences sociales implicites pour l'amélioration des systèmes de recommandation basés sur la confiance.

De nos jours, les plateformes d’e-commerce, de streaming et de réseaux sociaux jouent un rôle important dans notre quotidien. Cependant, l’ajout toujours croissant d’éléments sur ces plateformes (articles sur Amazon, vidéos sur Netflix et YouTube, publications sur Facebook et Instagram) rend difficile pour les utilisateurs de sélectionner les éléments qui les intéressent. L'intégration de systèmes de recommandation dans ces plateformes vise à proposer à chaque utilisateur une petite liste d'éléments correspondant à ses préférences. Pour améliorer les performances de ces systèmes de recommandation, certains travaux de la littérature intègrent une confiance explicite ou implicite entre les utilisateurs de la plateforme via des systèmes de recommandation basés sur la confiance. En effet, nombre de ces travaux reposent sur une confiance explicite, lorsque chaque utilisateur désigne ceux en qui il a confiance dans la plateforme. Mais ces informations sont rares sur la plupart des plateformes du monde réel. Ainsi, d'autres travaux proposent d'estimer la confiance implicite que chaque utilisateur peut accorder à un autre. Cependant, les travaux qui estiment la confiance implicite ne prennent pas en compte la dynamique temporelle des actions passées des utilisateurs et encore moins le fait qu'un utilisateur peut en influencer un autre sur une catégorie d'item et pas sur une autre. Dans cet article, nous proposons des stratégies sensibles au temps et au contenu pour estimer l'influence sociale d'un utilisateur sur un autre. La confiance implicite qui en résulte, consciente du temps et du contenu, est intégrée aux systèmes de recommandation basés sur la confiance, construits sur les K-Nearest Neighbours (KNN) et les techniques basées sur les graphiques. Les expériences réalisées pour les prédictions de notation avec KNN et les recommandations Top-N avec le modèle Graph montrent que la confiance implicite consciente du temps et du contenu permet d'améliorer les performances du KNN selon la métrique RMSE de 7% et 10%, et les performances du modèle graphique selon la métrique NDCG@10 de 59% et 08% respectivement sur les jeux de données Ciao et Epinions.
Nzekon Nzeko'o, Armel Jacques
March 23, 2025
Read article
Informatics and Applied Mathematics

Compositionality

Compositionality

Founded in 2017, Compositionality welcomes research articles in English in the field of the mathematics of composition across all disciplines. The journal is published by the Compositionality Charitable Incorporated Organisation.

  • Director of publication: John Baez
  • Editors-in-chief: Aleks Kissinger ; Joachim Kock
  • Medium: electronic
  • Frequency: annual
  • Date created: 2017
  • Date of publication on Episciences: 2024
  • eISSN: 2631-4444
  • Subjects: mathematics, computation, logic, physics, chemistry, engineering, linguistics, cognition
  • Language of publication: English
  • Review process: single blind peer review
  • CC BY 4.0 licence
  • Publisher: Compositionality Charitable Incorporated Organisation
    • Address: 108 Kennington Road, Kennington, Oxford, OX1 5PE
    • Country: United Kingdom
  • Contact: compositionality AT episciences.org
See website

Latest articles

Cloven operadic categories: An approach to operadic categories with cardinalities in finite unordered sets

We introduce and study operadic categories with cardinalities in finite sets and establish conditions under which their associated theories of operads and algebras are equivalent to the standard framework introduced in 2015 by Batanin and Markl. Our approach is particularly natural in applications to the operadic category of graphs and the related category of modular operads and their clones.
Markl, Martin
October 17, 2025
Read article

Additive Invariants of Open Petri Nets

We classify all additive invariants of open Petri nets: these are $\mathbb{N}$-valued invariants which are additive with respect to sequential and parallel composition of open Petri nets. In particular, we prove two classification theorems: one for open Petri nets and one for monically open Petri nets (i.e. open Petri nets whose interfaces are specified by monic maps). Our results can be summarized as follows. The additive invariants of open Petri nets are completely determined by their values on a particular class of single-transition Petri nets. However, for monically open Petri nets, the additive invariants are determined by their values on transitionless Petri nets and all single-transition Petri nets. Our results confirm a conjecture of John Baez (stated during the AMS' 2022 Mathematical Research Communities workshop).
Bumpus, Benjamin Merlin
July 25, 2025
Read article
Informatics and Applied Mathematics

DMTCS

[Discrete Mathematics & Theoretical Computer Science]

DMTCS

Discrete Mathematics & Theoretical Computer Science

Discrete Mathematics & Theoretical Computer Science (DMTCS) is a peer-reviewed journal created in 1997. As a member of the DMTCS Association, it publishes research articles in English in the fields of discrete mathematics and theoretical computer science, especially at the intersection of these two disciplines.

  • Director of publication: Jens Gustedt
  • Editors-in-chief: Christoph Haase, Dieter Rautenbach, Sergi Elizalde and Hadas Shachnai
  • Medium: electronic
  • Frequency: continuous
  • Date created: 1997
  • Date of publication on Episciences: 2016
  • eISSN: 1365-8050
  • Subjects: mathematics, computer science
  • Languages of publication: English
  • Review process: single blind peer review
  • CC BY 4.0 licence
  • Publisher: Association DMTCS
    • Address: c/o Jens Gustedt, 67A avenue Jean-Jaurès, 67100 Strasbourg
    • Country: France
  • Contact: dmtcs AT episciences.org
See website

Latest articles

Thresholds for the biased Maker-Breaker domination games

In the $(a,b)$-biased Maker-Breaker domination game, two players alternately select unplayed vertices in a graph $G$ such that Dominator selects $a$ and Staller selects $b$ vertices per move. Dominator wins if the vertices he selected during the game form a dominating set of $G$, while Staller wins if she can prevent Dominator from achieving this goal. Given a positive integer $b$, Dominator's threshold, $\textrm{a}_b$, is the minimum $a$ such that Dominator wins the $(a,b)$-biased game on $G$ when he starts the game. Similarly, $\textrm{a}'_b$ denotes the minimum $a$ such that Dominator wins when Staller starts the $(a,b)$-biased game. Staller's thresholds, $\textrm{b}_a$ and $\textrm{b}'_a$, are defined analogously. It is proved that Staller wins the $(k-1,k)$-biased games in a graph $G$ if its order is sufficiently large with respect to a function of $k$ and the maximum degree of $G$. Along the way, the $\ell$-local domination number of a graph is introduced. This new parameter is proved to bound Dominator's thresholds $\textrm{a}_\ell$ and $\textrm{a}_\ell'$ from above. As a consequence, $\textrm{a}_1'(G)\le 2$ holds for every claw-free graph $G$. More specific results are obtained for thresholds in line graphs and Cartesian grids. Based on the concept of $[1,k]$-factor of a graph $G$, we introduce the star partition width $σ(G)$ of $G$, and prove that $\textrm{a}_1'(G)\le σ(G)$ holds for any nontrivial graph $G$, while $\textrm{a}_1'(G)=σ(G)$ if $G$ is a tree.
Brešar, Boštjan
October 22, 2025
Read article

Low complexity binary words avoiding $(5/2)^+$-powers

Rote words are infinite words that contain $2n$ factors of length $n$ for every $n \geq 1$. Shallit and Shur, as well as Ollinger and Shallit, showed that there are Rote words that avoid $(5/2)^+$-powers and that this is best possible. In this note we give a structure theorem for the Rote words that avoid $(5/2)^+$-powers, confirming a conjecture of Ollinger and Shallit.
Currie, James
October 20, 2025
Read article
Informatics and Applied Mathematics
Proceedings

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—publishes proceedings of conferences and workshops in English that include significant theoretical advances in computer science and theoretical informatics.

  • Director of publication: Bruno Sportisse
  • Editor-in-chief: Michael Mislove
  • Medium: electronic
  • Frequency: continuous
  • Date created: 2022
  • Date of publication on Episciences: 2023
  • eISSN: 2969-2431
  • Subjects: computer science, theoretical informatics
  • Language of publication: English
  • Review process: single blind peer review
  • CC BY 4.0 licence
  • Publisher: Inria
    • Address: Domaine de Voluceau Rocquencourt – B.P. 105 78153 Le Chesnay Cedex
    • Country: France
  • Contact: entics AT episciences.org
See website

Latest articles

Implicit automata in {\lambda}-calculi III: affine planar string-to-string functions

We prove a characterization of first-order string-to-string transduction via $\lambda$-terms typed in non-commutative affine logic that compute with Church encoding, extending the analogous known characterization of star-free languages. We show that every first-order transduction can be computed by a $\lambda$-term using a known Krohn-Rhodes-style decomposition lemma. The converse direction is given by compiling $\lambda$-terms into two-way reversible planar transducers. The soundness of this translation involves showing that the transition functions of those transducers live in a monoidal closed category of diagrams in which we can interpret purely affine $\lambda$-terms. One challenge is that the unit of the tensor of the category in question is not a terminal object. As a result, our interpretation does not identify $\beta$-equivalent terms, but it does turn $\beta$-reductions into inequalities in a poset-enrichment of the category of diagrams.
Pradic, Cécilia
December 11, 2024
Read article

Cost-sensitive computational adequacy of higher-order recursion in synthetic domain theory

We study a cost-aware programming language for higher-order recursion dubbed $\textbf{PCF}_\mathsf{cost}$ in the setting of synthetic domain theory (SDT). Our main contribution relates the denotational cost semantics of $\textbf{PCF}_\mathsf{cost}$ to its computational cost semantics, a new kind of dynamic semantics for program execution that serves as a mathematically natural alternative to operational semantics in SDT. In particular we prove an internal, cost-sensitive version of Plotkin's computational adequacy theorem, giving a precise correspondence between the denotational and computational semantics for complete programs at base type. The constructions and proofs of this paper take place in the internal dependent type theory of an SDT topos extended by a phase distinction in the sense of Sterling and Harper. By controlling the interpretation of cost structure via the phase distinction in the denotational semantics, we show that $\textbf{PCF}_\mathsf{cost}$ programs also evince a noninterference property of cost and behavior. We verify the axioms of the type theory by means of a model construction based on relative sheaf models of SDT.
Niu, Yue
December 11, 2024
Read article
Informatics and Applied Mathematics

FI

[Fundamenta Informaticae]

FI

Fundamenta Informaticae

Fundamenta Informaticae, established in 1977, is a peer-reviewed scientific journal covering all areas of computer science, with main focus on theoretical foundations. The journal is published as Series IV of Annales Societatis Mathematicae Polonae, by the Polish Mathematical Society.

  • Director of publication: Prof. Jacek Miękisz
  • Editor-in-chief: Bartek Klin
  • Medium: electronic
  • Frequency: 3-4 volumes per year
  • Date created: 1977
  • Date of publication on Episciences: 2020
  • eISSN: 1875-8681
  • Subjects: computer science
  • Languages of publication: English
  • Review process: single blind peer review
  • CC BY 4.0 licence
  • Publisher: Polish Mathematical Society
    • Address: ul. Śniadeckich 8, 00-656 Warszawa
    • Country: Poland
  • Contact: fi AT episciences.org
See website

Latest articles

Runtime Repeated Recursion Unfolding in CHR: A Just-In-Time Online Program Optimization Strategy That Can Achieve Super-Linear Speedup

We introduce a just-in-time runtime program transformation strategy based on repeated recursion unfolding. Our online program optimization generates several versions of a recursion differentiated by the minimal number of recursive steps covered. The base case of the recursion is ignored in our technique. Our method is introduced here on the basis of single linear direct recursive rules. When a recursive call is encountered at runtime, first an unfolder creates specializations of the associated recursive rule on-the-fly and then an interpreter applies these rules to the call. Our approach reduces the number of recursive rule applications to its logarithm at the expense of introducing a logarithmic number of generic unfolded rules. We prove correctness of our online optimization technique and determine its time complexity. For recursions which have enough simplifyable unfoldings, a super-linear is possible, i.e. speedup by more than a constant factor. The necessary simplification is problem-specific and has to be provided at compile-time. In our speedup analysis, we prove a sufficient condition as well as a sufficient and necessary condition for super-linear speedup relating the complexity of the recursive steps of the original rule and the unfolded rules. We have implemented an unfolder and meta-interpreter for runtime repeated recursion unfolding with just five rules in Constraint Handling Rules (CHR) embedded in Prolog. We illustrate the feasibility of our approach with simplifications, time complexity results and benchmarks for some basic tractable algorithms. The simplifications require some insight and were derived manually. The runtime improvement quickly reaches several orders of magnitude, consistent with the super-linear speedup predicted by our theorems.
Fruehwirth, Thom
October 31, 2025
Read article

The geodesic cover problem for butterfly networks

A geodesic cover, also known as an isometric path cover, of a graph is a set of geodesics which cover the vertex set of the graph. An edge geodesic cover of a graph is a set of geodesics which cover the edge set of the graph. The geodesic (edge) cover number of a graph is the cardinality of a minimum (edge) geodesic cover. The (edge) geodesic cover problem of a graph is to find the (edge) geodesic cover number of the graph. Surprisingly, only partial solutions for these problems are available for most situations. In this paper we demonstrate that the geodesic cover number of the $r$-dimensional butterfly is $\lceil (2/3)2^r\rceil$ and that its edge geodesic cover number is $2^r$.
Manuel, Paul
October 27, 2025
Read article
Informatics and Applied Mathematics
Social Sciences and Humanities

JDMDH

[Journal of Data Mining and Digital Humanities]

JDMDH

Journal of Data Mining and Digital Humanities

Created in 2014, the Journal of Data Mining and Digital Humanities (JDMDH) is situated at the intersection of data mining and digital humanities. The articles published concern both knowledge extraction and management (network analysis, information extraction, semantic web, preference analysis, machine learning) and the humanities and social sciences (historical, political, linguistic, sociological, geographical, communication and archiving) in the digital age.

  • Director of publication: Bruno Sportisse
  • Editors-in-chief: Richi Nayak ; Laurent Romary ; Nicolas Turenne
  • Medium: electronic
  • Frequency: continuous
  • Date created: 2014
  • Date of publication on Episciences: 2014
  • eISSN: 2416-5999
  • Subjects: social sciences and humanities, digital humanities, text mining
  • Languages of publication: English, French
  • Review process: single blind peer review
  • CC BY 4.0 licence
  • Publisher: Inria
    • Address: Domaine de Voluceau Rocquencourt – B.P. 105 78153 Le Chesnay Cedex
    • Country: France
  • Contact: jdmdh AT episciences.org
See website

Latest articles

Interpretable Socioeconomic Profiling: A Deep Dive Beyond Narrative Classification

This work presents an interpretable framework for socioeconomic status (SES) profiling based on narrative data. Building on our previous publication, “AI Assistant for Socioeconomic Empowerment Using Federated Learning” (NLP4DH 2025), this extended study explores a complementary system that focuses on thematic topic modeling, transformer-based embedding comparisons, and visualization tools. The framework analyzes student and public narratives to detect SES-related themes (e.g., financial hardship, resilience, access to resources) and assigns SES profiles through similarity-based scoring. By emphasizing interpretability and topic-based filtering, the system facilitates analysis of language patterns linked to different SES groups while supporting qualitative inspection. Results demonstrate the model’s ability to generalize across diverse domains and align with known social science frameworks, contributing toward responsible and transparent AI in education and public policy contexts.
Abdelgaber, Nahed
October 14, 2025
Read article

Stability and change in Icelandic corpora: The case of Stylistic Fronting

We use Icelandic corpora, the Icelandic Gigaword Corpus, the Icelandic Parsed Historical Corpus, and the Newspaper Corpus, in order to investigate the history of a syntactic construction, Stylistic Fronting (SF). SF has long been noted to be associated with formal style and it has received considerable attention in the theoretical syntax literature, but less has been said in the literature about its history throughout the centuries and modern times. We find that use of SF remained stable from the 12th century to the 20th century, but its rate declines in the (late) 20th and 21st century. Our analysis furthermore shows that use of SF is only significantly connected to genre in the most recent data, suggesting that the link between SF and style may be a relatively modern innovation. Finally, we test our data for the Constant Rate Effect, revealing that it is present for some grammatical contexts of SF. Our paper is a digital humanities study of historical linguistics which would not be possible without parsed corpora that together span all centuries involved in the change.
Ingason, Anton Karl
October 14, 2025
Read article
Informatics and Applied Mathematics

JIPS

[Journal d’Interaction Personne-Système]

JIPS

Journal d’Interaction Personne-Système

Created in 2008 by the Association francophone d’interaction humain-machine, the Journal d’Interaction Personne-Système (JIPS) succeeded the Revue d’Interaction Homme-Machine (RIHM), itself founded in 1997 and active until 2007 (then becoming the Revue des Interactions Humaines Médiatisées).

JIPS ceased publication in April 2022; published articles remain accessible on the journal’s website.

  • Director of publication: Sophie Dupuy-Chessa
  • Medium: electronic
  • Collection: 2010-2020
  • Date created: 2008
  • Date of publication on Episciences: 2014
  • eISSN: 2418-1838
  • Subjects: computer science, engineering, technology, cognitive science
  • Languages of publication: English, French
  • CC BY 4.0 licence
  • Publisher: Association Francophone d’Interaction Homme-Machine (AFIHM)
    • Address: 385 rue de la Bibliothèque, 38041 Grenoble Cedex
    • Country: France
  • Contact: presidence AT afihm.org
See website

Latest articles

Informatics and Applied Mathematics

JoDaKISS

[Journal of Data- and Knowledge-integrated Simulation Science]

JoDaKISS

Journal of Data- and Knowledge-integrated Simulation Science

Coming soon

Journal of Data- and Knowledge-integrated Simulation Science (JoDaKISS) is an international, multidisciplinary journal dedicated to supporting and advancing simulation science by publishing high-quality data and software for scientific computer simulations. It is published by the Stuttgart Center of Simulation Science (SC SimTech, University of Stuttgart, Germany).

  • Director of publication: Holger Steeb
  • Editorial Board: Bernd Flemisch, Dominik Göddeke, Jeroen Hanselman, Jan Heiland, Sibylle Hermann, Melanie Herschel, Timo Koch, Holger Steeb
  • Medium: electronic
  • Frequency: continuous
  • Date created: 2024
  • eISSN: 2944-7666
  • Subjects: Simulation Science, Data-Rich Experiments, Direct Numerical Simulations
  • Language of publication: English
  • Review process: single blind peer review
  • CC BY 4.0 licence
  • Publisher: Stuttgart Center of Simulation Science (SC SimTech)
    • Address: Pfaffenwaldring 5a, 70569 Stuttgart
    • Country: Germany
  • Contact: jodakiss AT episciences.org
See website
Informatics and Applied Mathematics

JSAT

[Journal on Satisfiability, Boolean Modelling and Computation]

JSAT

Journal on Satisfiability, Boolean Modelling and Computation

The scope of JSAT is propositional reasoning, modeling and computation. The Satisfiability discipline is a central focus of JSAT. We welcome all sorts of contributions to this theme but also encourage authors to submit papers on related topics as Computational Logic, Constraint Programming, Satisfiability Modulo Theories, Quantified Boolean Logic, Pseudo Boolean Methods, zero-one
Programming, Integer Programming and Operations Research, whenever the link to Satisfiability is apparent.

  • Director of publication: Armin Biere
  • Managing Editors: Marijn Heule
  • Medium: electronic
  • Frequency: continuous
  • Date created: 2006
  • Date of publication on Episciences: 2025
  • eISSN:
  • Subjects: Applications of SAT Encoding and reformulation Formal Verification Parallel solvers Proof Complexity Pseudo-Boolean Optimization, MaxSAT, MUS extraction and related problems Quantified Boolean Formulas, theoretical or practical aspects SAT, theoretical or practical aspects Satisfiability Modulo Theories, theoretical or practical aspects Solver or tool design
  • Language of publication: English
  • Review process: single blind peer review
  • CC BY 4.0 licence
  • Publisher: SAT Association
    • Address: Satisfiability: Application and Theory (SAT) e.V. Kornblumenweg 9 – 07745 Jena
    • Country: Germany
  • Contact: coming soon
See website
Informatics and Applied Mathematics

LMCS

[Logical Methods in Computer Science]

LMCS

Logical Methods in Computer Science

Logical Methods in Computer Science (LMCS) publishes research articles in English on theoretical and practical areas of computer science involving logical methods, taken in a broad sense. Established in 2014, the journal is edited by Logical Methods in Computer Science e.V., a non-profit organisation whose aim is to facilitate the dissemination of scientific results related to logic in computer science.

  • Director of publication: Lars Birkedal
  • Editor-in-chief: Stefan Milius
  • Medium: electronic
  • Frequency: continuous
  • Date created: 2014
  • Date of publication on Episciences: 2015
  • eISSN: 1860-5974
  • Subjects: computer science, logical methods
  • Languages of publication: English
  • Review process: single blind peer review
  • CC BY 4.0 licence
  • Publisher: Logical Methods in Computer Science e.V.
    • Country: Germany
  • Contact: lmcs AT episciences.org
See website

Latest articles

Interpretation of Inaccessible Sets in Martin-Löf Type Theory with One Mahlo Universe

Rathjen proved that Aczel's constructive set theory $\mathbf{CZF}$ extended with inaccessible sets of all transfinite orders can be interpreted in Martin-Löf type theory $\mathbf{MLTT}$ extended with Setzer's Mahlo universe and another universe above it. In this paper we show that this interpretation can be carried out bottom-up without the universe above the Mahlo universe, provided we add an accessibility predicate instead. If we work in Martin-Löf type theory with extensional identity types the accessibility predicate can be defined in terms of $\mathrm{W}$-types. The main part of our interpretation has been formalised in the proof assistant Agda.
Takahashi, Yuta
October 30, 2025
Read article

Range (Rényi) Entropy Queries and Partitioning

Data partitioning that maximizes/minimizes the Shannon entropy, or more generally the Rényi entropy is a crucial subroutine in data compression, columnar storage, and cardinality estimation algorithms. These partition algorithms can be accelerated if we have a data structure to compute the entropy in different subsets of data when the algorithm needs to decide what block to construct. Such a data structure will also be useful for data analysts exploring different subsets of data to identify areas of interest. While it is generally known how to compute the Shannon or the Rényi entropy of a discrete distribution in the offline or streaming setting efficiently, we focus on the query setting where we aim to efficiently derive the entropy among a subset of data that satisfy some linear predicates. We solve this problem in a typical setting when we deal with real data, where data items are geometric points and each requested area is a query (hyper)rectangle. More specifically, we consider a set $P$ of $n$ weighted and colored points in $\mathbb{R}^d$, where $d$ is a constant. For the range S-entropy (resp. R-entropy) query problem, the goal is to construct a low space data structure, such that given a query (hyper)rectangle $R$, it computes the Shannon (resp. Rényi) entropy based on the colors and the weights of the points in $P\cap R$, in sublinear time. We show conditional lower bounds proving that we cannot hope for data structures with near-linear space and near-constant query time for both the range S-entropy and R-entropy query problems. Then, we propose exact data structures for $d=1$ and $d>1$ with $o(n^{2d})$ space and $o(n)$ query time for both problems. Finally, we propose near linear space data structures for returning either an additive or a multiplicative approximation of the Shannon (resp. Rényi) entropy in $P\cap R$.
Esmailpour, Aryan
October 30, 2025
Read article
Informatics and Applied Mathematics

MNA

[Mathematical Neuroscience and Applications]

MNA

Mathematical Neuroscience and Applications

Established in 2021, the journal Mathematical Neuroscience and Applications (MNA) focuses on mathematical modelling and analysis in all areas of neuroscience, i.e. the study of the nervous system and its dysfunctions. It is a continuation of the Journal of Mathematical Neuroscience (2011-2021), previously published by Springer. The journal welcomes articles in English.

  • Director of publication: Bruno Sportisse
  • Editor-in-chief: Olivier Faugeras
  • Medium: electronic
  • Frequency: annual
  • Date created: 2021
  • Date of publication on Episciences: 2021
  • eISSN: 2801-0159
  • Subjects: mathematics, neuroscience
  • Languages of publication: English
  • Review process: single blind peer review
  • CC BY 4.0 licence
  • Publisher: Inria
    • Address: Domaine de Voluceau Rocquencourt – B.P. 105 78153 Le Chesnay Cedex
    • Country: France
  • Contact: mna AT episciences.org
See website

Latest articles

Ordinal Characterization of Similarity Judgments

Characterizing judgments of similarity within a perceptual or semantic domain, and making inferences about the underlying structure of this domain from these judgments, has an increasingly important role in cognitive and systems neuroscience. We present a new framework for this purpose that makes limited assumptions about how perceptual distances are converted into similarity judgments. The approach starts from a dataset of empirical judgments of relative similarities: the fraction of times that a subject chooses one of two comparison stimuli to be more similar to a reference stimulus. These empirical judgments provide Bayesian estimates of underling choice probabilities. From these estimates, we derive indices that characterize the set of judgments in three ways: compatibility with a symmetric dis-similarity, compatibility with an ultrametric space, and compatibility with an additive tree. Each of the indices is derived from rank-order relationships among the choice probabilities that, as we show, are necessary and sufficient for local consistency with the three respective characteristics. We illustrate this approach with simulations and example psychophysical datasets of dis-similarity judgments in several visual domains and provide code that implements the analyses at https://github.com/jvlab/simrank.
Victor, Jonathan D.
August 07, 2025
Read article

A Quasi-Stationary Approach to Metastability in a System of Spiking Neurons with Synaptic Plasticity

After reviewing the behavioral studies of working memory and of the cellular substrate of the latter, we argue that metastable states constitute candidates for the type of transient information storage required by working memory. We then present a simple neural network model made of stochastic units whose synapses exhibit short-term facilitation. The Markov process dynamics of this model was specifically designed to be analytically tractable, simple to simulate numerically and to exhibit a quasi-stationary distribution (QSD). Since the state space is finite this QSD is also a Yaglom limit, which allows us to bridge the gap between quasi-stationarity and metastability by considering the relative orders of magnitude of the relaxation and absorption times. We present first analytical results: characterization of the absorbing region of the Markov process, irreducibility outside this absorbing region and consequently existence and uniqueness of a QSD. We then apply Perron-Frobenius spectral analysis to obtain any specific QSD, and design an approximate method for the first moments of this QSD when the exact method is intractable. Finally we use these methods to study the relaxation time toward the QSD and establish numerically the memorylessness of the time of extinction.
André, Morgan
January 02, 2025
Read article
Informatics and Applied Mathematics

TheoretiCS

TheoretiCS

Established in 2021, TheoretiCS covers all areas of Theoretical Computer Science (TCS). A joint effort of the TCS community, the journal is published by the TheoretiCS Foundation, a non-profit organisation based in Germany. The journal publishes research papers in English on an ongoing basis, including revised and extended versions of conference papers.

  • Director of publication: Thomas Schwentick
  • Editors-in-chief: Anca Muscholl and Uri Zwick
  • Medium: electronic
  • Frequency: continuous
  • Date created: 2021
  • Date of publication on Episciences: 2021
  • eISSN: 2751-4838
  • Subjects: Theoretical Computer Science
  • Language of publication: English
  • Review process: single blind peer review
  • CC BY 4.0 licence
  • Publisher: TheoretiCS Foundation e.V.
    • Address: c/o Thomas Schwentick – Schillingstr. 23, D-44139 Dortmund
    • Country: Germany
  • Contact: theoretics AT episciences.org
See website

Latest articles

Directed Acyclic Outerplanar Graphs Have Constant Stack Number

The stack number of a directed acyclic graph $G$ is the minimum $k$ for which there is a topological ordering of $G$ and a $k$-coloring of the edges such that no two edges of the same color cross, i.e., have alternating endpoints along the topological ordering. We prove that the stack number of directed acyclic outerplanar graphs is bounded by a constant, which gives a positive answer to a conjecture by Heath, Pemmaraju and Trenk [SIAM J. Computing, 1999]. As an immediate consequence, this shows that all upward outerplanar graphs have constant stack number, answering a question by Bhore et al. [Eur. J. Comb., 2023] and thereby making significant progress towards the problem for general upward planar graphs originating from Nowakowski and Parker [Order, 1989]. As our main tool we develop the novel technique of directed $H$-partitions, which might be of independent interest. We complement the bounded stack number for directed acyclic outerplanar graphs by constructing a family of directed acyclic 2-trees that have unbounded stack number, thereby refuting a conjecture by Nöllenburg and Pupyrev [GD 2023].
Jungeblut, Paul
October 16, 2025
Read article

3SUM in Preprocessed Universes: Faster and Simpler

We revisit the 3SUM problem in the \emph{preprocessed universes} setting. We present an algorithm that, given three sets $A$, $B$, $C$ of $n$ integers, preprocesses them in quadratic time, so that given any subsets $A' \subseteq A$, $B' \subseteq B$, $C' \subseteq C$, it can decide if there exist $a \in A'$, $b \in B'$, $c \in C'$ with $a+b=c$ in time $O(n^{1.5} \log n)$. In contrast to both the first subquadratic $\tilde{O}(n^{13/7})$-time algorithm by Chan and Lewenstein (STOC 2015) and the current fastest $\tilde{O}(n^{11/6})$-time algorithm by Chan, Vassilevska Williams, and Xu (STOC 2023), which are based on the Balog--Szemerédi--Gowers theorem from additive combinatorics, our algorithm uses only standard 3SUM-related techniques, namely FFT and linear hashing modulo a prime. It is therefore not only faster but also simpler. Just as the two previous algorithms, ours not only decides if there is a single 3SUM solution but it actually determines for each $c \in C'$ if there is a solution containing it. We also modify the algorithm to still work in the scenario where the set $C$ is unknown at the time of preprocessing. Finally, even though the simplest version of our algorithm is randomized, we show how to make it deterministic losing only polylogarithmic factors in the running time.
Kasliwal, Shashwat
October 16, 2025
Read article
Informatics and Applied Mathematics

ToC

[Theory of Computing]

ToC

Theory of Computing

Theory of Computing (ToC) is a diamond open access journal dedicated to the widest dissemination, free of charge, of research papers in theoretical computer science.

  • Director of publication: László Babai
  • Managing Editors: Oded Regev, Alexander Russell
  • Medium: electronic
  • Frequency: continuous
  • Date created: 2004
  • Date of publication on Episciences: 2025
  • eISSN: 1557-2862
  • Subjects: Theoretical Computer Science
  • Language of publication: English
  • Review process: single blind peer review
  • CC BY 4.0 licence
  • Publisher: Theoretical Computer Science Exchange
    • University of Chicago, Dept of Computer Science, 1100 E 58th St
      #152, Chicago, IL, USA
    • Country : USA
  • Contact: coming soon
See website