justin

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.

Today I read a paper titled “Computer-Generated Photorealistic Hair”

The abstract is:
This paper presents an efficient method for generating and rendering photorealistic hair in two dimensional pictures.

The method consists of three major steps.

Simulating an artist drawing is used to design the rough hair shape.

A convolution based filter is then used to generate photorealistic hair patches.

A refine procedure is finally used to blend the boundaries of the patches with surrounding areas.

This method can be used to create all types of photorealistic human hair (head hair, facial hair and body hair).

It is also suitable for fur and grass generation.

Applications of this method include: hairstyle designing/editing, damaged hair image restoration, human hair animation, virtual makeover of a human, and landscape creation..

Today I read a paper titled “The Risk Profile Problem for Stock Portfolio Optimization”

The abstract is:
This work initiates research into the problem of determining an optimal investment strategy for investors with different attitudes towards the trade-offs of risk and profit.

The probability distribution of the return values of the stocks that are considered by the investor are assumed to be known, while the joint distribution is unknown.

The problem is to find the best investment strategy in order to minimize the probability of losing a certain percentage of the invested capital based on different attitudes of the investors towards future outcomes of the stock market.

For portfolios made up of two stocks, this work shows how to exactly and quickly solve the problem of finding an optimal portfolio for aggressive or risk-averse investors, using an algorithm based on a fast greedy solution to a maximum flow problem.

However, an investor looking for an average-case guarantee (so is neither aggressive or risk-averse) must deal with a more difficult problem.

In particular, it is #P-complete to compute the distribution function associated with the average-case bound.

On the positive side, approximate answers can be computed by using random sampling techniques similar to those for high-dimensional volume estimation.

When k>2 stocks are considered, it is proved that a simple solution based on the same flow concepts as the 2-stock algorithm would imply that P = NP, so is highly unlikely.

This work gives approximation algorithms for this case as well as exact algorithms for some important special cases.

Today I read a paper titled “Behaviour-based Knowledge Systems: An Epigenetic Path from Behaviour to Knowledge”

The abstract is:
In this paper we expose the theoretical background underlying our current research.

This consists in the development of behaviour-based knowledge systems, for closing the gaps between behaviour-based and knowledge-based systems, and also between the understandings of the phenomena they model.

We expose the requirements and stages for developing behaviour-based knowledge systems and discuss their limits.

We believe that these are necessary conditions for the development of higher order cognitive capacities, in artificial and natural cognitive systems.

Today I read a paper titled “Towards a Theory of Cache-Efficient Algorithms”

The abstract is:
We describe a model that enables us to analyze the running time of an algorithm in a computer with a memory hierarchy with limited associativity, in terms of various cache parameters.

Our model, an extension of Aggarwal and Vitter’s I/O model, enables us to establish useful relationships between the cache complexity and the I/O complexity of computations.

As a corollary, we obtain cache-optimal algorithms for some fundamental problems like sorting, FFT, and an important subclass of permutations in the single-level cache model.

We also show that ignoring associativity concerns could lead to inferior performance, by analyzing the average-case cache behavior of mergesort.

We further extend our model to multiple levels of cache with limited associativity and present optimal algorithms for matrix transpose and sorting.

Our techniques may be used for systematic exploitation of the memory hierarchy starting from the algorithm design stage, and dealing with the hitherto unresolved problem of limited associativity.

Today I read a paper titled “Map Graphs”

The abstract is:
We consider a modified notion of planarity, in which two nations of a map are considered adjacent when they share any point of their boundaries (not necessarily an edge, as planarity requires).

Such adjacencies define a map graph.

We give an NP characterization for such graphs, and a cubic time recognition algorithm for a restricted version: given a graph, decide whether it is realized by adjacencies in a map without holes, in which at most four nations meet at any point.

Today I read a paper titled “Fully Sequential and Distributed Dynamic Algorithms for Minimum Spanning Trees”

The abstract is:
In this paper, we present a fully-dynamic distributed algorithm for maintaining a minimum spanning tree on general graphs with positive real edge weights.

The goal of a dynamic MST algorithm is to update efficiently the minimum spanning tree after dynamic changes like edge weight changes, rather than having to recompute it from scatch each time.

The first part of the paper surveys various algorithms available today both in sequential and distributed environments to solve static MST problem.

We also present some of the efficient sequential algorithms for computing dynamic MST like the Frederickson’s algorithm and Eppstein’s sparsification technique.

Lastly we present our new sequential and distributed algorithms for dynamic MST problem.

To our knowledge, this is the first of the distributed algorithms for computing dynamic MSTs.