Episciences.org
Not a member yet
6707 research outputs found
Sort by
Godement-Jacquet L-function, some conjectures and some consequences
No full textIn this paper, we investigate the mean square estimate for the logarithmic derivative of the Godement--Jacquet -function assuming the Riemann hypothesis for and Rudnick--Sarnak conjecture
Free Commutative Monoids in Homotopy Type Theory
No full textWe develop a constructive theory of finite multisets in Homotopy Type Theory,defining them as free commutative monoids. After recalling basic structuralproperties of the free commutative-monoid construction, we formalise andestablish the categorical universal property of two, necessarily equivalent,algebraic presentations of free commutative monoids using 1-HITs. Thesepresentations correspond to two different equational theories invariablyincluding commutation axioms. In this setting, we prove important structuralcombinatorial properties of finite multisets. These properties are establishedin full generality without assuming decidable equality on the carrier set. As an application, we present a constructive formalisation of the relationalmodel of classical linear logic and its differential structure. This leads toconstructively establishing that free commutative monoids are conicalrefinement monoids. Thereon we obtain a characterisation of the equality typeof finite multisets and a new presentation of the free commutative-monoidconstruction as a set-quotient of the list construction. These developmentscrucially rely on the commutation relation of creation/annihilation operatorsassociated with the free commutative-monoid construction seen as acombinatorial Fock space.Comment: Appeared in MFPS'2
Continuous Functions on Final Comodels of Free Algebraic Theories
No full textIn 2009, Ghani, Hancock and Pattinson gave a tree-like representation ofstream processors . In 2021, Garnershowed that this representation can be established in terms of algebraic theoryand comodels: the set of infinite streams is the final comodelof the algebraic theory of -valued input and the set ofstream processors can be seen asthe final --bimodel. In this paper, we generalizeGarner's results to the case of free algebraic theories.Comment: 17 page
The -space
No full textIn this paper, we introduce the concept of -spaces. We find thatstrong -spaces are -spaces, but the converse does not hold. Wegive a characterization for a topological space to be a -space. Weprove that the retract of a -space is a -space. We obtainthe result that for any space and , if the function space endowed with the Isbell topology is a -space, then isa -space. We also show that for any space , if the Smythpower space is a -space, then is a -space.Meanwhile, we give a counterexample to illustrate that conversely, for a-space , the Smyth power space may not be a-space
Quantaloidal Completions of Order-enriched Categories and Their Applications
No full textBy introducing the concept of quantaloidal completions for an order-enrichedcategory, relationships between the category of quantaloids and the category oforder-enriched categories are studied. It is proved that quantaloidalcompletions for an order-enriched category can be fully characterized ascompatible quotients of the power-set completion. As applications, we show thata special type of injective hull of an order-enriched category is the MacNeillecompletion; the free quantaloid over an order-enriched category is the Down-setcompletion
Subgame-perfect Equilibria in Mean-payoff Games (journal version)
No full textIn this paper, we provide an effective characterization of all thesubgame-perfect equilibria in infinite duration games played on finite graphswith mean-payoff objectives. To this end, we introduce the notion ofrequirement, and the notion of negotiation function. We establish that theplays that are supported by SPEs are exactly those that are consistent with afixed point of the negotiation function. Finally, we use that characterizationto prove that the SPE threshold problem, who status was left open in theliterature, is decidable.Comment: arXiv admin note: substantial text overlap with arXiv:2101.1068
Brooks' Theorem in Graph Streams: A Single-Pass Semi-Streaming Algorithm for -Coloring
No full textEvery graph with maximum degree can be colored with colors using a simple greedy algorithm. Remarkably, recent work has shown thatone can find such a coloring even in the semi-streaming model. But, in reality,one almost never needs colors to properly color a graph. Indeed,the celebrated \Brooks' theorem states that every (connected) graph besidecliques and odd cycles can be colored with colors. Can we find a-coloring in the semi-streaming model as well? We settle this key question in the affirmative by designing a randomizedsemi-streaming algorithm that given any graph, with high probability, eithercorrectly declares that the graph is not -colorable or outputs a-coloring of the graph. The proof of this result starts with a detour. We first (provably) identifythe extent to which the previous approaches for streaming coloring fail for-coloring: for instance, all these approaches can handle streams withrepeated edges and they can run in time -- we prove that neither ofthese tasks is possible for -coloring. These impossibility resultshowever pinpoint exactly what is missing from prior approaches when it comes to-coloring. We then build on these insights to design a semi-streaming algorithm thatuses a novel sparse-recovery approach based on sparse-densedecompositions to (partially) recover the "problematic" subgraphs of the input-- the ones that form the basis of our impossibility results -- and anew coloring approach for these subgraphs that allows for recoloring of othervertices in a controlled way without relying on local explorations or finding"augmenting paths" that are generally impossible for semi-streaming algorithms.We believe both these techniques can be of independent interest.Comment: Journal version in TheoretiCS. An extended abstract appeared in STOC 2022. 66 pages, 10 figure
Extended Addressing Machines for PCF, with Explicit Substitutions
No full textAddressing machines have been introduced as a formalism to construct modelsof the pure, untyped lambda-calculus. We extend the syntax of their programs byadding instructions for executing arithmetic operations on natural numbers, andintroduce a reflection principle allowing certain machines to access their ownaddress and perform recursive calls. We prove that the resulting extendedaddressing machines naturally model a weak call-by-name PCF with explicitsubstitutions. Finally, we show that they are also well-suited for representingregular PCF programs (closed terms) computing natural numbers.Comment: 16 pages, 5 pages appendi
Torus Actions on Quotients of Affine Spaces
No full textWe study the locus of fixed points of a torus action on a GIT quotient of acomplex vector space by a reductive complex algebraic group which actslinearly. We show that, under the assumption that acts freely on the stablelocus, the components of the fixed point locus are again GIT quotients oflinear subspaces by Levi subgroups.Comment: 19 pages, comments are welcome; v2: Eliminated an assumption in the main result, expanded applications section; v3: Final versio
Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries
No full textWe investigate trade-offs in static and dynamic evaluation of hierarchicalqueries with arbitrary free variables. In the static setting, the trade-off isbetween the time to partially compute the query result and the delay needed toenumerate its tuples. In the dynamic setting, we additionally consider the timeneeded to update the query result under single-tuple inserts or deletes to thedatabase. Our approach observes the degree of values in the database and uses differentcomputation and maintenance strategies for high-degree (heavy) and low-degree(light) values. For the latter it partially computes the result, while for theformer it computes enough information to allow for on-the-fly enumeration. We define the preprocessing time, the update time, and the enumeration delayas functions of the light/heavy threshold. By appropriately choosing thisthreshold, our approach recovers a number of prior results when restricted tohierarchical queries. We show that for a restricted class of hierarchical queries, our approachachieves worst-case optimal update time and enumeration delay conditioned onthe Online Matrix-Vector Multiplication Conjecture