Search

Graph sparsification underlies a large number of algorithms, ranging from approximation algorithms for cut problems to solvers for linear systems in the graph Laplacian. In its strongest form, "spectral sparsification" reduces the number of edges to near-linear in the number of nodes, while approximately preserving the cut and spectral structure of the graph. In this work we demonstrate a polynomial quantum speedup for spectral sparsification and many of its applications. In particular, we give a quantum algorithm that, given a weighted graph with $n$ nodes and $m$ edges, outputs a classical description of an $\epsilon$-spectral sparsifier in sublinear time $\tilde{O}(\sqrt{mn}/\epsilon)$. This contrasts with the optimal classical complexity $\tilde{O}(m)$. We also prove that our quantum algorithm is optimal up to polylog-factors. The algorithm builds on a string of existing results on sparsification, graph spanners, quantum algorithms for shortest paths, and efficient constructions for $k$-wise independent random strings. Our algorithm implies a quantum speedup for solving Laplacian systems and for approximating a range of cut problems such as min cut and sparsest cut., Comment: v2: several small improvements to the text. An extended abstract will appear in FOCS'20; v3: corrected a minor mistake in Appendix A; v4: final version as published in SICOMP

We present epistemic multilateral logic, a general logical framework for reasoning involving epistemic modality. Standard bilateral systems use propositional formulae marked with signs for assertion and rejection. Epistemic multilateral logic extends standard bilateral systems with a sign for the speech act of weak assertion (Incurvati & Schlöder, 2019) and an operator for epistemic modality. We prove that epistemic multilateral logic is sound and complete with respect to the modal logic $\mathbf {S5}$ modulo an appropriate translation. The logical framework developed provides the basis for a novel, proof-theoretic approach to the study of epistemic modality. To demonstrate the fruitfulness of the approach, we show how the framework allows us to reconcile classical logic with the contradictoriness of so-called Yalcin sentences and to distinguish between various inference patterns on the basis of the epistemic properties they preserve.

This manuscript presents a topological argumentation framework for modelling notions of evidence-based (i.e., justified) belief. Our framework relies on so-called topological evidence models to represent the pieces of evidence that an agent has at her disposal, and it uses abstract argumentation theory to select the pieces of evidence that the agent will use to define her beliefs. The tools from abstract argumentation theory allow us to model agents who make decisions in the presence of contradictory information. Thanks to this, it is possible to define two new notions of beliefs, grounded beliefs and fully grounded beliefs. These notions are discussed in this paper, analysed and compared with the existing notion of topological justified belief. This comparison revolves around three main issues: closure under conjunction introduction, the level of consistency and their logical strength.

The problem of lifting a preference order on a set of objects to a preference order on a family of subsets of this set is a fundamental problem with a wide variety of applications in AI. The process is often guided by axioms postulating properties the lifted order should have. Well-known impossibility results by Kannai and Peleg and by Barbera and Pattanaik tell us that some desirable axioms – namely dominance and (strict) independence – are not jointly satisfiable for any linear order on the objects if all non-empty sets of objects are to be ordered. On the other hand, if not all non-empty sets of objects are to be ordered, the axioms are jointly satisfiable for all linear orders on the objects for some families of sets. Such families are very important for applications as they allow for the use of lifted orders, for example, in combinatorial voting. In this paper, we determine the computational complexity of recognizing such families. We show that it is \Pi_2^p-complete to decide for a given family of subsets whether dominance and independence or dominance and strict independence are jointly satisfiable for all linear orders on the objects if the lifted order needs to be total. Furthermore, we show that the problem remains coNP-complete if the lifted order can be incomplete. Additionally, we show that the complexity of these problems can increase exponentially if the family of sets is not given explicitly but via a succinct domain restriction. Finally, we show that it is NP-complete to decide for a family of subsets whether dominance and independence or dominance and strict independence are jointly satisfiable for at least one linear order on the objects.

In recent years, there has been a surge in interest in using natural language processing (NLP) applications for clinical psychology and psychiatry. Despite the increased societal, economic, and academic interest, there has been no systematic critical analysis of the recent progress in NLP applications for mental disorders, or of the resources available for training and evaluating such systems.This chapter addresses this gap through two main contributions. First, it provides an overview of the NLP literature related to mental disorders, with a focus on autism, dyslexia, schizophrenia, depression and mental health in general. We discuss the strengths and shortcomings of current methodologies, specifically focusing on the challenges in obtaining large volumes of high-quality domain-specific data both for English and for lower-resource languages. We also provide a list of datasets publicly available for researchers who would like to develop NLP methods for specific mental disorders, categorized according to relevant criteria such as data source, language, annotation, and size. Our second contribution is a discussion on how to support the application of these methods to various languages and social contexts. This includes recommendations on conducting robust and ethical experiments from a machine learning perspective, and a discussion on how techniques such as cross-lingual transfer learning could be applied within this area.

We propose a new model for forming and revising beliefs about unknown probabilities. To go beyond what is known with certainty and represent the agent’s beliefs about probability, we consider a plausibility map, associating to each possible distribution a plausibility ranking. Beliefs are defined as in Belief Revision Theory, in terms of truth in the most plausible worlds (or more generally, truth in all the worlds that are plausible enough). We consider two forms of conditioning or belief update, corresponding to the acquisition of two types of information: (1) learning observable evidence obtained by repeated sampling from the unknown distribution; and (2) learning higher-order information about the distribution. The first changes only the plausibility map (via a ‘plausibilistic’ version of Bayes’ Rule), but leaves the given set of possible distributions essentially unchanged; the second rules out some distributions, thus shrinking the set of possibilities, without changing their plausibility ordering.. We look at stability of beliefs under either of these types of learning, defining two related notions (safe belief and statistical knowledge), as well as a measure of the verisimilitude of a given plausibility model. We prove a number of convergence results, showing how our agent’s beliefs track the true probability after repeated sampling, and how she eventually gains in a sense (statistical) knowledge of that true probability. Finally, we sketch the contours of a dynamic doxastic logic for statistical learning.

We answer the question of which conjunctive queries are uniquely characterized by polynomially many positive and negative examples, and how to construct such examples efficiently. As a consequence, we obtain a new efficient exact learning algorithm for a class of conjunctive queries. At the core of our contributions lie two new polynomial-time algorithms for constructing frontiers in the homomorphism lattice of finite structures. We also discuss implications for the unique characterizability and learnability of schema mappings and of description logic concepts., LIPIcs, Vol. 186, 24th International Conference on Database Theory (ICDT 2021), pages 9:1-9:24

This paper presents a simple decidable logic of functional dependence LFD, based on an extension of classical propositional logic with dependence atoms plus dependence quantifiers treated as modalities, within the setting of generalized assignment semantics for first order logic. The expressive strength, complete proof calculus and meta-properties of LFD are explored. Various language extensions are presented as well, up to undecidable modal-style logics for independence and dynamic logics of changing dependence models. Finally, more concrete settings for dependence are discussed: continuous dependence in topological models, linear dependence in vector spaces, and temporal dependence in dynamical systems and games., 56 pages. Journal of Philosophical Logic (2021)

The 2021 edition of AAMAS, the International Conference on Autonomous Agents and Multiagent Systems, took place from the 3rd to 7th of May 2021 (aamas2021.soton.ac.uk). This year it was organized in the form of a virtual event and attracted over 1,000 registered participants. As every year, the conference featured an exciting programme of contributed talks, keynotes addresses, tutorials, affiliated workshops, a doctoral consortium, and more.

Funder: studienstiftung des deutschen volkes; doi: http://dx.doi.org/10.13039/501100004350, Funder: Prins Bernhard Cultuurfonds, How many correct logics are there? Monists endorse that there is one, pluralists argue for many, and nihilists claim that there are none. Reasoning about these views requires a logic. That is the meta-logic. It turns out that there are some meta-logical challenges specifically for the pluralists. I will argue that these depend on an implicitly assumed absoluteness of correct logic. Pluralists can solve the challenges by giving up on this absoluteness and instead adopt contextualism about correct logic. This contextualism is naturalistically appealing.

In the context of aggregating intervals reflecting the views of several agents into a single interval, we investigate the impact of the form of representation chosen for the intervals involved. Specifically, we ask whether there are natural rules we can define both as rules that aggregate separately the left and right endpoints of intervals and as rules that aggregate separately the left endpoints and the interval widths. We show that on discrete scales it is essentially impossible to do so, while on continuous scales we can characterise the rules meeting these requirements as those that compute a weighted average of the endpoints of the individual intervals.

Restricted domains over voter preferences have been extensively studied within the area of computational social choice, initially for preferences that are total orders over the set of alternatives and subsequently for preferences that are dichotomous—i.e., that correspond to approved and disapproved alternatives. This paper contributes to the latter stream of work in a twofold manner. First, we obtain forbidden subprofile characterisations for various important dichotomous domains. Then, we are concerned with incomplete profiles that may arise in many real-world scenarios, where we have partial information about the voters’ preferences. We tackle the problem of determining whether an incomplete profile admits a completion within a certain restricted domain and design constructive, polynomial algorithms to that effect.

Condorcet extensions have long held a prominent place in social choice theory. A Condorcet extension will return the Condorcet winner as the unique winner whenever such an alternative exists. However, the definition of a Condorcet extension does not take into account possible manipulation by the voters. A profile where all agents vote truthfully may have a Condorcet winner, but this alternative may not end up in the set of winners if agents are acting strategically. Focusing on the class of tournament solutions, we show that many natural social choice functions in this class, such as the well-known Copeland and Slater rules, cannot guarantee the preservation of Condorcet winners when agents behave strategically. Our main result in this respect is an impossibility theorem that establishes that no tournament solution satisfying a very weak decisiveness requirement can provide such a guarantee. On the bright side, we identify several indecisive but otherwise attractive tournament solutions that do guarantee the preservation of Condorcet winners under strategic manipulation for a large class of preference extensions.

We provide a wide-ranging study of the scenario where a subset of the relations in a relational vocabulary is visible to a user—that is, their complete contents are known—while the remaining relations are invisible. We also have a background theory—invariants given by logical sentences—that may relate the visible relations to invisible ones, and also may constrain both the visible and invisible relations in isolation. We want to determine whether some other information, given as a positive existential formula, can be inferred using only the visible information and the background theory. This formula whose inference we are concerned with is denoted as the query . We consider whether positive information about the query can be inferred, and also whether negative information—the sentence does not hold—can be inferred. We further consider both the instance-level version of the problem, where both the query and the visible instance are given, and the schema-level version, where we want to know whether truth or falsity of the query can be inferred in some instance of the schema.

We prove that the modal logic of a crowded locally compact generalized ordered space is $\textsf {S4}$ . This provides a version of the McKinsey–Tarski theorem for generalized ordered spaces. We then utilize this theorem to axiomatize the modal logic of an arbitrary locally compact generalized ordered space.

In this paper, we explain why the antecedent of a biscuit conditional is relevant to its consequent by extending Douvenʼs evidential support theory of conditionals making use of utilities. By this extension, we can also explain why a biscuit conditional gives rise to the inference that the consequence is (most likely) true. Finally, we account for the intuition that (indicative) biscuit sentences are false when the antecedent is false and allow for counterfactual biscuits.

We prove that the existence of a measurable cardinal is equivalent to the existence of a normal space whose modal logic coincides with the modal logic of the Kripke frame isomorphic to the powerset of a two element set.

Software-controlled bots, also called social bots, are computer programs that act like human users on social media platforms. Recent work on detection of social bots is dominated by machine learning approaches. In this paper we explore bot detection as a model checking problem. We introduce Temporal Network Logic (TNL) which we use to specify social networks where agents can post and follow each other. In this logic we formalize different types of social bot behavior. These are formulas that are satisfied in a model of a network with bots. We provide a simple algorithm to extract a logical model from a real-life social network. We show that we can reduce TNL to a fragment of linear temporal logic with past and use this to establish the computational efficiency of model checking for social bot detection.

In recent work, Stalnaker proposes a logical framework in which belief is realized as a weakened form of knowledge. Building on Stalnaker's core insights, and using frameworks developed in previous work by Bjorndahl and Baltag et al., we employ topological tools to refine and, we argue, improve on this analysis. The structure of topological subset spaces allows for a natural distinction between what is known and (roughly speaking) what is knowable; we argue that the foundational axioms of Stalnaker's system rely intuitively on both of these notions. More precisely, we argue that the plausibility of the principles Stalnaker proposes relating knowledge and belief relies on a subtle equivocation between an "evidence-in-hand" conception of knowledge and a weaker "evidence-out-there" notion of what could come to be known. Our analysis leads to a trimodal logic of knowledge, knowability, and belief interpreted in topological subset spaces in which belief is definable in terms of knowledge and knowability. We provide a sound and complete axiomatization for this logic as well as its uni-modal belief fragment. We then consider weaker logics that preserve suitable translations of Stalnaker's postulates, yet do not allow for any reduction of belief. We propose novel topological semantics for these irreducible notions of belief, generalizing our previous semantics, and provide sound and complete axiomatizations for the corresponding logics., Comment: 26 pages

In this paper, we investigate the semantics and logic of choice-driven counterfactuals, that is, of counterfactuals whose evaluation relies on auxiliary premises about how agents are expected to act, i.e., about their default choice behavior. To do this, we merge one of the most prominent logics of agency in the philosophical literature, namely stit logic (Belnap et al. 2001; Horty 2001), with the well-known logic of counterfactuals due to Stalnaker (1968) and Lewis (1973). A key component of our semantics for counterfactuals is to distinguish between deviant and non-deviant actions at a moment, where an action available to an agent at a moment is deviant when its performance does not agree with the agent’s default choice behavior at that moment. After developing and axiomatizing a stit logic with action types, instants, and deviant actions, we study the philosophical implications and logical properties of two candidate semantics for choice-driven counterfactuals, one called rewind models inspired by Lewis (Nous13(4), 455–476 1979) and the other called independence models motivated by well-known counterexamples to Lewis’s proposal Slote (Philos. Rev.87(1), 3–27 1978). In the last part of the paper we consider how to evaluate choice-driven counterfactuals at moments arrived at by some agents performing a deviant action.

The switch Markov chain has been extensively studied as the most natural Markov chain Monte Carlo approach for sampling graphs with prescribed degree sequences. We show that the switch chain for sampling simple undirected graphs with a given degree sequence is rapidly mixing when the degree sequence is so-called strongly stable. Strong stability is satisfied by all degree sequences for which the switch chain was known to be rapidly mixing based on Sinclair's multicommodity flow method up until a recent manuscript of Erdős and coworkers in 2019. Our approach relies on an embedding argument, involving a Markov chain defined by Jerrum and Sinclair in 1990. This results in a much shorter proof that unifies (almost) all the rapid mixing results for the switch chain in the literature, and extends them up to sharp characterizations of P-stable degree sequences. In particular, our work resolves an open problem posed by Greenhill and Sfragara in 2017.

The celebrated van Benthem characterization theorem states that on Kripke structures modal logic is the bisimulation-invariant fragment of first-order logic. In this paper, we prove an analogue of the van Benthem characterization theorem for models based on descriptive general frames. This is an important class of general frames for which every modal logic is complete. These frames can be represented as Stone spaces equipped with a ‘continuous’ binary relation. The proof of our theorem generalizes Rosen’s proof of the van Benthem theorem for finite frames and uses as an essential technique a new notion of descriptive unravelling. We also develop a basic model theory for descriptive general frames and show that in many ways it behaves like the model theory of finite structures. In particular, we prove the failure of the compactness theorem, of the Beth definability theorem, of the Craig interpolation theorem and of the upward Löwenheim–Skolem theorem.1

Information exchange can be viewed as a process of asking questions and answering them. While dynamic epistemic logic traditionally focuses on statements, recent developments have been concerned with ways of incorporating questions. One approach, based on the framework of inquisitive semantics, is inquisitive dynamic epistemic logic ( $$\textsf {IDEL}$$ ). In this system, agents are represented with issues as well as information. On the dynamic level, it can model actions that raise new issues. Compared to other approaches, a limitation of $$\textsf {IDEL}$$ is that it can only encode public announcements. $$\textsf {IDEL}$$ can be refined to encode private questions, by merging its static basis, inquisitive epistemic logic ( $$\textsf {IEL}$$ ), with action model logic ( $$\textsf {AML}$$ ). This can be done in two ways, namely by enriching action models with questions as possible actions or with issues concerning which action takes place. This paper describes the corresponding dynamic logics, which are conservative extensions of both $$\textsf {AML}$$ and $$\textsf {IEL}$$ , and a sound and complete axiomatization is given for both.

Within ZFC, we develop a general technique to topologize trees that provides a uniform approach to topological completeness results in modal logic with respect to zero-dimensional Hausdorff spaces. Embeddings of these spaces into well-known extremally disconnected spaces then gives new completeness results for logics extending S4.2.

Citation impact is commonly assessed using direct, first-order citation relations. We consider here instead the indirect influence of publications on new publications via citations. We present a novel method to quantify the higher-order citation influence of publications, considering both direct, or first-order, and indirect, or higher-order citations. In particular, we are interested in higher-order citation influence at the level of disciplines. We apply this method to the whole Web of Science data at the level of disciplines. We find that a significant amount of influence—42%—stems from higher-order citations. Furthermore, we show that higher-order citation influence is helpful to quantify and visualize citation flows among disciplines, and to assess their degree of interdisciplinarity.

Optimally encoding classical information in a quantum system is one of the oldest and most fundamental challenges of quantum information theory. Holevo's bound places a hard upper limit on such encodings, while the Holevo-Schumacher-Westmoreland (HSW) theorem addresses the question of how many classical messages can be "packed" into a given quantum system. In this article, we use Sen's recent quantum joint typicality results to prove a one-shot multiparty quantum packing lemma generalizing the HSW theorem. The lemma is designed to be easily applicable in many network communication scenarios. As an illustration, we use it to straightforwardly obtain quantum generalizations of well-known classical coding schemes for the relay channel: multihop, coherent multihop, decode-forward, and partial decode-forward. We provide both finite blocklength and asymptotic results, the latter matching existing classical formulas. Given the key role of the classical packing lemma in network information theory, our packing lemma should help open the field to direct quantum generalization., Comment: 20 pages

The felicity, or acceptability, of IS generics, i.e. generic sentences with indefinite singulars, is considerably more restricted compared to BP generics, generics with bare plurals. The goal of this paper is to account for the limited felicity of IS generics compared to BP generics, on the one hand, while preserving the close similarity between the two types of generics, on the other. We do so by proposing a causal analysis of IS generics, and show that this corresponds closely with a probabilistic analysis of BP generics.

According to Adams (Inquiry 8:166–197, 1965), the acceptability of an indicative conditional goes with the conditional probability of the consequent given the antecedent. However, some conditionals seem to be inappropriate, although their corresponding conditional probability is high. These are cases with a missing link between antecedent and consequent. Other conditionals are appropriate even though the conditional probability is low. Finally, we have the so-called biscuit conditionals. In this paper we will generalize analyses of Douven (Synthese 164:19–44, 2008) and others to account for the appropriateness of conditionals in terms of evidential support. Our generalization involves making use of Value, or intensity. We will show how this generalization helps to account for biscuit conditionals and conditional threats and promises. Finally, a link is established between this analysis of conditionals and an analysis of generic sentences.

The lack of annotated data in many languages is a well-known challenge within the field of multilingual natural language processing (NLP). Therefore, many recent studies focus on zero-shot transfer learning and joint training across languages to overcome data scarcity for low-resource languages. In this work we (i) perform a comprehensive comparison of state-ofthe-art multilingual word and sentence encoders on the tasks of named entity recognition (NER) and part of speech (POS) tagging; and (ii) propose a new method for creating multilingual contextualized word embeddings, compare it to multiple baselines and show that it performs at or above state-of-theart level in zero-shot transfer settings. Finally, we show that our method allows for better knowledge sharing across languages in a joint training setting., 7 pages, 6 figures

It is well known that in his Prior Analysis, Aristotle presents the system of syllogisms. Although many commentators consider Aristotle’s system of modal syllogisms almost impossible to understand from a modern point of view or even inconsistent, many philosophers still tried to account for these claims by looking for a consistent semantics of it. In this paper we will argue for a causal analysis of modal categorical sentences based on the notion of causal power. According to Cheng (1997), the causal power of A to produce B can be measured probabilistically. Based on Cheng’s hypothesis, we will derive a qualitative semantics for modal categorical sentences. We will argue that our approach fits well with Aristotle’s analysis of real definition in the Posterior Analytics, and that in this way we can account in a relatively straightforward way (using just Venn diagrams) for several puzzling aspects of Aristotle’s system of modal syllogisms.

This paper proposes a formal framework for modeling the interaction of causal and (qualitative) epistemic reasoning. To this purpose, we extend the notion of a causal model with a representation of the epistemic state of an agent. On the side of the object language, we add operators to express knowledge and the act of observing new information. We provide a sound and complete axiomatization of the logic, and discuss the relation of this framework to causal team semantics., This is the long version of a paper that is to be published in the post-proceedings of the 3rd Dali Workshop on Dynamic Logic: New Trends and Applications. The post-proceedings will be published by Springer as a Lecture Notes in Computer Science volume

We develop a powerful approach that makes modern SAT solving techniques available as a tool to support the axiomatic analysis of economic matching mechanisms. Our central result is a preservation theorem, establishing sufficient conditions under which the possibility of designing a matching mechanism meeting certain axiomatic requirements for a given number of agents carries over to all scenarios with strictly fewer agents. This allows us to obtain general results about matching by verifying claims for specific instances using a SAT solver. We use our approach to automatically derive elementary proofs for two new impossibility theorems: (i) a strong form of Roth's classical result regarding the impossibility of designing mechanisms that are both stable and strategyproof and (ii) a result establishing the impossibility of guaranteeing stability while also respecting a basic notion of cross-group fairness (so-called gender-indifference).

We present a dynamic logic for inductive learning from partial observations by a “rational” learner, that obeys AGM postulates for belief revision. We apply our logic to an example, showing how various concrete properties can be learnt with certainty or inductively by such an AGM learner. We present a sound and complete axiomatization, based on a combination of relational and neighbourhood version of the canonical model method.

Recent years have seen a growing interest within the natural language processing (NLP) community in evaluating the ability of semantic models to capture human meaning representation in the brain. Existing research has mainly focused on applying semantic models to decode brain activity patterns associated with the meaning of individual words, and, more recently, this approach has been extended to sentences and larger text fragments. Our work is the first to investigate metaphor processing in the brain in this context. We evaluate a range of semantic models (word embeddings, compositional, and visual models) in their ability to decode brain activity associated with reading of both literal and metaphoric sentences. Our results suggest that compositional models and word embeddings are able to capture differences in the processing of literal and metaphoric sentences, providing support for the idea that the literal meaning is not fully accessible during familiar metaphor comprehension.

This paper is part of a series of proposals for using logic to analyse social networks. It studies the intertwining of two forms of information dynamics: social influence, through which an agent’s behaviour, opinions or features are affected by those of her social connections, and friendship selection, through which an agent chooses her social connections based on their common behaviour, opinions or features. The text provides a logical analysis of the two forms of dynamics (the main ingredients in the phenomenon known as homophily) as well as of their interaction, discussing also some of their variations.

Though fields such as art history, the history of philosophy, and intellectual history have been around for a long time, the author's interest is in the history of what scholars in all of these fields are doing in common. This book looks beyond the humanities to the practice of disciplined inquiry more generally, bringing together the history of the humanities and the sciences under the guise of a unified search for patterns.

In this book we are looking at Sun Tzu, the Art of War, an Chinese work onstrategy and warfare from about 2500 years ago. We use a mind map representation to look at the logic used by Sun Tzu. This allows us to uncover logic patterns in a systematic way.

Funding: European Research Council (ERC CoG), Grant Number 681404, ‘The Logic of Conceivability’. We study imagination as reality-oriented mental simulation (ROMS): the activity of simulating nonactual scenarios in one’s mind, to investigate what would happen if they were realized. Three connected questions concerning ROMS are: What is the logic, if there is one, of such an activity? How can we gain new knowledge via it? What is voluntary in it and what is not? We address them by building a list of core features of imagination as ROMS, drawing on research in cognitive psychology and the philosophy of mind. We then provide a logic of imagination as ROMS which models such features, combining techniques from epistemic logic, action logic, and subject matter semantics. Our logic comprises a modal propositional language with non-monotonic imagination operators, a formal semantics, and an axiomatization. Postprint

The research covered in this thesis is dedicated to provable post-quantum security of hash functions. Post-quantum security provides security guarantees against quantum attackers. We focus on analyzing the sponge construction, a cryptographic construction used in the standardized hash function SHA3. Our main results are proving a number of quantum security statements. These include standard-model security: collision-resistance and collapsingness, and more idealized notions such as indistinguishability and indifferentiability from a random oracle. All these results concern quantum security of the classical cryptosystems. From a more high-level perspective we find new applications and generalize several important proof techniques in post-quantum cryptography. We use the polynomial method to prove quantum indistinguishability of the sponge construction. We also develop a framework for quantum game-playing proofs, using the recently introduced techniques of compressed random oracles and the One-way-To-Hiding lemma. To establish the usefulness of the new framework we also prove a number of quantum indifferentiability results for other cryptographic constructions. On the way to these results, though, we address an open problem concerning quantum indifferentiability. Namely, we disprove a conjecture that forms the basis of a no-go theorem for a version of quantum indifferentiability.

The regulation of trans fats sets an interesting precedent for the regulation of other legal but harmful food ingredients, such as salt, sugar and saturated fat. In this paper, we distinguish three regulatory measures to reduce such ingredients in food and population intakes: the labelling of an ingredient, a limit on the amount of the ingredient in food products and a ban on the production technology that creates the ingredient. We will compare the regulations promulgated in the US and in the EU to reduce trans fats in food and population intakes. This comparison will identify a common focus on scientific risk assessment and precautionary action but a different orientation towards regulating the internal market and towards producer interests. The comparison also lays bare differences in the regulatory systems of the US and the EU that may inspire US and EU regulators to reflect on possible improvements for future fights against legal but harmful food ingredients.

Our main concern in this paper is the semantics of predicates of personal taste. However, in order to see these predicates in the right perspective, we had to broaden the scope to the wider class of relative gradable adjectives. We present an analysis of the meaning of these adjectives in the framework of update semantics. In this framework the meaning of a sentence is not identified with its truth conditions, but with its (potential) impact on people’s intentional states. In this respect, an important characteristic of relative gradable adjectives is the interplay between their evaluative features and people’s expectations. The dynamic set-up also makes it possible (a) to model the interpretation of a relative gradable adjective without supposing that the context always supplies a ‘cut-off’ point determining its application, and (b) to deal in a pragmatic way with situations in which the Sorites paradox arises.

We investigate the logical structure of intuitionistic Kripke-Platek set theory IKP , and show that the first-order logic of IKP is intuitionistic first-order logic IQC.

We prove that there exist profinite Heyting algebras that are not isomorphic to the profinite completion of any Heyting algebra. This resolves an open problem from 2009. More generally, we characterize those varieties of Heyting algebras in which profinite algebras are isomorphic to profinite completions. It turns out that there exists largest such. We give different characterizations of this variety and show that it is finitely axiomatizable and locally finite. From this it follows that it is decidable whether in a finitely axiomatizable variety of Heyting algebras all profinite members are profinite completions. In addition, we introduce and characterize representable varieties of Heyting algebras, thus drawing connection to the classical problem of representing posets as prime spectra.

We propose the first near-optimal quantum algorithm for estimating in Euclidean norm the mean of a vector-valued random variable with finite mean and covariance. Our result aims at extending the theory of multivariate sub-Gaussian estimators to the quantum setting. Unlike classically, where any univariate estimator can be turned into a multivariate estimator with at most a logarithmic overhead in the dimension, no similar result can be proved in the quantum setting. Indeed, Heinrich ruled out the existence of a quantum advantage for the mean estimation problem when the sample complexity is smaller than the dimension. Our main result is to show that, outside this low-precision regime, there is a quantum estimator that outperforms any classical estimator. Our approach is substantially more involved than in the univariate setting, where most quantum estimators rely only on phase estimation. We exploit a variety of additional algorithmic techniques such as amplitude amplification, the Bernstein-Vazirani algorithm, and quantum singular value transformation. Our analysis also uses concentration inequalities for multivariate truncated statistics. We develop our quantum estimators in two different input models that showed up in the literature before. The first one provides coherent access to the binary representation of the random variable and it encompasses the classical setting. In the second model, the random variable is directly encoded into the phases of quantum registers. This model arises naturally in many quantum algorithms but it is often incomparable to having classical samples. We adapt our techniques to these two settings and we show that the second model is strictly weaker for solving the mean estimation problem. Finally, we describe several applications of our algorithms, notably in measuring the expectation values of commuting observables and in the field of machine learning., 35 pages, 1 figure; v2: minor changes

Melodic contour is central to our ability to perceive and produce music. We propose to represent melodic contours as a combination of cosine functions, using the discrete cosine transform. The motivation for this approach is twofold: (1) it approximates a maximally informative contour representation (capturing most of the variation in as few dimensions as possible), but (2) it is nevertheless independent of the specifics of the data sets for which it is used. We consider the relation with principal component analysis, which only meets the first of these requirements. Theoretically, the principal components of a repertoire of random walks are known to be cosines. We find, empirically, that the principal components of melodies also closely approximate cosines in multiple musical traditions. We demonstrate the usefulness of the proposed representation by analyzing contours at three levels (complete songs, melodic phrases and melodic motifs) across multiple traditions in three small case studies.

This paper focuses on the problem of fairly and efficiently allocating resources to agents. We consider a specific setting, usually referred to as a housing market, where each agent must receive exactly one resource (and initially owns one). In this framework, in the domain of linear preferences, the Top Trading Cycle (TTC) algorithm is the only procedure satisfying Pareto-optimality, individual rationality and strategy-proofness. Under the restriction of single-peaked preferences, Crawler enjoys the same properties. These two centralized procedures might however involve long trading cycles. In this paper we focus instead on procedures involving the shortest cycles: bilateral swap-deals. In such swap dynamics, the agents perform pairwise mutually improving deals until reaching a swap-stable allocation (no improving swap-deal is possible). We prove that in the single-peaked domain every swap-stable allocation is Pareto-optimal, showing the efficiency of the swap dynamics. In fact, this domain turns out to be maximal when it comes to guaranteeing this property. Besides, both the outcome of TTC and Crawler can always be reached by sequences of swaps. However, some Pareto-optimal allocations are not reachable through improving swap-deals. We further analyze the outcome of swap dynamics through social welfare notions, in our context the average or minimum rank of the resources obtained by agents in the final allocation. We start by providing a worst-case analysis of these procedures. Finally, we present an extensive experimental study in which different versions of swap dynamics are compared to other existing allocation procedures. We show that they exhibit good results on average in this domain, under different cultures for generating synthetic data., Replaces our previous submission: "House Markets and Single-Peaked Preferences: From Centralized to Decentralized Allocation Procedures". Following reviewers' comments, leaves out our contribution on a variant of the Crawler procedure (goes in a separate submission) to concentrate on swap dynamics (new results added)

Belnap-Dunn logic (BD), sometimes also known as First Degree Entailment, is a four-valued propositional logic that complements the classical truth values of True and False with two non-classical truth values Neither and Both. The latter two are to account for the possibility of the available information being incomplete or providing contradictory evidence. In this paper, we present a probabilistic extension of BD that permits agents to have probabilistic beliefs about the truth and falsity of a proposition. We provide a sound and complete axiomatization for the framework defined and also identify policies for conditionalization and aggregation. Concretely, we introduce four-valued equivalents of Bayes’ and Jeffrey updating and also suggest mechanisms for aggregating information from different sources.

In this paper, we present an extensional system of mereology suitable to account for the intuitive distinction between heaplike and non-heaplike entities. Since the need to capture this distinction has been a key motivation for non-extensional mereologies, we first assess the main non-extensional systems advanced in the last years and highlight some mereological and metaphysical difficulties they involve. We then advance a novel program, according to which the distinction between heaplike and non-heaplike entities can be accounted for by bringing together the parthood relation characterized by classical extensional mereology and an Aristotelian extensional notion of potential parthood. Thus, while rejecting the thesis of mereological monism, our proposal is consistent with the thesis of mereological extensionalism. We show that within this framework it is possible to characterize the above-mentioned distinction, to define the relation of material constitution, and to capture three fundamental standpoints in metaphysics.

Belief revision is concerned with belief change fired by incoming information. Despite the variety of frameworks representing it, most revision policies share one crucial feature: incoming information outweighs current information and hence, in case of conflict, incoming information will prevail. However, if one is interested in representing the way actual humans revise their beliefs, one might not always want for the agent to blindly believe everything they are told. This manuscript presents a semantic approach to non-prioritized belief revision. It uses plausibility models for depicting an agent’s beliefs, and model operations for displaying the way beliefs change. The first proposal, semantically-based screened revision, compares the current model with the one the revision would yield, accepting or rejecting the incoming information depending on whether the ‘differences’ between these models go beyond a given threshold. The second proposal, semantically-based gradual revision, turns the binary decision of acceptance or rejection into a more general setting in which a revision always occurs, with the threshold used rather to choose ‘the right revision’ for the given input and model.

Natural languages exhibit many semantic universals, that is, properties of meaning shared across all languages. In this paper, we develop an explanation of one very prominent semantic universal, the monotonicity universal. While the existing work has shown that quantifiers satisfying the monotonicity universal are easier to learn, we provide a more complete explanation by considering the emergence of quantifiers from the perspective of cultural evolution. In particular, we show that quantifiers satisfy the monotonicity universal evolve reliably in an iterated learning paradigm with neural networks as agents.