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 ; Maurice Tchuenté ; Bruce Watson
  • 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

Les modèles LSAWfP non récursifs sont des workflows structurés

Les langages de workflow occupent une place importante dans la discipline du Business Process Management (BPM) : ils sont utilisés pour modéliser les processus opérationnels afin de faciliter leur gestion automatique à l'aide de systèmes BPM. Il existe de nombreux langages de workflow qui traitent de divers aspects (expressivité, analyse formelle, etc.). Au cours de la dernière décennie, certains langages de workflow basés sur des grammaires algébriques (ayant alors une sémantique formelle) et offrant de nouvelles perspectives à la modélisation des processus ont vu le jour : LSAWfP (a Language for the Specification of Administrative Workflow Processes) est l'un d'entre eux. LSAWfP présente de nombreux avantages par rapport aux langages existants, mais c'est son expressivité (qui a été très peu abordée dans les travaux antérieurs) qui est étudiée dans le présent document. En effet, les travaux présentés dans ce document visent à démontrer que tout modèle LSAWfP non récursif est un workflow structuré. Sachant que la majorité des systèmes BPM commerciaux ne gèrent que des workflows structurés, le résultat de cette étude montre que, bien que LSAWfP soit encore très théorique, il est un langage au potentiel économique certain.
Zekeng Ndadji, Milliam Maxime
July 05, 2023
Read article

Combiner Scrum et l'Architecture Dirigée par les modèles pour le développement d'un système de surveillance épidémiologique

Les systèmes de surveillance épidémiologiques évoluent avec le temps, en tenant compte du contexte et des données collectées. Ainsi, les logiciels utilisés doivent aussi évoluer pour pouvoir répondre aux besoins. Cependant, de nouvelles exigences des clients peuvent prendre du temps pour être implémentées, coûter plus cher (dans le cas où il faut recruter des programmeurs) et causer des problèmes comme le problème de régression logiciel. Ainsi, le logiciel peut devenir défaillant. Ceci est dû à un mauvais transfert des exigences des clients vers la mise en œuvre. Ce problème peut être évité si le système est développé en utilisant un framework et une architecture permettant le développement/la mise à jour rapide des logiciels de surveillance. La recherche empirique d'une part montre que l'Ingénierie Dirigée par les Modèles (par exemple, Architecture Dirigée par les Modèles ou Model-Driven Architecture - MDA) est plus efficace que les approches basées sur le code pour le développement et la maintenance de certains logiciels. D'autre part, les processus agiles tels que Scrum sont plus efficaces que les processus structurés lorsque les exigences sont sujettes aux changements fréquents. Il a été démontré que le développement des logiciels de santé comme les logiciels de surveillance épidémiologique en utilisant les processus structurés ou les approches de développement centrées sur le code n'est pas évident car ces logiciels sont sujettes aux changements fréquents. Dans ce travail, nous étudions la combinaison de Scrum avec MDA pour le développement du système de surveillance épidémiologique de la tuberculose. A son terme, nous avons trouvé la combinaison de Scrum et MDA simple, très utile lorsque l'outil sous-jacent peut générer tout le code source. La combinaison de Scrum et MDA a eu des effets positifs sur la productivité et la satisfaction des programmeurs et des clients. En plus, nous avons constaté que pour impliquer les non-informaticiens dans le développement ou la mise à jour, l'interface de modélisation doit être aussi simple que possible.
Azanzi, Jiomekong
July 04, 2023
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

Maker-Breaker domination game on trees when Staller wins

In the Maker-Breaker domination game played on a graph $G$, Dominator's goal is to select a dominating set and Staller's goal is to claim a closed neighborhood of some vertex. We study the cases when Staller can win the game. If Dominator (resp., Staller) starts the game, then $\gamma_{\rm SMB}(G)$ (resp., $\gamma_{\rm SMB}'(G)$) denotes the minimum number of moves Staller needs to win. For every positive integer $k$, trees $T$ with $\gamma_{\rm SMB}'(T)=k$ are characterized and a general upper bound on $\gamma_{\rm SMB}'$ is proved. Let $S = S(n_1,\dots, n_\ell)$ be the subdivided star obtained from the star with $\ell$ edges by subdividing its edges $n_1-1, \ldots, n_\ell-1$ times, respectively. Then $\gamma_{\rm SMB}'(S)$ is determined in all the cases except when $\ell\ge 4$ and each $n_i$ is even. The simplest formula is obtained when there are at least two odd $n_i$s. If $n_1$ and $n_2$ are the two smallest such numbers, then $\gamma_{\rm SMB}'(S(n_1,\dots, n_\ell))=\lceil \log_2(n_1+n_2+1)\rceil$. For caterpillars, exact formulas for $\gamma_{\rm SMB}$ and for $\gamma_{\rm SMB}'$ are established.
Bujtás, Csilla
September 06, 2023
Read article

Antisquares and Critical Exponents

The (bitwise) complement $\overline{x}$ of a binary word $x$ is obtained by changing each $0$ in $x$ to $1$ and vice versa. An $\textit{antisquare}$ is a nonempty word of the form $x\, \overline{x}$. In this paper, we study infinite binary words that do not contain arbitrarily large antisquares. For example, we show that the repetition threshold for the language of infinite binary words containing exactly two distinct antisquares is $(5+\sqrt{5})/2$. We also study repetition thresholds for related classes, where "two" in the previous sentence is replaced by a larger number. We say a binary word is $\textit{good}$ if the only antisquares it contains are $01$ and $10$. We characterize the minimal antisquares, that is, those words that are antisquares but all proper factors are good. We determine the growth rate of the number of good words of length $n$ and determine the repetition threshold between polynomial and exponential growth for the number of good words.
Baranwal, Aseem
September 06, 2023
Read article
Informatics and Applied Mathematics

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

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
March 21, 2023
Read 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
March 21, 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: Damian Niwiński
  • Medium: print and electronic
  • Frequency: 5-6 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

Diffuse and Localized Functional Dysconnectivity in Schizophrenia: a Bootstrapped Top-Down Approach

Schizophrenia (SZ) is a brain disorder leading to detached mind's normally integrated processes. Hence, the exploration of the symptoms in relation to functional connectivity (FC) had great relevance in the field. FC can be investigated on different levels, going from global features to single edges between regions, revealing diffuse and localized dysconnection patterns. In this context, SZ is characterized by a diverse global integration with reduced connectivity in specific areas of the Default Mode Network (DMN). However, the assessment of FC presents various sources of uncertainty. This study proposes a multi-level approach for more robust group-comparison. FC between 74 AAL brain areas of 15 healthy controls (HC) and 12 SZ subjects were used. Multi-level analyses and graph topological indexes evaluation were carried out by the previously published SPIDER-NET tool. Robustness was augmented by bootstrapped (BOOT) data and the stability was evaluated by removing one (RST1) or two subjects (RST2). The DMN subgraph was evaluated, toegether with overall local indexes and connection weights to enhance common activations/deactivations. At a global level, expected trends were found. The robustness assessment tests highlighted more stable results for BOOT compared to the direct data testing. Conversely, significant results were found in the analysis at lower levels. The DMN highlighted reduced connectivity and strength as well as increased deactivation in the SZ group. At local level, 13 areas were found to be significantly different ($p<0.05$), highlighting a greater divergence in the frontal lobe. These results were confirmed analyzing the negative edges, suggesting inverted connectivity between prefronto-temporal areas. In conclusion, multi-level analysis supported by BOOT is highly recommended, especially when diffuse and localized dysconnections must be investigated in limited samples.
Coluzzi, Davide
September 21, 2023
Read article

Error Correction for Discrete Tomography

Discrete tomography focuses on the reconstruction of functions $f: A \to \mathbb{R}$ from their line sums in a finite number $d$ of directions, where $A$ is a finite subset of $\mathbb{Z}^2$. Consequently, the techniques of discrete tomography often find application in areas where only a small number of projections are available. In 1978 M.B. Katz gave a necessary and sufficient condition for the uniqueness of the solution. Since then, several reconstruction methods have been introduced. Recently Pagani and Tijdeman developed a fast method to reconstruct $f$ if it is uniquely determined. Subsequently Ceko, Pagani and Tijdeman extended the method to the reconstruction of a function with the same line sums of $f$ in the general case. Up to here we assumed that the line sums are exact. In this paper we investigate the case where a small number of line sums are incorrect as may happen when discrete tomography is applied for data storage or transmission. We show how less than $d/2$ errors can be corrected and that this bound is the best possible.
Ceko, M.
September 21, 2023
Read article
Informatics and Applied Mathematics

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

The Effects of Political Martyrdom on Election Results: The Assassination of Abe

In developed nations assassinations are rare and thus the impact of such acts on the electoral and political landscape is understudied. In this paper, we focus on Twitter data to examine the effects of Japan's former Primer Minister Abe's assassination on the Japanese House of Councillors elections in 2022. We utilize sentiment analysis and emotion detection together with topic modeling on over 2 million tweets and compare them against tweets during previous election cycles. Our findings indicate that Twitter sentiments were negatively impacted by the event in the short term and that social media attention span has shortened. We also discuss how "necropolitics" affected the outcome of the elections in favor of the deceased's party meaning that there seems to have been an effect of Abe's death on the election outcome though the findings warrant further investigation for conclusive results.
Takagi, Miu Nicole
September 22, 2023
Read article

Interactive Analysis and Visualisation of Annotated Collocations in Spanish (AVAnCES)

Phraseology studies have been enhanced by Corpus Linguistics, which has become an interdisciplinary field where current technologies play an important role in its development. Computational tools have been implemented in the last decades with positive results on the identification of phrases in different languages. One specific technology that has impacted these studies is social media. As researchers, we have turned our attention to collecting data from these platforms, which comes with great advantages and its own challenges. One of the challenges is the way we design and build corpora relevant to the questions emerging in this type of language expression. This has been approached from different angles, but one that has given invaluable outputs is the building of linguistic corpora with the use of online web applications. In this paper, we take a multidimensional approach to the collection, design, and deployment of a phraseology corpus for Latin American Spanish from Twitter data, extracting features using NLP techniques, and presenting it in an interactive online web application. We expect to contribute to the methodologies used for Corpus Linguistics in the current technological age. Finally, we make this tool publicly available to be used by any researcher interested in the data itself and also on the technological tools developed here.
Gonzalez, Simon
September 22, 2023
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: 2008
  • 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

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

Answer Counting under Guarded TGDs

We study the complexity of answer counting for ontology-mediated queries and for querying under constraints, considering conjunctive queries and unions thereof (UCQs) as the query language and guarded TGDs as the ontology and constraint language, respectively. Our main result is a classification according to whether answer counting is fixed-parameter tractable (FPT), W[1]-equivalent, #W[1]-equivalent, #W[2]-hard, or #A[2]-equivalent, lifting a recent classification for UCQs without ontologies and constraints due to Dell et al. The classification pertains to various structural measures, namely treewidth, contract treewidth, starsize, and linked matching number. Our results rest on the assumption that the arity of relation symbols is bounded by a constant and, in the case of ontology-mediated querying, that all symbols from the ontology and query can occur in the data (so-called full data schema). We also study the meta-problems for the mentioned structural measures, that is, to decide whether a given ontology-mediated query or constraint-query specification is equivalent to one for which the structural measure is bounded.
Feier, Cristina
September 14, 2023
Read article

Arboreal Categories: An Axiomatic Theory of Resources

Game comonads provide a categorical syntax-free approach to finite model theory, and their Eilenberg-Moore coalgebras typically encode important combinatorial parameters of structures. In this paper, we develop a framework whereby the essential properties of these categories of coalgebras are captured in a purely axiomatic fashion. To this end, we introduce arboreal categories, which have an intrinsic process structure, allowing dynamic notions such as bisimulation and back-and-forth games, and resource notions such as number of rounds of a game, to be defined. These are related to extensional or "static" structures via arboreal covers, which are resource-indexed comonadic adjunctions. These ideas are developed in a general, axiomatic setting, and applied to relational structures, where the comonadic constructions for pebbling, Ehrenfeucht-Fra\"iss\'e and modal bisimulation games recently introduced by Abramsky et al. are recovered, showing that many of the fundamental notions of finite model theory and descriptive complexity arise from instances of arboreal covers.
Abramsky, Samson
August 10, 2023
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

Propagation of chaos in mean field networks of FitzHugh-Nagumo neurons

In this article, we are interested in the behavior of a fully connected network of $N$ neurons, where $N$ tends to infinity. We assume that the neurons follow the stochastic FitzHugh-Nagumo model, whose specificity is the non-linearity with a cubic term. We prove a result of uniform in time propagation of chaos of this model in a mean-field framework. We also exhibit explicit bounds. We use a coupling method initially suggested by A. Eberle (arXiv:1305.1233), and recently extended in (1805.11387), known as the reflection coupling. We simultaneously construct a solution of the $N$-particle system and $N$ independent copies of the non-linear McKean-Vlasov limit in such a way that, considering an appropriate semi-metric that takes into account the various possible behaviors of the processes, the two solutions tend to get closer together as $N$ increases, uniformly in time. The reflection coupling allows us to deal with the non-convexity of the underlying potential in the dynamics of the quantities defining our network, and show independence at the limit for the system in mean field interaction with sufficiently small Lipschitz continuous interactions.
Colombani, Laetitia
June 19, 2023
Read article

Gabor frames from contact geometry in models of the primary visual cortex

We analyze the interplay between contact geometry and Gabor filters signal analysis in geometric models of the primary visual cortex. We show in particular that a specific framed lattice and an associated Gabor system is determined by the Legendrian circle bundle structure of the $3$-manifold of contact elements on a surface (which models the V1-cortex), together with the presence of an almost-complex structure on the tangent bundle of the surface (which models the retinal surface). We identify a scaling of the lattice, also dictated by the manifold geometry, that ensures the frame condition is satisfied. We then consider a $5$-dimensional model where receptor profiles also involve a dependence on frequency and scale variables, in addition to the dependence on position and orientation. In this case we show that a proposed profile window function does not give rise to frames (even in a distributional sense), while a natural modification of the same generates Gabor frames with respect to the appropriate lattice determined by the contact geometry.
Liontou, Vasiliki
June 06, 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

Brooks' Theorem in Graph Streams: A Single-Pass Semi-Streaming Algorithm for $\Delta$-Coloring

Every graph with maximum degree $\Delta$ can be colored with $(\Delta+1)$ colors using a simple greedy algorithm. Remarkably, recent work has shown that one can find such a coloring even in the semi-streaming model. But, in reality, one almost never needs $(\Delta+1)$ colors to properly color a graph. Indeed, the celebrated \Brooks' theorem states that every (connected) graph beside cliques and odd cycles can be colored with $\Delta$ colors. Can we find a $\Delta$-coloring in the semi-streaming model as well? We settle this key question in the affirmative by designing a randomized semi-streaming algorithm that given any graph, with high probability, either correctly declares that the graph is not $\Delta$-colorable or outputs a $\Delta$-coloring of the graph. The proof of this result starts with a detour. We first (provably) identify the extent to which the previous approaches for streaming coloring fail for $\Delta$-coloring: for instance, all these approaches can handle streams with repeated edges and they can run in $o(n^2)$ time -- we prove that neither of these tasks is possible for $\Delta$-coloring. These impossibility results however pinpoint exactly what is missing from prior approaches when it comes to $\Delta$-coloring. We then build on these insights to design a semi-streaming algorithm that uses $(i)$ a novel sparse-recovery approach based on sparse-dense decompositions to (partially) recover the "problematic" subgraphs of the input -- the ones that form the basis of our impossibility results -- and $(ii)$ a new coloring approach for these subgraphs that allows for recoloring of other vertices in a controlled way without relying on local explorations or finding "augmenting paths" that are generally impossible for semi-streaming algorithms. We believe both these techniques can be of independent interest.
Assadi, Sepehr
August 25, 2023
Read article

Boosting Simple Learners

Boosting is a celebrated machine learning approach which is based on the idea of combining weak and moderately inaccurate hypotheses to a strong and accurate one. We study boosting under the assumption that the weak hypotheses belong to a class of bounded capacity. This assumption is inspired by the common convention that weak hypotheses are "rules-of-thumbs" from an "easy-to-learn class". (Schapire and Freund~'12, Shalev-Shwartz and Ben-David '14.) Formally, we assume the class of weak hypotheses has a bounded VC dimension. We focus on two main questions: (i) Oracle Complexity: How many weak hypotheses are needed to produce an accurate hypothesis? We design a novel boosting algorithm and demonstrate that it circumvents a classical lower bound by Freund and Schapire ('95, '12). Whereas the lower bound shows that $\Omega({1}/{\gamma^2})$ weak hypotheses with $\gamma$-margin are sometimes necessary, our new method requires only $\tilde{O}({1}/{\gamma})$ weak hypothesis, provided that they belong to a class of bounded VC dimension. Unlike previous boosting algorithms which aggregate the weak hypotheses by majority votes, the new boosting algorithm uses more complex ("deeper") aggregation rules. We complement this result by showing that complex aggregation rules are in fact necessary to circumvent the aforementioned lower bound. (ii) Expressivity: Which tasks can be learned by boosting weak hypotheses from a bounded VC class? Can complex concepts that are "far away" from the class be learned? Towards answering the first question we {introduce combinatorial-geometric parameters which capture expressivity in boosting.} As a corollary we provide an affirmative answer to the second question for well-studied classes, including half-spaces and decision stumps. Along the way, we establish and exploit connections with Discrepancy Theory.
Alon, Noga
June 19, 2023
Read article