Archives for 2003

Today I read a paper titled “On the NP-completeness of Finding an Optimal Strategy in Games with Common Payoffs”

The abstract is:
Consider a very simple class of (finite) games: after an initial move by nature, each player makes one move.

Moreover, the players have common interests: at each node, all the players get the same payoff.

We show that the problem of determining whether there exists a joint strategy where each player has an expected payoff of at least r is NP-complete as a function of the number of nodes in the extensive-form representation of the game..

Today I read a paper titled “Kalman filter control in the reinforcement learning framework”

The abstract is:
There is a growing interest in using Kalman-filter models in brain modelling.

In turn, it is of considerable importance to make Kalman-filters amenable for reinforcement learning.

In the usual formulation of optimal control it is computed off-line by solving a backward recursion.

In this technical note we show that slight modification of the linear-quadratic-Gaussian Kalman-filter model allows the on-line estimation of optimal control and makes the bridge to reinforcement learning.

Moreover, the learning rule for value estimation assumes a Hebbian form weighted by the error of the value estimation.

Today I read a paper titled “When being Weak is Brave: Privacy in Recommender Systems”

The abstract is:
We explore the conflict between personalization and privacy that arises from the existence of weak ties.

A weak tie is an unexpected connection that provides serendipitous recommendations.

However, information about weak ties could be used in conjunction with other sources of data to uncover identities and reveal other personal information.

In this article, we use a graph-theoretic model to study the benefit and risk from weak ties.

Today I read a paper titled “Detecting Race Conditions in Parallel Programs that Use Semaphores”

The abstract is:
We address the problem of detecting race conditions in programs that use semaphores for synchronization.

Netzer and Miller showed that it is NP-complete to detect race conditions in programs that use many semaphores.

We show in this paper that it remains NP-complete even if only two semaphores are used in the parallel programs.

For the tractable case, i.e., using only one semaphore, we give two algorithms for detecting race conditions from the trace of executing a parallel program on p processors, where n semaphore operations are executed.

The first algorithm determines in O(n) time whether a race condition exists between any two given operations.

The second algorithm runs in O(np log n) time and outputs a compact representation from which one can determine in O(1) time whether a race condition exists between any two given operations.

The second algorithm is near-optimal in that the running time is only O(log n) times the time required simply to write down the output.

Today I read a paper titled “On the Sum-of-Squares Algorithm for Bin Packing”

The abstract is:
In this paper we present a theoretical analysis of the deterministic on-line {\em Sum of Squares} algorithm ($SS$) for bin packing introduced and studied experimentally in \cite{CJK99}, along with several new variants.

$SS$ is applicable to any instance of bin packing in which the bin capacity $B$ and item sizes $s(a)$ are integral (or can be scaled to be so), and runs in time $O(nB)$.

It performs remarkably well from an average case point of view: For any discrete distribution in which the optimal expected waste is sublinear, $SS$ also has sublinear expected waste.

For any discrete distribution where the optimal expected waste is bounded, $SS$ has expected waste at most $O(\log n)$.

In addition, we discuss several interesting variants on $SS$, including a randomized $O(nB\log B)$-time on-line algorithm $SS^*$, based on $SS$, whose expected behavior is essentially optimal for all discrete distributions.

Algorithm $SS^*$ also depends on a new linear-programming-based pseudopolynomial-time algorithm for solving the NP-hard problem of determining, given a discrete distribution $F$, just what is the growth rate for the optimal expected waste.

This article is a greatly expanded version of the conference paper \cite{sumsq2000}.

Today I read a paper titled “Fast Hands-free Writing by Gaze Direction”

The abstract is:
We describe a method for text entry based on inverse arithmetic coding that relies on gaze direction and which is faster and more accurate than using an on-screen keyboard.

These benefits are derived from two innovations: the writing task is matched to the capabilities of the eye, and a language model is used to make predictable words and phrases easier to write.

Today I read a paper titled “Some Advances in Transformation-Based Part of Speech Tagging”

The abstract is:
Most recent research in trainable part of speech taggers has explored stochastic tagging.

While these taggers obtain high accuracy, linguistic information is captured indirectly, typically in tens of thousands of lexical and contextual probabilities.

In [Brill92], a trainable rule-based tagger was described that obtained performance comparable to that of stochastic taggers, but captured relevant linguistic information in a small number of simple non-stochastic rules.

In this paper, we describe a number of extensions to this rule-based tagger.

First, we describe a method for expressing lexical relations in tagging that are not captured by stochastic taggers.

Next, we show a rule-based approach to tagging unknown words.

Finally, we show how the tagger can be extended into a k-best tagger, where multiple tags can be assigned to words in some cases of uncertainty..

Today I read a paper titled “Generalized Cores”

The abstract is:
Cores are, besides connectivity components, one among few concepts that provides us with efficient decompositions of large graphs and networks.

In the paper a generalization of the notion of core of a graph based on vertex property function is presented.

It is shown that for the local monotone vertex property functions the corresponding cores can be determined in $O(m \max (\Delta, \log n))$ time.

Today I read a paper titled “Fuzzy Approaches to Abductive Inference”

The abstract is:
This paper proposes two kinds of fuzzy abductive inference in the framework of fuzzy rule base.

The abductive inference processes described here depend on the semantic of the rule.

We distinguish two classes of interpretation of a fuzzy rule, certainty generation rules and possible generation rules.

In this paper we present the architecture of abductive inference in the first class of interpretation.

We give two kinds of problem that we can resolve by using the proposed models of inference.

Today I read a paper titled “Searching for Spaceships”

The abstract is:
We describe software that searches for spaceships in Conway’s Game of Life and related two-dimensional cellular automata.

Our program searches through a state space related to the de Bruijn graph of the automaton, using a method that combines features of breadth first and iterative deepening search, and includes fast bit-parallel graph reachability and path enumeration algorithms for finding the successors of each state.

Successful results include a new 2c/7 spaceship in Life, found by searching a space with 2^126 states.

Today I read a paper titled “Cluster Computing: A High-Performance Contender”

The abstract is:
When you first heard people speak of Piles of PCs, the first thing that came to mind may have been a cluttered computer room with processors, monitors, and snarls of cables all around.

Collections of computers have undoubtedly become more sophisticated than in the early days of shared drives and modem connections.

No matter what you call them, Clusters of Workstations (COW), Networks of Workstations (NOW), Workstation Clusters (WCs), Clusters of PCs (CoPs), clusters of computers are now filling the processing niche once occupied by more powerful stand-alone machines.

This article discusses the need for cluster computing technology, Technologies, Components, and Applications, Supercluster Systems and Issues, The Need for a New Task Force, and Cluster Computing Educational Resources.

Today I read a paper titled “Sorting with a forklift”

The abstract is:
A fork stack is a generalised stack which allows pushes and pops of several items at a time.

We consider the problem of determining which input streams can be sorted using a single forkstack, or dually, which permutations of a fixed input stream can be produced using a single forkstack.

An algorithm is given to solve the sorting problem and the minimal unsortable sequences are found.

The results are extended to fork stacks where there are bounds on how many items can be pushed and popped at one time.

In this context we also establish how to enumerate the collection of sortable sequences.

Today I read a paper titled “Provably Bounded-Optimal Agents”

The abstract is:
Since its inception, artificial intelligence has relied upon a theoretical foundation centered around perfect rationality as the desired property of intelligent systems.

We argue, as others have done, that this foundation is inadequate because it imposes fundamentally unsatisfiable requirements.

As a result, there has arisen a wide gap between theory and practice in AI, hindering progress in the field.

We propose instead a property called bounded optimality.

Roughly speaking, an agent is bounded-optimal if its program is a solution to the constrained optimization problem presented by its architecture and the task environment.

We show how to construct agents with this property for a simple class of machine architectures in a broad class of real-time environments.

We illustrate these results using a simple model of an automated mail sorting facility.

We also define a weaker property, asymptotic bounded optimality (ABO), that generalizes the notion of optimality in classical complexity theory.

We then construct universal ABO programs, i.e., programs that are ABO no matter what real-time constraints are applied.

Universal ABO programs can be used as building blocks for more complex systems.

We conclude with a discussion of the prospects for bounded optimality as a theoretical basis for AI, and relate it to similar trends in philosophy, economics, and game theory..

Today I read a paper titled “Optimal Aggregation Algorithms for Middleware”

The abstract is:
Let D be a database of N objects where each object has m fields.

The objects are given in m sorted lists (where the ith list is sorted according to the ith field).

Our goal is to find the top k objects according to a monotone aggregation function t, while minimizing access to the lists.

The problem arises in several contexts.

In particular Fagin (JCSS 1999) considered it for the purpose of aggregating information in a multimedia database system.

We are interested in instance optimality, i.e.

that our algorithm will be as good as any other (correct) algorithm on any instance.

We provide and analyze several instance optimal algorithms for the task, with various access costs and models.