Archives for 2002

Today I read a paper titled “A better lower bound for quantum algorithms searching an ordered list”

The abstract is:
We show that any quantum algorithm searching an ordered list of n elements needs to examine at least 1/12 log n-O(1) of them.

Classically, log n queries are both necessary and sufficient.

This shows that quantum algorithms can achieve only a constant speedup for this problem.

Our result improves lower bounds of Buhrman and de Wolf(quant-ph/9811046) and Farhi, Goldstone, Gutmann and Sipser (quant-ph/9812057).

Today I read a paper titled “Perception games, the image understanding and interpretational geometry”

The abstract is:
The interactive game theoretical approach to the description of perception processes is proposed.

The subject is treated formally in terms of a new class of the verbalizable interactive games which are called the perception games.

An application of the previously elaborated formalism of dialogues and verbalizable interactive games to the visual perception allows to combine the linguistic (such as formal grammars), psycholinguistic and (interactive) game theoretical methods for analysis of the image understanding by a human that may be also useful for the elaboration of computer vision systems.

By the way the interactive game theoretical aspects of interpretational geometries are clarified.

Today I read a paper titled “Multimodal Surrogates for Video Browsing”

The abstract is:
Three types of video surrogates – visual (keyframes), verbal (keywords/phrases), and combination of the two – were designed and studied in a qualitative investigation of user cognitive processes.

The results favor the combined surrogates in which verbal information and images reinforce each other, lead to better comprehension, and may actually require less processing time.

The results also highlight image features users found most helpful.

These findings will inform the interface design and video representation for video retrieval and browsing.

Today I read a paper titled “Chunk Tagger – Statistical Recognition of Noun Phrases”

The abstract is:
We describe a stochastic approach to partial parsing, i.e., the recognition of syntactic structures of limited depth.

The technique utilises Markov Models, but goes beyond usual bracketing approaches, since it is capable of recognising not only the boundaries, but also the internal structure and syntactic category of simple as well as complex NP’s, PP’s, AP’s and adverbials.

We compare tagging accuracy for different applications and encoding schemes.

Today I read a paper titled “Digital Color Imaging”

The abstract is:
This paper surveys current technology and research in the area of digital color imaging.

In order to establish the background and lay down terminology, fundamental concepts of color perception and measurement are first presented us-ing vector-space notation and terminology.

Present-day color recording and reproduction systems are reviewed along with the common mathematical models used for representing these devices.

Algorithms for processing color images for display and communication are surveyed, and a forecast of research trends is attempted.

An extensive bibliography is provided..

Today I read a paper titled “A Fast General Methodology for Information-Theoretically Optimal Encodings of Graphs”

The abstract is:
We propose a fast methodology for encoding graphs with information-theoretically minimum numbers of bits.

Specifically, a graph with property pi is called a pi-graph.

If pi satisfies certain properties, then an n-node m-edge pi-graph G can be encoded by a binary string X such that (1) G and X can be obtained from each other in O(n log n) time, and (2) X has at most beta(n)+o(beta(n)) bits for any continuous super-additive function beta(n) so that there are at most 2^{beta(n)+o(beta(n))} distinct n-node pi-graphs.

The methodology is applicable to general classes of graphs; this paper focuses on planar graphs.

Examples of such pi include all conjunctions over the following groups of properties: (1) G is a planar graph or a plane graph; (2) G is directed or undirected; (3) G is triangulated, triconnected, biconnected, merely connected, or not required to be connected; (4) the nodes of G are labeled with labels from {1, …, ell_1} for ell_1 <= n; (5) the edges of G are labeled with labels from {1, ..., ell_2} for ell_2 <= m; and (6) each node (respectively, edge) of G has at most ell_3 = O(1) self-loops (respectively, ell_4 = O(1) multiple edges).

Moreover, ell_3 and ell_4 are not required to be O(1) for the cases of pi being a plane triangulation.

These examples are novel applications of small cycle separators of planar graphs and are the only nontrivial classes of graphs, other than rooted trees, with known polynomial-time information-theoretically optimal coding schemes..

Today I read a paper titled “Data sonification and sound visualization”

The abstract is:
This article describes a collaborative project between researchers in the Mathematics and Computer Science Division at Argonne National Laboratory and the Computer Music Project of the University of Illinois at Urbana-Champaign.

The project focuses on the use of sound for the exploration and analysis of complex data sets in scientific computing.

The article addresses digital sound synthesis in the context of DIASS (Digital Instrument for Additive Sound Synthesis) and sound visualization in a virtual-reality environment by means of M4CAVE.

It describes the procedures and preliminary results of some experiments in scientific sonification and sound visualization.