nils-herrmann/clean_scirepeval huggingface dataset:
Randomness in Private Computations

We consider the amount of randomness used in private distributed computations. Specifically, we show how n players can compute the exclusive-or (xor) of n boolean inputs t-privately, using only O(t2 log (n/t)) random bits (the best known upper bound is O(tn)). We accompany this result by a lower bound on the number of random bits required to carry out this task; we show that any protocol solving this problem requires at least t random bits (again, this significantly improves over the known lower bounds). 
For the upper bound, we show how, given m subsets of {1,...,n}, to construct in (deterministic) polynomial time a probability distribution of n random variables (i.e., a probability distribution over {0,1}n) such that (1) the parity of random variables in each of these m subsets is 0 or 1 with equal probability, and (2) the support of the distribution is of size at most 2m. This construction generalizes previously considered types of sample spaces (such as k-wise independent spaces and Schulman's spaces [Sample spaces uniform on neighborhoods, in Proc. of the 24th Annual ACM Symposium on Theory of Computing, ACM, New York, 1992, pp. 17--25]). We believe that this construction is of independent interest and may have various applications.
Virtual-credit: Efficient end-to-end credit based flow control

A new ow control scheme, called virtual credit that may be considered either as a credit based ow-control algorithm without a queue per session at the ports, or as a way to modify the credit based scheme and to bring it closer to an end-to-end rate based scheme, is presented. The new scheme brings the credit based and rate based ow-control schemes closer to each other, giving an attractive compromise between the two schemes. The new scheme enjoys the main advantages of the credit based ow-control scheme while not requiring a queue per session at the switches. A possible disadvantage of the scheme is the large buuer requirement at the switches to ensure very low cell loss rate (but no more than the corresponding buuer requirements in rate based schemes).
Learning with Maximum-Entropy Distributions

We are interested in distributions which are derived as a maximum entropy distribution from a given set of constraints. More specifically, we are interested in the case where the constraints are the expectation of individual and pairs of attributes. For such a given maximum entropy distribution (with some technical restrictions) we develop an efficient learning algorithm for read-once DNF. We extend our results to monotone read-k DNF following the techniques of (Hancock & Mansour, 1991).
Pessimistic Decision Tree Pruning Based on Tree Size

In this work we develop a new criteria to perform pessimistic decision tree pruning. Our method is theoretically sound and is based on theoretical concepts such as uniform convergence and the Vapnik-Chervonenkis dimension. We show that our criteria is very well motivated, from the theory side, and performs very well in practice. The accuracy of the new criteria is comparable to that of the current method used in C4.5.
An Information-Theoretic Analysis of Hard and Soft Assignment Methods for Clustering

Assignment methods are at the heart of many algorithms for unsupervised learning and clustering -- in particular, the well-known K-means and Expectation-Maximizatian (EM) algorithms. In this work, we study several different methods of assignment, including the "hard" assignments used by K-means and the "soft" assignments used by EM. While it is known that K-means minimizes the distortion on the data and EM maximizes the likelihood, little is known about the systematic differences of behavior between the two algorithms. Here we shed light on these differences via an information-theoretic analysis. The cornerstone of our results is a simple decomposition of the expected distortion, showing that K-means (and its extension for inferring general parametric densities from unlabeled sample data) must implicitly manage a trade-off between how similar the data assigned to each cluster are, and how the data are balanced among the clusters. How well the data are balanced is measured by the entropy of the partition defined by the hard assignments. In addition to letting us predict and verify systematic differences between K-means and EM on specific examples, the decomposition allows us to give a rather general argument showing that K-means will consistently find densities with less "overlap" than EM. We also study a third natural assignment method that we call posterior assignment, that is close in spirit to the soft assignments of EM, but leads to a surprisingly different algorithm.
Space Eecient Fair Queuing by Stochastic Memory Multiplexing

We propose a new scheme for multiplexing buuer space between ows contending for the same output port. In our scheme messages of the diierent ows are serviced in either Round-Robin or almost Round-Robin order, thus supporting fair queuing. Our scheme is both simple for hardware implementation and achieves high buuer space utilization (by taking advantage of statistical multiplexing between the ows). Therefore our scheme enjoys from both the simplicity of the hardware queue per ow scheme and the space eeciency of the linked-list based dynamic scheme, suggesting an attractive compromise between the two extremes.
Efficient On-Line Call Control Algorithms

In this paper we study the problem of on-linecall controlin a communication network, namely, the problem of accepting or rejecting an incoming call (a request for a connection between two points in a network) without having the knowledge of future calls. The problem is a part of the more general problem of bandwidth allocation and management. Intuition suggests that knowledge of future call arrivals can be crucial to the performance of the system. In this paper, however, we present preemptive deterministic on-line call control algorithms. We use competitive analysis to measure their performance?i.e., we compare our algorithms to their off-line, clairvoyant counterparts?and prove optimality for some of them. We consider two specific networks, a line of nodes and a single edge, and investigate a variety of cases concerning thevalueof the calls. The value is accrued only if the call terminates successfully; otherwise?if the call is rejected, or prematurely terminated?no value is gained. The performance of the algorithm is then measured by the cumulative value achieved, when given a sequence of calls. The variety of call value criteria that we study?constant; proportional to the length of the call's route; proportional to its holding time?captures many of the natural cost assignments to network services.
Learning Under Persistent Drift

In this paper we study learning algorithms for environments which are changing over time. Unlike most previous work, we are interested in the case where the changes might be rapid but their “direction” is relatively constant. We model this type of change by assuming that the target distribution is changing continuously at a constant rate from one extreme distribution to another. We show in this case how to use a simple weighting scheme to estimate the error of an hypothesis, and using this estimate, to minimize the error of the prediction.
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 are boosting algorithms. 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 weak advantage to build a tree achieving any desired level of accuracy. The bounds we obtain for this amplification show an interesting dependence on the splitting criterion used 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), small constant advantage over random guessing is amplified to constant error 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. The differing bounds have a natural 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 based on first principles meet the criteria of an independently motivated theoretical model.
Proof: Let N =

Lemma 4 plays a central role in our analysis. It gives a bound on the number of terms which are almost satissed by an assignment a, in terms of k and j. It is natural to ask how good is this bound. The following example, due to Galia Givaty (private communication), shows that it is essentially optimal (up to constants). More precisely, for any values of k and j we give a function F k;j with k j variables x 0 ; x 2 ; : : :; x kj?1 , and an assignment a such that jY (a)j = k j. The function F k;j has kj terms: t i = x i x i+1 : : :x i+k?1modkj (0 i kj ? 1) It can be easily veriied that the function is Read-k (the variable x i appears only in the terms t i?k+1modkj ; : : :; t i). It is also Satisfy-j as if an assignment satisses a term t i it cannot satisfy any of the k ? 1 terms t i?k+1modkj ; : : :; t i?1modkj (as they all contain the variable x i while t i contains x i). Now, let a be the all \1" assignment. Each term t i is almost satissed by a with respect to index i. Hence, jY (a)j = kj. 23 Bsh95] N. H. Bshouty. Exact learning boolean functions via the monotone theory. Jac94] J. Jackson. An eecient membership-query algorithm for learning DNF with respect to the uniform distribution. 22 Ang87] D. Angluin. Learning k-term DNF formulas using queries and counterexamples. learning DNF and characterizing statistical query learning using fourier analysis. 21 representation, so there is still a term t C that can be satissed. Therefore, we can deene a to be the assignment in which all the literals in C are set to zero, all the literals in t C are set to one, and all other literals are set arbitrarily. We thus have that C(a) = 0 but t C (a) = 1 (and hence F n (a) = 1), a contradiction. 7 Bibliographic Remarks The work presented here appeared in preliminary forms as AP92] and BKK + 94]. The algorithm for constant k and j is from AP92] and the extension to kj = O(log n= log log n) from BKK + 94]. The family of functions given in Section 6 was deened …
Phantom: a simple and effective flow control scheme

This paper presents Phantom, a simple constant space algorithm for rate based flow control. As shown by our simulations, it converges fast to a fair rate allocation while generating a moderate queue length. While our approach can be easily implemented in ATM switches for managing ABR traffic, it is also suitable for flow control in TCP router based networks. Both the introduced overhead and the required modifications in TCP flow control systems are minimal. The implementation of this approach in TCP guarantees fairness and provides a unifying interconnection between TCP routers and ATM networks. The new algorithm easily inter-operates with current TCP flow control mechanisms and thus can be gradually introduced into installed based TCP networks.
Phantom: A Simple and Effective Flow Control Scheme

This paper presents Phantom, a simple constant space algorithm for rate based flow control. As shown by our simulations, it converges fast to a fair rate allocation while generating a moderate queue length. While our approach can be easily implemented in ATM switches for managing ABR traffic, it is also suitable for flow control in TCP router based networks. Both the introduced overhead and the required modifications in TCP flow control systems are minimal. The implementation of this approach in TCP guarantees fairness and provides a unifying interconnection between TCP routers and ATM networks. The new algorithm easily inter-operates with current TCP flow control mechanisms and thus can be gradually introduced into installed based TCP networks.
Randomness in private computations

We consider the amount of randomness used in private distributed computations. Specifically, we show how n players can compute the exclusive-or (xor) of n boolean inputs t-privately, using only O(t2 log(n/t)) random bits (the best known upper bound is O(tn)). We accompany this result by a lower bound on the number of random bits required to carry out this task; we show that any protocol solving this problem requires at least t random bits (again, this significantly improves over the known lower bounds). For the upper bound, we show how, given m subsets of {1, . . . , n}, to construct in (deterministic) polynomial time a probability distribution of n random variables (i.e., a probability distribution over {0, 1}n) such that (1) the parity of random variables in each of these m subsets is 0 or 1 with equal probability, and (2) the support of the distribution is of size at most 2m. This construction generalizes previously considered types of sample spaces (such as k-wise independent spaces and Schulman’s spaces [Sample spaces uniform on neighborhoods, in Proc. of the 24th Annual ACM Symposium on Theory of Computing, ACM, New York, 1992, ). We believe that this construction is of independent interest and may have various applications.
Dynamic bandwidth allocation policies

When traffic of connectionless best effort protocols such as IP is carried over connection oriented protocols with guaranteed bandwidth, such as CBR connection in ATM, the interface layer between the protocols (i.e., AAL-the ATM adaption layer) needs to specify the bandwidth requirement and the duration of the bandwidth reservation. The purpose of this paper is to develop policies for deciding and for adjusting the amount of bandwidth requested for a best effort connection over such networks. Our aim is to develop such policies that achieve a good trade off between latency and utilization. The performances of the different policies are compared by an empirical evaluation.
Convergence complexity of optimistic rate based flow control algorithms (brief announcement)

This paper studies basic properties of rate based flowcontrol algorithms and the max-min fairness criteria. We suggest a new approach for modeling and analysis of such algorithms, which may be considered more “optimistic” and realistic than traditional approaches. For the max-min fairness criteria we show that under certain circumstances it may be very sensitive to small changes in the flows. Furthermore, we show that it may be hard to locally estimate in a given state how close a session is to its max-min fair allocation. Our abstraction separates the flow control algorithm into two parts. The scheduler, that in each state selects the next session to be considered for an increase, and the update rule by which the algorithm decides whether to perform the update or not. The convergence cornpleml~ of each algorithm is the total number of update operations applied until the algorithm quiesces. Three different schedulers are considered, depending on the selection in each state, of the next session to be improved: (1) global rnin scheduler that selects the globally smallest rate session that could still be improved. (2) Joccd min scheduler that selects any session whose rate may be improved, and which is smaller than all the sessions it shares an edge with. (3) arbitrary scheduler that selects an arbitrarily session. Note that the local min is more appropriate for a distributed environment than the global rein, and the arbitrary gives the highest degree of flexibility. Two variants are considered for the update decision: (1) a selected session rate is increased as long as it may be increased, and (2) approximate algorithms, in which the rate of a session is increased only if the increase is by more than 6. The approximate algorithms reach quiescence when no session may be increased by more than 6. The main results presented in this paper are:
Applying the Waek Learning Framework to Understand and Improve C4.5

There has long been a chasm between theoretical models of machine learning and practical machine learning algorithms. For instance, empirically successful algorithms such as C4:5 and backpropagation have not met the criteria of the PAC model and its variants. Conversely, the algorithms suggested by computational learning theory are usually too limited in various ways to nd wide application. The theoretical status of decision tree learning algorithms is a case in point: while it has been proven that C4:5 (and all reasonable variants of it) fails to meet the PAC model criteria , other recently proposed decision tree algorithms that do have non-trivial performance guarantees unfortunately require membership queries [6, 13]. Two recent developments have narrowed this gap between theory and practice|not for the PAC model, but for the related model known as weak learning or boosting . First, an algorithm called Adaboost was proposed that meets the formal criteria of the boosting model and is also competitive in practice [10]. Second, the basic algorithms underlying the popular C4:5 and CART programs have also very recently been shown to meet the formal criteria of the boosting model . Thus, it seems plausible that the weak learning framework may provide a setting for interaction between formal analysis and machine learning practice that is lacking in other theoretical models. Our aim in this paper is to push this interaction further in light of these recent developments. In particular, we perform experiments suggested by the formal results for Adaboost and C4:5 within the weak learning framework. We concentrate on two particularly intriguing issues. First, the theoretical boosting results for top-down decision tree algorithms such as C4:5 [12] suggest that a new splitting criterion may result in trees that are smaller and more accurate than those obtained using the usual information gain. We con rm this suggestion experimentally. Second, a super cial interpretation of the theoretical results suggests that Adaboost should vastly outperform C4:5. This is not the case in practice, and we argue through experimental results that the theory must be understood in terms of a measure of a boosting algorithm's behavior called its advantage sequence. We compare the advantage sequences for C4:5 and Adaboost in a number of experiments. We nd that these sequences have qualitatively different behavior that explains in large part the discrepancies between empirical performance and the theoretical results. Brie y, we nd that although C4:5 and Adaboost are both boosting algorithms, Adaboost creates successively \harder" ltered distributions, while C4:5 creates successively \easier" ones, in a sense that will be made precise.
Convergence complexity of optimistic rate based flow control algorithms (extended abstract)

This paper studies basic properties of rate based flowcontrol algorithms and of the max-min fairness criteria. For the algorithms we suggest a new approach for their mod cling 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 an 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 than the tlows according to 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 8 may change the allocation of another session by Cl(c$ .2 ~ ), but by no more than 0(6 . 2W). This implies that it might be hard to locally estimate in a given state how close a session is to its max-min fair allocation.
Competitive Access Time via Dynamic Storage Rearrangement (Preliminary Version).

Medallion-like articles for jewelry, decorative ornamentation and product identification, instrument panel light lenses and methods and apparatus for manufacturing same are disclosed. A medallion-like article for decorative or identification is formed by applying an uncured radiation curable polymer to an indicia bearing surface in a quantity sufficient to form a convex upper surface by means of its surface tension and then irradiating the polymer to effect its cure. Use of a flexible substrate, such as a vinyl or polyester film, upon which embossed indicia was formed, provides a flexible medallion which may be adhesively bonded to a contoured, non-planar surface. Upward curling of the medallion during cure is prevented by supporting the medallion on a water cooled platen during irradiation. A flexible, transparent lamp lense having a convex frontal surface is also formed by the ultraviolet cured photopolymer which is adhesively bonded adjacent to the lamp to form its lense.
Simple learning algorithms for decision trees and multivariate polynomials

In this paper we develop a new approach for learning decision trees and multivariate polynomials via interpolation of multivariate polynomials. This new approach yields simple learning algorithms for multivariate polynomials and decision trees over finite fields under any constant bounded product distribution. The output hypothesis is a (single) multivariate polynomial that is an /spl epsiv/-approximation of the target under any constant bounded product distribution. The new approach demonstrates the learnability of many classes under any constant bounded product distribution and using membership queries, such as j-disjoint DNF and multivariate polynomial with bounded degree over any field. The technique shows how to interpolate multivariate polynomials with bounded term size from membership queries only. This in particular gives a learning algorithm for O(log n)-depth decision tree from membership queries only and a new learning algorithm of any multivariate polynomial over sufficiently large fields from membership queries only. We show that our results for learning from membership queries only are the best possible.
Optimal universal learning and prediction of probabilistic concepts

We consider the following setting of the (supervised) learning problem. A sequence of input data x/sub 1/,...,x/sub t/,..., is given, one by one, and the goal is to predict the corresponding outputs y/sub 1/,...,y/sub t/,.... Our proposed solution for the supervised learning problem is Bayesian, and the contribution of this work lies in determining the optimal way to choose the Bayesian "prior" for the supervised learning problem, and observing the strong sequential, non-anticipating, structure of the resulting universal predictor.
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 requested bandwidth exceeds the capacity and not all requests can be served. Furthermore, acceptance/rejection decisions regarding connections have to be made on-line, without knowledge of future requests. We show that the ability to preempt (i.e., abort) connections while in service in order to be able to schedule ``more valuable'''' connections substantially improves the overall throughput of some networks. We present bandwidth allocation strategies that use preemption and show that they achieve constant competiveness with respect to the throughput, given that any single call occupies only a constant fraction of the bandwidth. Our results should be contrasted with recent works showing that nonpreemptive strategies have at most logarithmic competitiveness.