Search

Local certification is a topic originating from distributed computing, where a prover tries to convince the vertices of a graph $G$ that $G$ satisfies some property $\mathcal{P}$. To convince the vertices, the prover gives a small piece of information, called certificate, to each vertex, and the vertices then decide whether the property $\mathcal{P}$ is satisfied by just looking at their certificate and the certificates of their neighbors. When studying a property $\mathcal{P}$ in the perspective of local certification, the aim is to find the optimal size of the certificates needed to certify $\mathcal{P}$, which can be viewed a measure of the local complexity of $\mathcal{P}$. A certification scheme is considered to be efficient if the size of the certificates is polylogarithmic in the number of vertices. While there have been a number of meta-theorems providing efficient certification schemes for general graph classes, the proofs of the lower bounds on the size of the certificates are usually very problem-dependent. In this work, we introduce a notion of hardness reduction in local certification, and show that we can transfer a lower bound on the certificates for a property $\mathcal{P}$ to a lower bound for another property $\mathcal{P}'$, via a (local) hardness reduction from $\mathcal{P}$ to $\mathcal{P}'$. We then give a number of applications in which we obtain polynomial lower bounds for many classical properties using such reductions., Comment: 35 pages

The study of some parametric integrals is presented with a combined approach of analytical development, the usage of a Computed Algebra System (CAS) and of the Online Encyclopedia of Integer Sequences. The methodology for the solution includes a) an analytical investigation for the study of the parametric integral, b) computations with a CAS of the integral for specific values of the parameter, c) investigation of the connection between the integral and special functions or classical numbers, and d) derivation of a general algorithm for the complete computation of the parametric integral. The central example of the paper is the parametric integral \begin{equation*} \label{the general integral} I_{n}^{(p)}=\int_0^{\pi /4} x^p \tan^n x\; dx, \end{equation*} The work reveals a connection of this parametric integral with Catalan numbers., Comment: 15 pages,0 figure

In local certification, vertices of a $n$-vertex graph perform a local verification to check if a given property is satisfied by the graph. This verification is performed thanks to certificates, which are pieces of information that are given to the vertices. In this work, we focus on the local certification of $P_5$-freeness, and we prove a $O(n^{3/2})$ upper bound on the size of the certificates, which is (to our knowledge) the first subquadratic upper bound for this property.

The use of tunable pre-pulse is a common technique to enhance the high-order harmonic generation from surface plasma. The shape and dynamic of the electron density, the degree of ionization and its rate, and the plasma heating are influenced by the pre-pulse properties. Non-uniform pre-pulse could cause a spatially varying density map to the pre-plasma region, which serves as the spectrally up-conversion and reflection surface. The corresponding geometrical feature and plasma nature under laser field will affect the harmonic emission properties. In this study, the variation in harmonic beam pointing due to the electron density shape was investigated. Particle-in-cell simulations demonstrated that both plasma hydrodynamics and geometrical optical effect induce the deviation of harmonic beam from specular reflection. This research contributes to the understanding of the surface plasma dynamics during high harmonic generation process.

Local certification is the area of distributed network computing asking the following question: How to certify to the nodes of a network that a global property holds, if they are limited to a local verification? In this area, it is often essential to have identifiers, that is, unique integers assigned to the nodes. In this short paper, we show how to reduce the range of the identifiers, in three different settings. More precisely, we show how to rename identifiers in the classical local certification setting, when we can (resp. cannot) choose the new identifiers, and we show how a global certificate can help to encode very compactly a new identifier assignment that is not injective in general, but still useful. We conclude with a number of applications of these three results.

When the world changes, so does the text that humans write about it. How do we build language models that can be easily updated to reflect these changes? One popular approach is retrieval-augmented generation, in which new documents are inserted into a knowledge base and retrieved during prediction for downstream tasks. Most prior work on these systems have focused on improving behavior during prediction through better retrieval or reasoning. This paper introduces ERASE, which instead improves model behavior when new documents are acquired, by incrementally deleting or rewriting other entries in the knowledge base each time a document is added. In two new benchmark datasets evaluating models' ability to answer questions about a stream of news articles or conversations, ERASE improves accuracy relative to conventional retrieval-augmented generation by 7-13% (Mixtral-8x7B) and 6-10% (Llama-3-8B) absolute. Code and data are available at https://github.com/belindal/ERASE

Detecting specific structures in a network has been a very active theme of research in distributed computing for at least a decade. In this paper, we start the study of subgraph detection from the perspective of local certification. Remember that a local certification is a distributed mechanism enabling the nodes of a network to check the correctness of the current configuration, thanks to small pieces of information called certificates. Our main question is: For a given graph $H$, what is the minimum certificate size that allows checking that the network does not contain $H$ as a (possibly induced) subgraph? We show a variety of lower and upper bounds, uncovering an interesting interplay between the optimal certificate size, the size of the forbidden subgraph, and the locality of the verification. Along the way we introduce several new technical tools, in particular what we call the \emph{layered map}, which is not specific to forbidden subgraphs and that we expect to be useful for certifying many other properties.

We study the class of star-free languages. A long-standing goal is to classify them by the complexity of their descriptions. The most influential research effort involves concatenation hierarchies, which measure alternations between ``complement'' and ``union plus concatenation''. We explore alternative hierarchies that also stratify star-free languages. They are built with an operator $C\mapsto TL(C)$. From an input class $C$, it produces a larger one $TL(C)$, consisting of all languages definable in a variant of unary temporal logic, where temporal modalities depend on $C$. Level $n$ in the navigational hierarchy of basis $C$ is constructed by applying this operator $n$ times to $C$. As bases $G$, we focus on group languages and natural extensions thereof, denoted $G^+$. We prove that the navigational hierarchies of bases $G$ and $G^+$ are strictly intertwined and conduct a thorough investigation of their relationships with concatenation hierarchies. We also look at two problems on classes of languages: membership (decide if a language is in the class) and separation (decide, for two languages $L_1,L_2$, if there is a language $K$ in the class with $L_1\subseteq K$ and $L_2\cap K=\emptyset$). We prove that if separation is decidable for $G$, then so is membership for level \emph{two} in the navigational hierarchies of bases $G$ and $G^+$. We take a look at the trivial class $ST=\{\emptyset,A^*\}$. For the bases $ST$ and $ST^+$, the levels \emph{one} are standard variants of unary temporal logic. The levels \emph{two} correspond to variants of two-variable logic, investigated recently by Krebs, Lodaya, Pandya and Straubing. We solve one of their conjectures. We also prove that for these two bases, level \emph{two} has decidable \emph{separation}. Combined with earlier results on the operator $C\mapsto TL(C)$, this implies that level \emph{three} has decidable membership.

In this work, we provide an upper bound for global certification of graph homomorphism, a generalization of graph coloring. In certification, the nodes of a network should decide if the network satisfies a given property, thanks to small pieces of information called certificates. Here, there is only one global certificate which is shared by all the nodes, and the property we want to certify is the existence of a graph homomorphism to a given graph. For bipartiteness, a special case of graph homomorphism, Feuilloley and Hirvonen proved in~\cite{FeuilloleyH18} some upper and lower bounds on the size of the optimal certificate, and made the conjecture that their lower bound could be improved to match their upper bound. We prove that this conjecture is false: their lower bound was in fact optimal, and we prove it by providing the matching upper bound using a known result of perfect hashing.

We look at concatenation hierarchies of classes of regular languages. Each such hierarchy is determined by a single class, its basis: level $n$ is built by applying the Boolean polynomial closure operator (BPol), $n$ times to the basis. A prominent and difficult open question in automata theory is to decide membership of a regular language in a given level. For instance, for the historical dot-depth hierarchy, the decidability of membership is only known at levels one and two. We give a generic algebraic characterization of the operator BPol. This characterization implies that for any concatenation hierarchy, if $n$ is at least two, membership at level $n$ reduces to a more complex problem, called covering, for the previous level, $n-1$. Combined with earlier results on covering, this implies that membership is decidable for dot-depth three and for level two in most of the prominent hierarchies in the literature. For instance, we obtain that the levels two in both the modulo hierarchy and the group hierarchy have decidable membership.

By twisting the spectral triple of a riemannian spin manifold, we show how to generate an orthogonal and geodesic preserving torsion from a torsionless Dirac operator. We identify the group of twisted unitaries as the generator of torsion with co-exact three form. Through the fermionic action, the torsion term identifies with a Lorentzian energy-momentum 4-vector. The Lorentz group turns out to be a normal subgroup of the twisted unitaries. We also investigate the spectral action related to this model., Comment: Previous version (v1) split in two: the present paper focuses on twists of manifolds, torsion and Lorentz symmetry. It contains new results on twisting unitaries as generators of co-exact torsion form, and a systematic study of the unitaries that implement the twist. Results on the twist of arbitrary spectral triples will be extended in a foredooming paper. (update of metadata in v3)

Local certification is a distributed mechanism enabling the nodes of a network to check the correctness of the current configuration, thanks to small pieces of information called certificates. For many classic global properties, like checking the acyclicity of the network, the optimal size of the certificates depends on the size of the network, $n$. In this paper, we focus on properties for which the size of the certificates does not depend on $n$ but on other parameters. We focus on three such important properties and prove tight bounds for all of them. Namely, we prove that the optimal certification size is: $\Theta(\log k)$ for $k$-colorability (and even exactly $\lceil \log k \rceil$ bits in the anonymous model while previous works had only proved a $2$-bit lower bound); $(1/2)\log t+o(\log t)$ for dominating sets at distance $t$ (an unexpected and tighter-than-usual bound) ; and $\Theta(\log \Delta)$ for perfect matching in graphs of maximum degree $\Delta$ (the first non-trivial bound parameterized by $\Delta$). We also prove some surprising upper bounds, for example, certifying the existence of a perfect matching in a planar graph can be done with only two bits. In addition, we explore various specific cases for these properties, in particular improving our understanding of the trade-off between locality of the verification and certificate size., Comment: Accepted at STACS 2024

We introduce an operator on classes of regular languages, the star-free closure. Our motivation is to generalize standard results of automata theory within a unified framework. Given an arbitrary input class $C$, the star-free closure operator outputs the least class closed under Boolean operations and language concatenation, and containing all languages of $C$ as well as all finite languages. We establish several equivalent characterizations of star-free closure: in terms of regular expressions, first-order logic, pure future and future-past temporal logic, and recognition by finite monoids. A key ingredient is that star-free closure coincides with another closure operator, defined in terms of regular operations where Kleene stars are allowed in restricted~contexts. A consequence of this first result is that we can decide membership of a regular language in the star-free closure of a class whose separation problem is decidable. Moreover, we prove that separation itself is decidable for the star-free closure of any finite class, and of any class of group languages having itself decidable separation (plus mild additional properties). We actually show decidability of a stronger property, called covering.

We investigate an operator on classes of languages. For each class $C$, it outputs a new class $FO^2(I_C)$ associated with a variant of two-variable first-order logic equipped with a signature$I_C$ built from $C$. For $C = \{\emptyset, A^*\}$, we get the variant $FO^2(<)$ equipped with the linear order. For $C = \{\emptyset, \{\varepsilon\},A^+, A^*\}$, we get the variant $FO^2(<,+1)$, which also includes the successor. If $C$ consists of all Boolean combinations of languages $A^*aA^*$ where $a$ is a letter, we get the variant $FO^2(<,Bet)$, which also includes ``between relations''. We prove a generic algebraic characterization of the classes $FO^2(I_C)$. It smoothly and elegantly generalizes the known ones for all aforementioned cases. Moreover, it implies that if $C$ has decidable separation (plus mild properties), then $FO^2(I_C)$ has a decidable membership problem. We actually work with an equivalent definition of \fodc in terms of unary temporal logic. For each class $C$, we consider a variant $TL(C)$ of unary temporal logic whose future/past modalities depend on $C$ and such that $TL(C) = FO^2(I_C)$. Finally, we also characterize $FL(C)$ and $PL(C)$, the pure-future and pure-past restrictions of $TL(C)$. These characterizations as well imply that if \Cs is a class with decidable separation, then $FL(C)$ and $PL(C)$ have decidable membership.

Strong-field quantum electronics is emerging as a potential candidate in information processing but still coherence vs decoherence is a primary concern of the concept. Strong-field coherent processes in band gap materials have led during the last decade to the emergence of high harmonic generation in semiconductors, petahertz electronics, or strong-field quantum states. However, the coherent behavior of the sub-optical cycle-driven electrons has never been directly observed. We report here on the experimental evidence of coherent ultrashort emission of hot electrons from a nanostructured semiconductor. Our method uses sub-wavelength electric field enhancement to localize the electron emission within a nanometer-scale spot. We found similarities with the electron emission from metallic nanotips in the strong-field regime, a topic that has opened a vast domain of applications during the last decade. The electron spectra display both odd and even harmonic orders of the driving femtosecond laser frequency, a signature of the coherent nature of the electron emission and their attosecond timing. Our findings complete our knowledge of phenomena governing coherent strong-field processes in semiconductors and open perspectives for the generation of future quantum devices operating in the strong-field regime.

We look at classes of languages associated to the fragment of first-order logic B{\Sigma}1 which disallows quantifier alternations. Each class is defined by choosing the set of predicates on positions that may be used. Two key such fragments are those equipped with the linear ordering and possibly the successor relation. It is known that these two variants have decidable membership: "does an input regular language belong to the class ?". We rely on a characterization of B{\Sigma}1 by the operator BPol: given an input class C, it outputs a class BPol(C) that corresponds to a variant of B{\Sigma}1 equipped with special predicates associated to C. We extend these results in two orthogonal directions. First, we use two kinds of inputs: classes G of group languages (i.e., recognized by a DFA in which each letter induces a permutation of the states) and extensions thereof, written G+. The classes BPol(G) and BPol(G+) capture many variants of B{\Sigma}1 which use predicates such as the linear ordering, the successor, the modular predicates or the alphabetic modular predicates. Second, instead of membership, we explore the more general separation problem: decide if two regular languages can be separated by a language from the class under study. We show it is decidable for BPol(G) and BPol(G+) when this is the case for G. This was known for BPol(G) and for two particular classes BPol(G+). Yet, the algorithms were indirect and relied on involved frameworks, yielding poor upper complexity bounds. Our approach is direct. We work with elementary concepts (mainly, finite automata). Our main contribution consists in polynomial time Turing reductions from both BPol(G)- and BPol(G+)-separation to G-separation. This yields polynomial algorithms for key variants of B{\Sigma}1, including those equipped with the linear ordering and possibly the successor and/or the modular predicates.

We demonstrate a method to image an object using a self-probing approach based on semiconductor high-harmonic generation. On one hand, ptychography enables high-resolution imaging from the coherent light diffracted by an object. On the other hand, high-harmonic generation from crystals is emerging as a new source of extreme-ultraviolet ultrafast coherent light. We combine these two techniques by performing ptychography measurements with nano-patterned crystals serving as the object as well as the generation medium of the harmonics. We demonstrate that this strong field in situ approach can provide structural information about the object. With the future developments of crystal high harmonics as a compact short-wavelength light source, our demonstration can be an innovative approach for nanoscale imaging of photonic and electronic devices in research and industry.

We study a standard operator on classes of languages: unambiguous polynomial closure. We prove that for every class C of regular languages satisfying mild properties, the membership problem for its unambiguous polynomial closure UPol(C) reduces to the same problem for C. We also show that unambiguous polynomial closure coincides with alternating left and right deterministic closure. Moreover, we prove that if additionally C is finite, the separation and covering problems are decidable for UPol(C). Finally, we present an overview of the generic logical characterizations of the classes built using unambiguous polynomial closure.

Group languages are regular languages recognized by finite groups, or equivalently by finite automata in which each letter induces a permutation on the set of states. We investigate the separation problem for this class of languages: given two arbitrary regular languages as input, we show how to decide if there exists a group language containing the first one while being disjoint from the second. We prove that covering, a problem generalizing separation, is decidable. A simple covering algorithm was already known: it can be obtained indirectly as a corollary of an algebraic theorem by Ash. Unfortunately, while deducing the algorithm from this algebraic result is straightforward, all proofs of Ash's result itself require a strong background on algebraic concepts, and a wealth of technical machinery outside of automata theory. Our proof is independent of previous ones. It relies exclusively on standard notions from automata theory: we directly deal with separation and work with input languages represented by nondeterministic finite automata. We also investigate two strict subclasses. First, the alphabet modulo testable languages are those defined by counting the occurrences of each letter modulo some fixed integer (equivalently, they are the languages recognized by a commutative group). Secondly, the modulo languages are those defined by counting the length of words modulo some fixed integer. We prove that covering is decidable for both classes, with algorithms that rely on the construction made for group languages. Our proofs lead to tight complexity bounds for separation for all three classes, as well as for covering for both alphabet modulo testable languages and for modulo testable languages.

In this note, we consider the wave operator $\square_g$ in the case of globally hyperbolic, compactly supported perturbations of static spacetimes. We give an elementary proof of the essential self-adjointness of $\square_g$ and of uniform microlocal estimates for the resolvent in this setting. This provides a model for studying Lorentzian spectral zeta functions which is particularly simple, yet sufficiently general for locally deriving Einstein equations from a spectral Lagrangian., Comment: 15 pages; v2: typos fixed

The computer network world is changing and the NetDevOps approach has brought the dynamics of applications and systems into the field of communication infrastructure. Businesses are changing and businesses are faced with difficulties related to the diversity of hardware and software that make up those infrastructures. The "Intent-Based Networking - Concepts and Definitions" document describes the different parts of the ecosystem that could be involved in NetDevOps. The recognize, generate intent, translate and refine features need a new way to implement algorithms. This is where artificial intelligence comes in., Comment: 20 pages

We investigate two operators on classes of regular languages: polynomial closure (Pol) and Boolean closure (Bool). We apply these operators to classes of group languages G and to their well-suited extensions G+, which is the least Boolean algebra containing G and the singleton language containing the empty word. This yields the classes Bool(Pol(G)) and Bool(Pol(G+)). These classes form the first level in important classifications of classes of regular languages, called concatenation hierarchies, which admit natural logical characterizations. We present generic algebraic characterizations of these classes. They imply that one may decide whether a regular language belongs to such a class, provided that a more general problem called separation is decidable for the input class G. The proofs are constructive and rely exclusively on notions from language and automata theory.

Given a regular language L, we effectively construct a unary semigroup that recognizes the topological closure of L in the free unary semigroup relative to the variety of unary semigroups generated by the pseudovariety R of all finite R-trivial semigroups. In particular, we obtain a new effective solution of the separation problem of regular languages by R-languages.

We investigate the star-free closure, which associates to a class of languages its closure under Boolean operations and marked concatenation. We prove that the star-free closure of any finite class and of any class of groups languages with decidable separation (plus mild additional properties) has decidable separation. We actually show decidability of a stronger property, called covering. This generalizes many results on the subject in a unified framework. A key ingredient is that star-free closure coincides with another closure operator where Kleene stars are also allowed in restricted contexts.