justin

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..