ScholarBank@NUShttps://scholarbank.nus.edu.sgThe DSpace digital repository system captures, stores, indexes, preserves, and distributes digital research material.Fri, 20 May 2022 04:59:23 GMT2022-05-20T04:59:23Z50141- Improved bounds on the sample complexity of learninghttps://scholarbank.nus.edu.sg/handle/10635/43158Title: Improved bounds on the sample complexity of learning
Authors: Li, Yi; Long, Philip M.; Srinivasan, Aravind
Abstract: We present two improved bounds on the sample complexity of learning. First, we present a new general upper bound on the number of examples required to estimate all of the expectations of a set of random variables uniformly well. The quality of the estimates is measured using a variant of the relative error proposed by Haussler and Pollard. We also show that our bound is within a constant factor of the best possible. Our upper bound implies improved bounds on the sample complexity of learning according to Haussler's decision theoretic model. Next, we prove a lower bound on the sample complexity for learning according to the prediction model that is optimal to within a factor of 1+o(1).
Sat, 01 Jan 2000 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/431582000-01-01T00:00:00Z
- Approximating hyper-rectangles: Learning and pseudorandom setshttps://scholarbank.nus.edu.sg/handle/10635/99195Title: Approximating hyper-rectangles: Learning and pseudorandom sets
Authors: Auer, P.; Long, P.M.; Srinivasan, A.
Abstract: The PAC learning of rectangles has been studied because they have been found experimentally to yield excellent hypotheses for several applied learning problems. Also, pseudorandom sets for rectangles have been actively studied recently because (i) they are a subproblem common to the derandomization of depth-2 (DNF) circuits and derandomizing randomized logspace, and (ii) they approximate the distribution of n independent multivalued random variables. We present improved upper bounds for a class of such problems of "approximating" high-dimensional rectangles that arise in PAC learning and pseudorandomness. © 1998 Academic Press.
Tue, 01 Dec 1998 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/991951998-12-01T00:00:00Z
- Low-bandwidth routing and electrical power networkshttps://scholarbank.nus.edu.sg/handle/10635/99552Title: Low-bandwidth routing and electrical power networks
Authors: Cook, D.; Faber, V.; Marathe, M.; Srinivasan, A.; Sussmann, Y.J.
Abstract: Given a graph G and a (multi-)set of pairs of vertices in it, the classical NP-hard maximum edge-dis joint-paths problem (MDP) is to connect as many of the given pairs as possible using pairwise edge-disjoint paths in G. We study a relative of this problem: we have a network with fixed link capacities that may have to service large demands when necessary. In particular, individual demands are allowed to exceed capacities, and thus flows for some request pairs necessarily have to be split into different flow-paths. This is the framework for computational problems arising from: (i) electrical power networks due to the proposed deregulation of the electric utility industry in the USA, and (ii) applications such as real-time Internet services (e.g., telephone, fax, video). We show that these problems come in a few variants, some efficiently solvable and many NP-hard; we also present approximation algorithms for many of the NP-hard variants presented. Some of our approximation algorithms benefit from certain improved tail estimates that we derive; the latter also yield improved approximations for a family of packing integer programs.
Thu, 01 Jan 1998 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/995521998-01-01T00:00:00Z
- Improving the discrepancy bound for sparse matrices: Better approximations for sparse lattice approximation problemshttps://scholarbank.nus.edu.sg/handle/10635/99537Title: Improving the discrepancy bound for sparse matrices: Better approximations for sparse lattice approximation problems
Authors: Srinivasan, Aravind
Abstract: A powerful technique to approximate certain sparse integer programs due to Beck & Fiala, shows that matrices A∈{-1, 0, 1}m×n with no column having more than t nonzeroes, have discrepancy disc(A) less than 2t. An outstanding conjecture of Beck & Fiala is that this disc(A) here is O(√t). This, if true, would be best-possible; any bound of o(t) would be very interesting. We make progress on this by showing that certain related discrepancy measures of A that are lower bounds on disc(A), are O(t3/4log t) (i.e., o(t)). We also show that disc(A) = O(√t log n), improving the Beck-Spencer bound of O(√t log t log n). These results also apply to the lattice approximation problem of Raghavan. We show improved upper bounds on the discrepancy of two well-studied families of sparse matrices: l permutations of [n], and rectangles containing n points in Rk. We show a discrepancy bound of O(√l log n) for the former, improving on the previous-best O(l log n) due to Bohus. This improves the bounds for the latter, for k = 2, 3 and 4. We also present a simple connection between discrepancy and communication complexity.
Wed, 01 Jan 1997 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/995371997-01-01T00:00:00Z
- Randomized distributed edge coloring via an extension of the Chernoff-Hoeffding boundshttps://scholarbank.nus.edu.sg/handle/10635/99392Title: Randomized distributed edge coloring via an extension of the Chernoff-Hoeffding bounds
Authors: Panconesi, A.; Srinivasan, A.
Abstract: Certain types of routing, scheduling, and resource-allocation problems in a distributed setting can be modeled as edge-coloring problems. We present fast and simple randomized algorithms for edge coloring a graph in the synchronous distributed point-to-point model of computation. Our algorithms compute an edge coloring of a graph G with n nodes and maximum degree A with at most 1.6Δ + O(log1+δ n) colors with high probability (arbitrarily close to 1) for any fixed δ > 0; they run in polylogarithmic time. The upper bound on the number of colors improves upon the (2Δ - 1)-coloring achievable by a simple reduction to vertex coloring. To analyze the performance of our algorithms, we introduce new techniques for proving upper bounds on the tail probabilities of certain random variables. The Chernoff-Hoeffding bounds are fundamental tools that are used very frequently in estimating tail probabilities. However, they assume stochastic independence among certain random variables, which may not always hold. Our results extend the Chernoff-Hoeffding bounds to certain types of random variables which are not stochastically independent. We believe that these results are of independent interest and merit further study.
Tue, 01 Apr 1997 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/993921997-04-01T00:00:00Z
- Improved approximations for edge-disjoint paths, unsplittable flow, and related routing problemshttps://scholarbank.nus.edu.sg/handle/10635/99534Title: Improved approximations for edge-disjoint paths, unsplittable flow, and related routing problems
Authors: Srinivasan, Aravind
Abstract: We present improved approximation algorithms for a family of problems involving edge-disjoint paths and unsplittable flow, and for some related routing problems. The central theme of all our algorithms is the underlying multi-commodity flow relaxation.
Wed, 01 Jan 1997 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/995341997-01-01T00:00:00Z
- Improved Parallel Approximation of a Class of Integer Programming Problemshttps://scholarbank.nus.edu.sg/handle/10635/99307Title: Improved Parallel Approximation of a Class of Integer Programming Problems
Authors: Alon, N.; Srinivasan, A.
Abstract: We present a method to derandomize RNC algorithms, converting them to NC algorithms. Using it, we show how to approximate a class of NP-hard integer programming problems in NC, to within factors better than the current-best NC algorithms (of Berger and Rompel and Motwani et al.); in some cases, the approximation factors are as good as the best-known sequential algorithms, due to Raghavan. This class includes problems such as global wire-routing in VLSI gate arrays and a generalization of telephone network planning in SONET rings. Also for a subfamily of the "packing" integer programs, we provide the first NC approximation algorithms; this includes problems such as maximum matchings in hypergraphs, and generalizations. The key to the utility of our method is that it involves sums of superpolynomially many terms, which can however be computed in NC; this superpolynomiality is the bottleneck for some earlier approaches, due to Berger and Rompel and Motwani et al.
Tue, 01 Apr 1997 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/993071997-04-01T00:00:00Z
- Explicit OR-dispersers with polylogarithmic degreehttps://scholarbank.nus.edu.sg/handle/10635/99277Title: Explicit OR-dispersers with polylogarithmic degree
Authors: Saks, M.; Srinivasan, A.; Zhou, S.
Abstract: An (N, M, T)-OR-disperser is a bipartite multigraph G = (V, W, E) with |V| = N, and |W| = M, having the following expansion property: any subset of V having at least T vertices has a neighbor set of size at least M/2. For any pair of constants ξ, λ, 1 ≥ ξ > λ ≥ 0, any sufficiently large N, and for any T ≥ 2(log N)ξ, M ≤ 2(log N)λ, we give an explicit elementary construction of an (N, M, T)-OR-disperser such that the out-degree of any vertex in V is at most polylogarithmic in N. Using this with known applications of OR-dispersers yields several results. First, our construction implies that the complexity class Strong-RP defined by Sipser, equals RP. Second, for any fixed η > 0, we give the first polynomial-time simulation of RP algorithms using the output of any "η-minimally random" source. For any integral R > 0, such a source accepts a single request for an R-bit string and generates the string according to a distribution that assigns probability at most 2-Rη to any string. It is minimally random in the sense that any weaker source is insufficient to do a black-box polynomial-time simulation of RP algorithms.
Thu, 01 Jan 1998 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/992771998-01-01T00:00:00Z
- Constant-factor approximation algorithm for packet routing, and balancing local vs. global criteriahttps://scholarbank.nus.edu.sg/handle/10635/53281Title: Constant-factor approximation algorithm for packet routing, and balancing local vs. global criteria
Authors: Srinivasan, Aravind; Teo, Chung-Piaw
Abstract: We present the first constant-factor approximation algorithm for a fundamental problem: the store-and-forward packet routing problem on arbitrary networks. Furthermore, the queue sizes required at the edges are bounded by an absolute constant. Thus, this algorithm balances a global criterion (routing time) with a local criterion (maximum queue size), and shows how to get simultaneous good bounds for both (though, for this particular problem, approximating the routing time well, even without considering the queue-sizes, was open). We then consider a class of such local vs. global problems in the context of covering integer programs, and show how to improve the local criterion by more than a constant (roughly logarithmic) factor, by losing a constant factor in the global criterion; this is in comparison with the current-best algorithms.
Wed, 01 Jan 1997 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/532811997-01-01T00:00:00Z
- Computing with very weak random sourceshttps://scholarbank.nus.edu.sg/handle/10635/39099Title: Computing with very weak random sources
Authors: Srinivasan, A.; Zuckerman, D.
Abstract: We give an efficient algorithm to extract randomness from a very weak random source using a small additional number t of truly random bits. Our work extends that of Nisan and Zuckerman [J. Comput. System Sci., 52 (1996), pp. 43-52] in that t remains small even if the entropy rate is well below constant. A key application of this is in running randomized algorithms using such a very weak source of randomness. For any fixed γ > 0, we show how to simulate RP algorithms in time nO(log n) using the output of a δ-source with min-entropy Rγ. Such a weak random source is asked once for R bits; it outputs an R-bit string according to any probability distribution that places probability at most 2-R(γ) on each string. If γ > 1/2 , our simulation also works for BPP; for γ > 1 - 1/(k + 1), our simulation takes time nO(log(k)n) (log(k) is the logarithm iterated k times). We also give a polynomial-time BPP simulation using Chor-Goldreich sources of min-entropy RΩ(1), which is optimal. We present applications to time-space tradeoffs, expander constructions, and to the hardness of approximation. Of independent interest is our randomness-efficient Leftover Hash Lemma, a key tool for extracting randomness from weak random sources.
Fri, 01 Jan 1999 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/390991999-01-01T00:00:00Z
- Improved approximation guarantees for packing and covering integer programshttps://scholarbank.nus.edu.sg/handle/10635/39172Title: Improved approximation guarantees for packing and covering integer programs
Authors: Srinivasan, A.
Abstract: Several important NP-hard combinatorial optimization problems can be posed as packing/covering integer programs; the randomized rounding technique of Raghavan and Thompson is a powerful tool with which to approximate them well. We present one elementary unifying properly of all these integer linear programs and use the FKG correlation inequality to derive an improved analysis of randomized rounding on them. This yields a pessimistic estimator, thus presenting deterministic polynomial-time algorithms for them with approximation guarantees that are significantly better than those known.
Fri, 01 Jan 1999 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/391721999-01-01T00:00:00Z
- On the Complexity of Distributed Network Decompositionhttps://scholarbank.nus.edu.sg/handle/10635/99360Title: On the Complexity of Distributed Network Decomposition
Authors: Panconesi, A.; Srinivasan, A.
Abstract: In this paper, we improve the bounds for computing a network decomposition distributively and deterministically. Our algorithm computes an (n∈(n), n∈(n))-decomposition in nO(∈(n)) time, where ∈(n) = 1/ √log n. As a corollary we obtain improved deterministic bounds for distributively computing several graph structures such as maximal independent sets and Δ-vertex colorings. We also show that the class of graphs Script G sign whose maximum degree is nO(δ(n)) where δ(n) = 1/log log n is complete for the task of computing a near-optimal decomposition, i.e., a (log n, log n)-decomposition, in polylog(n) time. This is a corollary of a more general characterization, which pinpoints the weak points of existing network decomposition algorithms. Completeness is to be intended in the following sense: if we have an algorithm Script A sign that computes a near-optimal decomposition in polylog(n) time for graphs in Script G sign then we can compute a near-optimal decomposition in polylog(n) time for all graphs. © 1996 Academic Press, Inc.
Fri, 01 Mar 1996 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/993601996-03-01T00:00:00Z
- The one-inclusion graph algorithm is near-optimal for the prediction model of learninghttps://scholarbank.nus.edu.sg/handle/10635/43369Title: The one-inclusion graph algorithm is near-optimal for the prediction model of learning
Authors: Li, Y.; Long, P.M.; Srinivasan, A.
Abstract: Haussler, Littlestone, and Warmuth described a general-purpose algorithm for learning according to the prediction model, and proved an upper bound on the probability that their algorithm makes a mistake in terms of the number of examples seen and the Vapnik-Chervonenkis (VC) dimension of the concept class being learned. We show that their bound is within a factor of 1 + o(1) of the best possible such bound for any algorithm.
Mon, 01 Jan 2001 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/433692001-01-01T00:00:00Z
- Approximating low-congestion routing and column-restricted packing problemshttps://scholarbank.nus.edu.sg/handle/10635/39054Title: Approximating low-congestion routing and column-restricted packing problems
Authors: Baveja, A.; Srinivasan, A.
Abstract: The factorial and integral optima of column-sparse integer programs are proved to be `nearby'. This yields improved approximation algorithms for some generalizations of the knapsack problem, with applications to low-congestion routing in networks, file replication in distributed databases, and other packing problems.
Sat, 01 Jan 2000 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/390542000-01-01T00:00:00Z