Randomized range-maxima in nearly-constant parallel time

Given an array ofn input numbers, therange-maxima problem is that of preprocessing the data so that queries of the type what is the maximum value in subarray [i..j] can be answered quickly using one processor. We present a randomized preprocessing algorithm that runs inO(log^* n) time with high probability, using an optimal number of processors on a CRCW PRAM; each query can be processed in constant time by one processor. We also present a randomized algorithm for a parallel comparison model. Using an optimal number of processors, the preprocessing algorithm runs inO( (n)) time with high probability; each query can be processed inO ( (n)) time by one processor. (As is standard, (n) is the inverse of Ackermann function.) A constant time query can be achieved by some slowdown in the performance of the preprocessing stage.     

Incorporating Machine Learning into Established Bioinformatics Frameworks

The exponential growth of biomedical data in recent years has urged the application of numerous machine learning techniques to address emerging problems in biology and clinical research. By enabling the automatic feature extraction, selection, and generation of predictive models, these methods can be used to efficiently study complex biological systems. Machine learning techniques are frequently integrated with bioinformatic methods, as well as curated databases and biological networks, to enhance training and validation, identify the best interpretable features, and enable feature and model investigation. Here, we review recently developed methods that incorporate machine learning within the same framework with techniques from molecular evolution, protein structure analysis, systems biology, and disease genomics. We outline the challenges posed for machine learning, and, in particular, deep learning in biomedicine, and suggest unique opportunities for machine learning techniques integrated with established bioinformatics approaches to overcome some of these challenges.     

RL \subseteq SC

We show that any randomized logspace algorithm (running in polynomial time with bounded two-sided error) can be simulated deterministically in polynomial time andO(log² n) space. This puts RL in SC, Steve's Class In particular, we get a polynomial time,O(log² n) space algorithm for thest-connectivity problem on undirected graphs.Subject classifications. 68Q10, 68Q15, 68Q25.     

Enhancing comparison shopping agents through ordering and gradual information disclosure

The plethora of comparison shopping agents (CSAs) in today’s markets enables buyers to query more than a single CSA when shopping, thus expanding the list of sellers whose prices they obtain. This potentially decreases the chance of a purchase within any single interaction between a buyer and a CSA, and consequently decreases each CSAs’ expected revenue per-query. Obviously, a CSA can improve its competence in such settings by acquiring more sellers’ prices, potentially resulting in a more attractive “best price”. In this paper we suggest a complementary approach that improves the attractiveness of the best result returned based on intelligently controlling the order according to which they are presented to the user, in a way that utilizes several known cognitive-biases of human buyers. The advantage of this approach is in its ability to affect the buyer’s tendency to terminate her search for a better price, hence avoid querying further CSAs, without spending valuable resources on finding additional prices to present. The effectiveness of our method is demonstrated using real data, collected from four CSAs for five products. Our experiments confirm that the suggested method effectively influence people in a way that is highly advantageous to the CSA compared to the common method for presenting the prices. Furthermore, we experimentally show that all of the components of our method are essential to its success.     

A theoretical framework and empirical examination of the effects of foreign and translated interface language

Given the increased globalization and popularization of computer applications, translating a system's human interface into the local language has become a major consideration for software vendors and distributors. In this paper, we suggest a theoretical framework for the study of user interface translation. The framework includes recognizing vendors' and users' costs of, and benefits from, software translation. An experiment was conducted, based on this framework, to test user performance and preferences regarding interface translations. The experiment manipulated the translation of two interface components: documentation language and manipulation language. The results indicate that users are sensitive to different combinations of interface translation in a way that is commensurate with the instruction-following process (Terwilliger and Polson 1997). Users performed best when a fully translated interface was used and worst when only the manipulation language was translated. Users' preferences were in line with their performance, indicating that a cost benefit approach can serve as a promising starting point to the study of interface translation.     

Deterministic Resource Discovery in Distributed Networks

The resource discovery problem was introduced by Harchol-Balter, Leighton, and Lewin. They developed a number of algorithms for the problem in the weakly connected directed graph model. This model is a directed logical graph that represents the vertices’ knowledge about the topology of the underlying communication network. The current paper proposes a deterministic algorithm for the problem in the same model, with improved time, message, and communication complexities. Each previous algorithm had a complexity that was higher at least in one of the measures. Specifically, previous deterministic solutions required either time linear in the diameter of the initial network, or communication complexity $O(n^3)$ (with message complexity $O(n^2)$), or message complexity $O(|E_0| \log n)$ (where $E_0$ is the arc set of the initial graph $G_0$). Compared with the main randomized algorithm of Harchol-Balter, Leighton, and Lewin, the time complexity is reduced from $O(\log^2n)$ to\pagebreak[4] $O(\log n )$, the message complexity from $O(n \log^2 n)$ to $O(n \log n )$, and the communication complexity from $O(n^2 \log^3 n)$ to $O(|E_0|\log ^2 n )$. \par Our work significantly extends the connectivity algorithm of Shiloach and Vishkin which was originally given for a parallel model of computation. Our result also confirms a conjecture of Harchol-Balter, Leighton, and Lewin, and addresses an open question due to Lipton.     

Competitive analysis of incentive compatible on-line auctions

This paper studies auctions in a setting where the different bidders arrive at different times and the auction mechanism is required to make decisions about each bid as it is received. Such settings occur in computerized auctions of computational resources as well as in other settings. We call such auctions, on-line auctions.

We first characterize exactly on-line auctions that are incentive compatible, i.e. where rational bidders are always motivated to bid their true valuation. We then embark on a competitive worst-case analysis of incentive compatible on-line auctions. We obtain several results, the cleanest of which is an incentive compatible on-line auction for a large number of identical items. This auction has an optimal competitive ratio, both in terms of seller's revenue and in terms of the total social efficiency obtained.     

Superluminal tunnelling times as weak values

Abstract

We consider the tunnelling particle as a pre- and post-selected system and prove that the tunnelling time is the expectation value of the position of a ‘clock’ degree of freedom weakly coupled to it. Such a value, called a ‘weak value’, typically falls outside the eigenvalue spectrum of the operator. The appearance of unusual weak values has been associated with a unique interference structure called ‘superoscillations’ (band-limited functions which on a finite interval, approximate functions with spectra well outside their band). It is proposed that superoscillations play an important role in the interferences which give rise to superluminal effects. To demonstrate that, we consider a certain simple tunnelling barrier which allows a wave packet to travel in zero time and negligible distortion, a distance arbitrarily longer than the width of the wave packet. The peak is shown to result from a superoscillatory superposition at the tail. Similar reasoning applies to the dwell time. For this system, both the Wigner time (related to the group velocity) and a clock time correspond to superluminal velocities.