Search results for "Theoretical Computer Science"
showing 10 items of 1151 documents
An efficient distributed algorithm for generating and updating multicast trees
2006
As group applications are becoming widespread, efficient network utilization becomes a growing concern. Multicast transmission represents a necessary lower network service for the wide diffusion of new multimedia network applications. Multicast transmission may use network resources more efficiently than multiple point-to-point messages; however, creating optimal multicast trees (Steiner Tree Problem in networks) is prohibitively expensive. This paper proposes a distributed algorithm for the heuristic solution of the Steiner Tree Problem, allowing the construction of effective distribution trees using a coordination protocol among the network nodes. Furthermore, we propose a novel distribut…
Introduction to the GiNaC Framework for Symbolic Computation within the C++ Programming Language
2002
AbstractThe traditional split into a low level language and a high level language in the design of computer algebra systems may become obsolete with the advent of more versatile computer languages. We describe GiNaC, a special-purpose system that deliberately denies the need for such a distinction. It is entirely written in C++and the user can interact with it directly in that language. It was designed to provide efficient handling of multivariate polynomials, algebras and special functions that are needed for loop calculations in theoretical quantum field theory. It also bears some potential to become a more general purpose symbolic package.
Crowd-Averse Cyber-Physical Systems: The Paradigm of Robust Mean-Field Games
2016
For a networked controlled system, we illustrate the paradigm of robust mean-field games. This is a modeling framework at the interface of differential game theory, mathematical physics, and $H_{\infty}$ - optimal control that tries to capture the mutual influence between a crowd and its individuals. First, we establish a mean-field system for such games including the effects of adversarial disturbances. Second, we identify the optimal response of the individuals for a given population behavior. Third, we provide an analysis of equilibria and their stability.
Computational Complexity and Communication: Coordination in Two-Player Games
2002
The main contribution of this paper is the development and application of cryptographic techniques to the design of strategic communication mechanisms. One of the main assumptions in cryptography is the limitation of the computational power available to agents. We introduce the concept of limited computational complexity, and by borrowing results from cryptography, we construct a communication protocol to establish that every correlated equilibrium of a two-person game with rational payoffs can be achieved by means of computationally restricted unmediated communication. This result provides an example in game theory where limitations of computational abilities of players are helpful in solv…
Pragmatic languages with universal grammars
2012
Abstract This paper constructs the equilibrium for a specific code that can be seen as a “universal grammar” in a class of common interest Sender–Receiver games where players communicate through a noisy channel. We propose a Senderʼs signaling strategy which does not depend on either the game payoffs or the initial probability distribution. The Receiverʼs strategy partitions the set of possible sequences into subsets, with a single action assignment to each of them. The Senderʼs signaling strategy is a Nash equilibrium, i.e. when the Receiver responds best to the Senderʼs strategy, the Sender has no incentive to deviate. An example shows that a tie-breaking decoding is crucial for the block…
Quantum-over-Classical Advantage in Solving Multiplayer Games
2020
We study the applicability of quantum algorithms in computational game theory and generalize some results related to Subtraction games, which are sometimes referred to as one-heap Nim games.
Modular Strategies for Recursive Game Graphs
2006
AbstractMany problems in formal verification and program analysis can be formalized as computing winning strategies for two-player games on graphs. In this paper, we focus on solving games in recursive game graphs which can model the control flow in sequential programs with recursive procedure calls. While such games can be viewed as the pushdown games studied in the literature, the natural notion of winning in our framework requires the strategies to be modular with only local memory; that is, resolution of choices within a module does not depend on the context in which the module is invoked, but only on the history within the current invocation of the module. While reachability in (global…
Advantage of Quantum Strategies in Random Symmetric XOR Games
2013
Non-local games are known as a simple but useful model which is widely used for displaying nonlocal properties of quantum mechanics. In this paper we concentrate on a simple subset of non-local games: multiplayer XOR games with 1-bit inputs and 1-bit outputs which are symmetric w.r.t. permutations of players.
Learning by the Process of Elimination
2002
AbstractElimination of potential hypotheses is a fundamental component of many learning processes. In order to understand the nature of elimination, herein we study the following model of learning recursive functions from examples. On any target function, the learning machine has to eliminate all, save one, possible hypotheses such that the missing one correctly describes the target function. It turns out that this type of learning by the process of elimination (elm-learning, for short) can be stronger, weaker or of the same power as usual Gold style learning.While for usual learning any r.e. class of recursive functions can be learned in all of its numberings, this is no longer true for el…
A Similarity Evaluation Technique for Cooperative Problem Solving with a Group of Agents
1999
Evaluation of distance or similarity is very important in cooperative problem solving with a group of agents. Distance between problems is used by agents to recognize nearest solved problems for a new problem, distance between solutions is necessary to compare and evaluate the solutions made by different agents, and distance between agents is useful to evaluate weights of the agents to be able to integrate them by weighted voting. The goal of this paper is to develop a similarity evaluation technique to be used for cooperative problem solving with a group of agents. Virtual training environment used for this goal is represented by predicates that define relationships within three sets: prob…