Archives for 2004

Today I read a paper titled “Secure History Preservation Through Timeline Entanglement”

The abstract is:
A secure timeline is a tamper-evident historic record of the states through which a system goes throughout its operational history.

Secure timelines can help us reason about the temporal ordering of system states in a provable manner.

We extend secure timelines to encompass multiple, mutually distrustful services, using timeline entanglement.

Timeline entanglement associates disparate timelines maintained at independent systems, by linking undeniably the past of one timeline to the future of another.

Timeline entanglement is a sound method to map a time step in the history of one service onto the timeline of another, and helps clients of entangled services to get persistent temporal proofs for services rendered that survive the demise or non-cooperation of the originating service.

In this paper we present the design and implementation of Timeweave, our service development framework for timeline entanglement based on two novel disk-based authenticated data structures.

We evaluate Timeweave’s performance characteristics and show that it can be efficiently deployed in a loosely-coupled distributed system of a few hundred services with overhead of roughly 2-8% of the processing resources of a PC-grade system.

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.