School of Computing
Permanent URI for this community
Browse
Browsing School of Computing by Author "Aravind Srinivasan"
Now showing 1 - 6 of 6
Results Per Page
Sort Options
- ItemComputing with Very Weak Random Sources(1996-04-01T00:00:00Z) Aravind Srinivasan; David ZuchermanWe study how to run randomized algorithms when the source of randomness is very defective (weak). For any fixed epsilon > 0, we show how to simulate RP algorithms in time n^{O(log n)} using the output of a delta-source with min-entropy R^{epsilon}. 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^{epsilon}} on each string. If epsilon > 1/2, our simulation also works for BPP; for epsilon > 1-1/(k+1), our simulation takes time n^{O(logk n)} (logk is the logarithm iterated k times). We also give a polynomial-time BPP simulation using Chor-Goldreich sources of min-entropy R^{Omega(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. This also helps us build on the work of Nisan & Zuckerman in adding a small number t of truly random bits to a weak random source to extract quasi-random bits; for delta = o(1) we make t much smaller than does the work of Nisan & Zuckerman. Aravind Srinivasan is with the Dept. of Information Systems and Computer Science, National University of Singapore, Singapore 119260, Republic of Singapore. His work done in parts at the National University of Singapore, at the Institute for Advanced Study, Princeton, NJ, USA (supported in part by grant 93-6-6 of the Alfred P. Sloan Foundation), and at the DIMACS Center, Rutgers University, Piscataway, NJ, USA (supported in part by NSF-STC91-19999 and by support from the N.J. Commission on Science and Technology). E-mail: aravind@iscs.nus.sg. David Zuckerman is with the Department of Computer Sciences, The University of Texas at Austin, Austin, TX 78712, USA. Part of his work was supported by NSF NYI Grant No. CCR-9457799. Part of this work was done while this author was visiting The Hebrew University of Jerusalem, supported by a Lady Davis Postdoctoral Fellowship. E-mail: diz@cs.utexas.edu. Part of this work was done while the authors attended the workshop on ``Probability and Algorithms" organized by Joel Spencer and Michael Steele, which was held at the Institute for Mathematics and its Applications at the University of Minnesota from September 20th-24th, 1993. A preliminary version of this work appears in the "Proc. IEEE Symposium on Foundations of Computer Science", pages 264-275, 1994.
- ItemImproved Algorithms via Approximations of Probability Distributions(1996-10-01T00:00:00Z) Suresh Chari; Pankaj Rohatgi; Aravind SrinivasanWe present two techniques for approximating probability distributions. The first is a simple method for constructing the small-bias probability spaces introduced by Naor and Naor. We show how to efficiently combine this construction with the method of conditional probabilities to yield improved NC algorithms for many problems such as set discrepancy, finding large cuts in graphs, finding large acyclic subgraphs etc. The second is a construction of small probability spaces approximating general independent distributions, which is of smaller size than the constructions of Even, Goldreich, Luby, Nisan and Velickovic. Such approximations are useful, e.g., for the derandomization of certain randomized algorithms.
- ItemImproved Approximation Guarantees for Packing and Covering Integer Programs(1995-10-01T00:00:00Z) Aravind SrinivasanSeveral 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 to approximate them well. We present one elementary unifying property of all these integer programs, and use the FKG correlation inequality to derive an improved analysis of randomized rounding on them. This also yields a pessimistic estimator, thus presenting deterministic polynomial-time algorithms for them with approximation guarantees significantly better than those known. Part of this work was done while at the School of Mathematics, Institute for Advanced Study, Princeton, NJ 08540, USA, supported by grant 93-6-6 of the Alfred P. Sloan Foundation to the Institute for Advanced Study. Part of this work was done while at DIMACS, supported by NSF grant NSF-STC91-19999 to DIMACS and by support to DIMACS from the New Jersey Commission on Science and Technology. Part was done while visiting the Department of Computer Science, University of Warwick, Coventry CV4 7AL, UK, supported in part by the ESPRIT Basic Research Action Programme of the EC under contract No. 7141 (project ALCOM II).
- ItemImproved Approximations for Edge-Disjoint Paths, Unsplittable Flow, and Related Routing Problems(1997-04-01T00:00:00Z) Aravind SrinivasanAbstract not available.
- ItemImproved parallel approximation of a class of integer programming problems(1995-11-01T00:00:00Z) Noga Alon; Aravind SrinivasanWe 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 & Rompel and Motwani, Naor & Naor); 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 & Rompel and Motwani, Naor & Naor. Part of Alon's work was done while visiting the Institute for Advanced Study, School of Mathematics, Princeton, NJ 08540, USA, supported in part by the Sloan Foundation, grant No. 93-6-6 and by the Fund for Basic Research administered by the Israel Academy of Sciences. Srinivasan's work was done in part at the National University of Singapore, at DIMACS (supported in part by NSF-STC91-19999 and by support from the N.J. Commission on Science and Technology), and at the Institute for Advanced Study, Princeton (supported in part by grant 93-6-6 of the Alfred P. Sloan Foundation).
- ItemScheduling and Load-Balancing via Randomization(1997-11-01T00:00:00Z) Aravind SrinivasanAbstract not available.