The science papers I've read

Today I read a paper titled “Robust Classification with Context-Sensitive Features”

The abstract is:
This paper addresses the problem of classifying observations when features are context-sensitive, especially when the testing set involves a context that is different from the training set.

The paper begins with a precise definition of the problem, then general strategies are presented for enhancing the performance of classification algorithms on this type of problem.

These strategies are tested on three domains.

The first domain is the diagnosis of gas turbine engines.

The problem is to diagnose a faulty engine in one context, such as warm weather, when the fault has previously been seen only in another context, such as cold weather.

The second domain is speech recognition.

The context is given by the identity of the speaker.

The problem is to recognize words spoken by a new speaker, not represented in the training set.

The third domain is medical prognosis.

The problem is to predict whether a patient with hepatitis will live or die.

The context is the age of the patient.

For all three domains, exploiting context results in substantially more accurate classification.

Today I read a paper titled “Automatically Generating Interfaces for Personalized Interaction with Digital Libraries”

The abstract is:
We present an approach to automatically generate interfaces supporting personalized interaction with digital libraries; these interfaces augment the user-DL dialog by empowering the user to (optionally) supply out-of-turn information during an interaction, flatten or restructure the dialog, and enquire about dialog options.

Interfaces generated using this approach for CITIDEL are described.

Today I read a paper titled “The Freeze-Tag Problem: How to Wake Up a Swarm of Robots”

The abstract is:
An optimization problem that naturally arises in the study of swarm robotics is the Freeze-Tag Problem (FTP) of how to awaken a set of “asleep” robots, by having an awakened robot move to their locations.

Once a robot is awake, it can assist in awakening other slumbering robots.The objective is to have all robots awake as early as possible.

While the FTP bears some resemblance to problems from areas in combinatorial optimization such as routing, broadcasting, scheduling, and covering, its algorithmic characteristics are surprisingly different.

We consider both scenarios on graphs and in geometric environments.In graphs, robots sleep at vertices and there is a length function on the edges.

Awake robots travel along edges, with time depending on edge length.

For most scenarios, we consider the offline version of the problem, in which each awake robot knows the position of all other robots.

We prove that the problem is NP-hard, even for the special case of star graphs.

We also establish hardness of approximation, showing that it is NP-hard to obtain an approximation factor better than 5/3, even for graphs of bounded degree.These lower bounds are complemented with several positive algorithmic results, including: (1) We show that the natural greedy strategy on star graphs has a tight worst-case performance of 7/3 and give a polynomial-time approximation scheme (PTAS) for star graphs.

(2) We give a simple O(log D)-competitive online algorithm for graphs with maximum degree D and locally bounded edge weights.

(3) We give a PTAS, running in nearly linear time, for geometrically embedded instances.

Today I read a paper titled “The Interactive Minority Game: a Web-based investigation of human market interactions”

The abstract is:
The unprecedented access offered by the World Wide Web brings with it the potential to gather huge amounts of data on human activities.

Here we exploit this by using a toy model of financial markets, the Minority Game (MG), to investigate human speculative trading behaviour and information capacity.

Hundreds of individuals have played a total of tens of thousands of game turns against computer-controlled agents in the Web-based_Interactive Minority Game_.

The analytical understanding of the MG permits fine-tuning of the market situations encountered, allowing for investigation of human behaviour in a variety of controlled environments.

In particular, our results indicate a transition in players’ decision-making, as the markets become more difficult, between deductive behaviour making use of short-term trends in the market, and highly repetitive behaviour that ignores entirely the market history, yet outperforms random decision-making.

PACS: 02.50.Le; 89.65.Gh; 89.70.+c Keywords: Decision theory and game theory; Economics and financial markets; Information theory .

Today I read a paper titled “Algorithmic Clustering of Music”

The abstract is:
We present a fully automatic method for music classification, based only on compression of strings that represent the music pieces.

The method uses no background knowledge about music whatsoever: it is completely general and can, without change, be used in different areas like linguistic classification and genomics.

It is based on an ideal theory of the information content in individual objects (Kolmogorov complexity), information distance, and a universal similarity metric.

Experiments show that the method distinguishes reasonably well between various musical genres and can even cluster pieces by composer.

Today I read a paper titled “The one-round Voronoi game replayed”

The abstract is:
We consider the one-round Voronoi game, where player one (“White”, called “Wilma”) places a set of n points in a rectangular area of aspect ratio r <=1, followed by the second player (``Black'', called ``Barney''), who places the same number of points.

Each player wins the fraction of the board closest to one of his points, and the goal is to win more than half of the total area.

This problem has been studied by Cheong et al., who showed that for large enough $n$ and r=1, Barney has a strategy that guarantees a fraction of 1/2+a, for some small fixed a.

We resolve a number of open problems raised by that paper.

In particular, we give a precise characterization of the outcome of the game for optimal play: We show that Barney has a winning strategy for n>2 and r>sqrt{2}/n, and for n=2 and r>sqrt{3}/2.

Wilma wins in all remaining cases, i.e., for n>=3 and r<=sqrt{2}/n, for n=2 and r<=sqrt{3}/2, and for n=1.

We also discuss complexity aspects of the game on more general boards, by proving that for a polygon with holes, it is NP-hard to maximize the area Barney can win against a given set of points by Wilma.

Today I read a paper titled “Cyborg Systems as Platforms for Computer-Vision Algorithm-Development for Astrobiology”

The abstract is:
Employing the allegorical imagery from the film “The Matrix”, we motivate and discuss our `Cyborg Astrobiologist’ research program.

In this research program, we are using a wearable computer and video camcorder in order to test and train a computer-vision system to be a field-geologist and field-astrobiologist.

Today I read a paper titled “The Graphics Card as a Streaming Computer”

The abstract is:
Massive data sets have radically changed our understanding of how to design efficient algorithms; the streaming paradigm, whether it in terms of number of passes of an external memory algorithm, or the single pass and limited memory of a stream algorithm, appears to be the dominant method for coping with large data.

A very different kind of massive computation has had the same effect at the level of the CPU.

The most prominent example is that of the computations performed by a graphics card.

The operations themselves are very simple, and require very little memory, but require the ability to perform many computations extremely fast and in parallel to whatever degree possible.

What has resulted is a stream processor that is highly optimized for stream computations.

An intriguing side effect of this is the growing use of a graphics card as a general purpose stream processing engine.

In an ever-increasing array of applications, researchers are discovering that performing a computation on a graphics card is far faster than performing it on a CPU, and so are using a GPU as a stream co-processor..

Today I read a paper titled “Local Community Identification through User Access Patterns”

The abstract is:
Community identification algorithms have been used to enhance the quality of the services perceived by its users.

Although algorithms for community have a widespread use in the Web, their application to portals or specific subsets of the Web has not been much studied.

In this paper, we propose a technique for local community identification that takes into account user access behavior derived from access logs of servers in the Web.

The technique takes a departure from the existing community algorithms since it changes the focus of in terest, moving from authors to users.

Our approach does not use relations imposed by authors (e.g.

hyperlinks in the case of Web pages).

It uses information derived from user accesses to a service in order to infer relationships.

The communities identified are of great interest to content providers since they can be used to improve quality of their services.

We also propose an evaluation methodology for analyzing the results obtained by the algorithm.

We present two case studies based on actual data from two services: an online bookstore and an online radio.

The case of the online radio is particularly relevant, because it emphasizes the contribution of the proposed algorithm to find out communities in an environment (i.e., streaming media service) without links, that represent the relations imposed by authors (e.g.

hyperlinks in the case of Web pages).

Today I read a paper titled “On multiple connectedness of regions visible due to multiple diffuse reflections”

The abstract is:
It is known that the region V(s) of a simple polygon P, directly visible (illuminable) from an internal point s, is simply connected.

Aronov et al.

\cite{addpp981} established that the region V1(s) of a simple polygon visible from an internal point s due to at most one diffuse reflection on the boundary of the polygon P, is also simply connected.

In this paper we establish that the region V2(s), visible from s due to at most two diffuse reflections may be multiply connected; we demonstrate the construction of an n-sided simple polygon with a point s inside it so that and the region of P visible from s after at most two diffuse reflections is multiple connected..

Today I read a paper titled “Towards a Model-Based Framework for Integrating Usability and Software Engineering Life Cycles”

The abstract is:
In this position paper we propose a process model that provides a development infrastructure in which the usability engineering and software engineering life cycles co-exist in complementary roles.

We describe the motivation, hurdles, rationale, arguments, and implementation plan for the need, specification, and the usefulness of such a model.

Today I read a paper titled “Embedded Reflection Mapping”

The abstract is:
Environment maps are used to simulate reflections off curved objects.

We present a technique to reflect a user, or a group of users, in a real environment, onto a virtual object, in a virtual reality application, using the live video feeds from a set of cameras, in real-time.

Our setup can be used in a variety of environments ranging from outdoor or indoor scenes..

Today I read a paper titled “Communities of Practice: Going Virtual”

The abstract is:
With the current trends towards downsizing, outsourcing and globalisation, modern organisations are reducing the numbers of people they employ.

In addition, organisations now have to cope with the increasing internationalisation of business forcing collaboration and knowledge sharing across time and distance simultaneously.

There is a need for new ways of thinking about how knowledge is shared in distributed groups.

In this paper we explore a relatively new approach to knowledge sharing using Lave and Wenger’s (1991) theory of Communities of Practice (CoPs).

We investigate whether CoPs might translate to a geographically distributed international environment through a case study that explores the functioning of a CoP across national boundaries.

Today I read a paper titled “Practical and Robust Stenciled Shadow Volumes for Hardware-Accelerated Rendering”

The abstract is:
Twenty-five years ago, Crow published the shadow volume approach for determining shadowed regions in a scene.

A decade ago, Heidmann described a hardware-accelerated stencil buffer-based shadow volume algorithm.

Unfortunately hardware-accelerated stenciled shadow volume techniques have not been widely adopted by 3D games and applications due in large part to the lack of robustness of described techniques.

This situation persists despite widely available hardware support.

Specifically what has been lacking is a technique that robustly handles various “hard” situations created by near or far plane clipping of shadow volumes.

We describe a robust, artifact-free technique for hardware-accelerated rendering of stenciled shadow volumes.

Assuming existing hardware, we resolve the issues otherwise caused by shadow volume near and far plane clipping through a combination of (1) placing the conventional far clip plane “at infinity”, (2) rasterization with infinite shadow volume polygons via homogeneous coordinates, and (3) adopting a zfail stencil-testing scheme.

Depth clamping, a new rasterization feature provided by NVIDIA’s GeForce3, preserves existing depth precision by not requiring the far plane to be placed at infinity.

We also propose two-sided stencil testing to improve the efficiency of rendering stenciled shadow volumes..

Today I read a paper titled “An evaluation of Naive Bayesian anti-spam filtering”

The abstract is:
It has recently been argued that a Naive Bayesian classifier can be used to filter unsolicited bulk e-mail (“spam”).

We conduct a thorough evaluation of this proposal on a corpus that we make publicly available, contributing towards standard benchmarks.

At the same time we investigate the effect of attribute-set size, training-corpus size, lemmatization, and stop-lists on the filter’s performance, issues that had not been previously explored.

After introducing appropriate cost-sensitive evaluation measures, we reach the conclusion that additional safety nets are needed for the Naive Bayesian anti-spam filter to be viable in practice.

Today I read a paper titled “Enhancing a Search Algorithm to Perform Intelligent Backtracking”

The abstract is:
This paper illustrates how a Prolog program, using chronological backtracking to find a solution in some search space, can be enhanced to perform intelligent backtracking.

The enhancement crucially relies on the impurity of Prolog that allows a program to store information when a dead end is reached.

To illustrate the technique, a simple search program is enhanced.

To appear in Theory and Practice of Logic Programming.

Keywords: intelligent backtracking, dependency-directed backtracking, backjumping, conflict-directed backjumping, nogood sets, look-back.

Today I read a paper titled “Sequence Prediction based on Monotone Complexity”

The abstract is:
This paper studies sequence prediction based on the monotone Kolmogorov complexity Km=-log m, i.e.

based on universal deterministic/one-part MDL.

m is extremely close to Solomonoff’s prior M, the latter being an excellent predictor in deterministic as well as probabilistic environments, where performance is measured in terms of convergence of posteriors or losses.

Despite this closeness to M, it is difficult to assess the prediction quality of m, since little is known about the closeness of their posteriors, which are the important quantities for prediction.

We show that for deterministic computable environments, the “posterior” and losses of m converge, but rapid convergence could only be shown on-sequence; the off-sequence behavior is unclear.

In probabilistic environments, neither the posterior nor the losses converge, in general.

Today I read a paper titled “A Game Theoretic Framework for Incentives in P2P Systems”

The abstract is:
Peer-To-Peer (P2P) networks are self-organizing, distributed systems, with no centralized authority or infrastructure.

Because of the voluntary participation, the availability of resources in a P2P system can be highly variable and unpredictable.

In this paper, we use ideas from Game Theory to study the interaction of strategic and rational peers, and propose a differential service-based incentive scheme to improve the system’s performance.

Today I read a paper titled “How Push-To-Talk Makes Talk Less Pushy”

The abstract is:
This paper presents an exploratory study of college-age students using two-way, push-to-talk cellular radios.

We describe the observed and reported use of cellular radio by the participants.

We discuss how the half-duplex, lightweight cellular radio communication was associated with reduced interactional commitment, which meant the cellular radios could be used for a wide range of conversation styles.

One such style, intermittent conversation, is characterized by response delays.

Intermittent conversation is surprising in an audio medium, since it is typically associated with textual media such as instant messaging.

We present design implications of our findings.

Today I read a paper titled “A Bayesian Reflection on Surfaces”

The abstract is:
The topic of this paper is a novel Bayesian continuous-basis field representation and inference framework.

Within this paper several problems are solved: The maximally informative inference of continuous-basis fields, that is where the basis for the field is itself a continuous object and not representable in a finite manner; the tradeoff between accuracy of representation in terms of information learned, and memory or storage capacity in bits; the approximation of probability distributions so that a maximal amount of information about the object being inferred is preserved; an information theoretic justification for multigrid methodology.

The maximally informative field inference framework is described in full generality and denoted the Generalized Kalman Filter.

The Generalized Kalman Filter allows the update of field knowledge from previous knowledge at any scale, and new data, to new knowledge at any other scale.

An application example instance, the inference of continuous surfaces from measurements (for example, camera image data), is presented.

Today I read a paper titled “Collusion in Unrepeated, First-Price Auctions with an Uncertain Number of Participants”

The abstract is:
We consider the question of whether collusion among bidders (a “bidding ring”) can be supported in equilibrium of unrepeated first-price auctions.

Unlike previous work on the topic such as that by McAfee and McMillan [1992] and Marshall and Marx [2007], we do not assume that non-colluding agents have perfect knowledge about the number of colluding agents whose bids are suppressed by the bidding ring, and indeed even allow for the existence of multiple cartels.

Furthermore, while we treat the association of bidders with bidding rings as exogenous, we allow bidders to make strategic decisions about whether to join bidding rings when invited.

We identify a bidding ring protocol that results in an efficient allocation in Bayes{Nash equilibrium, under which non-colluding agents bid straightforwardly, and colluding agents join bidding rings when invited and truthfully declare their valuations to the ring center.

We show that bidding rings benefit ring centers and all agents, both members and non-members of bidding rings, at the auctioneer’s expense.

The techniques we introduce in this paper may also be useful for reasoning about other problems in which agents have asymmetric information about a setting..

Today I read a paper titled “Circle and sphere blending with conformal geometric algebra”

The abstract is:
Blending schemes based on circles provide smooth `fair’ interpolations between series of points.

Here we demonstrate a simple, robust set of algorithms for performing circle blends for a range of cases.

An arbitrary level of G-continuity can be achieved by simple alterations to the underlying parameterisation.

Our method exploits the computational framework provided by conformal geometric algebra.

This employs a five-dimensional representation of points in space, in contrast to the four-dimensional representation typically used in projective geometry.

The advantage of the conformal scheme is that straight lines and circles are treated in a single, unified framework.

As a further illustration of the power of the conformal framework, the basic idea is extended to the case of sphere blending to interpolate over a surface..

Today I read a paper titled “Fault-tolerant routing in peer-to-peer systems”

The abstract is:
We consider the problem of designing an overlay network and routing mechanism that permits finding resources efficiently in a peer-to-peer system.

We argue that many existing approaches to this problem can be modeled as the construction of a random graph embedded in a metric space whose points represent resource identifiers, where the probability of a connection between two nodes depends only on the distance between them in the metric space.

We study the performance of a peer-to-peer system where nodes are embedded at grid points in a simple metric space: a one-dimensional real line.

We prove upper and lower bounds on the message complexity of locating particular resources in such a system, under a variety of assumptions about failures of either nodes or the connections between them.

Our lower bounds in particular show that the use of inverse power-law distributions in routing, as suggested by Kleinberg (1999), is close to optimal.

We also give efficient heuristics to dynamically maintain such a system as new nodes arrive and old nodes depart.

Finally, we give experimental results that suggest promising directions for future work.

Today I read a paper titled “Bayesian Grammar Induction for Language Modeling”

The abstract is:
We describe a corpus-based induction algorithm for probabilistic context-free grammars.

The algorithm employs a greedy heuristic search within a Bayesian framework, and a post-pass using the Inside-Outside algorithm.

We compare the performance of our algorithm to n-gram models and the Inside-Outside algorithm in three language modeling tasks.

In two of the tasks, the training data is generated by a probabilistic context-free grammar and in both tasks our algorithm outperforms the other techniques.

The third task involves naturally-occurring data, and in this task our algorithm does not perform as well as n-gram models but vastly outperforms the Inside-Outside algorithm..

Today I read a paper titled “The Mysterious Optimality of Naive Bayes: Estimation of the Probability in the System of “Classifiers””

The abstract is:
Bayes Classifiers are widely used currently for recognition, identification and knowledge discovery.

The fields of application are, for example, image processing, medicine, chemistry (QSAR).

But by mysterious way the Naive Bayes Classifier usually gives a very nice and good presentation of a recognition.

It can not be improved considerably by more complex models of Bayes Classifier.

We demonstrate here a very nice and simple proof of the Naive Bayes Classifier optimality, that can explain this interesting fact.The derivation in the current paper is based on arXiv:cs/0202020v1 .

Today I read a paper titled “Synthesis of Low-Power Digital Circuits Derived from Binary Decision Diagrams”

The abstract is:
This paper introduces a novel method for synthesizing digital circuits derived from Binary Decision Diagrams (BDDs) that can yield to reduction in power dissipation.

The power reduction is achieved by decreasing the switching activity in a circuit while paying close attention to information measures as an optimization criterion.

We first present the technique of efficient BDD-based computation of information measures which are used to guide the power optimization procedures.

Using this technique, we have developed an algorithm of BDD reordering which leads to reducing the power consumption of the circuits derived from BDDs.

Results produced by the synthesis on the ISCAS benchmark circuits are very encouraging.

Today I read a paper titled “Playing Games with Algorithms: Algorithmic Combinatorial Game Theory”

The abstract is:
Combinatorial games lead to several interesting, clean problems in algorithms and complexity theory, many of which remain open.

The purpose of this paper is to provide an overview of the area to encourage further research.

In particular, we begin with general background in Combinatorial Game Theory, which analyzes ideal play in perfect-information games, and Constraint Logic, which provides a framework for showing hardness.

Then we survey results about the complexity of determining ideal play in these games, and the related problems of solving puzzles, in terms of both polynomial-time algorithms and computational intractability results.

Our review of background and survey of algorithmic results are by no means complete, but should serve as a useful primer.

Today I read a paper titled “Naive Bayes and Exemplar-Based approaches to Word Sense Disambiguation Revisited”

The abstract is:
This paper describes an experimental comparison between two standard supervised learning methods, namely Naive Bayes and Exemplar-based classification, on the Word Sense Disambiguation (WSD) problem.

The aim of the work is twofold.

Firstly, it attempts to contribute to clarify some confusing information about the comparison between both methods appearing in the related literature.

In doing so, several directions have been explored, including: testing several modifications of the basic learning algorithms and varying the feature space.

Secondly, an improvement of both algorithms is proposed, in order to deal with large attribute sets.

This modification, which basically consists in using only the positive information appearing in the examples, allows to improve greatly the efficiency of the methods, with no loss in accuracy.

The experiments have been performed on the largest sense-tagged corpus available containing the most frequent and ambiguous English words.

Results show that the Exemplar-based approach to WSD is generally superior to the Bayesian approach, especially when a specific metric for dealing with symbolic attributes is used.

Today I read a paper titled “Visualization of variations in human brain morphology using differentiating reflection functions”

The abstract is:
Conventional visualization media such as MRI prints and computer screens are inherently two dimensional, making them incapable of displaying true 3D volume data sets.

By applying only transparency or intensity projection, and ignoring light-matter interaction, results will likely fail to give optimal results.

Little research has been done on using reflectance functions to visually separate the various segments of a MRI volume.

We will explore if applying specific reflectance functions to individual anatomical structures can help in building an intuitive 2D image from a 3D dataset.

We will test our hypothesis by visualizing a statistical analysis of the genetic influences on variations in human brain morphology because it inherently contains complex and many different types of data making it a good candidate for our approach.

Today I read a paper titled “A neural network and iterative optimization hybrid for Dempster-Shafer clustering”

The abstract is:
In this paper we extend an earlier result within Dempster-Shafer theory [“Fast Dempster-Shafer Clustering Using a Neural Network Structure,” in Proc.

Seventh Int.

Conf.

Information Processing and Management of Uncertainty in Knowledge-Based Systems (IPMU 98)] where a large number of pieces of evidence are clustered into subsets by a neural network structure.

The clustering is done by minimizing a metaconflict function.

Previously we developed a method based on iterative optimization.

While the neural method had a much lower computation time than iterative optimization its average clustering performance was not as good.

Here, we develop a hybrid of the two methods.

We let the neural structure do the initial clustering in order to achieve a high computational performance.

Its solution is fed as the initial state to the iterative optimization in order to improve the clustering performance.

Today I read a paper titled “Agent Programming with Declarative Goals”

The abstract is:
A long and lasting problem in agent research has been to close the gap between agent logics and agent programming frameworks.

The main reason for this problem of establishing a link between agent logics and agent programming frameworks is identified and explained by the fact that agent programming frameworks have not incorporated the concept of a `declarative goal’.

Instead, such frameworks have focused mainly on plans or `goals-to-do’ instead of the end goals to be realised which are also called `goals-to-be’.

In this paper, a new programming language called GOAL is introduced which incorporates such declarative goals.

The notion of a `commitment strategy’ – one of the main theoretical insights due to agent logics, which explains the relation between beliefs and goals – is used to construct a computational semantics for GOAL.

Finally, a proof theory for proving properties of GOAL agents is introduced.

Thus, we offer a complete theory of agent programming in the sense that our theory provides both for a programming framework and a programming logic for such agents.

An example program is proven correct by using this programming logic.

Today I read a paper titled “A steady state model for graph power laws”

The abstract is:
Power law distribution seems to be an important characteristic of web graphs.

Several existing web graph models generate power law graphs by adding new vertices and non-uniform edge connectivities to existing graphs.

Researchers have conjectured that preferential connectivity and incremental growth are both required for the power law distribution.

In this paper, we propose a different web graph model with power law distribution that does not require incremental growth.

We also provide a comparison of our model with several others in their ability to predict web graph clustering behavior.

Today I read a paper titled “The Design and Experimental Analysis of Algorithms for Temporal Reasoning”

The abstract is:
Many applications — from planning and scheduling to problems in molecular biology — rely heavily on a temporal reasoning component.

In this paper, we discuss the design and empirical analysis of algorithms for a temporal reasoning system based on Allen’s influential interval-based framework for representing temporal information.

At the core of the system are algorithms for determining whether the temporal information is consistent, and, if so, finding one or more scenarios that are consistent with the temporal information.

Two important algorithms for these tasks are a path consistency algorithm and a backtracking algorithm.

For the path consistency algorithm, we develop techniques that can result in up to a ten-fold speedup over an already highly optimized implementation.

For the backtracking algorithm, we develop variable and value ordering heuristics that are shown empirically to dramatically improve the performance of the algorithm.

As well, we show that a previously suggested reformulation of the backtracking search problem can reduce the time and space requirements of the backtracking search.

Taken together, the techniques we develop allow a temporal reasoning component to solve problems that are of practical size.

Today I read a paper titled “Reasoning About Common Knowledge with Infinitely Many Agents”

The abstract is:
Complete axiomatizations and exponential-time decision procedures are provided for reasoning about knowledge and common knowledge when there are infinitely many agents.

The results show that reasoning about knowledge and common knowledge with infinitely many agents is no harder than when there are finitely many agents, provided that we can check the cardinality of certain set differences G – G’, where G and G’ are sets of agents.

Since our complexity results are independent of the cardinality of the sets G involved, they represent improvements over the previous results even with the sets of agents involved are finite.

Moreover, our results make clear the extent to which issues of complexity and completeness depend on how the sets of agents involved are represented.

Today I read a paper titled “Assisted Video Sequences Indexing : Motion Analysis Based on Interest Points”

The abstract is:
This work deals with content-based video indexing.

Our viewpoint is semi-automatic analysis of compressed video.

We consider the possible applications of motion analysis and moving object detection : assisting moving object indexing, summarising videos, and allowing image and motion queries.

We propose an approach based on interest points.

As first results, we test and compare the stability of different types of interest point detectors in compressed sequences.

Today I read a paper titled “About the finding of independent vertices of a graph”

The abstract is:
We examine the Maximum Independent Set Problem in an undirected graph.

The main result is that this problem can be considered as the solving the same problem in a subclass of the weighted normal twin-orthogonal graphs.

The problem is formulated which is dual to the problem above.

It is shown that, for trivial twin-orthogonal graphs, any of its maximal independent set is also maximum one.

Today I read a paper titled “Self-Organizing Machine Translation: Example-Driven Induction of Transfer Functions”

The abstract is:
With the advent of faster computers, the notion of doing machine translation from a huge stored database of translation examples is no longer unreasonable.

This paper describes an attempt to merge the Example-Based Machine Translation (EBMT) approach with psycholinguistic principles.

A new formalism for context- free grammars, called *marker-normal form*, is demonstrated and used to describe language data in a way compatible with psycholinguistic theories.

By embedding this formalism in a standard multivariate optimization framework, a system can be built that infers correct transfer functions for a set of bilingual sentence pairs and then uses those functions to translate novel sentences.

The validity of this line of reasoning has been tested in the development of a system called METLA-1.

This system has been used to infer English->French and English->Urdu transfer functions from small corpora.

The results of those experiments are examined, both in engineering terms as well as in more linguistic terms.

In general, the results of these experiments were psycho- logically and linguistically well-grounded while still achieving a respectable level of success when compared against a similar prototype using Hidden Markov Models..

Today I read a paper titled “Noise-Tolerant Learning, the Parity Problem, and the Statistical Query Model”

The abstract is:
We describe a slightly sub-exponential time algorithm for learning parity functions in the presence of random classification noise.

This results in a polynomial-time algorithm for the case of parity functions that depend on only the first O(log n log log n) bits of input.

This is the first known instance of an efficient noise-tolerant algorithm for a concept class that is provably not learnable in the Statistical Query model of Kearns.

Thus, we demonstrate that the set of problems learnable in the statistical query model is a strict subset of those problems learnable in the presence of noise in the PAC model.

In coding-theory terms, what we give is a poly(n)-time algorithm for decoding linear k by n codes in the presence of random noise for the case of k = c log n loglog n for some c > 0.

(The case of k = O(log n) is trivial since one can just individually check each of the 2^k possible messages and choose the one that yields the closest codeword.) A natural extension of the statistical query model is to allow queries about statistical properties that involve t-tuples of examples (as opposed to single examples).

The second result of this paper is to show that any class of functions learnable (strongly or weakly) with t-wise queries for t = O(log n) is also weakly learnable with standard unary queries.

Hence this natural extension to the statistical query model does not increase the set of weakly learnable functions.

Today I read a paper titled “Coin-Moving Puzzles”

The abstract is:
We introduce a new family of one-player games, involving the movement of coins from one configuration to another.

Moves are restricted so that a coin can be placed only in a position that is adjacent to at least two other coins.

The goal of this paper is to specify exactly which of these games are solvable.

By introducing the notion of a constant number of extra coins, we give tight theorems characterizing solvable puzzles on the square grid and equilateral-triangle grid.

These existence results are supplemented by polynomial-time algorithms for finding a solution..

Today I read a paper titled “Perfect simulation from the Quicksort limit distribution”

The abstract is:
The weak limit of the normalized number of comparisons needed by the Quicksort algorithm to sort n randomly permuted items is known to be determined implicitly by a distributional fixed-point equation.

We give an algorithm for perfect random variate generation from this distribution.

Today I read a paper titled “Data Security Equals Graph Connectivity”

The abstract is:
To protect sensitive information in a cross tabulated table, it is a common practice to suppress some of the cells in the table.

This paper investigates four levels of data security of a two-dimensional table concerning the effectiveness of this practice.

These four levels of data security protect the information contained in, respectively, individual cells, individual rows and columns, several rows or columns as a whole, and a table as a whole.

The paper presents efficient algorithms and NP-completeness results for testing and achieving these four levels of data security.

All these complexity results are obtained by means of fundamental equivalences between the four levels of data security of a table and four types of connectivity of a graph constructed from that table.

Today I read a paper titled “Aging, double helix and small world property in genetic algorithms”

The abstract is:
Over a quarter of century after the invention of genetic algorithms and miriads of their modifications, as well as successful implementations, we are still lacking many essential details of thorough analysis of it’s inner working.

One of such fundamental questions is: how many generations do we need to solve the optimization problem? This paper tries to answer this question, albeit in a fuzzy way, making use of the double helix concept.

As a byproduct we gain better understanding of the ways, in which the genetic algorithm may be fine tuned.

Today I read a paper titled “On-Line File Caching”

The abstract is:
In the on-line file-caching problem problem, the input is a sequence of requests for files, given on-line (one at a time).

Each file has a non-negative size and a non-negative retrieval cost.

The problem is to decide which files to keep in a fixed-size cache so as to minimize the sum of the retrieval costs for files that are not in the cache when requested.

The problem arises in web caching by browsers and by proxies.

This paper describes a natural generalization of LRU called Landlord and gives an analysis showing that it has an optimal performance guarantee (among deterministic on-line algorithms).

The paper also gives an analysis of the algorithm in a so-called “loosely” competitive model, showing that on a “typical” cache size, either the performance guarantee is O(1) or the total retrieval cost is insignificant.

Today I read a paper titled “The Self-Organizing Symbiotic Agent”

The abstract is:
In [N.

A.

Baas, Emergence, Hierarchies, and Hyper-structures, in C.G.

Langton ed., Artificial Life III, Addison Wesley, 1994.] a general framework for the study of Emergence and hyper-structure was presented.

This approach is mostly concerned with the description of such systems.

In this paper we will try to bring forth a different aspect of this model we feel will be useful in the engineering of agent based solutions, namely the symbiotic approach.

In this approach a self-organizing method of dividing the more complex “main-problem” to a hyper-structure of “sub-problems” with the aim of reducing complexity is desired.

A description of the general problem will be given along with some instances of related work.

This paper is intended to serve as an introductory challenge for general solutions to the described problem.

Today I read a paper titled “Solitaire Clobber”

The abstract is:
Clobber is a new two-player board game.

In this paper, we introduce the one-player variant Solitaire Clobber where the goal is to remove as many stones as possible from the board by alternating white and black moves.

We show that a checkerboard configuration on a single row (or single column) can be reduced to about n/4 stones.

For boards with at least two rows and two columns, we show that a checkerboard configuration can be reduced to a single stone if and only if the number of stones is not a multiple of three, and otherwise it can be reduced to two stones.

We also show that in general it is NP-complete to decide whether an arbitrary Clobber configuration can be reduced to a single stone..

Today I read a paper titled “Construction of an algorithm in parallel for the Fast Fourier Transform”

The abstract is:
It has been designed,built and executed a code for the Fast Fourier Transform (FFT),compiled and executed in a cluster of 2^n computers under the operating system MacOS and using the routines MacMPI.

As practical application,the code has been used to obtain the transformed from an astronomic imagen,to execute a filter on its and with a transformed inverse to recover the image with the variates given by the filter.The computers arrangement are installed in the Observatorio Astronomico National in Colombia under the name OAN Cluster and in this has been executed several applications.

Today I read a paper titled “The Lazy Bureaucrat Scheduling Problem”

The abstract is:
We introduce a new class of scheduling problems in which the optimization is performed by the worker (single “machine”) who performs the tasks.

A typical worker’s objective is to minimize the amount of work he does (he is “lazy”), or more generally, to schedule as inefficiently (in some sense) as possible.

The worker is subject to the constraint that he must be busy when there is work that he can do; we make this notion precise both in the preemptive and nonpreemptive settings.

The resulting class of “perverse” scheduling problems, which we denote “Lazy Bureaucrat Problems,” gives rise to a rich set of new questions that explore the distinction between maximization and minimization in computing optimal schedules.

Today I read a paper titled “One-Dimensional Peg Solitaire”

The abstract is:
We solve the problem of one-dimensional peg solitaire.

In particular, we show that the set of configurations that can be reduced to a single peg forms a regular language, and that a linear-time algorithm exists for reducing any configuration to the minimum number of pegs..

Today I read a paper titled “Genetic Algorithms for Extension Search in Default Logic”

The abstract is:
A default theory can be characterized by its sets of plausible conclusions, called its extensions.

But, due to the theoretical complexity of Default Logic (Sigma_2p-complete), the problem of finding such an extension is very difficult if one wants to deal with non trivial knowledge bases.

Based on the principle of natural selection, Genetic Algorithms have been quite successfully applied to combinatorial problems and seem useful for problems with huge search spaces and when no tractable algorithm is available.

The purpose of this paper is to show that techniques issued from Genetic Algorithms can be used in order to build an efficient default reasoning system.

After providing a formal description of the components required for an extension search based on Genetic Algorithms principles, we exhibit some experimental results.

Today I read a paper titled “Reducing Randomness via Irrational Numbers”

The abstract is:
We propose a general methodology for testing whether a given polynomial with integer coefficients is identically zero.

The methodology evaluates the polynomial at efficiently computable approximations of suitable irrational points.

In contrast to the classical technique of DeMillo, Lipton, Schwartz, and Zippel, this methodology can decrease the error probability by increasing the precision of the approximations instead of using more random bits.

Consequently, randomized algorithms that use the classical technique can generally be improved using the new methodology.

To demonstrate the methodology, we discuss two nontrivial applications.

The first is to decide whether a graph has a perfect matching in parallel.

Our new NC algorithm uses fewer random bits while doing less work than the previously best NC algorithm by Chari, Rohatgi, and Srinivasan.

The second application is to test the equality of two multisets of integers.

Our new algorithm improves upon the previously best algorithms by Blum and Kannan and can speed up their checking algorithm for sorting programs on a large range of inputs.