Search

Contemporary literature on the dynamics of economic activities in growing cities mainly focused on a few years or decades time frames. Using a new geo-historical database constructed from historical directories with about 1 million entries, we present a comprehensive analysis of the dynamics of activities in a major city, Paris, over almost a century (1829-1907). Our analysis suggests that activities that accompany city growth can be classified in different categories according to their dynamics and their scaling with population: (i) linear for everyday needs of residents (food stores, clothing retailers, health care practitioners), (ii) sublinear for public services (legal, administrative, educational), (iii) superlinear for the city's specific features (passing fads, specialization, timely needs). The dynamics of these activities is in addition very sensitive to historical perturbations such as large scale public works or political conflicts. These results shed light on the evolution of activities, a crucial component of growing cities., Comment: 11 pages, 3 figures

This paper summarizes the experiments and results of the HYBRINFOX team for the CheckThat! 2024 - Task 1 competition. We propose an approach enriching Language Models such as RoBERTa with embeddings produced by triples (subject ; predicate ; object) extracted from the text sentences. Our analysis of the developmental data shows that this method improves the performance of Language Models alone. On the evaluation data, its best performance was in English, where it achieved an F1 score of 71.1 and ranked 12th out of 27 candidates. On the other languages (Dutch and Arabic), it obtained more mixed results. Future research tracks are identified toward adapting this processing pipeline to more recent Large Language Models., Comment: Paper to appear in the Proceedings of the Conference and Labs of the Evaluation Forum (CLEF 2024 CheckThat!)

This paper presents the HYBRINFOX method used to solve Task 2 of Subjectivity detection of the CLEF 2024 CheckThat! competition. The specificity of the method is to use a hybrid system, combining a RoBERTa model, fine-tuned for subjectivity detection, a frozen sentence-BERT (sBERT) model to capture semantics, and several scores calculated by the English version of the expert system VAGO, developed independently of this task to measure vagueness and subjectivity in texts based on the lexicon. In English, the HYBRINFOX method ranked 1st with a macro F1 score of 0.7442 on the evaluation data. For the other languages, the method used a translation step into English, producing more mixed results (ranking 1st in Multilingual and 2nd in Italian over the baseline, but under the baseline in Bulgarian, German, and Arabic). We explain the principles of our hybrid approach, and outline ways in which the method could be improved for other languages besides English., Comment: To appear in the Proceedings of the Conference and Labs of the Evaluation Forum (CLEF 2024 CheckThat!)

This paper investigates the language of propaganda and its stylistic features. It presents the PPN dataset, standing for Propagandist Pseudo-News, a multisource, multilingual, multimodal dataset composed of news articles extracted from websites identified as propaganda sources by expert agencies. A limited sample from this set was randomly mixed with papers from the regular French press, and their URL masked, to conduct an annotation-experiment by humans, using 11 distinct labels. The results show that human annotators were able to reliably discriminate between the two types of press across each of the labels. We propose different NLP techniques to identify the cues used by the annotators, and to compare them with machine classification. They include the analyzer VAGO to measure discourse vagueness and subjectivity, a TF-IDF to serve as a baseline, and four different classifiers: two RoBERTa-based models, CATS using syntax, and one XGBoost combining syntactic and semantic features., Comment: Paper to appear in the EACL 2024 Proceedings of the Third Workshop on Understanding Implicit and Underspecified Language (UnImplicit 2024)

In recent years, large Transformer-based Pre-trained Language Models (PLM) have changed the Natural Language Processing (NLP) landscape, by pushing the performance boundaries of the state-of-the-art on a wide variety of tasks. However, this performance gain goes along with an increase in complexity, and as a result, the size of such models (up to billions of parameters) represents a constraint for their deployment on embedded devices or short-inference time tasks. To cope with this situation, compressed models emerged (e.g. DistilBERT), democratizing their usage in a growing number of applications that impact our daily lives. A crucial issue is the fairness of the predictions made by both PLMs and their distilled counterparts. In this paper, we propose an empirical exploration of this problem by formalizing two questions: (1) Can we identify the neural mechanism(s) responsible for gender bias in BERT (and by extension DistilBERT)? (2) Does distillation tend to accentuate or mitigate gender bias (e.g. is DistilBERT more prone to gender bias than its uncompressed version, BERT)? Our findings are the following: (I) one cannot identify a specific layer that produces bias; (II) every attention head uniformly encodes bias; except in the context of underrepresented classes with a high imbalance of the sensitive attribute; (III) this subset of heads is different as we re-fine tune the network; (IV) bias is more homogeneously produced by the heads in the distilled model.

Group fairness is a central research topic in text classification, where reaching fair treatment between sensitive groups (e.g. women vs. men) remains an open challenge. This paper presents a novel method for mitigating biases in neural text classification, agnostic to the model architecture. Considering the difficulty to distinguish fair from unfair information in a text encoder, we take inspiration from adversarial training to induce Wasserstein independence between representations learned to predict our target label and the ones learned to predict some sensitive attribute. Our approach provides two significant advantages. Firstly, it does not require annotations of sensitive attributes in both testing and training data. This is more suitable for real-life scenarios compared to existing methods that require annotations of sensitive attributes at train time. Second, our approach exhibits a comparable or better fairness-accuracy trade-off compared to existing methods.

This paper extends the work started in 2002 by Demaine, Demaine and Verill (DDV) on coin-moving puzzles. These puzzles have a long history in the recreational literature, but were first systematically analyzed by DDV, who gave a full characterization of the solvable puzzles on the triangular grid and a partial characterization of the solvable puzzles on the square grid. This article specifically extends the study of the game on the square grid. Notably, DDV's result on puzzles with two "extra coins" is shown to be overly broad: this paper provides counterexamples as well as a revised version of this theorem. A new method for solving puzzles with two extra coins is then presented, which covers some cases where the aforementioned theorem does not apply. Puzzles with just one extra coin seem even more complicated, and are only touched upon by DDV. This paper delves deeper, studying a class of such puzzles that may be considered equivalent to a game of "poking" coins. Within this class, some cases are considered that are amenable to analysis.

We define a $q$-linear path in a hypergraph $H$ as a sequence $(e_1,\ldots,e_L)$ of edges of $H$ such that $|e_i \cap e_{i+1}| \in [\![1,q]\!]$ and $e_i \cap e_j=\varnothing$ if $|i-j|>1$. In this paper, we study the connected components associated to these paths when $q=k-2$ where $k$ is the rank of $H$. If $k=3$ then $q=1$ which coincides with the well-known notion of linear path or loose path. We describe the structure of the connected components, using an algorithmic proof which shows that the connected components can be computed in polynomial time. We then mention two consequences of our algorithmic result. The first one is that deciding the winner of the Maker-Breaker game on a hypergraph of rank 3 can be done in polynomial time. The second one is that tractable cases for the NP-complete problem of "Paths Avoiding Forbidden Pairs" in a graph can be deduced from the recognition of a special type of line graph of a hypergraph.

The effect of toroidal rotation on both turbulent and neoclassical transport of tungsten (W) in tokamaks is investigated using the flux-driven, global, nonlinear 5D gyrokinetic code GYSELA. Nonlinear simulations are carried out with different levels of momentum injection that drive W to the supersonic regime, while the toroidal velocity of the main ions remains in the subsonic regime. The numerical simulations demonstrate that toroidal rotation induces centrifugal forces that cause W to accumulate in the outboard region, generating an in-out poloidal asymmetry. This asymmetry enhances neoclassical inward convection, which can lead to central accumulation of W in cases of strong plasma rotation. The core accumulation of W is mainly driven by inward neoclassical convection. However, as momentum injection continues, roto-diffusion, proportional to the radial gradient of the toroidal velocity, becomes significant and generate outward turbulent flux in the case of ion temperature gradient (ITG) turbulence. Overall, the numerical results from nonlinear GYSELA simulations are in qualitative agreement with the theoretical predictions for impurity transport, as well as experimental observations., Comment: 26 pages, 10 figures, to be published

Trapped ion modes (TIM) belong to the family of ion temperature gradient (ITG) modes, which are one of the important ingredients in heat turbulent transport at the ion scale in tokamak plasmas. It is essential to properly estimate their linear growth rate to understand their influence on ion-scale turbulent transport. A global linear analysis of a reduced gyro-bounce kinetic model for trapped particle modes is performed, and a spectral method is proposed to solve the dispersion relation. Importantly, the radial profile of the particle drift velocity is taken into account in the linear analysis by considering the magnetic flux {\psi} dependency of the equilibrium Hamiltonian H_{eq}({\psi}) in the quasi-neutrality equation and equilibrium gyro-bounce averaged distribution function F_{eq} . Using this spectral method, linear growth-rates of TIM instability in presence of different temperature profiles and precession frequencies of trapped ions, with an approximated constant Hamiltonian and the exact {\psi} dependent equilibrium Hamiltonian, are investigated. The growth-rate depends on the logarithmic gradient of temperature \kappa_{T} , density \kappa_{n} and equilibrium Hamiltonian \kappa_{\Lambda} . With the exact {\psi} dependent Hamiltonian, the growth rates and potential profiles are modified significantly, compared to the cases with approximated constant Hamiltonian. All the results from the global linear analysis agree with a semi-Lagrangian based linear Vlasov solver with a good accuracy. This spectral method is very fast and requires very less computation resources compared to a linear version of Vlasov-solver based on a semi-Lagrangian scheme.

In the Maker-Breaker positional game, Maker and Breaker take turns picking vertices of a hypergraph $H$, and Maker wins if and only if he claims all the vertices of some edge of $H$. This paper provides a general framework to study Maker-Breaker games, centered on the notion of danger at a vertex $x$, which is a subhypergraph representing an urgent threat that Breaker must hit with his next pick if Maker picks $x$. We then apply this concept in hypergraphs of rank 3, providing a structural characterization of the winner with perfect play as well as optimal strategies for both players based on danger intersections. We construct a family $\mathcal{F}$ of dangers such that a hypergraph $H$ of rank 3 is a Breaker win if and only if the $\mathcal{F}$-dangers at $x$ in $H$ intersect for all $x$. By construction of $\mathcal{F}$, this will mean that $H$ is a Maker win if and only if Maker can guarantee the appearance, within the first three rounds of play, of a very specific elementary subhypergraph (on which Maker easily wins). This last result has a consequence on the algorithmic complexity of deciding which player has a winning strategy on a given hypergraph: this problem, which is known to be PSPACE-complete on 6-uniform hypergraphs, is in polynomial time on hypergraphs of rank 3. This validates a conjecture by Rahman and Watson. Another corollary of our result is that, if Maker has a winning strategy on a hypergraph of rank 3, then he can ensure to claim an edge in a number of rounds that is logarithmic in the number of vertices. Note: The present updated version of this deposit provides a counterexample to a similar result which was incorrectly claimed recently (arXiv:2209.11202)., Comment: The present updated version of this deposit provides a counterexample to a similar result which was incorrectly claimed recently (arXiv:2209.11202)

Recent research considers few-shot intent detection as a meta-learning problem: the model is learning to learn from a consecutive set of small tasks named episodes. In this work, we propose ProtAugment, a meta-learning algorithm for short texts classification (the intent detection task). ProtAugment is a novel extension of Prototypical Networks, that limits overfitting on the bias introduced by the few-shots classification objective at each episode. It relies on diverse paraphrasing: a conditional language model is first fine-tuned for paraphrasing, and diversity is later introduced at the decoding stage at each meta-learning episode. The diverse paraphrasing is unsupervised as it is applied to unlabelled data, and then fueled to the Prototypical Network training objective as a consistency loss. ProtAugment is the state-of-the-art method for intent detection meta-learning, at no extra labeling efforts and without the need to fine-tune a conditional language model on a given application domain., Comment: Accepted at the 59th Annual Meeting of the Association for Computational Linguistics (ACL2021)

Modern classification models tend to struggle when the amount of annotated data is scarce. To overcome this issue, several neural few-shot classification models have emerged, yielding significant progress over time, both in Computer Vision and Natural Language Processing. In the latter, such models used to rely on fixed word embeddings before the advent of transformers. Additionally, some models used in Computer Vision are yet to be tested in NLP applications. In this paper, we compare all these models, first adapting those made in the field of image processing to NLP, and second providing them access to transformers. We then test these models equipped with the same transformer-based encoder on the intent detection task, known for having a large number of classes. Our results reveal that while methods perform almost equally on the ARSC dataset, this is not the case for the Intent Detection task, where the most recent and supposedly best competitors perform worse than older and simpler ones (while all are given access to transformers). We also show that a simple baseline is surprisingly strong. All the new developed models, as well as the evaluation framework, are made publicly available., Comment: Accepted at the 16th conference of the European Chapter of the Association for Computational Linguistics (EACL)

A $k$-proper edge-coloring of a graph G is called adjacent vertex-distinguishing if any two adjacent vertices are distinguished by the set of colors appearing in the edges incident to each vertex. The smallest value $k$ for which $G$ admits such coloring is denoted by $\chi'_a(G)$. We prove that $\chi'_a(G) = 2R + 1$ for most circulant graphs $C_n([1, R])$., Comment: Editor-neutral version

Active learning typically focuses on training a model on few labeled examples alone, while unlabeled ones are only used for acquisition. In this work we depart from this setting by using both labeled and unlabeled data during model training across active learning cycles. We do so by using unsupervised feature learning at the beginning of the active learning pipeline and semi-supervised learning at every active learning cycle, on all available data. The former has not been investigated before in active learning, while the study of latter in the context of deep learning is scarce and recent findings are not conclusive with respect to its benefit. Our idea is orthogonal to acquisition strategies by using more data, much like ensemble methods use more models. By systematically evaluating on a number of popular acquisition strategies and datasets, we find that the use of unlabeled data during model training brings a surprising accuracy improvement in image classification, compared to the differences between acquisition strategies. We thus explore smaller label budgets, even one label per class.

Thanks to the Big Data revolution and increasing computing capacities, Artificial Intelligence (AI) has made an impressive revival over the past few years and is now omnipresent in both research and industry. The creative sectors have always been early adopters of AI technologies and this continues to be the case. As a matter of fact, recent technological developments keep pushing the boundaries of intelligent systems in creative applications: the critically acclaimed movie "Sunspring", released in 2016, was entirely written by AI technology, and the first-ever Music Album, called "Hello World", produced using AI has been released this year. Simultaneously, the exploratory nature of the creative process is raising important technical challenges for AI such as the ability for AI-powered techniques to be accurate under limited data resources, as opposed to the conventional "Big Data" approach, or the ability to process, analyse and match data from multiple modalities (text, sound, images, etc.) at the same time. The purpose of this white paper is to understand future technological advances in AI and their growing impact on creative industries. This paper addresses the following questions: Where does AI operate in creative Industries? What is its operative role? How will AI transform creative industries in the next ten years? This white paper aims to provide a realistic perspective of the scope of AI actions in creative industries, proposes a vision of how this technology could contribute to research and development works in such context, and identifies research and development challenges.

NELL is a system that continuously reads the Web to extract knowledge in form of entities and relations between them. It has been running since January 2010 and extracted over 50,000,000 candidate statements. NELL's generated data comprises all the candidate statements together with detailed information about how it was generated. This information includes how each component of the system contributed to the extraction of the statement, as well as when that happened and how confident the system is in the veracity of the statement. However, the data is only available in an ad hoc CSV format that makes it difficult to exploit out of the context of NELL. In order to make it more usable for other communities, we adopt Linked Data principles to publish a more standardized, self-describing dataset with rich provenance metadata.

Word embeddings are commonly used as a starting point in many NLP models to achieve state-of-the-art performances. However, with a large vocabulary and many dimensions, these floating-point representations are expensive both in terms of memory and calculations which makes them unsuitable for use on low-resource devices. The method proposed in this paper transforms real-valued embeddings into binary embeddings while preserving semantic information, requiring only 128 or 256 bits for each vector. This leads to a small memory footprint and fast vector operations. The model is based on an autoencoder architecture, which also allows to reconstruct original vectors from the binary ones. Experimental results on semantic similarity, text classification and sentiment analysis tasks show that the binarization of word embeddings only leads to a loss of ~2% in accuracy while vector size is reduced by 97%. Furthermore, a top-k benchmark demonstrates that using these binary vectors is 30 times faster than using real-valued vectors., Comment: Accepted as a long paper at AAAI 2019

While Wikipedia exists in 287 languages, its content is unevenly distributed among them. In this work, we investigate the generation of open domain Wikipedia summaries in underserved languages using structured data from Wikidata. To this end, we propose a neural network architecture equipped with copy actions that learns to generate single-sentence and comprehensible textual summaries from Wikidata triples. We demonstrate the effectiveness of the proposed approach by evaluating it against a set of baselines on two languages of different natures: Arabic, a morphological rich language with a larger vocabulary than English, and Esperanto, a constructed language known for its easy acquisition., Comment: NAACL HTL 2018

We present a neural model for question generation from knowledge base triples in a "Zero-Shot" setup, that is generating questions for triples containing predicates, subject types or object types that were not seen at training time. Our model leverages triples occurrences in the natural language corpus in an encoder-decoder architecture, paired with an original part-of-speech copy action mechanism to generate questions. Benchmark and human evaluation show that our model sets a new state-of-the-art for zero-shot QG.

We explore methods to extract relations between named entities from free text in an unsupervised setting. In addition to standard feature extraction, we develop a novel method to re-weight word embeddings. We alleviate the problem of features sparsity using an individual feature reduction. Our approach exhibits a significant improvement by 5.8% over the state-of-the-art relation clustering scoring a F1-score of 0.416 on the NYT-FB dataset., Comment: 4 pages, published in ESWC 2017

Most people do not interact with Semantic Web data directly. Unless they have the expertise to understand the underlying technology, they need textual or visual interfaces to help them make sense of it. We explore the problem of generating natural language summaries for Semantic Web data. This is non-trivial, especially in an open-domain context. To address this problem, we explore the use of neural networks. Our system encodes the information from a set of triples into a vector of fixed dimensionality and generates a textual summary by conditioning the output on the encoded vector. We train and evaluate our models on two corpora of loosely aligned Wikipedia snippets and DBpedia and Wikidata triples with promising results.

Recently, several vertex identifying notions were introduced (identifying coloring, lid-coloring, ...), these notions were inspired by identifying codes. All of them, as well as original identifying code, are based on separating two vertices according to some conditions on their closed neighborhood. Therefore, twins can not be identified. So most of known results focus on twin-free graph. Here, we show how twins can modify optimal value of vertex-identifying parameters for identifying coloring and locally identifying coloring. \textbf{Keyword :} Identifying coloring, locally identifying coloring, twins, separating.

Continuous multimodal representations suitable for multimodal information retrieval are usually obtained with methods that heavily rely on multimodal autoencoders. In video hyperlinking, a task that aims at retrieving video segments, the state of the art is a variation of two interlocked networks working in opposing directions. These systems provide good multimodal embeddings and are also capable of translating from one representation space to the other. Operating on representation spaces, these networks lack the ability to operate in the original spaces (text or image), which makes it difficult to visualize the crossmodal function, and do not generalize well to unseen data. Recently, generative adversarial networks have gained popularity and have been used for generating realistic synthetic data and for obtaining high-level, single-modal latent representation spaces. In this work, we evaluate the feasibility of using GANs to obtain multimodal representations. We show that GANs can be used for multimodal representation learning and that they provide multimodal representations that are superior to representations obtained with multimodal autoencoders. Additionally, we illustrate the ability of visualizing crossmodal translations that can provide human-interpretable insights on learned GAN-based video hyperlinking models., Comment: 4 pages, 1 figure, 2 tables, published at ACM International Conference in Multimedia Retrieval (ICMR) 2017

There is an inherent need for autonomous cars, drones, and other robots to have a notion of how their environment behaves and to anticipate changes in the near future. In this work, we focus on anticipating future appearance given the current frame of a video. Existing work focuses on either predicting the future appearance as the next frame of a video, or predicting future motion as optical flow or motion trajectories starting from a single video frame. This work stretches the ability of CNNs (Convolutional Neural Networks) to predict an anticipation of appearance at an arbitrarily given future time, not necessarily the next video frame. We condition our predicted future appearance on a continuous time variable that allows us to anticipate future frames at a given temporal distance, directly from the input video frame. We show that CNNs can learn an intrinsic representation of typical appearance changes over time and successfully generate realistic predictions at a deliberate time difference in the near future., Comment: 11 pages, 1 figures, published in the International Conference of Image Analysis and Processing (ICIAP) 2017 and in the Netherlands Conference on Computer Vision (NCCV) 2016

Octal games are a well-defined family of two-player games played on heaps of counters, in which the players remove alternately a certain number of counters from a heap, sometimes being allowed to split a heap into two nonempty heaps, until no counter can be removed anymore. We extend the definition of octal games to play them on graphs: heaps are replaced by connected components and counters by vertices. Thus, an octal game on a path P\_n is equivalent to playing the same octal game on a heap of n counters. We study one of the simplest octal games, called 0.33, in which the players can remove one vertex or two adjacent vertices without disconnecting the graph. We study this game on trees and give a complete resolution of this game on subdivided stars and bistars.

The distinguishing number of a graph $H$ is a symmetry related graph invariant whose study started two decades ago. The distinguishing number $D(H)$ is the least integer $d$ such that $H$ has a $d$-distinguishing coloring. A $d$-distinguishing coloring is a coloring $c:V(H)\rightarrow\{1,\dots,d\}$ invariant only under the trivial automorphism. In this paper, we continue the study of a game variant of this parameter, recently introduced. The distinguishing game is a game with two players, Gentle and Rascal, with antagonist goals. This game is played on a graph $H$ with a fixed set of $d\in\mathbb N^*$ colors. Alternately, the two players choose a vertex of $H$ and color it with one of the $d$ colors. The game ends when all the vertices have been colored. Then Gentle wins if the coloring is $d$-distinguishing and Rascal wins otherwise. This game defines two new invariants, which are the minimum numbers of colors needed to ensure that Gentle has a winning strategy, depending who starts the game. The invariant could eventually be infinite. In this paper, we focus on cartesian product, a graph operation well studied in the classical case. We give sufficient conditions on the order of two connected factors $H$ and $F$ relatively prime, which ensure that one of the game distinguishing numbers of the cartesian product $H\square F$ is finite. If $H$ is a so-called involutive graph, we give an upper bound of order $D^2(H)$ for one of the game distinguishing numbers of $H\square F$. Finally, using in part the previous result, we compute the exact value of these invariants for cartesian products of relatively prime cycles. It turns out that the value is either infinite or equal to $2$, depending on the parity of the product order.

It has been conjectured that for every claw-free graph $G$ the choice number of $G$ is equal to its chromatic number. We focus on the special case of this conjecture where $G$ is perfect. Claw-free perfect graphs can be decomposed via clique-cutset into two special classes called elementary graphs and peculiar graphs. Based on this decomposition we prove that the conjecture holds true for every claw-free perfect graph with maximum clique size at most $4$.

The {\em Fibonacci cube} of dimension $n$, denoted as $\Gamma\_n$, is the subgraph of $n$-cube $Q\_n$ induced by vertices with no consecutive 1's. We study the maximum number of disjoint subgraphs in $\Gamma\_n$ isomorphic to $Q\_k$, and denote this number by $q\_k(n)$. We prove several recursive results for $q\_k(n)$, in particular we prove that $q\_{k}(n) = q\_{k-1}(n-2) + q\_{k}(n-3)$. We also prove a closed formula in which $q\_k(n)$ is given in terms of Fibonacci numbers, and finally we give the generating function for the sequence $\{q\_{k}(n)\}\_{n=0}^{ \infty}$.

We consider the problem of computing identifying codes of graphs and its fractional relaxation. The ratio between the size of optimal integer and fractional solutions is between 1 and 2 ln(|V|)+1 where V is the set of vertices of the graph. We focus on vertex-transitive graphs for which we can compute the exact fractional solution. There are known examples of vertex-transitive graphs that reach both bounds. We exhibit infinite families of vertex-transitive graphs with integer and fractional identifying codes of order |V|^a with a in {1/4,1/3,2/5}. These families are generalized quadrangles (strongly regular graphs based on finite geometries). They also provide examples for metric dimension of graphs.

The distinguishing number of a graph $G$ is a symmetry related graph invariant whose study started two decades ago. The distinguishing number $D(G)$ is the least integer $d$ such that $G$ has a $d$-distinguishing coloring. A distinguishing $d$-coloring is a coloring $c:V(G)\rightarrow\{1,...,d\}$ invariant only under the trivial automorphism. In this paper, we introduce a game variant of the distinguishing number. The distinguishing game is a game with two players, the Gentle and the Rascal, with antagonist goals. This game is played on a graph $G$ with a set of $d\in\mathbb N^*$ colors. Alternately, the two players choose a vertex of $G$ and color it with one of the $d$ colors. The game ends when all the vertices have been colored. Then the Gentle wins if the coloring is distinguishing and the Rascal wins otherwise. This game leads to define two new invariants for a graph $G$, which are the minimum numbers of colors needed to ensure that the Gentle has a winning strategy, depending on who starts. These invariants could be infinite, thus we start by giving sufficient conditions to have infinite game distinguishing numbers. We also show that for graphs with cyclic automorphisms group of prime odd order, both game invariants are finite. After that, we define a class of graphs, the involutive graphs, for which the game distinguishing number can be quadratically bounded above by the classical distinguishing number. The definition of this class is closely related to imprimitive actions whose blocks have size $2$. Then, we apply results on involutive graphs to compute the exact value of these invariants for hypercubes and even cycles. Finally, we study odd cycles, for which we are able to compute the exact value when their order is not prime. In the prime order case, we give an upper bound of $3$.

Introduced by Albertson et al. \cite{albertson}, the distinguishing number $D(G)$ of a graph $G$ is the least integer $r$ such that there is a $r$-labeling of the vertices of $G$ that is not preserved by any nontrivial automorphism of $G$. Most of graphs studied in literature have 2 as a distinguishing number value except complete, multipartite graphs or cartesian product of complete graphs depending on $n$. In this paper, we study circulant graphs of order $n$ where the adjacency is defined using a symmetric subset $A$ of $\mathbb{Z}_n$, called generator. We give a construction of a family of circulant graphs of order $n$ and we show that this class has distinct distinguishing numbers and these lasters are not depending on $n$.

A \textit{locally identifying coloring} ($lid$-coloring) of a graph is a proper coloring such that the sets of colors appearing in the closed neighborhoods of any pair of adjacent vertices having distinct neighborhoods are distinct. Our goal is to study a \textit{relaxed locally identifying coloring} ($rlid$-coloring) of a graph that is similar to locally identifying coloring for which the coloring is not necessary proper.We denote by $\chi_{rlid}(G)$ the minimum number of colors used in a relaxed locally identifying coloring of a graph $G$ In this paper, we prove that the problem of deciding that $\chi_{rlid}(G)=3$ for a $2$-degenerate planar graph $G$ is $NP$-complete. We give several bounds of $\chi_{rlid}(G)$ and construct graphs for which some of these bounds are tightened. Studying some families of graphs allows us to compare this parameter with the minimum number of colors used in a locally identifying coloring of a graph $G$ ($\chi_{lid}(G)$), the size of a minimum identifying code of $G$ ($\gamma_{id}(G)$) and the chromatic number of $G$ ($\chi(G)$).

We say that a 0-1 matrix $N$ of size $a\times b$ can be found in a collection of sets $\mathcal{H}$ if we can find sets $H_{1}, H_{2}, \dots, H_{a}$ in $\mathcal{H}$ and elements $e_1, e_2, \dots, e_b$ in $\cup_{H \in \mathcal{H}} H$ such that $N$ is the incidence matrix of the sets $H_{1}, H_{2}, \dots, H_{a}$ over the elements $e_1, e_2, \dots, e_b$. We prove the following Ramsey-type result: for every $n\in \N$, there exists a number S(n) such that in any collection of at least S(n) sets, one can find either the incidence matrix of a collection of $n$ singletons, or its complementary matrix, or the incidence matrix of a collection of $n$ sets completely ordered by inclusion. We give several results of the same extremal set theoretical flavour. For some of these, we give the exact value of the number of sets required.

We introduce the concept of constant $2$-labelling of a weighted graph and show how it can be used to obtain perfect weighted coverings. Roughly speaking, a constant $2$-labelling of a weighted graph is a $2$-colouring of its vertex set which preserves the sum of the weights of black vertices under some automorphisms. We study this problem on four types of weighted cycles. Our results on cycles allow us to determine $(r,a,b)$-codes in $\mathbb{Z}^2$ whenever $|a-b|>4$, $r\ge2$ and we give the precise values of $a$ and $b$. This is a refinement of Axenovich's theorem proved in 2003., Comment: 22 pages

In this paper we study identifying codes, locating-dominating codes, and total-dominating codes in Sierpinski graphs. We compute the minimum size of such codes in Sierpinski graphs.

A weak odd dominated (WOD) set in a graph is a subset B of vertices for which there exists a distinct set of vertices C such that every vertex in B has an odd number of neighbors in C. We point out the connections of weak odd domination with odd domination, [sigma,rho]-domination, and perfect codes. We introduce bounds on \kappa(G), the maximum size of WOD sets of a graph G, and on \kappa'(G), the minimum size of non WOD sets of G. Moreover, we prove that the corresponding decision problems are NP-complete. The study of weak odd domination is mainly motivated by the design of graph-based quantum secret sharing protocols: a graph G of order n corresponds to a secret sharing protocol which threshold is \kappa_Q(G) = max(\kappa(G), n-\kappa'(G)). These graph-based protocols are very promising in terms of physical implementation, however all such graph-based protocols studied in the literature have quasi-unanimity thresholds (i.e. \kappa_Q(G)=n-o(n) where n is the order of the graph G underlying the protocol). In this paper, we show using probabilistic methods, the existence of graphs with smaller \kappa_Q (i.e. \kappa_Q(G)< 0.811n where n is the order of G). We also prove that deciding for a given graph G whether \kappa_Q(G)< k is NP-complete, which means that one cannot efficiently double check that a graph randomly generated has actually a \kappa_Q smaller than 0.811n., Comment: Subsumes arXiv:1109.6181: Optimal accessing and non-accessing structures for graph protocols

One important class of online videos is that of news broadcasts. Most news organisations provide near-immediate access to topical news broadcasts over the Internet, through RSS streams or podcasts. Until lately, technology has not made it possible for a user to automatically go to the smaller parts, within a longer broadcast, that might interest them. Recent advances in both speech recognition systems and natural language processing have led to a number of robust tools that allow us to provide users with quicker, more focussed access to relevant segments of one or more news broadcast videos. Here we present our new interface for browsing or searching news broadcasts (video/audio) that exploits these new language processing tools to (i) provide immediate access to topical passages within news broadcasts, (ii) browse news broadcasts by events as well as by people, places and organisations, (iii) perform cross lingual search of news broadcasts, (iv) search for news through a map interface, (v) browse news by trending topics, and (vi) see automatically-generated textual clues for news segments, before listening. Our publicly searchable demonstrator currently indexes daily broadcast news content from 50 sources in English, French, Chinese, Arabic, Spanish, Dutch and Russian., Comment: NEM Summit, Torino : Italy (2011)

An accessing set in a graph is a subset B of vertices such that there exists D subset of B, such that each vertex of V\B has an even number of neighbors in D. In this paper, we introduce new bounds on the minimal size kappa'(G) of an accessing set, and on the maximal size kappa(G) of a non-accessing set of a graph G. We show strong connections with perfect codes and give explicitly kappa(G) and kappa'(G) for several families of graphs. Finally, we show that the corresponding decision problems are NP-Complete.

An identifying code of a graph is a subset of its vertices such that every vertex of the graph is uniquely identified by the set of its neighbours within the code. We study the edge-identifying code problem, i.e. the identifying code problem in line graphs. If $\ID(G)$ denotes the size of a minimum identifying code of an identifiable graph $G$, we show that the usual bound $\ID(G)\ge \lceil\log_2(n+1)\rceil$, where $n$ denotes the order of $G$, can be improved to $\Theta(\sqrt{n})$ in the class of line graphs. Moreover, this bound is tight. We also prove that the upper bound $\ID(\mathcal{L}(G))\leq 2|V(G)|-5$, where $\mathcal{L}(G)$ is the line graph of $G$, holds (with two exceptions). This implies that a conjecture of R. Klasing, A. Kosowski, A. Raspaud and the first author holds for a subclass of line graphs. Finally, we show that the edge-identifying code problem is NP-complete, even for the class of planar bipartite graphs of maximum degree~3 and arbitrarily large girth.

We introduce the notion of locally identifying coloring of a graph. A proper vertex-coloring c of a graph G is said to be locally identifying, if for any adjacent vertices u and v with distinct closed neighborhood, the sets of colors that appear in the closed neighborhood of u and v are distinct. Let $\chi_{lid}(G)$ be the minimum number of colors used in a locally identifying vertex-coloring of G. In this paper, we give several bounds on $\chi_{lid}$ for different families of graphs (planar graphs, some subclasses of perfect graphs, graphs with bounded maximum degree) and prove that deciding whether $\chi_{lid}(G)=3$ for a subcubic bipartite graph $G$ with large girth is an NP-complete problem., Comment: 21 pages

Identifying codes have been introduced in 1998 to model fault-detection in multiprocessor systems. In this paper, we introduce two variations of identifying codes: weak codes and light codes. They correspond to fault-detection by successive rounds. We give exact bounds for those two definitions for the family of cycles.

Let $G=(V,E)$ be an undirected graph without loops and multiple edges. A subset $C\subseteq V$ is called \emph{identifying} if for every vertex $x\in V$ the intersection of $C$ and the closed neighbourhood of $x$ is nonempty, and these intersections are different for different vertices $x$. Let $k$ be a positive integer. We will consider graphs where \emph{every} $k$-subset is identifying. We prove that for every $k>1$ the maximal order of such a graph is at most $2k-2.$ Constructions attaining the maximal order are given for infinitely many values of $k.$ The corresponding problem of $k$-subsets identifying any at most $\ell$ vertices is considered as well., Comment: 21 pages

Digital identity management intra and inter information systems, and, service oriented architectures, are the roots of identity federation. This kind of security architectures aims at enabling information system interoperability. Existing architectures, however, do not consider interoperability of heterogeneous federation architectures, which rely on different federation protocols.In this paper, we try to initiate an in-depth reflection on this issue, through the comparison of two main federation architecture specifications: SAML and WS-Federation. We firstly propose an overall outline of identity federation. We furthermore address the issue of interoperability for federation architectures using a different federation protocol. Afterwards, we compare SAML and WS-Federation. Eventually, we define the ways of convergence, and therefore, of interoperability.

To transcribe speech, automatic speech recognition systems use statistical methods, particularly hidden Markov model and N-gram models. Although these techniques perform well and lead to efficient systems, they approach their maximum possibilities. It seems thus necessary, in order to outperform current results, to use additional information, especially bound to language. However, introducing such knowledge must be realized taking into account specificities of spoken language (hesitations for example) and being robust to possible misrecognized words. This document presents a state of the art of these researches, evaluating the impact of the insertion of linguistic information on the quality of the transcription.

Quantum game theory offers a lot of interesting questions, and it is relevant to use the quantum information theory to resolve or improve games with lack of information : how to use the power of quantum entanglement to show the superiority of a quantum player that is allowed to use quantum mechanics versus a classical player, how to use quantum communication properties in cooperative games ... But games are also useful to make notions easier to understand, and permit to apprehend easier new ways of reasoning. The objective of this work is to formalize and to study a simple game with qubits using quantum notions of measurement and superposition but keeping a simple formalism so that knowing quantum mechanics is not necessary to play the game. We solve a quantum combinatorial game by giving a winning strategy for it. We also propose a quantisation of a family of combinatorial games., Comment: 13 pages

Two-level fluctuations of the magnetization state of pseudo spin-valve pillars Co(10 nm)/Cu(10 nm)/Co(30 nm) embedded in electrodeposited nanowires (~40 nm in diameter, 6000 nm in length) are triggered by spin-polarized currents of 10^7 A/cm^2 at room temperature. The statistical properties of the residence times in the parallel and antiparallel magnetization states reveal two effects with qualitatively different dependences on current intensity. The current appears to have the effect of a field determined as the bias field required to equalize these times. The bias field changes sign when the current polarity is reversed. At this field, the effect of a current density of 10^7 A/cm^2 is to lower the mean time for switching down to the microsecond range. This effect is independent of the sign of the current and is interpreted in terms of an effective temperature for the magnetization., Comment: 4 pages, 5 figures, revised version, to be published in Phys. Rev. Lett

The spin-dependent transport in multiwall carbon nanotubes obtained by chemical vapor deposition (CVD) in porous alumina membranes is studied. The zero bias anomaly is found to verify the predicted Luttinger liquid power law. The magnetoresistance at high fields varies in sign and amplitude from one sample to the other, which is probably due to the presence of dopant in the tube. In contrast, the magnetoresistance due to the spin polarized current is destroyed in the nanotube as expected in case of spin-charge separation., Comment: 4 pages, 5 figures