Justin Lloyd's Thinkering

Today I read a paper titled “Lower Bounds for Quantum Search and Derandomization”

The abstract is:
We prove lower bounds on the error probability of a quantum algorithm for searching through an unordered list of N items, as a function of the number T of queries it makes.

In particular, if T=O(sqrt{N}) then the error is lower bounded by a constant.

If we want error <1/2^N then we need T=Omega(N) queries.

We apply this to show that a quantum computer cannot do much better than a classical computer when amplifying the success probability of an RP-machine.

A classical computer can achieve error <=1/2^k using k applications of the RP-machine, a quantum computer still needs at least ck applications for this (when treating the machine as a black-box), where c>0 is a constant independent of k.

Furthermore, we prove a lower bound of Omega(sqrt{log N}/loglog N) queries for quantum bounded-error search of an ordered list of N items.

Today I read a paper titled “An Optimal Tabular Parsing Algorithm”

The abstract is:
In this paper we relate a number of parsing algorithms which have been developed in very different areas of parsing theory, and which include deterministic algorithms, tabular algorithms, and a parallel algorithm.

We show that these algorithms are based on the same underlying ideas.

By relating existing ideas, we hope to provide an opportunity to improve some algorithms based on features of others.

A second purpose of this paper is to answer a question which has come up in the area of tabular parsing, namely how to obtain a parsing algorithm with the property that the table will contain as little entries as possible, but without the possibility that two entries represent the same subderivation..

Today I read a paper titled “Exploring the Decision Forest: An Empirical Investigation of Occam’s Razor in Decision Tree Induction”

The abstract is:
We report on a series of experiments in which all decision trees consistent with the training data are constructed.

These experiments were run to gain an understanding of the properties of the set of consistent decision trees and the factors that affect the accuracy of individual trees.

In particular, we investigated the relationship between the size of a decision tree consistent with some training data and the accuracy of the tree on test data.

The experiments were performed on a massively parallel Maspar computer.

The results of the experiments on several artificial and two real world problems indicate that, for many of the problems investigated, smaller consistent decision trees are on average less accurate than the average accuracy of slightly larger trees..

Today I read a paper titled “Separation-Sensitive Collision Detection for Convex Objects”

The abstract is:
We develop a class of new kinetic data structures for collision detection between moving convex polytopes; the performance of these structures is sensitive to the separation of the polytopes during their motion.

For two convex polygons in the plane, let D be the maximum diameter of the polygons, and let s be the minimum distance between them during their motion.

Our separation certificate changes O(log(D/s)) times when the relative motion of the two polygons is a translation along a straight line or convex curve, O(D/s‾‾‾√)for translation along an algebraic trajectory, and O(D/s) for algebraic rigid motion (translation and rotation).

Each certificate update is performed in O(log(D/s)) time.

Variants of these data structures are also shown that exhibit \emph{hysteresis}—after a separation certificate fails, the new certificate cannot fail again until the objects have moved by some constant fraction of their current separation.

We can then bound the number of events by the combinatorial size of a certain cover of the motion path by balls..

Today I read a paper titled “Analogue Quantum Computers for Data Analysis”

The abstract is:
Analogue computers use continuous properties of physical system for modeling.

In the paper is described possibility of modeling by analogue quantum computers for some model of data analysis.

It is analogue associative memory and a formal neural network.

A particularity of the models is combination of continuous internal processes with discrete set of output states.

The modeling of the system by classical analogue computers was offered long times ago, but now it is not very effectively in comparison with modern digital computers.

The application of quantum analogue modelling looks quite possible for modern level of technology and it may be more effective than digital one, because number of element may be about Avogadro number (N=6.0E23)..

Today I read a paper titled “Symmetries and transitions of bounded Turing machines”

The abstract is:
We consider the structures given by repeatedly generalising the definition of finite state automata by symmetry considerations, and constructing analogues of transition monoids at each step.

This approach first gives us non-deterministic automata, then (non-deterministic) two-way automata and bounded Turing machines — that is, Turing machines where the read / write head is unable to move past the end of the input word.

In the case of two-way automata, the transition monoids generalise to endomorphism monoids in compact closed categories.

These use Girard’s resolution formula (from the Geometry of Interaction representation of linear logic) to construct the images of singleton words.

In the case of bounded Turing machines, the transition homomorphism generalises to a monoid homomorphism from the natural numbers to a monoid constructed from the union of endomorphism monoids of a compact closed category, together with an appropriate composition.

These use Girard’s execution formula (also from the Geometry of Interaction representation of linear logic) to construct images of singletons.