nils-herrmann/clean_scirepeval huggingface dataset:
Competitive queue policies for differentiated services

We consider the setting of a network providing differentiated services. As is often the case in differentiated services, we assume the packets are tagged as either being high- or low-priority packets. Outgoing links in the network are serviced by a single FIFO queue. Our model gives a benefit of /spl alpha//spl ges/1 to each high-priority packet and a benefit of 1 to each low-priority packet. A queue policy controls which of the arriving packets are dropped and which enter the queue. Once a packet enters the queue it is eventually sent. The aim of a queue policy is to maximize the sum of the benefits of all the packets it delivers. We analyze and compare different queue policies for this problem using the competitive analysis approach, where the benefit of the online policy is compared to the benefit of an optimal offline policy. We derive both upper and lower bounds for the policies we consider, and in most cases our bounds are tight. We believe that competitive analysis gives important insight into the performance of these simple queuing policies.
Optimal smoothing schedules for real-time streams (extended abstract)

We consider the problem of smoothing real-time streams (such as video streams), where the goal is to reproduce a variable-bandwidth stream remotely, while minimizing bandwidth cost, space overhead, and playback delay. We focus on lossy schedules, where some bytes may be dropped due to limited bandwidth or space. We present the following results. First, we determine the optimal tradeoff between buffer space, queuing delay, and link bandwidth for lossy smoothing schedules. Specifically, this means that if one of these parameters is under our control, we can precisely calculate the optimal value which minimizes data loss while avoiding resource wastage. The tradeoff is accomplished by a simple generic algorithm, that allows one some freedom in choosing which data to discard. This algorithm is very easy to implement both at the server and at the client, and it enjoys the nice property that only the server decides which data to discard, and the client needs only to reconstruct the stream. In a second set of results we study the case where different parts of the data have different importance, modeled by assigning a real “weight” to each byte in the stream. For this setting we use competitive analysis, i.e., we compare the weight delivered by on-line algorithms to the weight of an optimal off-line schedule using the same resources. We prove that a natural greedy algorithm is 4-competitive. We also prove a lower bound of 1.25 on the competitive ratio of any deterministic on-line algorithm. Finally, we give a few experimental results which show that smoothing is extremely effective in practice, and that the greedy algorithm performs very well in the weighted case.
Boosting Using Branching Programs

It is known that decision tree learning can be viewed as a form of boosting. Given a weak learning hypothesis one can show that the training error of a decision tree declines as |T| where |T| is the size of the decision tree and b is a constant determined by the weak learning hypothesis. Here we consider the case of decision DAGs—decision trees in which a given node can be shared by different branches of the tree, also called branching programs (BP). Node sharing allows a branching program to be exponentially more compact than the corresponding decision tree. We show that under the same weak learning assumption used for decision tree learning there exists a greedy BP-growth algorithm whose training error is guaranteed to decline as 2−b`|T|, where |T| is the size of the branching program and b is a constant determined by the weak learning hypothesis. Therefore, from the perspective of boosting theory, branching programs are exponentially more efficient than decision trees.
Convergence Complexity of Optimistic Rate-Based Flow-Control Algorithms

This paper studies basic properties of rate-based flow-control algorithms and of the max-min fairness criteria. For the algorithms we suggest a new approach for their modeling and analysis, which may be considered more “optimistic” and realistic than traditional approaches. Three variations of the approach are presented, and their rate of convergence to the optimal max-min fairness solution is analyzed. In addition, we introduce and analyze approximate rate-based flow-control algorithms. We show that under certain conditions the approximate algorithms may converge faster. However, we show that the resulting flows may be substantially different from the flows dictated by the max-min fairness. We further demonstrate that the max-min fairness solution can be very sensitive to small changes, i.e., there are configurations in which an addition or deletion of a session with rate ? may change the allocation of another session by ?(?·2n/2), but by no more thanO(?·2n). This implies that the max-min fairness criteria may provide a bad estimate of how far a set of flow allocations is from the optimal allocation.
On Propagating Updates in a Byzantine Environment

We study how to efficiently diffuse updates to a large distributed system of data replicas, some of which may exhibit arbitrary (Byzantine) failures. We assume that strictly fewer than $t$ replicas fail, and that each update is initially received by at least $t$ correct replicas. The goal is to diffuse each update to all correct replicas while ensuring that correct replicas accept no updates generated spuriously by faulty replicas. To achieve reliable diffusion, each correct replica accepts an update only after receiving it from at least $t$ others. We provide the first analysis of epidemic-style protocols for such environments. This analysis is fundamentally different from known analyses for the benign case due to our treatment of fully Byzantine failures---which, among other things, precludes the use of digital signatures for authenticating forwarded updates. We propose two epidemic-style diffusion algorithms and two measures that characterize the efficiency of diffusion algorithms in general. We characterize both of our algorithms according to these measures, and also prove lower bounds with regards to these measures that show that our algorithms are close to optimal.
Trade-offs between Communication Throughput and Parallel Time

We study the effect of limited communication throughput on parallel computation in a setting where the number of processors is much smaller than the length of the input. Our model haspprocessors that communicate through a shared memory of sizem. The input has sizenand can be read directly by all the processors. We will be primarily interested in studying cases wheren?p?m. As a test case we study the list reversal problem. For this problem we prove a time lower bound of?(n/mp). (A similar lower bound holds also for the problems of sorting, finding all unique elements, convolution, and universal hashing.) This result demonstrates that limiting the communication (i.e., smallm) could have significant effect on parallel computation. We show an almost matching upper bound ofO((n/mp)logO(1)n). The upper bound requires the development of a few interesting techniques which can alleviate the limited communication in some general settings. Specifically, we show how to emulate a large shared memory on a limited shared memory efficiently. The lower bound applies even to randomized machines, and the upper bound is a randomized algorithm. We also argue that some standard methodology for designing parallel algorithms appears to require a relatively high level of communication throughput. Our results suggest that new alternative methodologies that need a lower such level must be invented for parallel machines that enable a low level of communication throughput, since otherwise those machines will be severly handicapped as general purpose parallel machines. Although we do not rule that out, we cannot offer any encouraging evidence to suggest that such new methodologies are likely to be found.
Approximate Planning in Large POMDPs via Reusable Trajectories

We consider the problem of reliably choosing a near-best strategy from a restricted class of strategies II in a partially observable Markov decision process (POMDP). We assume we are given the ability to simulate the POMDP, and study what might be called the sample complexity -- that is, the amount of data one must generate in the POMDP in order to choose a good strategy. We prove upper bounds on the sample complexity showing that, even for infinitely large and arbitrarily complex POMDPs, the amount of data needed can be finite, and depends only linearly on the complexity of the restricted strategy class II, and exponentially on the horizon time. This latter dependence can be eased in a variety of ways, including the application of gradient and local search algorithms. Our measure of complexity generalizes the classical supervised learning notion of VC dimension to the settings of reinforcement learning and planning.
Boosting with Multi-Way Branching in Decision Trees

It is known that decision tree learning can be viewed as a form of boosting. However, existing boosting theorems for decision tree learning allow only binary-branching trees and the generalization to multi-branching trees is not immediate. Practical decision tree algorithms, such as CART and C4.5, implement a trade-off between the number of branches and the improvement in tree quality as measured by an index function. Here we give a boosting justification for a particular quantitative trade-off curve. Our main theorem states, in essence, that if we require an improvement proportional to the log of the number of branches then top-down greedy construction of decision trees remains an effective boosting algorithm.
Bandwidth Allocation with Preemption

Bandwidth allocation is a fundamental problem in the design of networks where bandwidth has to be reserved for connections in advance. The problem is intensified when the overall requested bandwidth exceeds the capacity and not all requests can be served. Furthermore, acceptance/rejection decisions regarding connections have to be made online, without knowledge of future requests. We show that the ability to preempt (i.e., abort) connections while in service in order to schedule "more valuable" connections substantially improves the throughput of some networks. We present bandwidth allocation strategies that use preemption and show that they achieve constant competitiveness with respect to the throughput, given that any single call requests at most a constant fraction of the bandwidth. Our results should be contrasted with recent works showing that nonpreemptive strategies have at most inverse logarithmic competitiveness.
On the Boosting Ability of Top-Down Decision Tree Learning Algorithms

We analyze the performance of top?down algorithms for decision tree learning, such as those employed by the widely used C4.5 and CART software packages. Our main result is a proof that such algorithms areboostingalgorithms. By this we mean that if the functions that label the internal nodes of the decision tree can weakly approximate the unknown target function, then the top?down algorithms we study will amplify this weaks advantage to build a tree achieving any desired level of accuracy. The bounds we obtain for this amplification show an interesting dependence on thesplitting criterionused by the top?down algorithm. More precisely, if the functions used to label the internal nodes have error 1/2??as approximations to the target function, then for the splitting criteria used by CART and C4.5, trees of size (1/?)O(1/?2?2)and (1/?)O(log(1/?)/?2)(respectively) suffice to drive the error below?. Thus (for example), a small constant advantage over random guessing is amplified to any larger constant advantage with trees of constant size. For a new splitting criterion suggested by our analysis, the much stronger bound of (1/?)O(1/?2)which is polynomial in 1/?) is obtained, which is provably optimal for decision tree algorithms. The differing bounds have a natured explanation in terms of concavity properties of the splitting criterion. The primary contribution of this work is in proving that some popular and empirically successful heuristics that are base on first principles meet the criteria of an independently motivated theoretical model.
Empirical evaluation of interest-level criteria

Efficient association rule mining algorithms already exist, however, as the size of databases increases, the number of patterns mined by the algorithms increases to such an extent that their manual evaluation becomes impractical. Automatic evaluation methods are, therefore, required in order to sift through the initial list of rules, which the datamining algorithm outputs. These evaluation methods, or criteria, rank the association rules mined from the dataset. We empirically examined several such statistical criteria: new criteria, as well as previously known ones. The empirical evaluation was conducted using several databases, including a large real-life dataset, acquired from an order-by-phone grocery store, a dataset composed from www proxy logs, and several datasets from the UCI repository. We were interested in discovering whether the ranking performed by the various criteria is similar or easily distinguishable. Our evaluation detected, when significant differences exist, three patterns of behavior in the eight criteria we examined. There is an obvious dilemma in determining how many association rules to choose (in accordance with support and confidence parameters). The tradeoff is between having stringent parameters and, therefore, few rules, or lenient parameters and, thus, a multitude of rules. In many cases, our empirical evaluation revealed that most of the rules found by the comparably strict parameters ranked highly according to the interestingness criteria, when using lax parameters (producing significantly more association rules). Finally, we discuss the association rules that ranked highest, explain why these results are sound, and how they direct future research.
Reinforcement learning and mistake bounded algorithms

Markov Decision Process (MDP) and Partially Observable MDP (POMDP) have become the model of choice in reinforcement learning. This work explores an interesting connection between mistake bounded learning algorithms and computing a near-best strategy, from a restricted class of strategies, for a given POMDP. We show that if a class of strategies has a mistake bound algorithm that makes at most d mistakes, then there is an algorithm to compute a near-best strategy from the class in time polynomial in l/c, the accuracy parameter, log(1/6), the confidence parameter, H, the horizon parameter, and exponential in d, the mistake bound. Our transformation assumes only the ability to execute actions in the POMDP and the ability to reset the POMDP to its initial state.
On diffusing updates in a Byzantine environment

We study how to efficiently diffuse updates to a large distributed system of data replicas, some of which may exhibit arbitrary (Byzantine) failures. We assume that strictly fewer than t replicas fail, and that each update is initially received by at least t correct replicas. The goal is to diffuse each update to all correct replicas while ensuring that correct replicas accept no updates generated spuriously by faulty replicas. To achieve reliable diffusion, each correct replica accepts an update only after receiving it from at least t others. We provide the first analysis of epidemic-style protocols for such environments. This analysis is fundamentally different from known analyses for the benign case due to our treatment of fully Byzantine failure-which, among other things, precludes the use of digital signatures for authenticating forwarded updates. We propose two epidemic-style diffusion algorithms and two measures that characterize the efficiency of diffusion algorithms in general. We characterize both of our algorithms according to these measures, and also prove lower bounds with regards to these measures that show that our algorithms are close to optimal.
Exact Inference of Hidden Structure from Sample Data in noisy-OR Networks

In the literature on graphical models, there has been increased attention paid to the problems of learning hidden structure (see Heckerman [H96] for survey) and causal mechanisms from sample data [H96, P88, S93, P95, F98]. In most settings we should expect the former to be difficult, and the latter potentially impossible without experimental intervention. In this work, we examine some restricted settings in which perfectly reconstruct the hidden structure solely on the basis of observed sample data.
Jitter control in QoS networks

We study jitter control in networks guaranteeing quality of service (QoS). Jitter measures variability of delivery times in packet streams. We propose on-line algorithms that control jitter and compare their performance to the best possible (by an off-line algorithm) for any given arrival sequence. For delay jitter, where the goal is to minimize the difference between delay times of different packets, we give an on-line algorithm using buffer size of 2B which guarantees the same delay-jitter as an off-line algorithm using buffer space B. We show that 2B space is the minimum space required by any on-line algorithm to provide delay-jitter related to the best possible delay-jitter using B buffer space. We also show that the guarantees made by our online algorithm hold even for distributed implementations, where the total buffer space is distributed along the path of the connection, provided that the input stream satisfies a certain simple property. For rate jitter, where the goal is to minimize the difference between inter-arrival times, we develop an on-line algorithm using a buffer of size 2B+h for any h/spl ges/1, and compare its jitter to the jitter of an optimal off-line algorithm using buffer size B. Our algorithm guarantees that the difference is bounded by a term proportional to B/h. We also prove that 2B space is necessary for on-line algorithms with non trivial guarantees for rate-jitter control.
Lower Bounds for Randomized Mutual Exclusion

We establish, for the first time, lower bounds for randomized mutual exclusion algorithms (with a read-modify-write operation). Our main result is that a constant-size shared variable cannot guarantee strong fairness, even if randomization is allowed. In fact, we prove a lower bound of $\Omega (\log\log n)$ bits on the size of the shared variable, which is also tight. 
We investigate weaker fairness conditions and derive tight (upper and lower) bounds for them as well. Surprisingly, it turns out that slightly weakening the fairness condition results in an exponential reduction in the size of the required shared variable. Our lower bounds rely on an analysis of Markov chains that may be of interest on its own and may have applications elsewhere.
A Fast, Bottom-Up Decision Tree Pruning Algorithm with Near-Optimal Generalization

In this work, we present a new bottom-up algorithm for decision tree pruning that is very e cient (requiring only a single pass through the given tree), and prove a strong performance guarantee for the generalization error of the resulting pruned tree. We work in the typical setting in which the given tree T may have been derived from the given training sample S, and thus may badly over t S. In this setting, we give bounds on the amount of additional generalization error that our pruning su ers compared to the optimal pruning of T . More generally, our results show that if there is a pruning of T with small error, and whose size is small compared to jSj, then our algorithm will nd a pruning whose error is not much larger. This style of result has been called an index of resolvability result by Barron and Cover in the context of density estimation. A novel feature of our algorithm is its locality | the decision to prune a subtree is based entirely on properties of that subtree and the sample reaching it. To analyze our algorithm, we develop tools of local uniform convergence, a generalization of the standard notion that may prove useful in other settings.
Competitive dynamic bandwidth allocation

We propose a realistic theoretical model for dynamic bandwidth allocation. Our model takes into account the two classical quality of service parameters: latency and utilization, together with a newly introduced parameter: number of bandwidth allocation changes,which am costly operations in today’s networks. Our model assumes that sessions join the network with a certain delay requirement ratherthan a bandwidth requirement as assumed in previous models. In addition, the network has a certain utilization requirement. Given bounds on latency and utilization, we design online algorithms that minimize the number of bandwidth allocation changes.
An Omega(D log (N/D)) Lower Bound for Broadcast in Radio Networks

We show that for any randomized broadcast protocol for radio networks, there exists a network in which the expected time to broadcast a message is $\Omega(D\log (N/D))$, where D is the diameter of the network and N is the number of nodes. This implies a tight lower bound of $\Omega(D\log N)$ for any $D \le N^{1-\varepsilon}$, where $\varepsilon > 0$ is any constant.
On construction ofk-wise independent random variables

AbstractA 0–1probability space is a probability space (Ω, 2Ω,P), where the sample space Ω⊂-{0, 1}n for somen. A probability space isk-wise independent if, whenYi is defined to be theith coordinate or the randomn-vector, then any subset ofk of theYi's is (mutually) independent, and it is said to be a probability spacefor p1,p2, ...,pn ifP[Yi=1]=pi.We study constructions ofk-wise independent 0–1 probability spaces in which thepi's are arbitrary. It was known that for anyp1,p2, ...,pn, ak-wise independent probability space of size
$$m(n,k) = \left( {\begin{array}{*{20}c} n \\ k \\ \end{array} } \right) + \left( {\begin{array}{*{20}c} n \\ {k - 1} \\ \end{array} } \right) + \left( {\begin{array}{*{20}c} n \\ {k - 2} \\ \end{array} } \right) + ... + \left( {\begin{array}{*{20}c} n \\ 0 \\ \end{array} } \right)$$
 always exists. We prove that for somep1,p2, ...,pn ∈ [0,1],m(n,k) is a lower bound on the size of anyk-wise independent 0–1 probability space. For each fixedk, we prove that everyk-wise independent 0–1 probability space when eachpi=k/n has size Ω(nk). For a very large degree of independence —k=[αn], for α>1/2- and allpi=1/2, we prove a lower bound on the size of
$$2^n \left( {1 - \frac{1}{{2\alpha }}} \right)$$
. We also give explicit constructions ofk-wise independent 0–1 probability spaces.
Slide-The Key to Polynomial End-to-End Communication

We consider the basic task of ofend-to-end communicationin dynamic networks, that is, delivery in finite time of data items generated on-line by a sender, to a receiver, in order and without duplication or omission.A dynamic communication network is one in which links may repeatedly fail and recover. In such a network, though it is impossible to establish a communication path consisting of nonfailed links, reliable communication is possible, if there is no cut of permanently failed links between a sender and receiver.This paper presents the first polynomial complexity end-to-end communication protocol in dynamic networks. In the worst case the protocol sendsO(n2m) messages per data item delivered, wherenandmare the number of processors and number of links in the network respectively. The centerpiece of our solution is the novelslideprotocol, a simple and efficient method for delivering tokens across an unreliable network.Slideis the basis for several self-stabilizing protocols and load-balancing algorithms for dynamic networks that have subsequently appeared in the literature.We use our end-to-end protocol to derive a file-transfer protocol for sufficiently large files. The bit communication complexity of this protocol isO(nD) bits, whereDis the size in bits of the file. This file-transfer protocol yields anO(n)amortizedmessage complexity end-to-end protocol.