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

Deux Schémas de Stéganographie Textuelles basés sur le codage des couleurs.

La stéganographie textuelle est un mécanisme permettant de cacher un message secret dans un texte. Dans ce papier, nous proposons un schéma stéganographique basé sur le codage de couleurs. Ce schéma comprend deux méthodes différentes : la première, basée sur les permutations et la seconde, basée sur les systèmes de numération. Etant donné un message secret et un texte de couverture, les méthodes proposées cachent le message secret dans le texte de couverture en le coloriant. Le stégo-texte est ensuite envoyé au destinataire par mail. Après expérimentations, les résultats obtenus montrent que nos modèles proposent un meilleure capacité d'embarquement par rapport au schéma d'Aruna Malik et al. sur laquelle repose notre idée.
Karnel Sadie, Juvet
October 28, 2024
Read article

Application du modèle de représentation acoustique multilingue XLSR pour la transcription de l'Ewondo

Les modèles auto-supervisés récemment popularisés apparaissent comme une solution au problème de la faible disponibilité des données grâce à un transfert d'apprentissage parcimonieux. Nous étudions l'efficacité de ces modèles acoustiques multilingues, en l'occurrence wav2vec 2.0 XLSR-53 et wav2vec 2.0 XLSR-128, pour la tâche de transcription de la langue Ewondo (parlée au Cameroun). Les expériences ont été menées sur 11 minutes de discours construits à partir de 103 phrases lues. Malgré une forte capacité de généralisation du modèle acoustique multilingue, les résultats préliminaires montrent que la distance entre les langues intégrées dans le XLSR (anglais, français, espagnol, allemand, mandarin, . . .) et l'ewondo a un impact important sur la performance du modèle de transcription. Les performances les plus élevées obtenues sont de l'ordre de 69% pour le WER et de 28.1% pour le CER. Une analyse de ces résultats préliminaires est effectuée et interprétée afin de proposer des pistes d'amélioration efficaces.
Yannick Yomie, Nzeuhang
October 28, 2024
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

Homotopy Theoretic and Categorical Models of Neural Information Networks

In this paper we develop a novel mathematical formalism for the modeling of neural information networks endowed with additional structure in the form of assignments of resources, either computational or metabolic or informational. The starting point for this construction is the notion of summing functors and of Segal's Gamma-spaces in homotopy theory. The main results in this paper include functorial assignments of concurrent/distributed computing architectures and associated binary codes to networks and their subsystems, a categorical form of the Hopfield network dynamics, which recovers the usual Hopfield equations when applied to a suitable category of weighted codes, a functorial assignment to networks of corresponding information structures and information cohomology, and a cohomological version of integrated information.
Manin, Yuri
September 06, 2024
Read article

A Framework for Universality in Physics, Computer Science, and Beyond

Turing machines and spin models share a notion of universality according to which some simulate all others. Is there a theory of universality that captures this notion? We set up a categorical framework for universality which includes as instances universal Turing machines, universal spin models, NP completeness, top of a preorder, denseness of a subset, and more. By identifying necessary conditions for universality, we show that universal spin models cannot be finite. We also characterize when universality can be distinguished from a trivial one and use it to show that universal Turing machines are non-trivial in this sense. Our framework allows not only to compare universalities within each instance, but also instances themselves. We leverage a Fixed Point Theorem inspired by a result of Lawvere to establish that universality and negation give rise to unreachability (such as uncomputability). As such, this work sets the basis for a unified approach to universality and invites the study of further examples within the framework.
Gonda, Tomáš
August 29, 2024
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

Spanning trees for many different numbers of leaves

Let $G$ be a connected graph and $L(G)$ the set of all integers $k$ such that $G$ contains a spanning tree with exactly $k$ leaves. We show that for a connected graph $G$, the set $L(G)$ is contiguous. It follows from work of Chen, Ren, and Shan that every connected and locally connected $n$-vertex graph -- this includes triangulations -- has a spanning tree with at least $n/2 + 1$ leaves, so by a classic theorem of Whitney and our result, in any plane $4$-connected $n$-vertex triangulation one can find for any integer $k$ which is at least $2$ and at most $n/2 + 1$ a spanning tree with exactly $k$ leaves (and each of these trees can be constructed in polynomial time). We also prove that there exist infinitely many $n$ such that there is a plane $4$-connected $n$-vertex triangulation containing a spanning tree with $2n/3$ leaves, but no spanning tree with more than $2n/3$ leaves.
Noguchi, Kenta
November 18, 2024
Read article

Recognition of chordal graphs and cographs which are Cover-Incomparability graphs

Cover-Incomparability graphs (C-I graphs) are an interesting class of graphs from posets. A C-I graph is a graph from a poset $P=(V,\le)$ with vertex set $V$, and the edge-set is the union of edge sets of the cover graph and the incomparability graph of the poset. The recognition of the C-I graphs is known to be NP-complete (Maxov\'{a} et al., Order 26(3), 229--236(2009)). In this paper, we prove that chordal graphs having at most two independent simplicial vertices are exactly the chordal graphs which are also C-I graphs. A similar result is obtained for cographs as well. Using the structural results of these graphs, we derive linear time recognition algorithms for chordal graphs and cographs which are C-I graphs.
Anil, Arun
November 15, 2024
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

Profinite lambda-terms and parametricity

Combining ideas coming from Stone duality and Reynolds parametricity, we formulate in a clean and principled way a notion of profinite lambda-term which, we show, generalizes at every type the traditional notion of profinite word coming from automata theory. We start by defining the Stone space of profinite lambda-terms as a projective limit of finite sets of usual lambda-terms, considered modulo a notion of equivalence based on the finite standard model. One main contribution of the paper is to establish that, somewhat surprisingly, the resulting notion of profinite lambda-term coming from Stone duality lives in perfect harmony with the principles of Reynolds parametricity. In addition, we show that the notion of profinite lambda-term is compositional by constructing a cartesian closed category of profinite lambda-terms, and we establish that the embedding from lambda-terms modulo beta-eta-conversion to profinite lambda-terms is faithful using Statman's finite completeness theorem. Finally, we prove that the traditional Church encoding of finite words into lambda-terms can be extended to profinite words, and leads to a homeomorphism between the space of profinite words and the space of profinite lambda-terms of the corresponding Church type.
van Gool, Sam
November 23, 2023
Read article

Dependent Type Refinements for Futures

Type refinements combine the compositionality of typechecking with the expressivity of program logics, offering a synergistic approach to program verification. In this paper we apply dependent type refinements to SAX, a futures-based process calculus that arises from the Curry-Howard interpretation of the intuitionistic semi-axiomatic sequent calculus and includes unrestricted recursion both at the level of types and processes. With our type refinement system, we can reason about the partial correctness of SAX programs, complementing prior work on sized type refinements that supports reasoning about termination. Our design regime synthesizes the infinitary proof theory of SAX with that of bidirectional typing and Hoare logic, deriving some standard reasoning principles for data and (co)recursion while enabling information hiding for codata. We prove syntactic type soundness, which entails a notion of partial correctness that respects codata encapsulation. We illustrate our language through a few simple examples.
Somayyajula, Siva
November 23, 2023
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: print and 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

Proving Confluence in the Confluence Framework with CONFident

This article describes the *Confluence Framework*, a novel framework for proving and disproving confluence using a divide-and-conquer modular strategy, and its implementation in CONFident. Using this approach, we are able to automatically prove and disprove confluence of *Generalized Term Rewriting Systems*, where (i) only selected arguments of function symbols can be rewritten and (ii) a rather general class of conditional rules can be used. This includes, as particular cases, several variants of rewrite systems such as (context-sensitive) *term rewriting systems*, *string rewriting systems*, and (context-sensitive) *conditional term rewriting systems*. The divide-and-conquer modular strategy allows us to combine in a proof tree different techniques for proving confluence, including modular decompositions, checking joinability of (conditional) critical and variable pairs, transformations, etc., and auxiliary tasks required by them, e.g., joinability of terms, joinability of conditional pairs, etc.
Gutiérrez, Raúl
November 10, 2024
Read article

On Complexity Bounds and Confluence of Parallel Term Rewriting

We revisit parallel-innermost term rewriting as a model of parallel computation on inductive data structures and provide a corresponding notion of runtime complexity parametric in the size of the start term. We propose automatic techniques to derive both upper and lower bounds on parallel complexity of rewriting that enable a direct reuse of existing techniques for sequential complexity. Our approach to find lower bounds requires confluence of the parallel-innermost rewrite relation, thus we also provide effective sufficient criteria for proving confluence. The applicability and the precision of the method are demonstrated by the relatively light effort in extending the program analysis tool AProVE and by experiments on numerous benchmarks from the literature.
Baudon, Thaïs
November 10, 2024
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

Reliable Part-of-Speech Tagging of Historical Corpora through Set-Valued Prediction

Syntactic annotation of corpora in the form of part-of-speech (POS) tags is a key requirement for both linguistic research and subsequent automated natural language processing (NLP) tasks. This problem is commonly tackled using machine learning methods, i.e., by training a POS tagger on a sufficiently large corpus of labeled data. While the problem of POS tagging can essentially be considered as solved for modern languages, historical corpora turn out to be much more difficult, especially due to the lack of native speakers and sparsity of training data. Moreover, most texts have no sentences as we know them today, nor a common orthography. These irregularities render the task of automated POS tagging more difficult and error-prone. Under these circumstances, instead of forcing the POS tagger to predict and commit to a single tag, it should be enabled to express its uncertainty. In this paper, we consider POS tagging within the framework of set-valued prediction, which allows the POS tagger to express its uncertainty via predicting a set of candidate POS tags instead of guessing a single one. The goal is to guarantee a high confidence that the correct POS tag is included while keeping the number of candidates small. In our experimental study, we find that extending state-of-the-art POS taggers to set-valued prediction yields more precise and robust taggings, especially for unknown words, i.e., words not occurring in the training data.
Heid, Stefan
October 21, 2024
Read article

Temporal Sequencing of Documents

We outline an unsupervised method for temporal rank ordering of sets of historical documents, namely American State of the Union Addresses and DEEDS, a corpus of medieval English property transfer documents. Our method relies upon effectively capturing the gradual change in word usage via a bandwidth estimate for the non-parametric Generalized Linear Models (Fan, Heckman, and Wand, 1995). The number of possible rank orders needed to search through for cost functions related to the bandwidth can be quite large, even for a small set of documents. We tackle this problem of combinatorial optimization using the Simulated Annealing algorithm, which allows us to obtain the optimal document temporal orders. Our rank ordering method significantly improved the temporal sequencing of both corpora compared to a randomly sequenced baseline. This unsupervised approach should enable the temporal ordering of undated document sets.
Gervers, Michael
September 24, 2024
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

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
February 08, 2021
Read 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
January 22, 2021
Read article
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
  • 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

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

Refl-Spanners: A Purely Regular Approach to Non-Regular Core Spanners

The regular spanners (characterised by vset-automata) are closed under the algebraic operations of union, join and projection, and have desirable algorithmic properties. The core spanners (introduced by Fagin, Kimelfeld, Reiss, and Vansummeren (PODS 2013, JACM 2015) as a formalisation of the core functionality of the query language AQL used in IBM's SystemT) additionally need string-equality selections and it has been shown by Freydenberger and Holldack (ICDT 2016, Theory of Computing Systems 2018) that this leads to high complexity and even undecidability of the typical problems in static analysis and query evaluation. We propose an alternative approach to core spanners: by incorporating the string-equality selections directly into the regular language that represents the underlying regular spanner (instead of treating it as an algebraic operation on the table extracted by the regular spanner), we obtain a fragment of core spanners that, while having slightly weaker expressive power than the full class of core spanners, arguably still covers the intuitive applications of string-equality selections for information extraction and has much better upper complexity bounds of the typical problems in static analysis and query evaluation.
Schmid, Markus L.
November 20, 2024
Read article

Reasonable Space for the ${\lambda}$-Calculus, Logarithmically

Can the $\lambda$-calculus be considered a reasonable computational model? Can we use it for measuring the time $\textit{and}$ space consumption of algorithms? While the literature contains positive answers about time, much less is known about space. This paper presents a new reasonable space cost model for the $\lambda$-calculus, based on a variant over the Krivine abstract machine. For the first time, this cost model is able to accommodate logarithmic space. Moreover, we study the time behavior of our machine and show how to transport our results to the call-by-value $\lambda$-calculus.
Accattoli, Beniamino
November 19, 2024
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

A mean-field model of Integrate-and-Fire neurons: non-linear stability of the stationary solutions

We investigate a stochastic network composed of Integrate-and-Fire spiking neurons, focusing on its mean-field asymptotics. We consider an invariant probability measure of the McKean-Vlasov equation and establish an explicit sufficient condition to ensure the local stability of this invariant distribution. Furthermore, we prove a conjecture proposed initially by J. Touboul and P. Robert regarding the bistable nature of a specific instance of this neuronal model.
Cormier, Quentin
September 27, 2024
Read article

Neural Coding as a Statistical Testing Problem

We take the testing perspective to understand what the minimal discrimination time between two stimuli is for different types of rate coding neurons. Our main goal is to describe the testing abilities of two different encoding systems: place cells and grid cells. In particular, we show, through the notion of adaptation, that a fixed place cell system can have a minimum discrimination time that decreases when the stimuli are further away. This could be a considerable advantage for the place cell system that could complement the grid cell system, which is able to discriminate stimuli that are much closer than place cells.
Ost, Guilherme
December 29, 2023
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: Javier Esparza ; 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

On complete classes of valuated matroids

We characterize a rich class of valuated matroids, called R-minor valuated matroids that includes the indicator functions of matroids, and is closed under operations such as taking minors, duality, and induction by network. We exhibit a family of valuated matroids that are not R-minor based on sparse paving matroids. Valuated matroids are inherently related to gross substitute valuations in mathematical economics. By the same token we refute the Matroid Based Valuation Conjecture by Ostrovsky and Paes Leme (Theoretical Economics 2015) asserting that every gross substitute valuation arises from weighted matroid rank functions by repeated applications of merge and endowment operations. Our result also has implications in the context of Lorentzian polynomials: it reveals the limitations of known construction operations.
Husić, Edin
November 18, 2024
Read article

Optimal Algorithm for the Planar Two-Center Problem

We study a fundamental problem in Computational Geometry, the planar two-center problem. In this problem, the input is a set $S$ of $n$ points in the plane and the goal is to find two smallest congruent disks whose union contains all points of $S$. A longstanding open problem has been to obtain an $O(n\log n)$-time algorithm for planar two-center, matching the $\Omega(n\log n)$ lower bound given by Eppstein [SODA'97]. Towards this, researchers have made a lot of efforts over decades. The previous best algorithm, given by Wang [SoCG'20], solves the problem in $O(n\log^2 n)$ time. In this paper, we present an $O(n\log n)$-time (deterministic) algorithm for planar two-center, which completely resolves this open problem.
Cho, Kyungjin
November 05, 2024
Read article