The science papers I've read

Today I read a paper titled “The Complexity of Clickomania”

The abstract is:
We study a popular puzzle game known variously as Clickomania and Same Game.

Basically, a rectangular grid of blocks is initially colored with some number of colors, and the player repeatedly removes a chosen connected monochromatic group of at least two square blocks, and any blocks above it fall down.

We show that one-column puzzles can be solved, i.e., the maximum possible number of blocks can be removed, in linear time for two colors, and in polynomial time for an arbitrary number of colors.

On the other hand, deciding whether a puzzle is solvable (all blocks can be removed) is NP-complete for two columns and five colors, or five columns and three colors.

Today I read a paper titled “A Learning Algorithm for Evolving Cascade Neural Networks”

The abstract is:
A new learning algorithm for Evolving Cascade Neural Networks (ECNNs) is described.

An ECNN starts to learn with one input node and then adding new inputs as well as new hidden neurons evolves it.

The trained ECNN has a nearly minimal number of input and hidden neurons as well as connections.

The algorithm was successfully applied to classify artifacts and normal segments in clinical electroencephalograms (EEGs).

The EEG segments were visually labeled by EEG-viewer.

The trained ECNN has correctly classified 96.69% of the testing segments.

It is slightly better than a standard fully connected neural network.

Today I read a paper titled “Semi-automatic vectorization of linear networks on rasterized cartographic maps”

The abstract is:
A system for semi-automatic vectorization of linear networks (roads, rivers, etc.) on rasterized cartographic maps is presented.

In this system, human intervention is limited to a graphic, interactive selection of the color attributes of the information to be obtained.

Using this data, the system performs a preliminary extraction of the linear network, which is subsequently completed, refined and vectorized by means of an automatic procedure.

Results on maps of different sources and scales are included.

—– Se presenta un sistema semi-automatico de vectorizacion de redes de objetos lineales (carreteras, rios, etc.) en mapas cartograficos digitalizados.

En este sistema, la intervencion humana queda reducida a la seleccion grafica interactiva de los atributos de color de la informacion a obtener.

Con estos datos, el sistema realiza una extraccion preliminar de la red lineal, que se completa, refina y vectoriza mediante un procedimiento automatico.

Se presentan resultados de la aplicacion del sistema sobre imagenes digitalizadas de mapas de distinta procedencia y escala.

Today I read a paper titled “Stochastic fuzzy controller”

The abstract is:
A standard approach to building a fuzzy controller based on stochastic logic uses binary random signals with an average (expected value of a random variable) in the range [0, 1].

A different approach is presented, founded on a representation of the membership functions with the probability density functions.

Today I read a paper titled “Computing Conformal Structure of Surfaces”

The abstract is:
This paper solves the problem of computing conformal structures of general 2-manifolds represented as triangle meshes.

We compute conformal structures in the following way: first compute homology bases from simplicial complex structures, then construct dual cohomology bases and diffuse them to harmonic 1-forms.

Next, we construct bases of holomorphic differentials.

We then obtain period matrices by integrating holomorphic differentials along homology bases.

We also study the global conformal mapping between genus zero surfaces and spheres, and between general meshes and planes.

Our method of computing conformal structures can be applied to tackle fundamental problems in computer aid design and computer graphics, such as geometry classification and identification, and surface global parametrization.

Today I read a paper titled “A Cartography for 2×2 Symmetric Games”

The abstract is:
A bidimensional representation of the space of 2×2 Symmetric Games in the strategic representation is proposed.

This representation provides a tool for the classification of 2×2 symmetric games, quantification of the fraction of them having a certain feature, and predictions of changes in the characteristics of a game when a change in done on the payoff matrix that defines it.

Today I read a paper titled “An Algorithm for Transforming Color Images into Tactile Graphics”

The abstract is:
This paper presents an algorithm that transforms color visual images, like photographs or paintings, into tactile graphics.

In the algorithm, the edges of objects are detected and colors of the objects are estimated.

Then, the edges and the colors are encoded into lines and textures in the output tactile image.

Design of the method is substantiated by various qualities of haptic recognizing of images.

Also, means of presentation of the tactile images in printouts are discussed.

Example translated images are shown.

Today I read a paper titled “Uniform Proofs of Order Independence for Various Strategy Elimination Procedures”

The abstract is:
We provide elementary and uniform proofs of order independence for various strategy elimination procedures for finite strategic games, both for dominance by pure and by mixed strategies.

The proofs follow the same pattern and focus on the structural properties of the dominance relations.

They rely on Newman’s Lemma established in 1942 and related results on the abstract reduction systems.

Today I read a paper titled “An In-Place Sorting with O(n log n) Comparisons and O(n) Moves”

The abstract is:
We present the first in-place algorithm for sorting an array of size n that performs, in the worst case, at most O(n log n) element comparisons and O(n) element transports.

This solves a long-standing open problem, stated explicitly, e.g., in [J.I.

Munro and V.

Raman, Sorting with minimum data movement, J.

Algorithms, 13, 374-93, 1992], of whether there exists a sorting algorithm that matches the asymptotic lower bounds on all computational resources simultaneously.

Today I read a paper titled “Traffic Accident Analysis Using Decision Trees and Neural Networks”

The abstract is:
The costs of fatalities and injuries due to traffic accident have a great impact on society.

This paper presents our research to model the severity of injury resulting from traffic accidents using artificial neural networks and decision trees.

We have applied them to an actual data set obtained from the National Automotive Sampling System (NASS) General Estimates System (GES).

Experiment results reveal that in all the cases the decision tree outperforms the neural network.

Our research analysis also shows that the three most important factors in fatal injury are: driver’s seat belt usage, light condition of the roadway, and driver’s alcohol usage.

Today I read a paper titled “Multidimensional data classification with artificial neural networks”

The abstract is:
Multi-dimensional data classification is an important and challenging problem in many astro-particle experiments.

Neural networks have proved to be versatile and robust in multi-dimensional data classification.

In this article we shall study the classification of gamma from the hadrons for the MAGIC Experiment.

Two neural networks have been used for the classification task.

One is Multi-Layer Perceptron based on supervised learning and other is Self-Organising Map (SOM), which is based on unsupervised learning technique.

The results have been shown and the possible ways of combining these networks have been proposed to yield better and faster classification results.

Today I read a paper titled “Mobile Re-Finding of Web Information Using a Voice Interface”

The abstract is:
Mobile access to information is a considerable problem for many users, especially to information found on the Web.

In this paper, we explore how a voice-controlled service, accessible by telephone, could support mobile users’ needs for refinding specific information previously found on the Web.

We outline challenges in creating such a service and describe architectural and user interfaces issues discovered in an exploratory prototype we built called WebContext.

We also present the results of a study, motivated by our experience with WebContext, to explore what people remember about information that they are trying to refind and how they express information refinding requests in a collaborative conversation.

As part of the study, we examine how end-usercreated Web page annotations can be used to help support mobile information re-finding.

We observed the use of URLs, page titles, and descriptions of page contents to help identify waypoints in the search process.

Furthermore, we observed that the annotations were utilized extensively, indicating that explicitly added context by the user can play an important role in re-finding.

Today I read a paper titled “The Anatomy of the Grid – Enabling Scalable Virtual Organizations”

The abstract is:
“Grid” computing has emerged as an important new field, distinguished from conventional distributed computing by its focus on large-scale resource sharing, innovative applications, and, in some cases, high-performance orientation.

In this article, we define this new field.

First, we review the “Grid problem,” which we define as flexible, secure, coordinated resource sharing among dynamic collections of individuals, institutions, and resources-what we refer to as virtual organizations.

In such settings, we encounter unique authentication, authorization, resource access, resource discovery, and other challenges.

It is this class of problem that is addressed by Grid technologies.

Next, we present an extensible and open Grid architecture, in which protocols, services, application programming interfaces, and software development kits are categorized according to their roles in enabling resource sharing.

We describe requirements that we believe any such mechanisms must satisfy, and we discuss the central role played by the intergrid protocols that enable interoperability among different Grid systems.

Finally, we discuss how Grid technologies relate to other contemporary technologies, including enterprise integration, application service provider, storage service provider, and peer-to-peer computing.

We maintain that Grid concepts and technologies complement and have much to contribute to these other approaches.

Today I read a paper titled “The Gibbs Representation of 3D Rotations”

The abstract is:
This paper revisits the little-known Gibbs-Rodrigues representation of rotations in a three-dimensional space and demonstrates a set of algorithms for handling it.

In this representation the rotation is itself represented as a three-dimensional vector.

The vector is parallel to the axis of rotation and its three components transform covariantly on change of coordinates.

The mapping from rotations to vectors is 1:1 apart from computation error.

The discontinuities of the representation require special handling but are not problematic.

The rotation matrix can be generated efficiently from the vector without the use of transcendental functions, and vice-versa.

The representation is more efficient than Euler angles, has affinities with Hassenpflug’s Argyris angles and is very closely related to the quaternion representation.

While the quaternion representation avoids the discontinuities inherent in any 3-component representation, this problem is readily overcome.

The present paper gives efficient algorithms for computing the set of rotations which map a given vector to another of the same length and the rotation which maps a given pair of vectors to another pair of the same length and subtended angle.

Today I read a paper titled “An implemented model of punning riddles”

The abstract is:
In this paper, we discuss a model of simple question-answer punning, implemented in a program, JAPE, which generates riddles from humour-independent lexical entries.

The model uses two main types of structure: schemata, which determine the relationships between key words in a joke, and templates, which produce the surface form of the joke.

JAPE succeeds in generating pieces of text that are recognizably jokes, but some of them are not very good jokes.

We mention some potential improvements and extensions, including post-production heuristics for ordering the jokes according to quality..

Today I read a paper titled “Ranking Pages by Topology and Popularity within Web Sites”

The abstract is:
We compare two link analysis ranking methods of web pages in a site.

The first, called Site Rank, is an adaptation of PageRank to the granularity of a web site and the second, called Popularity Rank, is based on the frequencies of user clicks on the outlinks in a page that are captured by navigation sessions of users through the web site.

We ran experiments on artificially created web sites of different sizes and on two real data sets, employing the relative entropy to compare the distributions of the two ranking methods.

For the real data sets we also employ a nonparametric measure, called Spearman’s footrule, which we use to compare the top-ten web pages ranked by the two methods.

Our main result is that the distributions of the Popularity Rank and Site Rank are surprisingly close to each other, implying that the topology of a web site is very instrumental in guiding users through the site.

Thus, in practice, the Site Rank provides a reasonable first order approximation of the aggregate behaviour of users within a web site given by the Popularity Rank.

Today I read a paper titled “A symbolic description of punning riddles and its computer implementation”

The abstract is:
Riddles based on simple puns can be classified according to the patterns of word, syllable or phrase similarity they depend upon.

We have devised a formal model of the semantic and syntactic regularities underlying some of the simpler types of punning riddle.

We have also implemented this preliminary theory in a computer program which can generate riddles from a lexicon containing general data about words and phrases; that is, the lexicon content is not customised to produce jokes.

Informal evaluation of the program’s results by a set of human judges suggest that the riddles produced by this program are of comparable quality to those in general circulation among school children..

Today I read a paper titled “An Exploratory Study of Mobile Computing Use by Knowledge Workers”

The abstract is:
This paper describes some preliminary results from a 20-week study on the use of Compaq iPAQ Personal Digital Assistants (PDAs) by 10 senior developers, analysts, technical managers, and senior organisational managers.

The goal of the study was to identify what applications were used, how and where they were used, the problems and issues that arose, and how use of the iPAQs changed over the study period.

The paper highlights some interesting uses of the iPAQs, and identifies some of the characteristics of successful mobile applications.

Today I read a paper titled “An Automatic Method of Finding Topic Boundaries”

The abstract is:
This article outlines a new method of locating discourse boundaries based on lexical cohesion and a graphical technique called dotplotting.

The application of dotplotting to discourse segmentation can be performed either manually, by examining a graph, or automatically, using an optimization algorithm.

The results of two experiments involving automatically locating boundaries between a series of concatenated documents are presented.

Areas of application and future directions for this work are also outlined..

Today I read a paper titled “A General, Sound and Efficient Natural Language Parsing Algorithm based on Syntactic Constraints Propagation”

The abstract is:
This paper presents a new context-free parsing algorithm based on a bidirectional strictly horizontal strategy which incorporates strong top-down predictions (derivations and adjacencies).

From a functional point of view, the parser is able to propagate syntactic constraints reducing parsing ambiguity.

From a computational perspective, the algorithm includes different techniques aimed at the improvement of the manipulation and representation of the structures used.

Today I read a paper titled “Exposing Software Defined Radio Functionality To Native Operating System Applications via Virtual Devices”

The abstract is:
Many reconfigurable platforms require that applications be written specifically to take advantage of the reconfigurable hardware.

In a PC-based environment, this presents an undesirable constraint in that the many already available applications cannot leverage on such hardware.

Greatest benefit can only be derived from reconfigurable devices if even native OS applications can transparently utilize reconfigurable devices as they would normal full-fledged hardware devices.

This paper presents how Proteus Virtual Devices are used to expose reconfigurable hardware in a transparent manner for use by typical native OS applications.

Today I read a paper titled “Efficient Tree Layout in a Multilevel Memory Hierarchy”

The abstract is:
We consider the problem of laying out a tree with fixed parent/child structure in hierarchical memory.

The goal is to minimize the expected number of block transfers performed during a search along a root-to-leaf path, subject to a given probability distribution on the leaves.

This problem was previously considered by Gil and Itai, who developed optimal but slow algorithms when the block-transfer size B is known.

We present faster but approximate algorithms for the same problem; the fastest such algorithm runs in linear time and produces a solution that is within an additive constant of optimal.

In addition, we show how to extend any approximately optimal algorithm to the cache-oblivious setting in which the block-transfer size is unknown to the algorithm.

The query performance of the cache-oblivious layout is within a constant factor of the query performance of the optimal known-block-size layout.

Computing the cache-oblivious layout requires only logarithmically many calls to the layout algorithm for known block size; in particular, the cache-oblivious layout can be computed in O(N lg N) time, where N is the number of nodes.

Finally, we analyze two greedy strategies, and show that they have a performance ratio between Omega(lg B / lg lg B) and O(lg B) when compared to the optimal layout.

Today I read a paper titled “Business Intelligence from Web Usage Mining”

The abstract is:
The rapid e-commerce growth has made both business community and customers face a new situation.

Due to intense competition on one hand and the customer’s option to choose from several alternatives business community has realized the necessity of intelligent marketing strategies and relationship management.

Web usage mining attempts to discover useful knowledge from the secondary data obtained from the interactions of the users with the Web.

Web usage mining has become very critical for effective Web site management, creating adaptive Web sites, business and support services, personalization, network traffic flow analysis and so on.

In this paper, we present the important concepts of Web usage mining and its various practical applications.

We further present a novel approach ‘intelligent-miner’ (i-Miner) to optimize the concurrent architecture of a fuzzy clustering algorithm (to discover web data clusters) and a fuzzy inference system to analyze the Web site visitor trends.

A hybrid evolutionary fuzzy clustering algorithm is proposed in this paper to optimally segregate similar user interests.

The clustered data is then used to analyze the trends using a Takagi-Sugeno fuzzy inference system learned using a combination of evolutionary algorithm and neural network learning.

Proposed approach is compared with self-organizing maps (to discover patterns) and several function approximation techniques like neural networks, linear genetic programming and Takagi-Sugeno fuzzy inference system (to analyze the clusters).

The results are graphically illustrated and the practical significance is discussed in detail.

Empirical results clearly show that the proposed Web usage-mining framework is efficient.

Today I read a paper titled “How many candidates are needed to make elections hard to manipulate?”

The abstract is:
In multiagent settings where the agents have different preferences, preference aggregation is a central issue.

Voting is a general method for preference aggregation, but seminal results have shown that all general voting protocols are manipulable.

One could try to avoid manipulation by using voting protocols where determining a beneficial manipulation is hard computationally.

The complexity of manipulating realistic elections where the number of candidates is a small constant was recently studied (Conitzer 2002), but the emphasis was on the question of whether or not a protocol becomes hard to manipulate for some constant number of candidates.

That work, in many cases, left open the question: How many candidates are needed to make elections hard to manipulate? This is a crucial question when comparing the relative manipulability of different voting protocols.

In this paper we answer that question for the voting protocols of the earlier study: plurality, Borda, STV, Copeland, maximin, regular cup, and randomized cup.

We also answer that question for two voting protocols for which no results on the complexity of manipulation have been derived before: veto and plurality with runoff.

It turns out that the voting protocols under study become hard to manipulate at 3 candidates, 4 candidates, 7 candidates, or never.

Today I read a paper titled “Benchmarking and Implementation of Probability-Based Simulations on Programmable Graphics Cards”

The abstract is:
The latest Graphics Processing Units (GPUs) are reported to reach up to 200 billion floating point operations per second (200 Gflops) and to have price performance of 0.1 cents per M flop.

These facts raise great interest in the plausibility of extending the GPUs’ use to non-graphics applications, in particular numerical simulations on structured grids (lattice).

We review previous work on using GPUs for non-graphics applications, implement probability-based simulations on the GPU, namely the Ising and percolation models, implement vector operation benchmarks for the GPU, and finally compare the CPU’s and GPU’s performance.

A general conclusion from the results obtained is that moving computations from the CPU to the GPU is feasible, yielding good time and price performance, for certain lattice computations.

Preliminary results also show that it is feasible to use them in parallel .

Today I read a paper titled “Surface Triangulation — The Metric Approach”

The abstract is:
We embark in a program of studying the problem of better approximating surfaces by triangulations(triangular meshes) by considering the approximating triangulations as finite metric spaces and the target smooth surface as their Haussdorff-Gromov limit.

This allows us to define in a more natural way the relevant elements, constants and invariants s.a.

principal directions and principal values, Gaussian and Mean curvature, etc.

By a “natural way” we mean an intrinsic, discrete, metric definitions as opposed to approximating or paraphrasing the differentiable notions.

In this way we hope to circumvent computational errors and, indeed, conceptual ones, that are often inherent to the classical, “numerical” approach.

In this first study we consider the problem of determining the Gaussian curvature of a polyhedral surface, by using the {\em embedding curvature} in the sense of Wald (and Menger).

We present two modalities of employing these definitions for the computation of Gaussian curvature.

Today I read a paper titled “Classes of service under perfect competition and technological change: a model for the dynamics of the Internet?”

The abstract is:
Certain services may be provided in a continuous, one-dimensional, ordered range of different qualities and a customer requiring a service of quality q can only be offered a quality superior or equal to q.

Only a discrete set of different qualities will be offered, and a service provider will provide the same service (of fixed quality b) to all customers requesting qualities of service inferior or equal to b.

Assuming all services (of quality b) are priced identically, a monopolist will choose the qualities of service and the prices that maximize profit but, under perfect competition, a service provider will choose the (inferior) quality of service that can be priced at the lowest price.

Assuming significant economies of scale, two fundamentally different regimes are possible: either a number of different classes of service are offered (DC regime), or a unique class of service offers an unbounded quality of service (UC regime).

The DC regime appears in one of two sub-regimes: one, BDC, in which a finite number of classes is offered, the qualities of service offered are bounded and requests for high-quality services are not met, or UDC in which an infinite number of classes of service are offered and every request is met.

The types of the demand curve and of the economies of scale, not the pace of technological change, determine the regime and the class boundaries.

The price structure in the DC regime obeys very general laws..

Today I read a paper titled “Least squares fitting of circles and lines”

The abstract is:
We study theoretical and computational aspects of the least squares fit (LSF) of circles and circular arcs.

First we discuss the existence and uniqueness of LSF and various parametrization schemes.

Then we evaluate several popular circle fitting algorithms and propose a new one that surpasses the existing methods in reliability.

We also discuss and compare direct (algebraic) circle fits.

Today I read a paper titled “An effective Procedure for Speeding up Algorithms”

The abstract is:
The provably asymptotically fastest algorithm within a factor of 5 for formally described problems will be constructed.

The main idea is to enumerate all programs provably equivalent to the original problem by enumerating all proofs.

The algorithm could be interpreted as a generalization and improvement of Levin search, which is, within a multiplicative constant, the fastest algorithm for inverting functions.

Blum’s speed-up theorem is avoided by taking into account only programs for which a correctness proof exists.

Furthermore, it is shown that the fastest program that computes a certain function is also one of the shortest programs provably computing this function.

To quantify this statement, the definition of Kolmogorov complexity is extended, and two new natural measures for the complexity of a function are defined.

Today I read a paper titled “The Guidebook, the Friend, and the Room: Visitor Experience in a Historic House”

The abstract is:
In this paper, we describe an electronic guidebook prototype and report on a study of its use in a historic house.

Supported by mechanisms in the guidebook, visitors constructed experiences that had a high degree of interaction with three entities: the guidebook, their companions, and the house and its contents.

For example, we found that most visitors played audio descriptions played through speakers (rather than using headphones or reading textual descriptions) to facilitate communication with their companions.

Today I read a paper titled “Neuro Fuzzy Systems: Sate-of-the-Art Modeling Techniques”

The abstract is:
Fusion of Artificial Neural Networks (ANN) and Fuzzy Inference Systems (FIS) have attracted the growing interest of researchers in various scientific and engineering areas due to the growing need of adaptive intelligent systems to solve the real world problems.

ANN learns from scratch by adjusting the interconnections between layers.

FIS is a popular computing framework based on the concept of fuzzy set theory, fuzzy if-then rules, and fuzzy reasoning.

The advantages of a combination of ANN and FIS are obvious.

There are several approaches to integrate ANN and FIS and very often it depends on the application.

We broadly classify the integration of ANN and FIS into three categories namely concurrent model, cooperative model and fully fused model.

This paper starts with a discussion of the features of each model and generalize the advantages and deficiencies of each model.

We further focus the review on the different types of fused neuro-fuzzy systems and citing the advantages and disadvantages of each model.

Today I read a paper titled “Expected Qualitative Utility Maximization”

The abstract is:
 model for decision making that generalizes Expected Utility Maximization is presented.

This model, Expected Qualitative Utility Maximization, encompasses the Maximin criterion.

It relaxes both the Independence and the Continuity postulates.

Its main ingredient is the definition of a qualitative order on nonstandard models of the real numbers and the consideration of nonstandard utilities.

Expected Qualitative Utility Maximization is characterized by an original weakening of von Neumann-Morgenstern’s postulates.

Subjective probabilities may be defined from those weakened postulates, as Anscombe and Aumann did from the original postulates.

Subjective probabilities are numbers, not matrices as in the Subjective Expected Lexicographic Utility approach..

Today I read a paper titled “Improved Heterogeneous Distance Functions”

The abstract is:
Instance-based learning techniques typically handle continuous and linear input values well, but often do not handle nominal input attributes appropriately.

The Value Difference Metric (VDM) was designed to find reasonable distance values between nominal attribute values, but it largely ignores continuous attributes, requiring discretization to map continuous values into nominal values.

This paper proposes three new heterogeneous distance functions, called the Heterogeneous Value Difference Metric (HVDM), the Interpolated Value Difference Metric (IVDM), and the Windowed Value Difference Metric (WVDM).

These new distance functions are designed to handle applications with nominal attributes, continuous attributes, or both.

In experiments on 48 applications the new distance metrics achieve higher classification accuracy on average than three previous distance functions on those datasets that have both nominal and continuous attributes.

Today I read a paper titled “Fast Approximation of Centrality”

The abstract is:
Social studies researchers use graphs to model group activities in social networks.

An important property in this context is the centrality of a vertex: the inverse of the average distance to each other vertex.

We describe a randomized approximation algorithm for centrality in weighted graphs.

For graphs exhibiting the small world phenomenon, our method estimates the centrality of all vertices with high probability within a (1+epsilon) factor in near-linear time.

Today I read a paper titled “Min-Max Fine Heaps”

The abstract is:
In this paper we present a new data structure for double ended priority queue, called min-max fine heap, which combines the techniques used in fine heap and traditional min-max heap.

The standard operations on this proposed structure are also presented, and their analysis indicates that the new structure outperforms the traditional one.

Today I read a paper titled “A Neuro-Fuzzy Approach for Modelling Electricity Demand in Victoria”

The abstract is:
Neuro-fuzzy systems have attracted growing interest of researchers in various scientific and engineering areas due to the increasing need of intelligent systems.

This paper evaluates the use of two popular soft computing techniques and conventional statistical approach based on Box–Jenkins autoregressive integrated moving average (ARIMA) model to predict electricity demand in the State of Victoria, Australia.

The soft computing methods considered are an evolving fuzzy neural network (EFuNN) and an artificial neural network (ANN) trained using scaled conjugate gradient algorithm (CGA) and backpropagation (BP) algorithm.

The forecast accuracy is compared with the forecasts used by Victorian Power Exchange (VPX) and the actual energy demand.

To evaluate, we considered load demand patterns for 10 consecutive months taken every 30 min for training the different prediction models.

Test results show that the neuro-fuzzy system performed better than neural networks, ARIMA model and the VPX forecasts.

Today I read a paper titled “Near Rationality and Competitive Equilibria in Networked Systems”

The abstract is:
A growing body of literature in networked systems research relies on game theory and mechanism design to model and address the potential lack of cooperation between self-interested users.

Most game-theoretic models applied to system research only describe competitive equilibria in terms of pure Nash equilibria, that is, a situation where the strategy of each user is deterministic, and is her best response to the strategies of all the other users.

However, the assumptions necessary for a pure Nash equilibrium to hold may be too stringent for practical systems.

Using three case studies on computer security, TCP congestion control, and network formation, we outline the limits of game-theoretic models relying on Nash equilibria, and we argue that considering competitive equilibria of a more general form may help reconcile predictions from game-theoretic models with empirically observed behavior.

Today I read a paper titled “Generative Programming of Graphical User Interfaces”

The abstract is:
Generative Programming (GP) is a computing paradigm allowing automatic creation of entire software families utilizing the configuration of elementary and reusable components.

GP can be projected on different technologies, e.g.

C++-templates, Java-Beans, Aspect-Oriented Programming (AOP), or Frame technology.

This paper focuses on Frame Technology, which aids the possible implementation and completion of software components.

The purpose of this paper is to introduce the GP paradigm in the area of GUI application generation.

It demonstrates how automatically customized executable applications with GUI parts can be generated from an abstract specification.

Today I read a paper titled “Optimally cutting a surface into a disk”

The abstract is:
We consider the problem of cutting a set of edges on a polyhedral manifold surface, possibly with boundary, to obtain a single topological disk, minimizing either the total number of cut edges or their total length.

We show that this problem is NP-hard, even for manifolds without boundary and for punctured spheres.

We also describe an algorithm with running time n^{O(g+k)}, where n is the combinatorial complexity, g is the genus, and k is the number of boundary components of the input surface.

Finally, we describe a greedy algorithm that outputs a O(log^2 g)-approximation of the minimum cut graph in O(g^2 n log n) time.

Today I read a paper titled “Fast Universalization of Investment Strategies with Provably Good Relative Returns”

The abstract is:
A universalization of a parameterized investment strategy is an online algorithm whose average daily performance approaches that of the strategy operating with the optimal parameters determined offline in hindsight.

We present a general framework for universalizing investment strategies and discuss conditions under which investment strategies are universalizable.

We present examples of common investment strategies that fit into our framework.

The examples include both trading strategies that decide positions in individual stocks, and portfolio strategies that allocate wealth among multiple stocks.

This work extends Cover’s universal portfolio work.

We also discuss the runtime efficiency of universalization algorithms.

While a straightforward implementation of our algorithms runs in time exponential in the number of parameters, we show that the efficient universal portfolio computation technique of Kalai and Vempala involving the sampling of log-concave functions can be generalized to other classes of investment strategies.

Today I read a paper titled “Artificial Neural Networks for Beginners”

The abstract is:
The scope of this teaching package is to make a brief induction to Artificial Neural Networks (ANNs) for people who have no previous knowledge of them.

We first make a brief introduction to models of networks, for then describing in general terms ANNs.

As an application, we explain the backpropagation algorithm, since it is widely used and many other algorithms are derived from it.

The user should know algebra and the handling of functions and vectors.

Differential calculus is recommendable, but not necessary.

The contents of this package should be understood by people with high school education.

It would be useful for people who are just curious about what are ANNs, or for people who want to become familiar with them, so when they study them more fully, they will already have clear notions of ANNs.

Also, people who only want to apply the backpropagation algorithm without a detailed and formal explanation of it will find this material useful.

This work should not be seen as “Nets for dummies”, but of course it is not a treatise.

Much of the formality is skipped for the sake of simplicity.

Detailed explanations and demonstrations can be found in the referred readings.

The included exercises complement the understanding of the theory.

The on-line resources are highly recommended for extending this brief induction.

Today I read a paper titled “The Geometric Maximum Traveling Salesman Problem”

The abstract is:
We consider the traveling salesman problem when the cities are points in R^d for some fixed d and distances are computed according to geometric distances, determined by some norm.

We show that for any polyhedral norm, the problem of finding a tour of maximum length can be solved in polynomial time.

If arithmetic operations are assumed to take unit time, our algorithms run in time O(n^{f-2} log n), where f is the number of facets of the polyhedron determining the polyhedral norm.

Thus for example we have O(n^2 log n) algorithms for the cases of points in the plane under the Rectilinear and Sup norms.

This is in contrast to the fact that finding a minimum length tour in each case is NP-hard.

Our approach can be extended to the more general case of quasi-norms with not necessarily symmetric unit ball, where we get a complexity of O(n^{2f-2} log n).

For the special case of two-dimensional metrics with f=4 (which includes the Rectilinear and Sup norms), we present a simple algorithm with O(n) running time.

The algorithm does not use any indirect addressing, so its running time remains valid even in comparison based models in which sorting requires Omega(n \log n) time.

The basic mechanism of the algorithm provides some intuition on why polyhedral norms allow fast algorithms.

Complementing the results on simplicity for polyhedral norms, we prove that for the case of Euclidean distances in R^d for d>2, the Maximum TSP is NP-hard.

This sheds new light on the well-studied difficulties of Euclidean distances.

Today I read a paper titled “Neural Network Methods for Boundary Value Problems Defined in Arbitrarily Shaped Domains”

The abstract is:
Partial differential equations (PDEs) with Dirichlet boundary conditions defined on boundaries with simple geometry have been succesfuly treated using sigmoidal multilayer perceptrons in previous works.

This article deals with the case of complex boundary geometry, where the boundary is determined by a number of points that belong to it and are closely located, so as to offer a reasonable representation.

Two networks are employed: a multilayer perceptron and a radial basis function network.

The later is used to account for the satisfaction of the boundary conditions.

The method has been successfuly tested on two-dimensional and three-dimensional PDEs and has yielded accurate solutions.

Today I read a paper titled “Secure History Preservation Through Timeline Entanglement”

The abstract is:
A secure timeline is a tamper-evident historic record of the states through which a system goes throughout its operational history.

Secure timelines can help us reason about the temporal ordering of system states in a provable manner.

We extend secure timelines to encompass multiple, mutually distrustful services, using timeline entanglement.

Timeline entanglement associates disparate timelines maintained at independent systems, by linking undeniably the past of one timeline to the future of another.

Timeline entanglement is a sound method to map a time step in the history of one service onto the timeline of another, and helps clients of entangled services to get persistent temporal proofs for services rendered that survive the demise or non-cooperation of the originating service.

In this paper we present the design and implementation of Timeweave, our service development framework for timeline entanglement based on two novel disk-based authenticated data structures.

We evaluate Timeweave’s performance characteristics and show that it can be efficiently deployed in a loosely-coupled distributed system of a few hundred services with overhead of roughly 2-8% of the processing resources of a PC-grade system.

Today I read a paper titled “Tap Tips: Lightweight Discovery of Touchscreen Targets”

The abstract is:
We describe tap tips, a technique for providing touch-screen target location hints.

Tap tips are lightweight in that they are non-modal, appear only when needed, require a minimal number of user gestures, and do not add to the standard touchscreen gesture vocabulary.

We discuss our implementation of tap tips in an electronic guidebook system and some usability test results.

Today I read a paper titled “Using Simulated Annealing to Calculate the Trembles of Trembling Hand Perfection”

The abstract is:
Within the literature on non-cooperative game theory, there have been a number of attempts to propose logorithms which will compute Nash equilibria.

Rather than derive a new algorithm, this paper shows that the family of algorithms known as Markov chain Monte Carlo (MCMC) can be used to calculate Nash equilibria.

MCMC is a type of Monte Carlo simulation that relies on Markov chains to ensure its regularity conditions.

MCMC has been widely used throughout the statistics and optimization literature, where variants of this algorithm are known as simulated annealing.

This paper shows that there is interesting connection between the trembles that underlie the functioning of this algorithm and the type of Nash refinement known as trembling hand perfection.

Today I read a paper titled “In vivo spam filtering: A challenge problem for data mining”

The abstract is:
Spam, also known as Unsolicited Commercial Email (UCE), is the bane of email communication.

Many data mining researchers have addressed the problem of detecting spam, generally by treating it as a static text classification problem.

True in vivo spam filtering has characteristics that make it a rich and challenging domain for data mining.

Indeed, real-world datasets with these characteristics are typically difficult to acquire and to share.

This paper demonstrates some of these characteristics and argues that researchers should pursue in vivo spam filtering as an accessible domain for investigating them.

Today I read a paper titled “Note on Needle in a Haystack”

The abstract is:
Introduced below is a quantum database method, not only for retrieval but also for creation.

It uses a particular structure of true’s and false’s in a state vector of n qubits, permitting up to 2**2**n words, vastly more than for classical bits.

Several copies are produced so that later they can be destructively observed and a word determined with high probability.

Grover’s algorithm is proposed below to read out, nondestructively the unknown contents of a given stored state vector using only one state vector.

Today I read a paper titled “Dealing With Curious Players in Secure Networks”

The abstract is:
In secure communications networks there are a great number of user behavioural problems, which need to be dealt with.

Curious players pose a very real and serious threat to the integrity of such a network.

By traversing a network a Curious player could uncover secret information, which that user has no need to know, by simply posing as a loyalty check.

Loyalty checks are done simply to gauge the integrity of the network with respect to players who act in a malicious manner.

We wish to propose a method, which can deal with Curious players trying to obtain “Need to Know” information using a combined Fault-tolerant, Cryptographic and Game Theoretic Approach.

Today I read a paper titled “Combinatorial Auctions with Decreasing Marginal Utilities”

The abstract is:
In most of microeconomic theory, consumers are assumed to exhibit decreasing marginal utilities.

This paper considers combinatorial auctions among such submodular buyers.

The valuations of such buyers are placed within a hierarchy of valuations that exhibit no complementarities, a hierarchy that includes also OR and XOR combinations of singleton valuations, and valuations satisfying the gross substitutes property.

Those last valuations are shown to form a zero-measure subset of the submodular valuations that have positive measure.

While we show that the allocation problem among submodular valuations is NP-hard, we present an efficient greedy 2-approximation algorithm for this case and generalize it to the case of limited complementarities.

No such approximation algorithm exists in a setting allowing for arbitrary complementarities.

Some results about strategic aspects of combinatorial auctions among players with decreasing marginal utilities are also presented..