Speed Scaling of Processes with Arbitrary Speedup Curves on a Multiprocessor

We consider the setting of a multiprocessor where the speeds of the m processors can be individually scaled. Jobs arrive over time and have varying degrees of parallelizability. A nonclairvoyant scheduler must assign the processes to processors, and scale the speeds of the processors. We consider the objective of energy plus flow time. We assume that a processor running at speed s uses power s ^α for some constant α>1. For processes that may have side effects or that are not checkpointable, we show an W(m^(a-1)/a2)\Omega(m^{(\alpha -1)/\alpha^{2}}) bound on the competitive ratio of any randomized algorithm. For checkpointable processes without side effects, we give an O(log m)-competitive algorithm. Thus for processes that may have side effects or that are not checkpointable, the achievable competitive ratio grows quickly with the number of processors, but for checkpointable processes without side effects, the achievable competitive ratio grows slowly with the number of processors. We then show a lower bound of Ω(log ^1/α m) on the competitive ratio of any randomized algorithm for checkpointable processes without side effects.     

Efficient Reorganization of Binary Search Trees

We consider the problem of maintaining a binary search tree ({bst}) that minimizes the average access cost needed to satisfy randomly generated requests. We analyze scenarios in which the accesses are generated according to a vector of fixed probabilities which is unknown . Our approach is statistical. We devise policies for modifying the tree structure dynamically, using rotations of accessed records. The aim is to produce good approximations of the optimal structure of the tree, while keeping the number of rotations as small as possible. The heuristics that we propose achieve a close approximation to the optimal BST, with lower organization costs than any previously studied. We introduce the MOVE_ONCE rule. The average access cost to the tree under this rule is shown to equal the value achieved by the common rule Move to the Root (MTR). The advantage of MOVE_ONCE over MTR and similar rules is that it relocates each of the items in the tree at most once. We show that the total expected cost of modifying the tree by the MOVE_ONCE rule is bounded from above by 2(n+1)H _n -4n rotations (in a tree with n records), where H _n is the n th harmonic number. Extensive experiments show that this value is an overestimate, and in fact the number of rotations is linear for all the access probability vectors we tested. An approximate analysis is shown to match the experimental results, producing the expected number n((π ² /3)-2) - 2\ln n+0.1354 . Next we combine the MOVE_ONCE rule with reference counters, one per record, that provide estimates of the reference probabilities. We call the resulting reorganization rule MOUCS. We show that, for any δ , α >0 and sufficiently large n , it achieves a cost that approaches the optimum up to an absolute difference of δ with probability higher than 1- α , within a number of accesses that is proportional to n (\lg n) ² /(αδ ² ) . Received March 10, 2001; revised March 26, 2001.     

Competitive Call Control in Mobile Networks

Abstract. In this paper we deal with competitive local on-line algorithms for non-preemptive channel allocation in mobile networks. The signal interferences in a network are modeled using an interference graph G . We prove that the greedy on-line algorithm is Δ -competitive, where Δ is the maximum degree of G . We employ the ``classify and randomly select" paradigm [5], [17], and give a 5 -competitive randomized algorithm for the case of planar interference graphs, a 2 -competitive randomized algorithm for trees, and a (2c) -competitive randomized algorithm for graphs of arboricity c . We also show that the problem of call control in mobile networks with multiple available frequencies reduces to the problem of call control in mobile networks with a single frequency. Using this reduction, we present on-line algorithms for general networks with a single frequency. We give a local on-line algorithm which is (α (δ +1 + α )/(1/2+α ) ² )-competitive, where α is the independence number of G , and δ is the average degree of G . The above results hold in the case when the duration of each request is infinite, and the benefit the algorithm gains by accepting each request is equal to one. They are extended to handle requests of arbitrary durations, and arbitrary benefits.     

Learning noisy linear classifiers via adaptive and selective sampling

We introduce efficient margin-based algorithms for selective sampling and filtering in binary classification tasks. Experiments on real-world textual data reveal that our algorithms perform significantly better than popular and similarly efficient competitors. Using the so-called Mammen-Tsybakov low noise condition to parametrize the instance distribution, and assuming linear label noise, we show bounds on the convergence rate to the Bayes risk of a weaker adaptive variant of our selective sampler. Our analysis reveals that, excluding logarithmic factors, the average risk of this adaptive sampler converges to the Bayes risk at rate N ^{−(1+α)(2+α)/2(3+α)} where N denotes the number of queried labels, and α>0 is the exponent in the low noise condition. For all $\alpha>\sqrt{3}-1\approx0.73$\alpha>\sqrt{3}-1\approx0.73 this convergence rate is asymptotically faster than the rate N ^{−(1+α)/(2+α)} achieved by the fully supervised version of the base selective sampler, which queries all labels. Moreover, for α→∞ (hard margin condition) the gap between the semi- and fully-supervised rates becomes exponential.     

Approximation of functions by means of a new generalized Bernstein operator

In this paper we first use a probabilistic method to construct a linear positive polynomial operatorL _{m, r} ^α,β Bernstein type, depending on a non-negative integer parameterr and on two real parameters α and β, such that 0≤α≤β. Then we investigate the approximation properties of this operator mapping into itself the Banach spaceC[0,1] of real-valued continuous functions on [0,1]. A special attention is accorded to the case of the operatorL _m,r=L _m,r ^0,0 . We prove that the remainder of the approximation formula of a functionfεC[0,1] byL _m,r f can be represented either by means of divided differences, or in an integral form, obtained by using a classical theorem of Peano. We give also an asymptotic estimate for this remainder. The operatorL _m,r enjoys the variation diminishing property—in the sense of I. J. Schoenberg [15]. By extending the known inequalities of T. Popoviciu [12] and G. G. Lorentz [7], we evaluate the orders of approximation in terms of the modulus of continuity of the functionf or of its derivative. In the last section of this paper we determine the point spectrum of the operatorL _m,r and , finally, we present a quadrature formula which can be constructed by means of this operator. Dedicated to Professor Aldo Ghizzetti on his 75th birthday     

Average Rate Speed Scaling

Speed scaling is a power management technique that involves dynamically changing the speed of a processor. This gives rise to dual-objective scheduling problems, where the operating system both wants to conserve energy and optimize some Quality of Service (QoS) measure of the resulting schedule. Yao, Demers, and Shenker (Proc. IEEE Symp. Foundations of Computer Science, pp. 374–382, 1995) considered the problem where the QoS constraint is deadline feasibility and the objective is to minimize the energy used. They proposed an online speed scaling algorithm Average Rate (AVR) that runs each job at a constant speed between its release and its deadline. They showed that the competitive ratio of AVR is at most (2α) ^α /2 if a processor running at speed s uses power s ^α . We show the competitive ratio of AVR is at least ((2−δ)α) ^α /2, where δ is a function of α that approaches zero as α approaches infinity. This shows that the competitive analysis of AVR by Yao, Demers, and Shenker is essentially tight, at least for large α. We also give an alternative proof that the competitive ratio of AVR is at most (2α) ^α /2 using a potential function argument. We believe that this analysis is significantly simpler and more elementary than the original analysis of AVR in Yao et al. (Proc. IEEE Symp. Foundations of Computer Science, pp. 374–382, 1995).     

Graph Complexity and Slice Functions

   Abstract. A graph-theoretic approach to study the complexity of Boolean functions was initiated by Pudlák, R?dl, and Savicky [PRS] by defining models of computation on graphs. These models generalize well-known models of Boolean complexity such as circuits, branching programs, and two-party communication complexity. A Boolean function f is called a 2-slice function if it evaluates to zero on inputs with less than two 1's and evaluates to one on inputs with more than two 1's. On inputs with exactly two 1's f may be nontrivially defined. There is a natural correspondence between 2-slice functions and graphs. Using the framework of graph complexity, we show that sufficiently strong superlinear monotone lower bounds for the very special class of {2-slice functions} would imply superpolynomial lower bounds over a complete basis for certain functions derived from them. We prove, for instance, that a lower bound of n ^1+Ω(1) on the (monotone) formula size of an explicit 2-slice function f on n variables would imply a 2 ^Ω(ℓ) lower bound on the formula size over a complete basis of another explicit function g on l variables, where l=Θ( log n) . We also consider lower bound questions for depth-3 bipartite graph complexity. We prove a weak lower bound on this measure using algebraic methods. For instance, our result gives a lower bound of Ω(( log n) ³ / ( log log n) ⁵ ) for bipartite graphs arising from Hadamard matrices, such as the Paley-type bipartite graphs. Lower bounds for depth-3 bipartite graph complexity are motivated by two significant applications: (i) a lower bound of n ^Ω(1) on the depth-3 complexity of an explicit n -vertex bipartite graph would yield superlinear size lower bounds on log-depth Boolean circuits for an explicit function, and (ii) a lower bound of

Time-Space Tradeoff in Derandomizing Probabilistic Logspace

Nisan showed that any randomized logarithmic space algorithm (running in polynomial time and with two-sided error) can be simulated by a deterministic algorithm that runs simultaneously in polynomial time and Θ(log² n) space. Subsequently Saks and Zhou improved the space complexity and showed that a deterministic simulation can be carried out in space Θ(log^1.5n). However, their simulation runs in time n^{Θ(log^{0.5}n)}. We prove a time--space tradeoff that interpolates these two simulations. Specifically, we prove that, for any 0 ≤ α ≤ 0.5, any randomized logarithmic space algorithm (running in polynomial time and with two-sided error) can be simulated deterministically in time n^{O(log^{0.5-α}n)} and space O(log^{1.5+α}n). That is, we prove that BPL ⊆ DTISP[n^{O(log^{0.5-α}n)}, O(log^1.5+αn)].     

Improved Routing and Sorting on Multibutterflies

This paper shows that an N -node AKS network (as described by Paterson) can be embedded in a ( 3N / 2 ) -node twinbutterfly network (i.e., a multibutterfly constructed by superimposing two butterfly networks) with load 1, congestion 1, and dilation 2. The result has several implications, including the first deterministic algorithms for sorting and finding the median of n log n items on an n -input multibutterfly in O ( log n ) time, a work-efficient deterministic algorithm for finding the median of n log ² n log log n items on an n -input multibutterfly in O (log n log log n ) time, and a three-dimensional VLSI layout for the n -input AKS network with volume O(n ^3/2 ) . While these algorithms are not practical, they provide further evidence of the robustness of multibutterfly networks. We also present a separate, and more practical, deterministic algorithm for routing h -relations on an n -input multibutterfly in O(h + log n) time. Previously, only algorithms for solving h one-to-one routing problems were known. Finally, we show that a twinbutterfly, whose individual splitters do not exhibit expansion, can emulate a bounded-degree multibutterfly with (α,β) -expansion, for any α⋅β < 1/4 . Received July 23, 1997; revised May 18, 1998.     

Special classes of separable Goppa codes with improved parameter estimates

We show that subclasses of q-ary separable Goppa codes Γ(L, G) with L = {α ∈ GF(q ^2ℓ): G(α) ∈ 0} and with special Goppa polynomials G(x) can be represented as a chain of equivalent and embedded codes. For all codes of the chain we obtain an improved bound for the dimension and find an exact value of the minimum distance. A chain of binary codes is considered as a particular case with specific properties.     

Improved Approximation Results for the Minimum Energy Broadcasting Problem

In this paper we present new results on the performance of the Minimum Spanning Tree heuristic for the Minimum Energy Broadcast Routing (MEBR) problem. We first prove that, for any number of dimensions d≥2, the approximation ratio of the heuristic does not increase when the power attenuation coefficient α, that is the exponent to which the coverage distance must be raised to give the emission power, grows. Moreover, we show that, for any fixed instance, as a limit for α going to infinity, the ratio tends to the lower bound of Clementi et al. (Proceedings of the 18th annual symposium on theoretical aspects of computer science (STACS), pp. 121–131, 2001), Wan et al. (Wirel. Netw. 8(6):607–617, 2002) given by the d-dimensional kissing number, thus closing the existing gap between the upper and the lower bound. We then introduce a new analysis allowing to establish a 7.45-approximation ratio for the 2-dimensional case, thus significantly decreasing the previously known 12 upper bound (Wan et al. in Wirel. Netw. 8(6):607–617, 2002) (actually corrected to 12.15 in Klasing et al. (Proceedings of the 3rd IFIP-TC6 international networking conference, pp. 866–877, 2004)). Finally, we extend our analysis to any number of dimensions d≥2 and any α≥d, obtaining a general approximation ratio of 3 ^d −1, again independent of α. The improvements of the approximation ratios are specifically significant in comparison with the lower bounds given by the kissing numbers, as these grow at least exponentially with respect to d. The research was partially funded by the European project COST Action 293, “Graphs and Algorithms in Communication Networks” (GRAAL). Preliminary version of this paper appeared in Flammini et al. (Proceedings of ACM joint workshop on foundations of mobile computing (DIALM-POMC), pp. 85–91, 2004).     

Nonclairvoyant Speed Scaling for Flow and Energy

We give three results related to online nonclairvoyant speed scaling to minimize total flow time plus energy. We give a nonclairvoyant algorithm LAPS, and show that for every power function of the form P(s)=s ^α , LAPS is O(1)-competitive; more precisely, the competitive ratio is 8 for α=2, 13 for α=3, and \frac2a²lna\frac{2\alpha^{2}}{\ln\alpha} for α>3. We then show that there is no constant c, and no deterministic nonclairvoyant algorithm A, such that A is c-competitive for every power function of the form P(s)=s ^α . So necessarily the achievable competitive ratio increases as the steepness of the power function increases. Finally we show that there is a fixed, very steep, power function for which no nonclairvoyant algorithm can be O(1)-competitive.     

Adiabatic quantum counting by geometric phase estimation

We design an adiabatic quantum algorithm for the counting problem, i.e., approximating the proportion, α, of the marked items in a given database. As the quantum system undergoes a designed cyclic adiabatic evolution, it acquires a Berry phase 2πα. By estimating the Berry phase, we can approximate α, and solve the problem. For an error bound e{\epsilon}, the algorithm can solve the problem with cost of order (\frac1e)^3/2{(\frac{1}{\epsilon})^{3/2}}, which is not as good as the optimal algorithm in the quantum circuit model, but better than the classical random algorithm. Moreover, since the Berry phase is a purely geometric feature, the result may be robust to decoherence and resilient to certain noise.     

Stackelberg Strategies for Selfish Routing in General Multicommodity Networks

A natural generalization of the selfish routing setting arises when some of the users obey a central coordinating authority, while the rest act selfishly. Such behavior can be modeled by dividing the users into an α fraction that are routed according to the central coordinator’s routing strategy (Stackelberg strategy), and the remaining 1−α that determine their strategy selfishly, given the routing of the coordinated users. One seeks to quantify the resulting price of anarchy, i.e., the ratio of the cost of the worst traffic equilibrium to the system optimum, as a function of α. It is well-known that for α=0 and linear latency functions the price of anarchy is at most 4/3 (J. ACM 49, 236–259, 2002). If α tends to 1, the price of anarchy should also tend to 1 for any reasonable algorithm used by the coordinator. We analyze two such algorithms for Stackelberg routing, LLF and SCALE. For general topology networks, multicommodity users, and linear latency functions, we show a price of anarchy bound for SCALE which decreases from 4/3 to 1 as α increases from 0 to 1, and depends only on α. Up to this work, such a tradeoff was known only for the case of two nodes connected with parallel links (SIAM J. Comput. 33, 332–350, 2004), while for general networks it was not clear whether such a result could be achieved, even in the single-commodity case. We show a weaker bound for LLF and also some extensions to general latency functions. The existence of a central coordinator is a rather strong requirement for a network. We show that we can do away with such a coordinator, as long as we are allowed to impose taxes (tolls) on the edges in order to steer the selfish users towards an improved system cost. As long as there is at least a fraction α of users that pay their taxes, we show the existence of taxes that lead to the simulation of SCALE by the tax-payers. The extension of the results mentioned above quantifies the improvement on the system cost as the number of tax-evaders decreases. Research of G. Karakostas supported by an NSERC Discovery Grant and MITACS. Research of S. Kolliopoulos partially supported by the University of Athens under the project Kapodistrias.     

The essential order of approximation for nearly exponential type neural networks

1 Introduction Artificial neural networks have been extensively applied in various fields of science and engineering. Why is so is mainly because the feedforward neural networks (FNNs) have the universal approximation capability[1-9]. A typical example of…     

Entropy of Operators or why Matrix Multiplication is Hard for Depth-Two Circuits

We consider unbounded fanin depth-2 circuits with arbitrary boolean functions as gates. We define the entropy of an operator f:{0,1} ⁿ →{0,1} ^m as the logarithm of the maximum number of vectors distinguishable by at least one special subfunction of f. Our main result is that every depth-2 circuit for f requires at least entropy(f) wires. This is reminiscent of a classical lower bound of Nechiporuk on the formula size, and gives an information-theoretic explanation of why some operators require many wires. We use this to prove a tight estimate Θ(n ³) of the smallest number of wires in any depth-2 circuit computing the product of two n by n matrices over any finite field. Previously known lower bound for this operator was Ω(n ²log n).     

Geometric Restrictions on Producible Polygonal Protein Chains

Fixed-angle polygonal chains in three dimensions serve as an interesting model of protein backbones. Here we consider such chains produced inside a "machine" modeled crudely as a cone, and examine the constraints this model places on the producible chains. We call this notion producible, and prove as our main result that a chain whose maximum turn angle is α is producible in a cone of half-angle ≥ α if and only if the chain is flattenable, that is, the chain can be reconfigured without self-intersection to lie flat in a plane. This result establishes that two seemingly disparate classes of chains are in fact identical. Along the way, we discover that all producible configurations of a chain can be moved to a canonical configuration resembling a helix. One consequence is an algorithm that reconfigures between any two flat states of a "nonacute chain" in O(n) "moves," improving the O(n²)-move algorithm in [ADD+]. Finally, we prove that the producible chains are rare in the following technical sense. A random chain of n links is defined by drawing the lengths and angles from any "regular" (e.g., uniform) distribution on any subset of the possible values. A random configuration of a chain embeds into ℝ³ by in addition drawing the dihedral angles from any regular distribution. If a class of chains has a locked configuration (and no nontrivial class is known to avoid locked configurations), then the probability that a random configuration of a random chain is producible approaches zero geometrically as n → ∞.     

Universal routing schemes

Summary.  In this paper, we deal with the compact routing problem, that is implementing routing schemes that use a minimum memory size on each router. A universal routing scheme is a scheme that applies to all n-node networks. In [31], Peleg and Upfal showed that one cannot implement a universal routing scheme with less than a total of Ω(n ^1+1/(2s+4)) memory bits for any given stretch factor s≧1. We improve this bound for stretch factors s, 1≦s<2, by proving that any near-shortest path universal routing scheme uses a total of Ω(n ²) memory bits in the worst-case. This result is obtained by counting the minimum number of routing functions necessary to route on all n-node networks. Moreover, and more fundamentally, we give a tight bound of Θ(n log n) bits for the local minimum memory requirement of universal routing scheme of stretch factors s, 1≦s<2. More precisely, for any fixed constant ɛ, 0<ɛ<1, there exists a n-node network G on which at least Ω(n ^ɛ) routers require Θ(n log n) bits each to code any routing function on G of stretch factor <2. This means that, whatever you choose the routing scheme, there exists a network on which one cannot compress locally the routing information better than routing tables do. Received: August 1995 / Accepted: August 1996     

Fuzzy <Emphasis Type="Italic">R</Emphasis>-subgroups with thresholds of near-rings and implication operators

Using the belongs to relation (∈) and quasi-coincidence with relation (q) between fuzzy points and fuzzy sets, the concept of (α, β)-fuzzy R-subgroup of a near-ring where α , β are any two of {∈, q, ∈∨q , ∈∧q} with α ≠ ∈∧q is introduced and related properties are investigated. We also introduce the notion of a fuzzy R-subgroup with thresholds which is a generalization of an ordinary fuzzy R-subgroup and an (∈, ∈∨q)-fuzzy R-subgroup. Finally, we give the definition of an implication-based fuzzy R-subgroup.     

Asymptotically Optimal Solutions for Small World Graphs

We consider the problem of determining constructions with an asymptotically optimal oblivious diameter in small world graphs under the Kleinberg’s model. In particular, we give the first general lower bound holding for any monotone distance distribution, that is induced by a monotone generating function. Namely, we prove that the expected oblivious diameter is Ω(log ² n) even on a path of n nodes. We then focus on deterministic constructions and after showing that the problem of minimizing the oblivious diameter is generally intractable, we give asymptotically optimal solutions, that is with a logarithmic oblivious diameter, for paths, trees and Cartesian products of graphs, including d-dimensional grids for any fixed value of d. The research was partially funded by the European project COST Action 293, “Graphs and Algorithms in Communication Networks” (GRAAL).