Episciences.org
Not a member yet
6707 research outputs found
Sort by
Carrières d’algorithmes : la détection automatique de motifs dans des graphes (années 1950–1970). Contribution à l’histoire des premiers apports des sciences sociales à l’informatique
No full textPlutniak, Sébastien. 2021. “Assyrian Merchants meet Nuclear Physicists: History of the Early Contributions from Social Sciences to Computer Science. The Case of Automatic Pattern Detection in Graphs (1950s–1970s)”, Interdisciplinary Science Reviews, 46, 4, p. 547-568, doi: 10.1080/03080188.2021.1877502.La détection de communautés est une question centrale en analyse de réseaux. Cet article combine une approche socio-historique à la reconstruction expérimentale de programmes informatiques afin d'éclairer l'histoire des premiers algorithmes de détection de cliques, problème qui compte encore aujourd'hui parmi les problèmes NP-complets non résolus. Restituer les recherches menées par l'archéologue Jean-Claude Gardin depuis les années 1950 sur le traitement de l'information non numérique et l'analyse de graphes met en évidence ces contributions précoces à l'informatique réalisées depuis les sciences humaines et sociales. Ces applications originales de l'informatique aux humanités ont reçu une réception et une reconnaissance limitées. Ce fait est éclairé par deux facteurs : 1) les politiques de financement, qui ont motivé le transfert des efforts de recherche sur les graphes depuis un éphémère espace interdisciplinaire vers des organisations de recherche en informatique, domaine alors émergent ; 2) les carrières erratiques des algorithmes, où l'efficacité, les erreurs, les corrections et le statut des auteurs ont été des facteurs déterminants. Ces facteurs se combinent aux effets des historiographies et des bibliographies sur la conservation, la découvrabilité et la réutilisation des résultats scientifiques
Inapproximability of Unique Games in Fixed-Point Logic with Counting
No full textWe study the extent to which it is possible to approximate the optimal valueof a Unique Games instance in Fixed-Point Logic with Counting (FPC). Formally,we prove lower bounds against the accuracy of FPC-interpretations that mapUnique Games instances (encoded as relational structures) to rational numbersgiving the approximate fraction of constraints that can be satisfied. We provetwo new FPC-inexpressibility results for Unique Games: the existence of a-inapproximability gap, and inapproximability to withinany constant factor. Previous recent work has established similarFPC-inapproximability results for a small handful of other problems. Ourconstruction builds upon some of these ideas, but contains a novel technique.While most FPC-inexpressibility results are based on variants of theCFI-construction, ours is significantly different. We start with a graph ofvery large girth and label the edges with random affine vector spaces over that determine the constraints in the two structures.Duplicator's strategy involves maintaining a partial isomorphism over a minimaltree that spans the pebbled vertices of the graph.Comment: arXiv admin note: text overlap with arXiv:2008.0311
A Fibrational Tale of Operational Logical Relations: Pure, Effectful and Differential
No full textLogical relations built on top of an operational semantics are one of themost successful proof methods in programming language semantics. In recentyears, more and more expressive notions of operationally-based logicalrelations have been designed and applied to specific families of languages.However, a unifying abstract framework for operationally-based logicalrelations is still missing. We show how fibrations can provide a uniformtreatment of operational logical relations, using as reference example alambda-calculus with generic effects endowed with a novel, abstract operationalsemantics defined on a large class of categories. Moreover, this abstractperspective allows us to give a solid mathematical ground also to differentiallogical relations -- a recently introduced notion of higher-order distancebetween programs -- both pure and effectful, bringing them back to a commonpicture with traditional ones
Filtered formal groups, Cartier duality, and derived algebraic geometry
No full textWe develop a notion of formal groups in the filtered setting and describe aduality relating these to a specified class of filtered Hopf algebras. We thenstudy a deformation to the normal cone construction in the setting of derivedalgebraic geometry. Applied to the unit section of a formal group, this provides a -equivariant degenerationof to its tangent Lie algebra. We prove a unicity resulton complete filtrations, which, in particular, identifies the resultingfiltration on the coordinate algebra of this deformation with the adicfiltration on the coordinate algebra of . We use this ina special case, together with the aforementioned notion of Cartier duality, torecover the filtration on the filtered circle of [MRT19]. Finally, weinvestigate some properties of -Hochschild homology setout in loc. cit., and describe "lifts" of these invariants to the setting ofspectral algebraic geometry.Comment: Publication versio
Two sufficient conditions for graphs to admit path factors
No full textLet be a set of connected graphs. Then a spanning subgraph of is called an -factor if each component of is isomorphicto some member of . Especially, when every graph in is a path, is a path factor. For a positive integer , we write. Then a -factormeans a path factor in which every component admits at least vertices. Agraph is called a -factor deleted graph if admits a -factor for any with. A graph is called a -factor criticalgraph if has a -factor for any with . In this paper, we present two degree conditions for graphs to be-factor deleted graphs and-factor critical graphs. Furthermore, we show that thetwo results are best possible in some sense.Comment: 11 page
Contact graphs of boxes with unidirectional contacts
No full textThis paper is devoted to the study of particular geometrically definedintersection classes of graphs. Those were previously studied by Magnant andMartin, who proved that these graphs have arbitrary large chromatic number,while being triangle-free. We give several structural properties of thesegraphs, and we raise several questions.Comment: Minor chang
Node Replication: Theory And Practice
No full textWe define and study a term calculus implementing higher-order nodereplication. It is used to specify two different (weak) evaluation strategies:call-by-name and fully lazy call-by-need, that are shown to be observationallyequivalent by using type theoretical technical tools
Offline and online energy-efficient monitoring of scattered uncertain logs using a bounding model
No full textMonitoring the correctness of distributed cyber-physical systems isessential. Detecting possible safety violations can be hard when some samplesare uncertain or missing. We monitor here black-box cyber-physical system, withlogs being uncertain both in the state and timestamp dimensions: that is, notonly the logged value is known with some uncertainty, but the time at which thelog was made is uncertain too. In addition, we make use of an over-approximatedyet expressive model, given by a non-linear extension of dynamical systems.Given an offline log, our approach is able to monitor the log against safetyspecifications with a limited number of false alarms. As a second contribution,we show that our approach can be used online to minimize the number of sampletriggers, with the aim at energetic efficiency. We apply our approach to threebenchmarks, an anesthesia model, an adaptive cruise controller and an aircraftorbiting system
Generalizations of quasielliptic curves
No full textWe generalize the notion of quasielliptic curves, which have infinitesimalsymmetries and exist only in characteristic two and three, to a remarkablehierarchy of regular curves having infinitesimal symmetries, defined in allcharacteristics and having higher genera. This relies on the study of certaininfinitesimal group schemes acting on the affine line and certaincompactifications. The group schemes are defined in terms of invertibleadditive polynomials over rings with nilpotent elements, and thecompactification is constructed with the theory of numerical semigroups. Theexistence of regular twisted forms relies on Brion's recent theory ofequivariant normalization. Furthermore, extending results of Serre from therealm of group cohomology, we describe non-abelian cohomology for semidirectproducts, to compute in special cases the collection of all twisted forms.Comment: 31 page
Linear-time logics -- a coalgebraic perspective
No full textWe describe a general approach to deriving linear-time logics for a widevariety of state-based, quantitative systems, by modelling the latter ascoalgebras whose type incorporates both branching and linear behaviour.Concretely, we define logics whose syntax is determined by the type of linearbehaviour, and whose domain of truth values is determined by the type ofbranching behaviour, and we provide two semantics for them: a step-wisesemantics akin to that of standard coalgebraic logics, and a path-basedsemantics akin to that of standard linear-time logics. The former semantics isuseful for model checking, whereas the latter is the more natural semantics, asit measures the extent with which qualitative properties hold along computationpaths from a given state. Our main result is the equivalence of the twosemantics. We also provide a semantic characterisation of a notion of logicaldistance induced by these logics. Instances of our logics support reasoningabout the possibility, likelihood or minimal cost of exhibiting a givenlinear-time property