Justin Lloyd's Thinkering

Today I read a paper titled “1-way quantum finite automata: strengths, weaknesses and generalizations”

The abstract is:
We study 1-way quantum finite automata (QFAs).

First, we compare them with their classical counterparts.

We show that, if an automaton is required to give the correct answer with a large probability (over 0.98), then the power of 1-way QFAs is equal to the power of 1-way reversible automata.

However, quantum automata giving the correct answer with smaller probabilities are more powerful than reversible automata.

Second, we show that 1-way QFAs can be very space-efficient.

Namely, we construct a 1-way QFA which is exponentially smaller than any equivalent classical (even randomized) finite automaton.

This construction may be useful for design of other space-efficient quantum algorithms.

Third, we consider several generalizations of 1-way QFAs.

Here, our goal is to find a model which is more powerful than 1-way QFAs keeping the quantum part as simple as possible..

Today I read a paper titled “Reversibility and Adiabatic Computation: Trading Time and Space for Energy”

The abstract is:
Future miniaturization and mobilization of computing devices requires energy parsimonious `adiabatic’ computation.

This is contingent on logical reversibility of computation.

An example is the idea of quantum computations which are reversible except for the irreversible observation steps.

We propose to study quantitatively the exchange of computational resources like time and space for irreversibility in computations.

Reversible simulations of irreversible computations are memory intensive.

Such (polynomial time) simulations are analysed here in terms of `reversible’ pebble games.

We show that Bennett’s pebbling strategy uses least additional space for the greatest number of simulated steps.

We derive a trade-off for storage space versus irreversible erasure.

Next we consider reversible computation itself.

An alternative proof is provided for the precise expression of the ultimate irreversibility cost of an otherwise reversible computation without restrictions on time and space use.

A time-irreversibility trade-off hierarchy in the exponential time region is exhibited.

Finally, extreme time-irreversibility trade-offs for reversible computations in the thoroughly unrealistic range of computable versus noncomputable time-bounds are given.

Today I read a paper titled “Adaptive Load Balancing: A Study in Multi-Agent Learning”

The abstract is:
We study the process of multi-agent reinforcement learning in the context of load balancing in a distributed system, without use of either central coordination or explicit communication.

We first define a precise framework in which to study adaptive load balancing, important features of which are its stochastic nature and the purely local information available to individual agents.

Given this framework, we show illuminating results on the interplay between basic adaptive behavior parameters and their effect on system efficiency.

We then investigate the properties of adaptive load balancing in heterogeneous populations, and address the issue of exploration vs.

exploitation in that context.

Finally, we show that naive use of communication may not improve, and might even harm system efficiency.

Today I read a paper titled “Context-free multilanguages”

The abstract is:
This article is a sketch of ideas that were once intended to appear in the author’s famous series, “The Art of Computer Programming”.

He generalizes the notion of a context-free language from a set to a multiset of words over an alphabet.

The idea is to keep track of the number of ways to parse a string.

For example, “fruit flies like a banana” can famously be parsed in two ways; analogous examples in the setting of programming languages may yet be important in the future.

Today I read a paper titled “On Partially Controlled Multi-Agent Systems”

The abstract is:
Motivated by the control theoretic distinction between controllable and uncontrollable events, we distinguish between two types of agents within a multi-agent system: controllable agents, which are directly controlled by the system’s designer, and uncontrollable agents, which are not under the designer’s direct control.

We refer to such systems as partially controlled multi-agent systems, and we investigate how one might influence the behavior of the uncontrolled agents through appropriate design of the controlled agents.

In particular, we wish to understand which problems are naturally described in these terms, what methods can be applied to influence the uncontrollable agents, the effectiveness of such methods, and whether similar methods work across different domains.

Using a game-theoretic framework, this paper studies the design of partially controlled multi-agent systems in two contexts: in one context, the uncontrollable agents are expected utility maximizers, while in the other they are reinforcement learners.

We suggest different techniques for controlling agents’ behavior in each domain, assess their success, and examine their relationship.

Today I read a paper titled “Automatic processing proper names in texts”

The abstract is:
This paper shows first the problems raised by proper names in natural language processing.

Second, it introduces the knowledge representation structure we use based on conceptual graphs.

Then it explains the techniques which are used to process known and unknown proper names.

At last, it gives the performance of the system and the further works we intend to deal with..