We consider the inductive inference model of Gold [15]. Suppose we are given a set of functions that are learnable with certain number of mind changes and errors. What can we consistently predict about those functions if we are allowed fewer mind changes or errors? In [20] we relaxed the notion of exact learning by considering some higher level properties of the input-output behavior of a given function. in this context, a learner produces a program that describes the property of a given function. Can we predict generic properties such as threshold or modality if we allow fewer number of mind changes or errors? These questions were completely answered in [20] when the learner is restricted to a single IIM. In this paper we allow a team of IIMs to collaborate in the learning process. The learning is considered to be successful if any one of the team member succeeds. A motivation for this extension is to understand and characterize properties that are learnable for a given set of functions in a team environment.

We consider the inductive inference model of Gold [15]. Suppose we are given a set of functions that are learnable with certain number of mind changes and errors. What properties of these functions are learnable if we allow fewer number of mind changes or errors? In order to answer this question this paper extends the Inductive Inference model introduced by Gold [15]. Another motivation for this extension is to understand and characterize properties that are learnable for a given set of functions. Our extension considers a wide range of properties of function based on their input-output relationship. Two specific properties of functions are studied in this paper. The first property, which we call modality, explores how the output of a function fluctuates. For example, consider a function that predicts the price of a stock. A brokerage company buys and sells stocks very often in a day for its clients with the intent of maximizing their profit. If the company is able predict the trend of the stock market "reasonably" accurately then it is bound to be very successful. Identification criterion for this property of a function f is called PREX which predicts if f(x) is equal to, less than or greater than f(x+1) for each x. Next, as opposed to a constant tracking by a brokerage company, an individual investor does not often track dynamic changes in stock values. Instead, the investor would like to move the investment to a less risky option when the investment exceeds or falls below certain threshold. We capture this notion using an identification criterion called TREX that essentially predicts if a function value is at, above, or below a threshold value. Conceptually,modality prediction (i.e., PREX) and threshold prediction (i.e., TREX) are "easier" than EX learning. We show that neither the number of errors nor the number of mind-changes can be reduced when we ease the learning criterion from exact learning to learning modality or threshold. We also prove that PREX and TREX are totally different properties to predict. That is, the strategy for a brokerage company may not be a good strategy for individual investor and vice versa.

We study fault-tolerant multiprocessor scheduling under the realistic assumption that the occurrence of faults cannot be predicted. The goal in these problems is to minimize the delay incurred by the jobs. Since this is an online problem we use competitive analysis to evaluate possible algorithms. For the problems of minimizing the makespan and minimizing the average completion time (for static release times), we give nonclairvoyant algorithms (both deterministic and randomized) that have provably asymptotically optimal competitive ratios. The main tool used by these algorithms to combat faults is redundancy. We also show that randomization has the same effect as redundancy.

We consider the problem of scheduling a collection of dynamically arriving jobs with unknown execution times so as to minimize the average flow time. This is the classic CPU scheduling problem faced by time-sharing operating systems where preemption is allowed. It is easy to see that every algorithm that doesn't unnecessarily idle the processor is at worst n -competitive, where n is the number of jobs. Yet there was no known nonclairvoyant algorithm, deterministic or randomized, with a competitive ratio provably O ( n 1−ϵ ). In this article, we give a randomized nonclairvoyant algorithm, RMLF, that has competitive ratio O (log n log log n ) against an oblivious adversary. RMLF is a slight variation of the multilevel feedback (MLF) algorithm used by the UNIX operating system, further justifying the adoption of this algorithm. It is known that every randomized nonclairvoyant algorithm is Ω(log n )-competitive, and that every deterministic nonclairvoyant algorithm is Ω( n 1/3 )-competitive.

Let f:{0, 1}/sup n//spl times/{0, 1}/sup n//spl rarr/{0, 1}. Assume Alice has x/sub 1/, ..., x/sub k//spl isin/{0, 1}/sup n/, Bob has y/sub 1/, ..., y/sub k//spl isin/{0, 1}/sup n/, and they want to compute f(x/sub 1/, y/sub 1/)/spl middot//spl middot//spl middot/f(x/sub k/, y/sub k/) communicating as few bits as possible. The Direct Sum Conjecture of Karchmer, Raz, and Wigderson, states that the obvious way to compute it (computing f(x/sub 1/, y/sub 1/), then f(x/sub 2/, y/sub 2/), etc.) is, roughly speaking, the best. This conjecture arose in the study of circuits. Since a variant of it implies NC/sup 1//spl ne/NC/sup 2/. We consider three related problems. Enumeration: Alice and Bob output e/spl les/2/sup k/-1 elements of {0, 1}/sup k/: one of which is f(x/sub 1/, y/sub 1/)/spl middot//spl middot//spl middot/f(x/sub k/, y/sub k/). Elimination: Alice and Bob output an element of {0, 1}/sup k/ that is not f(x/sub 1/ y/sub 1/)/spl middot//spl middot//spl middot/f(x/sub k/, y/sub k/) Selection: (k=2) Alice and Bob output i/spl sim/{1,2} such that if f(x/sub 1/, y/sub 1/)=1 V f(x/sub 2/, Y/sub 2/)=1 then f(x/sub i/, y/sub i/)=1. We establish lower bounds on ELIM(f/sup k/) for particular f and connect the complexity of ELIM(f/sup k/), ENUM(k, f/sup k/), and SELECT(f/sup 2/) to the direct sum conjecture and other conjectures.

We introduce resource augmentation as a method for analyzing online scheduling problems. In resource augmentation analysis the on-line scheduler is given more resources, say faster processors or more processors, than the adversary. We apply this analysis to two well-known on-line scheduling problems, the classic uniprocessor CPU scheduling problem 1 | r i , pmtn|Σ F i , and the best-effort firm real-time scheduling problem 1| r i , pmtn | Σ w i ( 1- U i ). It is known that there are no constant competitive nonclairvoyant on-line algorithms for these problems. We show that there are simple on-line scheduling algorithms for these problems that are constant competitive if the online scheduler is equipped with a slightly faster processor than the adversary. Thus, a moderate increase in processor speed effectively gives the on-line scheduler the power of clairvoyance. Furthermore, the on-line scheduler can be constant competitive on all inputs that are not closely correlated with processor speed. We also show that the performance of an on-line scheduler is best-effort real time scheduling can be significantly improved if the system is designed in such a way that the laxity of every job is proportional to its length.

We study the online transportation problem under the assumption that the adversary has only half as many servers at each site as the online algorithm. We show that the GREEDY algorithm is $\Theta( {\rm min}(m, \lg C))$-competitive under this assumption, where m is the number of server sites and C is the total number of servers. We then present an algorithm BALANCE, which is a simple modification of the GREEDY algorithm, that is, O(1)-competitive under this assumption.

Article FINite learning capabilities and their limits Share on Authors: Robert Daley Department of Computer Science, University of Pittsburgh, Pittsburgh, PA Department of Computer Science, University of Pittsburgh, Pittsburgh, PAView Profile , Bala Kalyanasundaram Department of Computer Science, University of Pittsburgh, Pittsburgh, PA Department of Computer Science, University of Pittsburgh, Pittsburgh, PAView Profile Authors Info & Claims COLT '97: Proceedings of the tenth annual conference on Computational learning theoryJuly 1997 Pages 81–89https://doi.org/10.1145/267460.267483Online:01 July 1997Publication History 2citation134DownloadsMetricsTotal Citations2Total Downloads134Last 12 Months1Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We consider the problem of scheduling a collection of dynamically arriving jobs with unknown execution times so as to minimize the average response/flow time. This is the classic CPU scheduling problem faced by time sharing operating systems. In the standard 3-field scheduling notation this is the nonclairvoyant version of 1|pmtn, r/sub j/|/spl Sigma/F/sub j/. Its easy to see that every algorithm that doesn't unnecessarily idle the processor is at worst n-competitive, where n is the number of jobs. Yet there is no known nonclairvoyant algorithm, deterministic or randomized, with a competitive ratio provably o(n). We present a randomized nonclairvoyant algorithm, RMLF, that has competitive ratio /spl theta/(lognloglogn) against an adaptive adversary. RMLF is a slight variation of the multi level feedback (MLF) algorithm used by the Unix operating system, further justifying the adoption of this algorithm. R. Motwani et al. (1994) showed that every randomized nonclairvoyant algorithm is /spl Omega/2(log n)competitive, and that every deterministic nonclairvoyant algorithm is /spl Omega/2(n/sup 1/3/)-competitive.

We consider several well known nonclairvoyant scheduling problems, including the problem of minimizing the average response time, and best-effort firm real-time scheduling. It is known that there are no deterministic online algorithms for these problems with bounded (or even polylogarithmic in the number of jobs) competitive ratios. We show that moderately increasing the speed of the processor used by the non-clairvoyant scheduler effectively gives this scheduler the power of clairvoyence. Furthermore, we show that there exist online algorithms with bounded competitive ratios on all inputs that are not closely correlated with processor speed.

We show that for every probabilistic FIN-type learner with success ratio greater than 2449, there is another pluralistic (or team) FIN-type learner with success ratio 24 that simulates the former. We will also show that this simulation result is tight. We obtain as a consequence of this work a characterization of FIN-type team learning with success ratio between 2449 and 12. We also obtain several additional points (viz., 2041, 1837, 1735) in the capability sequence for FIN-type learning, which taken together suggest that the complete sequence of capabilities will turn out to be a very complex matter.

We study fault-tolerant multiprocessor nonpreemptive scheduling under the realistic assumption that the occurrence of faults can not be predicted.The goal in these problems is to minimize the delay incurred by the jobs.Since this is an on-line problem we use competitive analysis to evaluate possible algorithms.For the problems of minimizing the make-span, and minimizing the average response time (for static release times), we give nonclairvoyant algorithms (both deterministic and randomized) that have provably asymptotically optimal competitive ratios.The main tool used by these algorithms to combat faults is redundancy.We show that randomization has the same effect as redundancy.work on scheduling either assumes that there are

We consider the capabilities of probabilistic and team learners who (a) are allowed to conjecture only one hypothesis when given a function to learn; and (b) must always produce a program (i.e. hypotheses) that halts on every input. Learners satisfying only (a) are termed FIN-type learners, and learners satisfying both (a) and (b) are termed PFIN-type learners. We show that the structure of the learning capability of probabilistic and team learning with success ratio above 1/2 in PFIN-type learning is analogous to the structure observed in FIN-type learning. On the contrary, the structure of probabilistic and team learning with success ratio below 1/2 is more sparse for PFIN-type learning than for FIN-type learning. For n ≥ 2, we show that the probabilistic hierarchy below 1/2 for PFIN-type learning is denned by the sequence 4n/(9n − 2), which has an accumulation point at 4/9. We also show that the redundancy type at the accumulation point 4/9 is different from the one observed at 1/2. More interestingly, for the first time, we show the occurrence of redundancy even at points that are not accumulation points.

We consider the power of randomization in finite learning when a bounded number of mind changes are allowed.We show that in the ~m+2_3 range ( ~~+a _2, 1] the capability type of probabilistic as well as pluralistic FIN-type (also PFIN-type) learners is defined by the sequence 2"'+7-3 n+l {w n ~O}, where m ~O is the allowed number of mind changes for the learners.This generalizes most of the results known in the literature on finite learning.For any fixed number of mind changes, we show that deterministic strategies can simulate probabilistic strategies where the success ratio is close to but not equal to 1. F'inaHy, our results demonstrate the power of redundancy when a bounded number of mind changes are allowed.In contrast, it is known that the power of redundancy disappears when an apriori unbounded (but finite) number of mind changes are allowed.

The type of learning which we consider is finite learning( F]N-t ype) where a learner is permitted to conjecture only one program for the function which it is trying to learn.In this paper we investigate the relative learning capabilities of probabilistic and pluralistic learners when they are allowed to conjecture programs which have errors in them.Pluralistic learners are teams of learners which cooperate in trying to learn a function.We determine the exact point at which probabilistic learners are more powerful than deterministic (i.e., a team of size one) learners.

We show that for every probabilistic FIN-type learner with success ratio greater than 24/49, there is another probabilistic FIN-type learner with success ratio 1/2 that simulates the former. We will also show that this simulation result is tight. We obtain as a consequence of this work a characterization of FIN-type team learning with success ratio between 24/49 and 1/2. We conjecture that the learning capabilities of probabilistic FIN-type learners for probabilities beginning at probability 1/2 are delimited by the sequence 8n/17n-2 for n > 2, which has an accumulation point at 8/17.

It is shown that, for inputs of length n, the probabilistic (bounded error) communication complexity of set intersection is $\Theta ( n )$. Since set intersection can be recognized nondeterministically by exchanging $O( \log n )$ bits, the result implies an exponential gap between nondeterminism and probabilism. This gap is the largest possible. The first general technique to analyze the probabilistic communication complexity of sparse languages is also described.

We construct a family (Gp | p) of directed acyclic graphs such that any black pebble strategy for Gp requires p2 pebbles whereas 3p+1 pebbles are sufficient when white pebbles are allowed.