Página 20 dos resultados de 10730 itens digitais encontrados em 0.068 segundos

Noise stability of functions with low influences: invariance and optimality

Mossel, Elchanan; O'Donnell, Ryan; Oleszkiewicz, Krzysztof
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
466.35477%
In this paper we study functions with low influences on product probability spaces. The analysis of boolean functions with low influences has become a central problem in discrete Fourier analysis. It is motivated by fundamental questions arising from the construction of probabilistically checkable proofs in theoretical computer science and from problems in the theory of social choice in economics. We prove an invariance principle for multilinear polynomials with low influences and bounded degree; it shows that under mild conditions the distribution of such polynomials is essentially invariant for all product spaces. Ours is one of the very few known non-linear invariance principles. It has the advantage that its proof is simple and that the error bounds are explicit. We also show that the assumption of bounded degree can be eliminated if the polynomials are slightly ``smoothed''; this extension is essential for our applications to ``noise stability''-type problems. In particular, as applications of the invariance principle we prove two conjectures: the ``Majority Is Stablest'' conjecture from theoretical computer science, which was the original motivation for this work, and the ``It Ain't Over Till It's Over'' conjecture from social choice theory.

Relating toy models of quantum computation: comprehension, complementarity and dagger mix autonomous categories

Pavlovic, Dusko
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 04/06/2010 Português
Relevância na Pesquisa
466.35477%
Toy models have been used to separate important features of quantum computation from the rich background of the standard Hilbert space model. Category theory, on the other hand, is a general tool to separate components of mathematical structures, and analyze one layer at a time. It seems natural to combine the two approaches, and several authors have already pursued this idea. We explore *categorical comprehension construction* as a tool for adding features to toy models. We use it to comprehend quantum propositions and probabilities within the basic model of finite-dimensional Hilbert spaces. We also analyze complementary quantum observables over the category of sets and relations. This leads into the realm of *test spaces*, a well-studied model. We present one of many possible extensions of this model, enabled by the comprehension construction. Conspicuously, all models obtained in this way carry the same categorical structure, *extending* the familiar dagger compact framework with the complementation operations. We call the obtained structure *dagger mix autonomous*, because it extends mix autonomous categories, popular in computer science, in a similar way like dagger compact structure extends compact categories. Dagger mix autonomous categories seem to arise quite naturally in quantum computation...

New directions in mechanism design

Meng, Jiangtao
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 21/12/2005 Português
Relevância na Pesquisa
466.35477%
Mechanism design uses the tools of economics and game theory to design rules of interaction for economic transactions that will,in principle, yield some de- sired outcome. In the last few years this field has received much interest of researchers in computer science, especially with the Internet developing as a platform for communications and connections among enormous numbers of computers and humans. Arguably the most positive result in mechanism de- sign is truthful and there are only one general truthful mechanisms so far : the generalized Vickrey-Clarke-Groves (VCG) mechanism. But VCG mecha- nism has one shortage: The implementation of truthfulness is on the cost of decreasing the revenue of the mechanism. (e.g., Ning Chen and Hong Zhu. [1999]). We introduce three new characters of mechanism:partly truthful, criti- cal, consistent, and introduce a new mechanism: X mechanism that satisfy the above three characters. Like VCG mechanism, X mechanism also generalizes from Vickery Auction and is consistent with Vickery auction in many ways, but the extended methods used in X mechanism is different from that in VCG mechanism . This paper will demonstrate that X mechanism better than VCG mechanism in optimizing utility of mechanism, which is the original intention of mechanism design. So partly truthful...

Toward a Classification of Finite Partial-Monitoring Games

Antos, András; Bartók, Gábor; Pál, Dávid; Szepesvári, Csaba
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
466.35477%
Partial-monitoring games constitute a mathematical framework for sequential decision making problems with imperfect feedback: The learner repeatedly chooses an action, opponent responds with an outcome, and then the learner suffers a loss and receives a feedback signal, both of which are fixed functions of the action and the outcome. The goal of the learner is to minimize his total cumulative loss. We make progress towards the classification of these games based on their minimax expected regret. Namely, we classify almost all games with two outcomes and finite number of actions: We show that their minimax expected regret is either zero, $\widetilde{\Theta}(\sqrt{T})$, $\Theta(T^{2/3})$, or $\Theta(T)$ and we give a simple and efficiently computable classification of these four classes of games. Our hope is that the result can serve as a stepping stone toward classifying all finite partial-monitoring games.; Comment: Submitted for review to Theoretical Computer Science (Special Issue of the conference Algorithmic Learning Theory 2010)

The Inverse Task of the Reflexive Game Theory: Theoretical Matters, Practical Applications and Relationship with Other Issues

Tarasenko, Sergey
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 15/11/2010 Português
Relevância na Pesquisa
466.35477%
The Reflexive Game Theory (RGT) has been recently proposed by Vladimir Lefebvre to model behavior of individuals in groups. The goal of this study is to introduce the Inverse task. We consider methods of solution together with practical applications. We present a brief overview of the RGT for easy understanding of the problem. We also develop the schematic representation of the RGT inference algorithms to create the basis for soft- and hardware solutions of the RGT tasks. We propose a unified hierarchy of schemas to represent humans and robots. This hierarchy is considered as a unified framework to solve the entire spectrum of the RGT tasks. We conclude by illustrating how this framework can be applied for modeling of mixed groups of humans and robots. All together this provides the exhaustive solution of the Inverse task and clearly illustrates its role and relationships with other issues considered in the RGT.; Comment: 27 pages, 6 figures, 3 tables

Middleware-based Database Replication: The Gaps between Theory and Practice

Cecchet, Emmanuel; Candea, George; Ailamaki, Anastasia
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
466.35477%
The need for high availability and performance in data management systems has been fueling a long running interest in database replication from both academia and industry. However, academic groups often attack replication problems in isolation, overlooking the need for completeness in their solutions, while commercial teams take a holistic approach that often misses opportunities for fundamental innovation. This has created over time a gap between academic research and industrial practice. This paper aims to characterize the gap along three axes: performance, availability, and administration. We build on our own experience developing and deploying replication systems in commercial and academic settings, as well as on a large body of prior related work. We sift through representative examples from the last decade of open-source, academic, and commercial database replication systems and combine this material with case studies from real systems deployed at Fortune 500 customers. We propose two agendas, one for academic research and one for industrial R&D, which we believe can bridge the gap within 5-10 years. This way, we hope to both motivate and help researchers in making the theory and practice of middleware-based database replication more relevant to each other.; Comment: 14 pages. Appears in Proc. ACM SIGMOD International Conference on Management of Data...

Incidence Theorems and Their Applications

Dvir, Zeev
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
466.35477%
We survey recent (and not so recent) results concerning arrangements of lines, points and other geometric objects and the applications these results have in theoretical computer science and combinatorics. The three main types of problems we will discuss are: (1) Counting incidences: Given a set (or several sets) of geometric objects (lines, points, etc..), what is the maximum number of incidences (or intersections) that can exist between elements in different sets? We will see several results of this type, such as the Szemeredi-Trotter theorem, over the reals and over finite fields and discuss their applications in combinatorics (e.g., in the recent solution of Guth and Katz to Erdos' distance problem) and in computer science (in explicit constructions of multi-source extractors). (2) Kakeya type problems: These problems deal with arrangements of lines that point in different directions. The goal is to try and understand to what extent these lines can overlap one another. We will discuss these questions both over the reals and over finite fields and see how they come up in the theory of randomness-extractors. (3) Sylvester-Gallai type problems: In this type of problems, one is presented with a configuration of points that contain many `local' dependencies (e.g....

Explicit Substitutions for Contextual Type Theory

Abel, Andreas; Pientka, Brigitte
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 14/09/2010 Português
Relevância na Pesquisa
466.35477%
In this paper, we present an explicit substitution calculus which distinguishes between ordinary bound variables and meta-variables. Its typing discipline is derived from contextual modal type theory. We first present a dependently typed lambda calculus with explicit substitutions for ordinary variables and explicit meta-substitutions for meta-variables. We then present a weak head normalization procedure which performs both substitutions lazily and in a single pass thereby combining substitution walks for the two different classes of variables. Finally, we describe a bidirectional type checking algorithm which uses weak head normalization and prove soundness.; Comment: In Proceedings LFMTP 2010, arXiv:1009.2189

The CIFF Proof Procedure for Abductive Logic Programming with Constraints: Theory, Implementation and Experiments

Mancarella, P.; Terreni, G.; Sadri, F.; Toni, F.; Endriss, U.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 05/06/2009 Português
Relevância na Pesquisa
466.35477%
We present the CIFF proof procedure for abductive logic programming with constraints, and we prove its correctness. CIFF is an extension of the IFF proof procedure for abductive logic programming, relaxing the original restrictions over variable quantification (allowedness conditions) and incorporating a constraint solver to deal with numerical constraints as in constraint logic programming. Finally, we describe the CIFF system, comparing it with state of the art abductive systems and answer set solvers and showing how to use it to program some applications. (To appear in Theory and Practice of Logic Programming - TPLP).

Digital morphogenesis via Schelling segregation

Barmpalias, George; Elwes, Richard; Lewis-Pye, Andy
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
466.35477%
Schelling's model of segregation looks to explain the way in which particles or agents of two types may come to arrange themselves spatially into configurations consisting of large homogeneous clusters, i.e.\ connected regions consisting of only one type. As one of the earliest agent based models studied by economists and perhaps the most famous model of self-organising behaviour, it also has direct links to areas at the interface between computer science and statistical mechanics, such as the Ising model and the study of contagion and cascading phenomena in networks. While the model has been extensively studied it has largely resisted rigorous analysis, prior results from the literature generally pertaining to variants of the model which are tweaked so as to be amenable to standard techniques from statistical mechanics or stochastic evolutionary game theory. In \cite{BK}, Brandt, Immorlica, Kamath and Kleinberg provided the first rigorous analysis of the unperturbed model, for a specific set of input parameters. Here we provide a rigorous analysis of the model's behaviour much more generally and establish some surprising forms of threshold behaviour, notably the existence of situations where an \emph{increased} level of intolerance for neighbouring agents of opposite type leads almost certainly to \emph{decreased} segregation.

Towards a theory of good SAT representations

Gwynne, Matthew; Kullmann, Oliver
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
466.35477%
We aim at providing a foundation of a theory of "good" SAT representations F of boolean functions f. We argue that the hierarchy UC_k of unit-refutation complete clause-sets of level k, introduced by the authors, provides the most basic target classes, that is, F in UC_k is to be achieved for k as small as feasible. If F does not contain new variables, i.e., F is equivalent (as a CNF) to f, then F in UC_1 is similar to "achieving (generalised) arc consistency" known from the literature (it is somewhat weaker, but theoretically much nicer to handle). We show that for polysize representations of boolean functions in this sense, the hierarchy UC_k is strict. The boolean functions for these separations are "doped" minimally unsatisfiable clause-sets of deficiency 1; these functions have been introduced in [Sloan, Soerenyi, Turan, 2007], and we generalise their construction and show a correspondence to a strengthened notion of irredundant sub-clause-sets. Turning from lower bounds to upper bounds, we believe that many common CNF representations fit into the UC_k scheme, and we give some basic tools to construct representations in UC_1 with new variables, based on the Tseitin translation. Note that regarding new variables the UC_1-representations are stronger than mere "arc consistency"...

On the mathematical synthesis of equational logics

Fiore, Marcelo; Hur, Chung-Kil
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
466.35477%
We provide a mathematical theory and methodology for synthesising equational logics from algebraic metatheories. We illustrate our methodology by means of two applications: a rational reconstruction of Birkhoff's Equational Logic and a new equational logic for reasoning about algebraic structure with name-binding operators.; Comment: Final version for publication in Logical Methods in Computer Science

An Ehrenfeucht-Fraisse Game Approach to Collapse Results in Database Theory

Schweikardt, Nicole
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 20/12/2002 Português
Relevância na Pesquisa
466.35477%
We present a new Ehrenfeucht-Fraisse game approach to collapse results in database theory and we show that, in principle, this approach suffices to prove every natural generic collapse result. Following this approach we can deal with certain infinite databases where previous, highly involved methods fail. We prove the natural generic collapse for Z-embeddable databases over any linearly ordered context structure with arbitrary monadic predicates, and for N-embeddable databases over the context structure (R,<,+,Mon_Q,Groups). Here, N, Z, R, denote the sets of natural numbers, integers, and real numbers, respectively. Groups is the collection of all subgroups of (R,+) that contain Z, and Mon_Q is the collection of all subsets of a particular infinite subset Q of N. Restricting the complexity of the formulas that may be used to formulate queries to Boolean combinations of purely existential first-order formulas, we even obtain the collapse for N-embeddable databases over any linearly ordered context structure with arbitrary predicates. Finally, we develop the notion of N-representable databases, which is a natural generalization of the classical notion of finitely representable databases. We show that natural generic collapse results for N-embeddable databases can be lifted to the larger class of N-representable databases. To obtain...

Packing, Scheduling and Covering Problems in a Game-Theoretic Perspective

Kleiman, Elena
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 28/10/2011 Português
Relevância na Pesquisa
466.35477%
Many packing, scheduling and covering problems that were previously considered by computer science literature in the context of various transportation and production problems, appear also suitable for describing and modeling various fundamental aspects in networks optimization such as routing, resource allocation, congestion control, etc. Various combinatorial problems were already studied from the game theoretic standpoint, and we attempt to complement to this body of research. Specifically, we consider the bin packing problem both in the classic and parametric versions, the job scheduling problem and the machine covering problem in various machine models. We suggest new interpretations of such problems in the context of modern networks and study these problems from a game theoretic perspective by modeling them as games, and then concerning various game theoretic concepts in these games by combining tools from game theory and the traditional combinatorial optimization. In the framework of this research we introduce and study models that were not considered before, and also improve upon previously known results.; Comment: PhD thesis

Quantified Multimodal Logics in Simple Type Theory

Benzmueller, Christoph; Paulson, Lawrence C.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 14/05/2009 Português
Relevância na Pesquisa
466.35477%
We present a straightforward embedding of quantified multimodal logic in simple type theory and prove its soundness and completeness. Modal operators are replaced by quantification over a type of possible worlds. We present simple experiments, using existing higher-order theorem provers, to demonstrate that the embedding allows automated proofs of statements in these logics, as well as meta properties of them.; Comment: ii + 22 pages

A Theory of Explicit Substitutions with Safe and Full Composition

Kesner, Delia
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
466.35477%
Many different systems with explicit substitutions have been proposed to implement a large class of higher-order languages. Motivations and challenges that guided the development of such calculi in functional frameworks are surveyed in the first part of this paper. Then, very simple technology in named variable-style notation is used to establish a theory of explicit substitutions for the lambda-calculus which enjoys a whole set of useful properties such as full composition, simulation of one-step beta-reduction, preservation of beta-strong normalisation, strong normalisation of typed terms and confluence on metaterms. Normalisation of related calculi is also discussed.; Comment: 29 pages Special Issue: Selected Papers of the Conference "International Colloquium on Automata, Languages and Programming 2008" edited by Giuseppe Castagna and Igor Walukiewicz

Set theory and tableaux for teaching propositional logic

Guallart, Nino; Nepomuceno-Fernandez, Angel
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 13/07/2015 Português
Relevância na Pesquisa
466.35477%
In this work we suggest the use of a set-theoretical interpretation of semantic tableaux for teaching propositional logic. If the student has previous notions of basic set theory, this approach to semantical tableaux can clarify her the way semantic trees operate, linking the syntactical and semantical sides of the process. Also, it may be useful for the introduction of more advanced topics in logic, like modal logic.; Comment: Proceedings of the Fourth International Conference on Tools for Teaching Logic (TTL2015), Rennes, France, June 9-12, 2015. Editors: M. Antonia Huertas, Jo\~ao Marcos, Mar\'ia Manzano, Sophie Pinchinat, Fran\c{c}ois Schwarzentruber

Towards a Complexity-through-Realisability Theory

Seiller, Thomas
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
466.35477%
We explain how recent developments in the fields of realisability models for linear logic -- or geometry of interaction -- and implicit computational complexity can lead to a new approach of implicit computational complexity. This semantic-based approach should apply uniformly to various computational paradigms, and enable the use of new mathematical methods and tools to attack problem in computational complexity. This paper provides the background, motivations and perspectives of this complexity-through-realisability theory to be developed, and illustrates it with recent results.

Finding maxmin allocations in cooperative and competitive fair division

Dall'Aglio, Marco; Di Luca, Camilla
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
466.35477%
We consider upper and lower bounds for maxmin allocations of a completely divisible good in both competitive and cooperative strategic contexts. We then derive a subgradient algorithm to compute the exact value up to any fixed degree of precision.; Comment: 20 pages, 3 figures. This third version improves the overll presentation; Optimization and Control (math.OC), Computer Science and Game Theory (cs.GT), Probability (math.PR)

Dialectics of Knowledge Representation in a Granular Rough Set Theory

Mani, A.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
466.35477%
The concepts of rough and definite objects are relatively more determinate than those of granules and granulation in general rough set theory (RST) [1]. Representation of rough objects can however depend on the dialectical relation between granulation and definiteness. In this research, we make this exact in the context of RST over proto-transitive approximation spaces. This approach can be directly extended to many other types of RST. These are used for formulating an extended concept of knowledge interpretation (KI)(relative the situation for classical RST) and the problem of knowledge representation (KR) is solved. These will be of direct interest in granular KR in RST as developed by the present author [2] and of rough objects in general. In [3], these have already been used for five different semantics by the present author. This is an extended version of [4] with key examples and more results.; Comment: Enlarged version of Refereed Conference Paper. 18 pp 1 figure. (An extended version is to appear soon)