Archives for 2002

Today I read a paper titled “Genetic Algorithms in Time-Dependent Environments”

The abstract is:
The influence of time-dependent fitnesses on the infinite population dynamics of simple genetic algorithms (without crossover) is analyzed.

Based on general arguments, a schematic phase diagram is constructed that allows one to characterize the asymptotic states in dependence on the mutation rate and the time scale of changes.

Furthermore, the notion of regular changes is raised for which the population can be shown to converge towards a generalized quasispecies.

Based on this, error thresholds and an optimal mutation rate are approximately calculated for a generational genetic algorithm with a moving needle-in-the-haystack landscape.

The so found phase diagram is fully consistent with our general considerations.

Today I read a paper titled “A Flexible Shallow Approach to Text Generation”

The abstract is:
In order to support the efficient development of NL generation systems, two orthogonal methods are currently pursued with emphasis: (1) reusable, general, and linguistically motivated surface realization components, and (2) simple, task-oriented template-based techniques.

In this paper we argue that, from an application-oriented perspective, the benefits of both are still limited.

In order to improve this situation, we suggest and evaluate shallow generation methods associated with increased flexibility.

We advise a close connection between domain-motivated and linguistic ontologies that supports the quick adaptation to new tasks and domains, rather than the reuse of general resources.

Our method is especially designed for generating reports with limited linguistic variations.

Today I read a paper titled “A Differential Invariant for Zooming”

The abstract is:
This paper presents an invariant under scaling and linear brightness change.

The invariant is based on differentials and therefore is a local feature.

Rotationally invariant 2-d differential Gaussian operators up to third order are proposed for the implementation of the invariant.

The performance is analyzed by simulating a camera zoom-out.

Today I read a paper titled “Dynamic Backtracking”

The abstract is:
Because of their occasional need to return to shallow points in a search tree, existing backtracking methods can sometimes erase meaningful progress toward solving a search problem.

In this paper, we present a method by which backtrack points can be moved deeper in the search space, thereby avoiding this difficulty.

The technique developed is a variant of dependency-directed backtracking that uses only polynomial space while still providing useful control information and retaining the completeness guarantees provided by earlier approaches..

Today I read a paper titled “An Even Faster and More Unifying Algorithm for Comparing Trees via Unbalanced Bipartite Matchings”

The abstract is:
A widely used method for determining the similarity of two labeled trees is to compute a maximum agreement subtree of the two trees.

Previous work on this similarity measure is only concerned with the comparison of labeled trees of two special kinds, namely, uniformly labeled trees (i.e., trees with all their nodes labeled by the same symbol) and evolutionary trees (i.e., leaf-labeled trees with distinct symbols for distinct leaves).

This paper presents an algorithm for comparing trees that are labeled in an arbitrary manner.

In addition to this generality, this algorithm is faster than the previous algorithms.

Another contribution of this paper is on maximum weight bipartite matchings.

We show how to speed up the best known matching algorithms when the input graphs are node-unbalanced or weight-unbalanced.

Based on these enhancements, we obtain an efficient algorithm for a new matching problem called the hierarchical bipartite matching problem, which is at the core of our maximum agreement subtree algorithm.

Today I read a paper titled “A Quick Glance at Quantum Cryptography”

The abstract is:
The recent application of the principles of quantum mechanics to cryptography has led to a remarkable new dimension in secret communication.

As a result of these new developments, it is now possible to construct cryptographic communication systems which detect unauthorized eavesdropping should it occur, and which give a guarantee of no eavesdropping should it not occur.

CONTENTS P3.

Cryptographic systems before quantum cryptography P7.

Preamble to quantum cryptography P10.

The BB84 quantum cryptographic protocol without noise P16.

The BB84 quantum cryptographic protocol with noise P19..The B92 quantum cryptographic protocol P21.

EPR quantum cryptographic protocols P25.

Other protocols P25.

Eavesdropping stategies and counter measures P26.

Conclusion P29.

Appendix A.

The no cloning theorem P30.

Appendix B.

Proof that an undetectable eavesdropper can obtain no information from the B92 protocol P31.

Appendix C.

Part of a Rosetta stone for quantum mechanics P44.

References .

Today I read a paper titled “Opportunity Cost Algorithms for Combinatorial Auctions”

The abstract is:
Two general algorithms based on opportunity costs are given for approximating a revenue-maximizing set of bids an auctioneer should accept, in a combinatorial auction in which each bidder offers a price for some subset of the available goods and the auctioneer can only accept non-intersecting bids.

Since this problem is difficult even to approximate in general, the algorithms are most useful when the bids are restricted to be connected node subsets of an underlying object graph that represents which objects are relevant to each other.

The approximation ratios of the algorithms depend on structural properties of this graph and are small constants for many interesting families of object graphs.

The running times of the algorithms are linear in the size of the bid graph, which describes the conflicts between bids.

Extensions of the algorithms allow for efficient processing of additional constraints, such as budget constraints that associate bids with particular bidders and limit how many bids from a particular bidder can be accepted.

Today I read a paper titled “Quantum simulations of classical random walks and undirected graph connectivity”

The abstract is:
It is not currently known if quantum Turing machines can efficiently simulate probabilistic computations in the space-bounded case.

In this paper we show that space-bounded quantum Turing machines can efficiently simulate a limited class of random processes: random walks on undirected graphs.

By means of such simulations, it is demonstrated that the undirected graph connectivity problem for regular graphs can be solved by one-sided error quantum Turing machines that run in logspace and halt absolutely.

It follows that symmetric logspace is contained in the quantum analogue of randomized logspace.

Today I read a paper titled “An Integrated Heuristic Scheme for Partial Parse Evaluation”

The abstract is:
GLR* is a recently developed robust version of the Generalized LR Parser, that can parse almost ANY input sentence by ignoring unrecognizable parts of the sentence.

On a given input sentence, the parser returns a collection of parses that correspond to maximal, or close to maximal, parsable subsets of the original input.

This paper describes recent work on developing an integrated heuristic scheme for selecting the parse that is deemed “best” from such a collection.

We describe the heuristic measures used and their combination scheme.

Preliminary results from experiments conducted on parsing speech recognized spontaneous speech are also reported..

Today I read a paper titled “Optimal Constructions of Hybrid Algorithms”

The abstract is:
We study on-line strategies for solving problems with hybrid algorithms.

There is a problem Q and w basic algorithms for solving Q.

For some lambda <= w, we have a computer with lambda disjoint memory areas, each of which can be used to run a basic algorithm and store its intermediate results.

In the worst case, only one basic algorithm can solve Q in finite time, and all the other basic algorithms run forever without solving Q.

To solve Q with a hybrid algorithm constructed from the basic algorithms, we run a basic algorithm for some time, then switch to another, and continue this process until Q is solved.

The goal is to solve Q in the least amount of time.

Using competitive ratios to measure the efficiency of a hybrid algorithm, we construct an optimal deterministic hybrid algorithm and an efficient randomized hybrid algorithm.

This resolves an open question on searching with multiple robots posed by Baeza-Yates, Culberson and Rawlins.

We also prove that our randomized algorithm is optimal for lambda = 1, settling a conjecture of Kao, Reif and Tate.

Today I read a paper titled “Differentiated End-to-End Internet Services using a Weighted Proportional Fair Sharing TCP”

The abstract is:
In this document we study the application of weighted proportional fairness to data flows in the Internet.

We let the users set the weights of their connections in order to maximise the utility they get from the network.

When combined with a pricing scheme where connections are billed by weight and time, such a system is known to maximise the total utility of the network.

Our study case is a national Web cache server connected to long distance links.

We propose two ways of weighting TCP connections by manipulating some parameters of the protocol and present results from simulations and prototypes.

We finally discuss how proportional fairness could be used to implement an Internet with differentiated services.

Today I read a paper titled “Detecting and Correcting Speech Repairs”

The abstract is:
Interactive spoken dialog provides many new challenges for spoken language systems.

One of the most critical is the prevalence of speech repairs.

This paper presents an algorithm that detects and corrects speech repairs based on finding the repair pattern.

The repair pattern is built by finding word matches and word replacements, and identifying fragments and editing terms.

Rather than using a set of prebuilt templates, we build the pattern on the fly.

In a fair test, our method, when combined with a statistical model to filter possible repairs, was successful at detecting and correcting 80\% of the repairs, without using prosodic information or a parser..

Today I read a paper titled “Toward Natural Gesture/Speech Control of a Large Display”

The abstract is:
In recent years because of the advances in computer vision research, free hand gestures have been explored as means of human-computer interaction (HCI).

Together with improved speech processing technology it is an important step toward natural multimodal HCI.

However, inclusion of non-predefined continuous gestures into a multimodal framework is a challenging problem.

In this paper, we propose a structured approach for studying patterns of multimodal language in the context of a 2D-display control.

We consider systematic analysis of gestures from observable kinematical primitives to their semantics as pertinent to a linguistic structure.

Proposed semantic classification of co-verbal gestures distinguishes six categories based on their spatio-temporal deixis.

We discuss evolution of a computational framework for gesture and speech integration which was used to develop an interactive testbed (iMAP).

The testbed enabled elicitation of adequate, non-sequential, multimodal patterns in a narrative mode of HCI.

Conducted user studies illustrate significance of accounting for the temporal alignment of gesture and speech parts in semantic mapping.

Furthermore, co-occurrence analysis of gesture/speech production suggests syntactic organization of gestures at the lexical level.