justin

Today I read a paper titled “Tap Tips: Lightweight Discovery of Touchscreen Targets”

The abstract is:
We describe tap tips, a technique for providing touch-screen target location hints.

Tap tips are lightweight in that they are non-modal, appear only when needed, require a minimal number of user gestures, and do not add to the standard touchscreen gesture vocabulary.

We discuss our implementation of tap tips in an electronic guidebook system and some usability test results.

Today I read a paper titled “Using Simulated Annealing to Calculate the Trembles of Trembling Hand Perfection”

The abstract is:
Within the literature on non-cooperative game theory, there have been a number of attempts to propose logorithms which will compute Nash equilibria.

Rather than derive a new algorithm, this paper shows that the family of algorithms known as Markov chain Monte Carlo (MCMC) can be used to calculate Nash equilibria.

MCMC is a type of Monte Carlo simulation that relies on Markov chains to ensure its regularity conditions.

MCMC has been widely used throughout the statistics and optimization literature, where variants of this algorithm are known as simulated annealing.

This paper shows that there is interesting connection between the trembles that underlie the functioning of this algorithm and the type of Nash refinement known as trembling hand perfection.

Today I read a paper titled “In vivo spam filtering: A challenge problem for data mining”

The abstract is:
Spam, also known as Unsolicited Commercial Email (UCE), is the bane of email communication.

Many data mining researchers have addressed the problem of detecting spam, generally by treating it as a static text classification problem.

True in vivo spam filtering has characteristics that make it a rich and challenging domain for data mining.

Indeed, real-world datasets with these characteristics are typically difficult to acquire and to share.

This paper demonstrates some of these characteristics and argues that researchers should pursue in vivo spam filtering as an accessible domain for investigating them.

Today I read a paper titled “Note on Needle in a Haystack”

The abstract is:
Introduced below is a quantum database method, not only for retrieval but also for creation.

It uses a particular structure of true’s and false’s in a state vector of n qubits, permitting up to 2**2**n words, vastly more than for classical bits.

Several copies are produced so that later they can be destructively observed and a word determined with high probability.

Grover’s algorithm is proposed below to read out, nondestructively the unknown contents of a given stored state vector using only one state vector.

Today I read a paper titled “Dealing With Curious Players in Secure Networks”

The abstract is:
In secure communications networks there are a great number of user behavioural problems, which need to be dealt with.

Curious players pose a very real and serious threat to the integrity of such a network.

By traversing a network a Curious player could uncover secret information, which that user has no need to know, by simply posing as a loyalty check.

Loyalty checks are done simply to gauge the integrity of the network with respect to players who act in a malicious manner.

We wish to propose a method, which can deal with Curious players trying to obtain “Need to Know” information using a combined Fault-tolerant, Cryptographic and Game Theoretic Approach.

Today I read a paper titled “Combinatorial Auctions with Decreasing Marginal Utilities”

The abstract is:
In most of microeconomic theory, consumers are assumed to exhibit decreasing marginal utilities.

This paper considers combinatorial auctions among such submodular buyers.

The valuations of such buyers are placed within a hierarchy of valuations that exhibit no complementarities, a hierarchy that includes also OR and XOR combinations of singleton valuations, and valuations satisfying the gross substitutes property.

Those last valuations are shown to form a zero-measure subset of the submodular valuations that have positive measure.

While we show that the allocation problem among submodular valuations is NP-hard, we present an efficient greedy 2-approximation algorithm for this case and generalize it to the case of limited complementarities.

No such approximation algorithm exists in a setting allowing for arbitrary complementarities.

Some results about strategic aspects of combinatorial auctions among players with decreasing marginal utilities are also presented..

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 .