Episciences.org
Not a member yet
6707 research outputs found
Sort by
A Refined Laser Method and Faster Matrix Multiplication
No full textThe complexity of matrix multiplication is measured in terms of , thesmallest real number such that two matrices can be multiplied using field operations for all ; the best bounduntil now is [Le Gall'14]. All bounds on since 1986have been obtained using the so-called laser method, a way to lower-bound the`value' of a tensor in designing matrix multiplication algorithms. The mainresult of this paper is a refinement of the laser method that improves theresulting value bound for most sufficiently large tensors. Thus, even beforecomputing any specific values, it is clear that we achieve an improved bound on, and we indeed obtain the best bound on to date: The improvement is of the same magnitude as the improvement that [LeGall'14] obtained over the previous bound [Vassilevska W.'12]. Our improvementto the laser method is quite general, and we believe it will have furtherapplications in arithmetic complexity.Comment: 32 pages; TheoretiCS journal versio
Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability
No full textWe show that feasibility of the level of the Lasserresemidefinite programming hierarchy for graph isomorphism can be expressed as ahomomorphism indistinguishability relation. In other words, we define a class of graphs such that graphs and are not distinguished bythe level of the Lasserre hierarchy if and only if they admit thesame number of homomorphisms from any graph in . By analysingthe treewidth of graphs in , we prove that the level of Sherali--Adams linear programming hierarchy is as strong as the level of Lasserre. Moreover, we show that this is best possiblein the sense that cannot be lowered to for any . The same resultholds for the Lasserre hierarchy with non-negativity constraints, which wesimilarly characterise in terms of homomorphism indistinguishability over afamily of graphs. Additionally, we give characterisations oflevel- Lasserre with non-negativity constraints in terms of logicalequivalence and via a graph colouring algorithm akin to the Weisfeiler--Lemanalgorithm. This provides a polynomial time algorithm for determining if twogiven graphs are distinguished by the level of the Lasserrehierarchy with non-negativity constraints.Comment: Full version. 36 pages, 6 figure
Mise en œuvre d’un dispositif expérimental en Bretagne pour sécuriser l’engagement patient dans le partenariat en ETP, au regard de son statut et de la préservation de ses droits sociaux
No full textIn its recommendation to "support and encourage the commitment of users in the social, medico-social and health sectors", the Haute Autorité de Santé (French National Authority for Health) states that "provision should be made for compensation or remuneration for those concerned who make a commitment on behalf of others and to the quality of care and support". Planning: ARS Bretagne, which is supporting this commitment by patients through experiments and the allocation of funding, "has commissioned a working group of patient partners and professionals from 2019 to support the partnership between patients, carers and healthcare professionals in TVE and to define the needs. The principle of remunerating patient partners involved in TVE has been established, subject to the condition that there is no impact on their social entitlements (disability pension, benefits, etc.). In order to ensure that their social security entitlements are maintained if they return to work, some patients who are actively involved with social security bodies (CPAM, MDPH, CAF, Pôle emploi, Cap emploi) have received different or even contradictory responses, depending on the people they talk to and the bodies involved, leaving them in a state of uncertainty and reinforcing their feeling of vulnerability, which has led them to give up getting involved. This project is in response to a call for tenders issued in 2022, with a view to making patient involvement administratively secure. With the creation and free availability of an interactive digital tool since March 2023, partner patients can assess the feasibility of a paid commitment in terms of maintaining their social rights. Training for local resource representatives on the issues raised will begin in January 2024, and will complement this tool with a support approach for partner patients who feel they need it.Outlook: An assessment of this experimental project will be carried out throughout its lifetime to ensure that it meets the needs of partner patients, the reality of the area and the desired partnership.Contexte : La Haute Autorité de Santé, dans sa recommandation à « soutenir et encourager l’engagement des usagers dans les secteurs social, médico-social et sanitaire » précise « de prévoir des modalités d’indemnisation ou de rémunération pour les personnes concernées qui s’engagent pour autrui et pour la qualité des soins et des accompagnements ». Planification : L’ARS Bretagne soutenant cet engagement des patients par le biais d’expérimentation et l’attribution de financements » a missionné, dès 2019, un groupe de travail composé de patients partenaires et de professionnels pour accompagner le partenariat entre patients, aidants et professionnels de santé en ETP et en décliner les besoins. Le principe de la rétribution des patients partenaires intervenant en ETP a été posé, sous conditions du non-impact sur leurs droits sociaux (pension invalidité, allocations, etc.). Afin de s’assurer du maintien de leurs droits sociaux en cas de reprise d’activité, certains patients pro actifs auprès des organismes sociaux (CPAM, MDPH, CAF, Pôle emploi, Cap emploi) ont, selon les interlocuteurs et les organismes, reçus des réponses différentes voire contradictoires, les laissant dans une incertitude renforçant ainsi un sentiment de vulnérabilité et les amenant à renoncer à s’engager. Ce projet répond à un appel d’offre de 2022, en vue de sécuriser administrativement l’implication des patients. Par la création et la mise à disposition gratuite d’un support numérique interactif depuis mars 2023, les patients partenaires peuvent évaluer la faisabilité d’un engagement rétribué au regard du maintien de leurs droits sociaux. Une formation de représentants locaux-ressources sur les questions évoquées, débutera en janvier 2024, et viendra compléter cet outil d’une démarche d’accompagnement à destination des patients partenaires qui en sentiraient le besoin. Perspectives : Un bilan de ce projet expérimental sera conduit tout au long de son activité afin de s’assurer qu’il réponde aux besoins des patients partenaires, à la réalité du territoire et au partenariat souhaité
Homotopy Theoretic and Categorical Models of Neural Information Networks
No full textIn this paper we develop a novel mathematical formalism for the modeling ofneural information networks endowed with additional structure in the form ofassignments of resources, either computational or metabolic or informational.The starting point for this construction is the notion of summing functors andof Segal's Gamma-spaces in homotopy theory. The main results in this paperinclude functorial assignments of concurrent/distributed computingarchitectures and associated binary codes to networks and their subsystems, acategorical form of the Hopfield network dynamics, which recovers the usualHopfield equations when applied to a suitable category of weighted codes, afunctorial assignment to networks of corresponding information structures andinformation cohomology, and a cohomological version of integrated information.Comment: published version: 86 pages LaTe
Faster parameterized algorithms for modification problems to minor-closed classes
No full textLet be a minor-closed graph class and let be an -vertexgraph. We say that is a -apex of if contains a set ofat most vertices such that belongs to . Our firstresult is an algorithm that decides whether is a -apex of intime , where is a polynomial functiondepending on . This algorithm improves the previous one, given bySau, Stamoulis, and Thilikos [ICALP 2020], whose running time was 2^{{\sfpoly}(k)}\cdot n^3. The elimination distance of to , denoted by, is the minimum number of rounds required to reduce eachconnected component of to a graph in by removing one vertex fromeach connected component in each round. Bulian and Dawar [Algorithmica 2017]provided an FPT-algorithm, with parameter , to decide whether {\sfed}_{\cal G}(G)\leq k. However, its dependence on is not explicit. Weextend the techniques used in the first algorithm to decide whether {\sfed}_{\cal G}(G)\leq k in time . This isthe first algorithm for this problem with an explicit parametric dependence in. In the special case where excludes some apex-graph as a minor,we give two alternative algorithms, running in time 2^{2^{{\cal O}(k^2\logk)}}\cdot n^2 and respectively, where and depend on . As a stepping stone for these algorithms, weprovide an algorithm that decides whether in time, where is the treewidth of . Finally, we provide explicit upper bounds on the sizeof the graphs in the minor-obstruction set of the class of graphs {\calE}_k({\cal G})=\{G\mid{\sf ed}_{\cal G}(G)\leq k\}.Comment: 75 pages. TheoretiCS journal article. Abstract abbreviated to fit arXiv limitatio
On 2nd-order fully-nonlinear equations with links to 3rd-order fully-nonlinear equations
No full textWe derive the general conditions for fully-nonlinear symmetry-integrablesecond-order evolution equations and their first-order recursion operators. Wethen apply the established Propositions to find links between a class offully-nonlinear third-order symmetry-integrable evolution equations andfully-nonlinear second-order symmetry-integrable evolution equations.Comment: 12 page
Coalgebraic Satisfiability Checking for Arithmetic -Calculi
No full textThe coalgebraic -calculus provides a generic semantic framework forfixpoint logics over systems whose branching type goes beyond the standardrelational setup, e.g. probabilistic, weighted, or game-based. Previous work onthe coalgebraic -calculus includes an exponential-time upper bound onsatisfiability checking, which however relies on the availability of tableaurules for the next-step modalities that are sufficiently well-behaved in aformally defined sense; in particular, rule matches need to be representable bypolynomial-sized codes, and the sequent duals of the rules need to absorb cut.While such rule sets have been identified for some important cases, they arenot known to exist in all cases of interest, in particular ones involvingeither integer weights as in the graded -calculus, or real-valued weightsin combination with non-linear arithmetic. In the present work, we prove thesame upper complexity bound under more general assumptions, specificallyregarding the complexity of the (much simpler) satisfiability problem for theunderlying one-step logic, roughly described as the nesting-free next-stepfragment of the logic. The bound is realized by a generic global cachingalgorithm that supports on-the-fly satisfiability checking. Notably, ourapproach directly accommodates unguarded formulae, and thus avoids use of theguardedness transformation. Example applications include new exponential-timeupper bounds for satisfiability checking in an extension of the graded-calculus with polynomial inequalities (including positive Presburgerarithmetic), as well as an extension of the (two-valued) probabilistic-calculus with polynomial inequalities
A Note on Graph Burning of Path Forests
No full textGraph burning is a natural discrete graph algorithm inspired by the spread ofsocial contagion. Despite its simplicity, some open problems remain steadfastlyunsolved, notably the burning number conjecture, which says that everyconnected graph of order has burning number at most . Earlier, weshowed that the conjecture also holds for a path forest, which is disconnected,provided each of its paths is sufficiently long. However, finding the leastsufficient length for this to hold turns out to be nontrivial. In this note, wepresent our initial findings and conjectures that associate the problem to somenaturally impossibly burnable path forests. It is noteworthy that our problemcan be reformulated as a topic concerning sumset partition of integers.Comment: Accepted and published by DMTC
Profunctor Optics, a Categorical Update
No full textOptics are bidirectional data accessors that capture data transformationpatterns such as accessing subfields or iterating over containers. Profunctoroptics are a particular choice of representation supporting modularity, meaningthat we can construct accessors for complex structures by combining simplerones. Profunctor optics have previously been studied only in an unenriched andnon-mixed setting, in which both directions of access are modelled in the samecategory. However, functional programming languages are arguably betterdescribed by enriched categories; and we have found that some structures in theliterature are actually mixed optics, with access directions modelled indifferent categories. Our work generalizes a classic result by Pastro andStreet on Tambara theory and uses it to describe mixed V-enriched profunctoroptics and to endow them with V-category structure. We provide some originalfamilies of optics and derivations, including an elementary one for traversals.Finally, we discuss a Haskell implementation.Comment: 38 pages. Final version with Compositionality metadata, does not change theorem numberin
Encodability Criteria for Quantum Based Systems
No full textQuantum based systems are a relatively new research area for that differentmodelling languages including process calculi are currently under development.Encodings are often used to compare process calculi. Quality criteria are usedthen to rule out trivial or meaningless encodings. In this new context ofquantum based systems, it is necessary to analyse the applicability of thesequality criteria and to potentially extend or adapt them. As a first step, wetest the suitability of classical criteria for encodings between quantum basedlanguages and discuss new criteria. Concretely, we present an encoding, from alanguage inspired by CQP into a language inspired by qCCS. We show that thisencoding satisfies compositionality, name invariance (for channel and qubitnames), operational correspondence, divergence reflection, successsensitiveness, and that it preserves the size of quantum registers. Then weshow that there is no encoding from qCCS into CQP that is compositional,operationally corresponding, and success sensitive