Arrow Research search

Author name cluster

Ramesh Hariharan

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

24 papers
2 author rows

Possible papers

24

STOC Conference 2011 Conference Paper

A general framework for graph sparsification

  • Wai Shing Fung
  • Ramesh Hariharan
  • Nicholas J. A. Harvey
  • Debmalya Panigrahi

We present a general framework for constructing cut sparsifiers in undirected graphs --- weighted subgraphs for which every cut has the same weight as the original graph, up to a multiplicative factor of (1 ε). Using this framework, we simplify, unify and improve upon previous sparsification results. As simple instantiations of this framework, we show that sparsifiers can be constructed by sampling edges according to their strength (a result of Benczur and Karger), effective resistance (a result of Spielman and Srivastava), edge connectivity , or by sampling random spanning trees . Sampling according to edge connectivity is the most aggressive method, and the most challenging to analyze. Our proof that this method produces sparsifiers resolves an open question of Benczur and Karger. While the above results are interesting from a combinatorial standpoint, we also prove new algorithmic results. In particular, we develop techniques that give the first (optimal) O(m)-time sparsification algorithm for unweighted graphs. Our algorithm has a running time of O(m) + ~O(n/ε 2 ) for weighted graphs, which is also linear unless the input graph is very sparse itself. In both cases, this improves upon the previous best running times (due to Benczur and Karger) of O(m log 2 n) (for the unweighted case) and O(m log 3 n) (for the weighted case) respectively. Our algorithm constructs sparsifiers that contain O(n log n/ε 2 ) edges in expectation; the only known construction of sparsifiers with fewer edges is by a substantially slower algorithm running in O(n 3 m / ε 2 ) time. A key ingredient of our proofs is a natural generalization of Karger's bound on the number of small cuts in an undirected graph. Given the numerous applications of Karger's bound, we suspect that our generalization will also be of independent interest.

Details

NeurIPS Conference 2007 Conference Paper

A Randomized Algorithm for Large Scale Support Vector Learning

  • Krishnan Kumar
  • Chiru Bhattacharya
  • Ramesh Hariharan

We propose a randomized algorithm for large scale SVM learning which solves the problem by iterating over random subsets of the data. Crucial to the algorithm for scalability is the size of the subsets chosen. In the context of text classification we show that, by using ideas from random projections, a sample size of O(log n) can be used to obtain a solution which is close to the optimal with a high probability. Experiments done on synthetic and real life data sets demonstrate that the algorithm scales up SVM learners, without loss in accuracy.

PDF Details

STOC Conference 2007 Conference Paper

An Õ(mn) Gomory-Hu tree construction algorithm for unweighted graphs

  • Ramesh Hariharan
  • Telikepalli Kavitha
  • Debmalya Panigrahi
  • Anand Bhalgat

We present a fast algorithm for computing a Gomory-Hu tree or cut tree for an unweighted undirected graph G = (V,E). The expected running time of our algorithm is Õ(mc) where |E| = m and c is the maximum u-vedge connectivity, where u,v ∈ V. When the input graph is also simple (i.e., it has no parallel edges), then the u-v edge connectivity for each pair of vertices u and v is at most n-1; so the expected running time of our algorithm for simple unweighted graphs is Õ(mn). All the algorithms currently known for constructing a Gomory-Hu tree [8,9] use n-1 minimum s -t cut (i.e., max flow) subroutines. This in conjunction with the current fastest Õ(n 20/9 ) max flow algorithm due to Karger and Levine [11] yields the current best running time of Õ(n 20/9 n) for Gomory-Hu tree construction on simpleunweighted graphs with m edges and n vertices. Thus we present the first Õ(mn) algorithm for constructing a Gomory-Hu tree for simple unweighted graphs.We do not use a max flow subroutine here; we present an efficient tree packing algorithm for computing Steiner edge connectivity and use this algorithm as our main subroutine. The advantage in using a tree packing algorithm for constructing a Gomory-Hu tree is that the work done in computing a minimum Steiner cut for a Steiner set S ⊆ V can be reused for computing a minimum Steiner cut for certain Steiner sets S' ⊆ S.

Details

I&C Journal 2004 Journal Article

Parallel two dimensional witness computation

  • Richard Cole
  • Zvi Galil
  • Ramesh Hariharan
  • S. Muthukrishnan
  • Kunsoo Park

An optimal parallel CRCW-PRAM algorithm to compute witnesses for all non-period vectors of an m 1×m 2 pattern is given. The algorithm takes O(loglogm) time and does O(m 1×m 2) work, where m=max{m 1, m 2}. This yields a work optimal algorithm for 2D pattern matching which takes O(loglogm) preprocessing time and O(1) text processing time.

Details DOI

STOC Conference 2003 Conference Paper

A fast algorithm for computing steiner edge connectivity

  • Richard Cole 0001
  • Ramesh Hariharan

Given an undirected graph or an Eulerian directed graph G and a subset S of its vertices, we show how to determine the edge connectivity C of the vertices in S in time O(C 3 n log n+m) . This algorithm is based on an efficient construction of tree packings which generalizes Edmonds' Theorem. These packings also yield a characterization of all minimal Steiner cuts of size C from which an efficient data structure for maintaining edge connectivity between vertices in S under edge insertion can be obtained. This data structure enables the efficient construction of a cactus tree for representing significant C -cuts among these vertices, called C -separations, in the same time bound. In turn, we use the cactus tree to give a fast implementation of an approximation algorithm for the Survivable Network Design problem due to Williamson, Goemans, Mihail and Vazirani.

Details

I&C Journal 2003 Journal Article

Overlap matching

  • Amihood Amir
  • Richard Cole
  • Ramesh Hariharan
  • Moshe Lewenstein
  • Ely Porat

We propose a new paradigm for string matching, namely structural matching. In structural matching, the text and pattern contents are not important. Rather, some areas in the text and pattern, such as intervals, are singled out. A “match” is a text location where a specified relation between the text and pattern areas is satisfied. In particular we define the structural matching problem of overlap (parity) matching. We seek the text locations where all overlaps of the given pattern and text intervals have even length. We show that this problem can be solved in time O(nlogm), where the text length is n and the pattern length is m. As an application of overlap matching, we show how to reduce the string matching with swaps problem to the overlap matching problem. The string matching with swaps problem is the problem of string matching in the presence of local swaps. The best deterministic upper bound known for this problem was O(nm 1/3logmlogσ) for a general alphabet Σ, where σ=min(m, |Σ|). Our reduction provides a solution to the pattern matching with swaps problem in time O(nlogmlogσ).

Details DOI

STOC Conference 2002 Conference Paper

Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths

  • Surender Baswana
  • Ramesh Hariharan
  • Sandeep Sen

We present improved algorithms for maintaining transitive closure and all-pairs shortest paths/distances in a digraph under deletion of edges.(MATH) For the problem of transitive closure, the previous best known algorithms, for achieving O (1) query time, require O (\min(m, \frac{n^3}{m}))$ amortized update time, implying an upper bound of O (n^{\frac{3}{2}})$ on update time per edge-deletion. We present an algorithm that achieves $O(1)$ query time and O (n \log^2n + \frac{n^2}{\sqrt{m}}{\sqrt{\log n}})$ update time per edge-deletion, thus improving the upper bound to O (n^{\frac{4}{3}}\sqrt[3]{\log n})$.(MATH) For the problem of maintaining all-pairs shortest distances in unweighted digraph under deletion of edges, we present an algorithm that requires O (\frac{n^3}{m} \log^2 n)$ amortized update time and answers a distance query in O (1) time. This improves the previous best known update bound by a factor of log n . For maintaining all-pairs shortest paths, we present an algorithm that achieves O (\min(n^{\frac{3}{2}} \sqrt{\log n}, \frac{n^3}{m} \log ^2n))$ amortized update time and reports a shortest path in optimal time (proportional to the length of the path). For the latter problem we improve the worst amortized update time bound by a factor of O (\sqrt{\frac{n}{\log n}})$.(MATH) We also present the first decremental algorithm for maintaining all-pairs (1+ε) approximate shortest paths/distances, for any ε > 0 , that achieves a sub-quadratic update time of O ( n log 2 n + \frac{n^2}{\sqrt{\epsilon m}}\sqrt{\log n})$ and optimal query time.Our algorithms are randomized and have one-sided error for query (with probability O (1/ n c ) for any constant c ).

Details

STOC Conference 2002 Conference Paper

Verifying candidate matches in sparse and wildcard matching

  • Richard Cole 0001
  • Ramesh Hariharan

(MATH) This paper obtains the following results on pattern matching problems in which the text has length n and the pattern has length m An O ( n log m ) time deterministic algorithm for the String Matching with Wildcards problems, even when the alphabet is large. An O ( k log 2 m ) time Las Vegas algorithm for the Sparse String Matching with Wildcards problem, where k « n is the number of non-zeros in the text. We also give Las Vegas algorithms for the higher dimensional version of this problem. As an application of the above, an O ( n log 2 m ) time Las Vegas algorithm for the Subset Matching and Tree Pattern Matching problems, and a Las Vegas algorithm for the Geometric Pattern Matching problem. Finally, an O ( n log 2 m ) time deterministic algorithm for Subset Matching and Tree Pattern Matching.

Details

FOCS Conference 1995 Conference Paper

Derandomizing Semidefinite Programming Based Approximation Algorithms

  • Sanjeev Mahajan
  • Ramesh Hariharan

Remarkable breakthroughs have been made recently in obtaining approximate solutions to some fundamental NP-Complete problems, namely Max-Cut, Max k-Cut, Max-Sat, Max-Dicut, Max-Bisection, k Vertex Coloring, Independent Set, etc. These breakthroughs all involve polynomial time randomized algorithms based upon semidefinite programming, a technique pioneered by M. Goemans and D. Williamson (1994). In this paper, we give techniques to derandomize the above class of randomized algorithms, thus obtaining polynomial time deterministic algorithms with the same approximation ratios for the above problems. Note that Goemans and Williamson also gave an elegant method to derandomize their Max-Cut algorithm. We show here that their technique has a fatal flaw. The techniques we subsequently develop are very different from theirs. At the heart of our technique is the use of spherical symmetry to convert a nested sequence of n integrations, which cannot be approximated sufficiently well in polynomial time, to a nested sequence of just a constant number of integrations, which can be approximated sufficiently well in polynomial time.

Details

FOCS Conference 1993 Conference Paper

Optimally fast parallel algorithms for preprocessing and pattern matching in one and two dimensions

  • Richard Cole 0001
  • Maxime Crochemore
  • Zvi Galil
  • Leszek Gasieniec
  • Ramesh Hariharan
  • S. Muthukrishnan 0001
  • Kunsoo Park
  • Wojciech Rytter

All algorithms below are optimal alphabet-independent parallel CRCW PRAM algorithms. In one dimension: Given a pattern string of length m for the string-matching problem, we design an algorithm that computes a deterministic sample of a sufficiently long substring in constant time. This problem used to be a bottleneck in the pattern preprocessing for one- and two-dimensional pattern matching. The best previous time bound was O(log/sup 2/ m/log log m). We use this algorithm to obtain the following results. 1. Improving the preprocessing of the constant-time text search algorithm from O(log/sup 2/ m/log log m) to n(log log m), which is now best possible. 2. A constant-time deterministic string-matching algorithm in the case that the text length n satisfies n=/spl Omega/(m/sup 1+/spl epsiv//) for a constant /spl epsiv/>0. 3. A simple probabilistic string-matching algorithm that has constant time with high probability for random input. 4. A constant expected time Las-Vegas algorithm for computing the period of the pattern and all witnesses and thus string matching itself, solving the main open problem remaining in string matching. >

Details

FOCS Conference 1992 Conference Paper

Tighter Bounds on the Exact Complexity of String Matching (Extended Abstract)

  • Richard Cole 0001
  • Ramesh Hariharan

The paper considers how many character comparisons are needed to find all occurrences of a pattern of length m in a text of length n. The main contribution is to show an upper bound of the form n + O(n/m) character comparisons, following preprocessing. Specifically, the authors show an upper bound of n+8/3(m+1)(n-m) character comparisons. This bound is achieved by an online algorithm which performs O(n) work in total, requires O(m) space and O(m/sup 2/) time for preprocessing. In addition the following lower bounds are shown: for online algorithms, a bound of n+11/5(m+1) (n-m) character comparisons for m = 10 + 11 k, for any integer k >or= 1, and for general algorithms, a bound of n+2(n-m)/m+3 character comparisons, for m=2 k+l, for any integer k>or=1. >

Details
v2026.09.13