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

Theory and practice of secret commitment

Halevi, Shai
Fonte: Massachusetts Institute of Technology Publicador: Massachusetts Institute of Technology
Tipo: Tese de Doutorado Formato: 80 p.
Português
Relevância na Pesquisa
555.33023%
by Shai Halevi.; Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1997.; Includes bibliographical references (p. 77-80).

Functional compression : theory and application

Doshi, Vishal D. (Vishal Devendra)
Fonte: Massachusetts Institute of Technology Publicador: Massachusetts Institute of Technology
Tipo: Tese de Doutorado Formato: 77 p.
Português
Relevância na Pesquisa
555.33023%
We consider the problem of functional compression. The objective is to separately compress possibly correlated discrete sources such that an arbitrary deterministic function of those sources can be computed given the compressed data from each source. This is motivated by problems in sensor networks and database privacy. Our architecture gives a quantitative definition of privacy for database statistics. Further, we show that it can provide significant coding gains in sensor networks. We consider both the lossless and lossy computation of a function. Specifically, we present results of the rate regions for three instances of the problem where there are two sources: 1) lossless computation where one source is available at the decoder, 2) under a special condition, lossless computation where both sources are separately encoded, and 3) lossy computation where one source is available at the decoder. Wyner and Ziv (1976) considered the third problem for the special case f(X, Y) = X and derived a rate distortion function. Yamamoto (1982) extended this result to a general function. Both of these results are in terms of an auxiliary random variable. Orlitsky and Roche (2001), for the zero distortion case, gave this variable a precise interpretation in terms of the properties of the characteristic graph; this led to a particular coding scheme. We extend that result by providing an achievability scheme that is based on the coloring of the characteristic graph. This suggests a layered architecture where the functional layer controls the coloring scheme...

Existential Theorems in Computational Complexity Theory: Size and Robustness

Zimand, Marius ; Hemaspaandra, Lane A.
Fonte: University of Rochester. Computer Science Department. Publicador: University of Rochester. Computer Science Department.
Tipo: Thesis; Technical Report
Português
Relevância na Pesquisa
555.33023%
Thesis (Ph. D.)--University of Rochester. Dept. of Computer Science, 1996. Simultaneously published in the Technical Report series.; How strong are the results in computational complexity that assert, under certain hypotheses, the existence of an object? Are there many such objects, or are there few? To what extent can we relax the hypotheses and still maintain the same conclusions? These are the types of questions that are studied in this thesis. More precisely, we investigate some of the central existential results in computational complexity from the point of view of size and robustness. Below is a sample of the results in the thesis. We show that for any effective enumeration of computational devices that cover the whole set of computable functions and for any complexity measure satisfying a single axiom, neither the set of speedable functions nor the set of functions that generate complexity gaps is small from a topological point of view. We show that, with probability one on the set of oracles, there is a set in NP^A that asymptotically splits in half any infinite set in P^A. This is the strongest currently known relativized separation of NP from P. We also show that most (in the resource-bounded measure sense) sets that are computable in exponential time do not have even very weak membership-related properties that are computable in polynomial time. We prove that in almost all relativized worlds...

Redundancy : eliminating it, exploiting it

Homan, Christopher M. (1969 - ); Hemaspaandra, Lane A.
Fonte: University of Rochester. Computer Science Department. Publicador: University of Rochester. Computer Science Department.
Tipo: Technical Report; Thesis Formato: Number of Pages:xi, 95 leaves
Português
Relevância na Pesquisa
555.33023%
Thesis (Ph. D.)--University of Rochester. Dept. of Computer Science, 2003.; Redundancy is a basic property of many computational settings. This thesis concerns techniques for eliminating redundancy in some cases, and exploiting it in others. We study one-way functions, i.e., functions that are easy to compute but hard to invert. Such functions were previously studied as cryptographic primitives. Since it remains an open question whether one-way functions exist, we study the question of their existence in relation to a variety of complexity-theoretic hypotheses. Starting with one-way functions in which redundancy in the preimage is absolutely minimal, i.e. one-to-one, we provide the first characterization of the existence of one-way permutations by a complexity class separation hypothesis, namely $P eq up inter coup$. Next, we study a type of one-way function that provably can never be one-to-one. Strong, total, associative, one-way functions are two-argument, one-way functions that are hard to invert, even if one of their arguments is known. Such special, one-way functions were originally used to construct secret-key agreement and digital signature protocols. We study techniques for creating such functions whose amount of preimage redundancy (as a function of the length of the corresponding image element) is minimized. We show that...

Towards a Computational Theory of Grounding in Natural Language Conversation

Traum, David R. (1963 - )
Fonte: University of Rochester. Computer Science Department. Publicador: University of Rochester. Computer Science Department.
Tipo: Relatório
Português
Relevância na Pesquisa
555.33023%
Theories of speech acts view utterances as actions which attempt to change the mental states of agents participating in a conversation. Recent work in computer science has tried to formalize speech acts in terms of the logic of action in AI planning systems. However most of these planning systems make simplifying assumptions about the world which are too strong to capture many features of conversation. One of these assumptions has been that the intent of an utterance is mutually understood by participants in a conversation, merely in virtue of its having been uttered in their presence. [Clark and Marshall, 1981] have assumptions of attention, rationality, and understandability to accomplish this. [Perrault, 1990] uses an assumption of observability. While these assumptions may be acceptable for processing written discourse without time constraints, they are not able to handle a large class of natural language utterances, including acknowledgements, and repairs. These phenomena have been studied in a descriptive fashion by sociologists and psychologists. I present ideas leading to a computational processing model of how agents come to reach a state of mutual understanding about intentions behind utterances. This involves a richer...

Decision Theory and Artificial Intelligence II: the Hungry Monkey

Feldman, Jerome A. ; Sproull, Robert F.
Fonte: University of Rochester. Computer Science Department. Publicador: University of Rochester. Computer Science Department.
Tipo: Relatório
Português
Relevância na Pesquisa
553.211%
This paper describes a problem-solving framework in which aspects of mathematical decision theory are incorporated into symbolic problem-solving techniques currently predominant In artificial intelligence. The utility function of decision theory is used to reveal tradeoffs among competing strategies for achieving various goals, taking into account such factors as reliability, the complexity of steps in the strategy, and the value of the goal. The utility function on strategies can therefore be used as a guide when searching for good strategies. It is also used to formulate solutions to the problems of how to acquire a world model, how much planning effort is worthwhile, and whether verification tests should be performed. These techniques are illustrated by application to the classic monkey and bananas problem.

Extending relAPS to first order logic

Aameri, Bahar
Fonte: Brock University Publicador: Brock University
Tipo: Electronic Thesis or Dissertation
Português
Relevância na Pesquisa
555.33023%
RelAPS is an interactive system assisting in proving relation-algebraic theorems. The aim of the system is to provide an environment where a user can perform a relation-algebraic proof similar to doing it using pencil and paper. The previous version of RelAPS accepts only Horn-formulas. To extend the system to first order logic, we have defined and implemented a new language based on theory of allegories as well as a new calculus. The language has two different kinds of terms; object terms and relational terms, where object terms are built from object constant symbols and object variables, and relational terms from typed relational constant symbols, typed relational variables, typed operation symbols and the regular operations available in any allegory. The calculus is a mixture of natural deduction and the sequent calculus. It is formulated in a sequent style but with exactly one formula on the right-hand side. We have shown soundness and completeness of this new logic which verifies that the underlying proof system of RelAPS is working correctly.

Numerical analysis of the Lyapunov equation with application to interconnected power systems

Fonte: Electronic Systems Laboratory, Dept. of Electical Engineering and Computer Science, Massachusetts Institute of Technology Publicador: Electronic Systems Laboratory, Dept. of Electical Engineering and Computer Science, Massachusetts Institute of Technology
Formato: 111 p.; application/pdf
Português
Relevância na Pesquisa
555.33023%
by Thomas Mac Athay.; Bibliography: p.109-111.; Prepared under grant ERDA-E(49-18)-2087. Originally presented as the author's thesis, (M.S. and E.E.), M.I.T. Dept. of Electrical Engineering and Computer Science, 1976.

Perturbation methods in decentralized stochastic control

Fonte: Electronic Systems Laboratory, Dept. of Electrical Engineering and Computer Science, Massachusetts Institute of Technology Publicador: Electronic Systems Laboratory, Dept. of Electrical Engineering and Computer Science, Massachusetts Institute of Technology
Formato: 197 p.; application/pdf
Português
Relevância na Pesquisa
555.33023%
by Demosthenis Teneketzis.; Bibliography: p.195-197.; The research was conducted under grant NGL-22-009-124, grant AFOSR-72-2273, and grant ERDA-E (49-18)-2087. Originally presented as the author's thesis, (M.S.), M.I.T. Dept. of Electrical Engineering and Computer Science, 1976.

Beyond Nash Equilibrium: Solution Concepts for the 21st Century

Halpern, Joseph Y.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 12/06/2008 Português
Relevância na Pesquisa
476.97387%
Nash equilibrium is the most commonly-used notion of equilibrium in game theory. However, it suffers from numerous problems. Some are well known in the game theory community; for example, the Nash equilibrium of repeated prisoner's dilemma is neither normatively nor descriptively reasonable. However, new problems arise when considering Nash equilibrium from a computer science perspective: for example, Nash equilibrium is not robust (it does not tolerate ``faulty'' or ``unexpected'' behavior), it does not deal with coalitions, it does not take computation cost into account, and it does not deal with cases where players are not aware of all aspects of the game. Solution concepts that try to address these shortcomings of Nash equilibrium are discussed.

A Qualitative Comparison of the Suitability of Four Theorem Provers for Basic Auction Theory

Lange, Christoph; Caminati, Marco B.; Kerber, Manfred; Mossakowski, Till; Rowat, Colin; Wenzel, Makarius; Windsteiger, Wolfgang
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
477.84387%
Novel auction schemes are constantly being designed. Their design has significant consequences for the allocation of goods and the revenues generated. But how to tell whether a new design has the desired properties, such as efficiency, i.e. allocating goods to those bidders who value them most? We say: by formal, machine-checked proofs. We investigated the suitability of the Isabelle, Theorema, Mizar, and Hets/CASL/TPTP theorem provers for reproducing a key result of auction theory: Vickrey's 1961 theorem on the properties of second-price auctions. Based on our formalisation experience, taking an auction designer's perspective, we give recommendations on what system to use for formalising auctions, and outline further steps towards a complete auction theory toolbox.; Comment: Conference on Intelligent Computer Mathematics, 8-12 July, Bath, UK. Published as number 7961 in Lecture Notes in Artificial Intelligence, Springer

Data types with symmetries and polynomial functors over groupoids

Kock, Joachim
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 02/10/2012 Português
Relevância na Pesquisa
474.53492%
Polynomial functors are useful in the theory of data types, where they are often called containers. They are also useful in algebra, combinatorics, topology, and higher category theory, and in this broader perspective the polynomial aspect is often prominent and justifies the terminology. For example, Tambara's theorem states that the category of finite polynomial functors is the Lawvere theory for commutative semirings. In this talk I will explain how an upgrade of the theory from sets to groupoids is useful to deal with data types with symmetries, and provides a common generalisation of and a clean unifying framework for quotient containers (cf. Abbott et al.), species and analytic functors (Joyal 1985), as well as the stuff types of Baez-Dolan. The multi-variate setting also includes relations and spans, multispans, and stuff operators. An attractive feature of this theory is that with the correct homotopical approach - homotopy slices, homotopy pullbacks, homotopy colimits, etc. - the groupoid case looks exactly like the set case. After some standard examples, I will illustrate the notion of data-types-with-symmetries with examples from quantum field theory, where the symmetries of complicated tree structures of graphs play a crucial role...

Computer-Aided Discovery and Categorisation of Personality Axioms

Kramer, Simon
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 24/03/2014 Português
Relevância na Pesquisa
474.37062%
We propose a computer-algebraic, order-theoretic framework based on intuitionistic logic for the computer-aided discovery of personality axioms from personality-test data and their mathematical categorisation into formal personality theories in the spirit of F.~Klein's Erlanger Programm for geometrical theories. As a result, formal personality theories can be automatically generated, diagrammatically visualised, and mathematically characterised in terms of categories of invariant-preserving transformations in the sense of Klein and category theory. Our personality theories and categories are induced by implicational invariants that are ground instances of intuitionistic implication, which we postulate as axioms. In our mindset, the essence of personality, and thus mental health and illness, is its invariance. The truth of these axioms is algorithmically extracted from histories of partially-ordered, symbolic data of observed behaviour. The personality-test data and the personality theories are related by a Galois-connection in our framework. As data format, we adopt the format of the symbolic values generated by the Szondi-test, a personality test based on L.~Szondi's unifying, depth-psychological theory of fate analysis.; Comment: related to arXiv:1403.2000

From truth to computability I

Japaridze, Giorgi
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
476.97387%
The recently initiated approach called computability logic is a formal theory of interactive computation. See a comprehensive online source on the subject at http://www.cis.upenn.edu/~giorgi/cl.html . The present paper contains a soundness and completeness proof for the deductive system CL3 which axiomatizes the most basic first-order fragment of computability logic called the finite-depth, elementary-base fragment. Among the potential application areas for this result are the theory of interactive computation, constructive applied theories, knowledgebase systems, systems for resource-bound planning and action. This paper is self-contained as it reintroduces all relevant definitions as well as main motivations.; Comment: To appear in Theoretical Computer Science

On the Theory of Structural Subtyping

Kuncak, Viktor; Rinard, Martin
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 05/08/2004 Português
Relevância na Pesquisa
475.4028%
We show that the first-order theory of structural subtyping of non-recursive types is decidable. Let $\Sigma$ be a language consisting of function symbols (representing type constructors) and $C$ a decidable structure in the relational language $L$ containing a binary relation $\leq$. $C$ represents primitive types; $\leq$ represents a subtype ordering. We introduce the notion of $\Sigma$-term-power of $C$, which generalizes the structure arising in structural subtyping. The domain of the $\Sigma$-term-power of $C$ is the set of $\Sigma$-terms over the set of elements of $C$. We show that the decidability of the first-order theory of $C$ implies the decidability of the first-order theory of the $\Sigma$-term-power of $C$. Our decision procedure makes use of quantifier elimination for term algebras and Feferman-Vaught theorem. Our result implies the decidability of the first-order theory of structural subtyping of non-recursive types.; Comment: 51 page. A version appeared in LICS 2003

What Should be Hidden and Open in Computer Security: Lessons from Deception, the Art of War, Law, and Economic Theory

Swire, Peter P.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 24/09/2001 Português
Relevância na Pesquisa
475.70027%
"What Should be Hidden and Open in Computer Security: Lessons from Deception, the Art of War, Law, and Economic Theory" Peter P. Swire, George Washington University. Imagine a military base. It is defended against possible attack. Do we expect the base to reveal the location of booby traps and other defenses? No. But for many computer applications,a software developer will need to reveal a great deal about the code to get other system owners to trust the code and know how to operate with it. This article examines these conflicting intuitions and develops a theory about what should be open and hidden in computer security. Part I of the paper shows how substantial openness is typical for major computer security topics, such as firewalls, packaged software, and encryption. Part II shows what factors will lead to openness or hiddenness in computer security. Part III presents an economic analysis of the issue of what should be open in computer security. The owner who does not reveal the booby traps is like a monopolist, while the open-source software supplier is in a competitive market. This economic approach allows us to identify possible market failures in how much openness occurs for computer security. Part IV examines the contrasting approaches of Sun Tzu and Clausewitz to the role of hiddenness and deception in military strategy. The computer security...

A DDoS-Aware IDS Model Based on Danger Theory and Mobile Agents

Zamani, Mahdi; Movahedi, Mahnush; Ebadzadeh, Mohammad; Pedram, Hossein
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
477.2691%
We propose an artificial immune model for intrusion detection in distributed systems based on a relatively recent theory in immunology called Danger theory. Based on Danger theory, immune response in natural systems is a result of sensing corruption as well as sensing unknown substances. In contrast, traditional self-nonself discrimination theory states that immune response is only initiated by sensing nonself (unknown) patterns. Danger theory solves many problems that could only be partially explained by the traditional model. Although the traditional model is simpler, such problems result in high false positive rates in immune-inspired intrusion detection systems. We believe using danger theory in a multi-agent environment that computationally emulates the behavior of natural immune systems is effective in reducing false positive rates. We first describe a simplified scenario of immune response in natural systems based on danger theory and then, convert it to a computational model as a network protocol. In our protocol, we define several immune signals and model cell signaling via message passing between agents that emulate cells. Most messages include application-specific patterns that must be meaningfully extracted from various system properties. We show how to model these messages in practice by performing a case study on the problem of detecting distributed denial-of-service attacks in wireless sensor networks. We conduct a set of systematic experiments to find a set of performance metrics that can accurately distinguish malicious patterns. The results indicate that the system can be efficiently used to detect malicious patterns with a high level of accuracy.; Comment: 10 pages...

Distributed Computing with Adaptive Heuristics

Jaggard, Aaron D.; Schapira, Michael; Wright, Rebecca N.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
477.8975%
We use ideas from distributed computing to study dynamic environments in which computational nodes, or decision makers, follow adaptive heuristics (Hart 2005), i.e., simple and unsophisticated rules of behavior, e.g., repeatedly "best replying" to others' actions, and minimizing "regret", that have been extensively studied in game theory and economics. We explore when convergence of such simple dynamics to an equilibrium is guaranteed in asynchronous computational environments, where nodes can act at any time. Our research agenda, distributed computing with adaptive heuristics, lies on the borderline of computer science (including distributed computing and learning) and game theory (including game dynamics and adaptive heuristics). We exhibit a general non-termination result for a broad class of heuristics with bounded recall---that is, simple rules of behavior that depend only on recent history of interaction between nodes. We consider implications of our result across a wide variety of interesting and timely applications: game theory, circuit design, social networks, routing and congestion control. We also study the computational and communication complexity of asynchronous dynamics and present some basic observations regarding the effects of asynchrony on no-regret dynamics. We believe that our work opens a new avenue for research in both distributed computing and game theory.; Comment: 36 pages...

String diagrams for game theory

Hedges, Jules
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 20/03/2015 Português
Relevância na Pesquisa
476.19773%
This paper presents a monoidal category whose morphisms are games (in the sense of game theory, not game semantics) and an associated diagrammatic language. The two basic operations of a monoidal category, namely categorical composition and tensor product, correspond roughly to sequential and simultaneous composition of games. This leads to a compositional theory in which we can reason about properties of games in terms of corresponding properties of the component parts. In particular, we give a definition of Nash equilibrium which is recursive on the causal structure of the game. The key technical idea in this paper is the use of continuation passing style for reasoning about the future consequences of players' choices, closely based on applications of selection functions in game theory. Additionally, the clean categorical foundation gives many opportunities for generalisation, for example to learning agents.

Towards a readable formalisation of category theory

O'Keefe, Greg
Fonte: Elsevier Publicador: Elsevier
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
553.211%
We formally develop category theory up to Yoneda's lemma, using Isabelle/HOL/Isar, and survey previous formalisations. By using recently added Isabelle features, we have produced a formal text that more closely approximates informal mathematics.