# A melhor ferramenta para a sua pesquisa, trabalho e TCC!

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

## Noise stability of functions with low influences: invariance and optimality

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.

Link permanente para citações:

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

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%

#Quantum Physics#Computer Science - Logic in Computer Science#Mathematical Physics#Mathematics - Category Theory

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...

Link permanente para citações:

## New directions in mechanism design

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...

Link permanente para citações:

## Toward a Classification of Finite Partial-Monitoring Games

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)

Link permanente para citações:

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

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%

#Computer Science - Multiagent Systems#Computer Science - Artificial Intelligence#Computer Science - Robotics

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

Link permanente para citações:

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

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Português

Relevância na Pesquisa

466.35477%

#Computer Science - Databases#Computer Science - Distributed, Parallel, and Cluster Computing#Computer Science - Performance#H.2#C.2.4#C.4#D.4.5

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...

Link permanente para citações:

## Incidence Theorems and Their Applications

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....

Link permanente para citações:

## Explicit Substitutions for Contextual Type Theory

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

Link permanente para citações:

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

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).

Link permanente para citações:

## Digital morphogenesis via Schelling segregation

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.

Link permanente para citações:

## Towards a theory of good SAT representations

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Português

Relevância na Pesquisa

466.35477%

#Computer Science - Artificial Intelligence#Computer Science - Logic in Computer Science#68T15, 68T30#F.4.1

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"...

Link permanente para citações:

## On the mathematical synthesis of equational logics

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Português

Relevância na Pesquisa

466.35477%

#Computer Science - Logic in Computer Science#Mathematics - Category Theory#Mathematics - Logic#D.3.1, F.3.1, F.3.2, F.4.1, I.2.3

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

Link permanente para citações:

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

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...

Link permanente para citações:

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

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

Link permanente para citações:

## Quantified Multimodal Logics in Simple Type Theory

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%

#Computer Science - Artificial Intelligence#Computer Science - Logic in Computer Science#I.2.4#I.2.3#F.4.1

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

Link permanente para citações:

## A Theory of Explicit Substitutions with Safe and Full Composition

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Português

Relevância na Pesquisa

466.35477%

#Computer Science - Programming Languages#Computer Science - Logic in Computer Science#F.3.2#D.1.1#F.4.1

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

Link permanente para citações:

## Set theory and tableaux for teaching propositional logic

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

Link permanente para citações:

## Towards a Complexity-through-Realisability Theory

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Português

Relevância na Pesquisa

466.35477%

#Computer Science - Logic in Computer Science#Computer Science - Computational Complexity#Mathematics - Logic#Mathematics - Operator Algebras

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.

Link permanente para citações:

## Finding maxmin allocations in cooperative and competitive fair division

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Português

Relevância na Pesquisa

466.35477%

#Mathematics - Optimization and Control#Computer Science - Computer Science and Game Theory#Mathematics - Probability

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)

Link permanente para citações:

## Dialectics of Knowledge Representation in a Granular Rough Set Theory

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Português

Relevância na Pesquisa

466.35477%

#Computer Science - Artificial Intelligence#Computer Science - Logic in Computer Science#06Axx, 03G25, 03B60, 08B20, 68U35

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)

Link permanente para citações: