<p>Shiv Nadar University is a comprehensive, multidisciplinary, research-focused, and student-centric University offering a full range of academic programs at the undergraduate, postgraduate and doctoral level. With state-of-the-art infrastructure, the University comprises of academic wings, sophisticated labs, international standard sports facilities, amphitheaters, auditorium, conference rooms and smart classrooms. The University&rsquo;s goal is to become internationally recognized for the quality of its research and creative endeavors and their applicability to improving quality of life, generating new insights and expanding the boundaries of human knowledge creativity. Committed to excellence in teaching, research and service, the University aims to serve the higher education needs of India and the world beyond.</p>

Shiv Nadar University

For Reed-Solomon codes with block length n and dimension k, the Johnson theorem states that for a Hamming ball of radius smaller than n - sqrt(n k), there can be at most O (n2) codewords. It was not known whether for larger radius, the number of codewords is polynomial. The best known list decoding algorithm for Reed-Solomon codes due to Guruswami and Sudan [Venkatesan Guruswami, Madhu Sudan, Improved decoding of Reed-Solomon and algebraic-geometry codes, IEEE Transactions on Information Theory 45 (6) (1999) 1757-1767] is also known to work in polynomial time only within this radius. In this paper we prove that when k &lt; α n for any constant 0 &lt; α &lt; 1, we can overcome the barrier of the Johnson bound for list decoding of Reed-Solomon codes (even if the field size is exponential). More specifically in such a case, we prove that for Hamming ball of radius n - sqrt(n k) + c (for any c &gt; 0) there can be at most O (nc frac(2 sqrt(α), (1 - sqrt(α))2) + c + 2) number of codewords. For any constant c, we describe a polynomial time algorithm for enumerating all of them, thereby also improving on the Guruswami-Sudan algorithm. Although the improvement is modest, this provides evidence for the first time that the n - sqrt(n k) bound is not sacrosanct for such a high rate. We apply our method to obtain sharper bounds on a list recovery problem introduced by Guruswami and Rudra [Venkatesan Guruswami, Atri Rudra, Limits to list decoding Reed-Solomon codes, IEEE Transactions on Information Theory 52 (8) (2006) 3642-3649] where they establish super-polynomial lower bounds on the output size when the list size exceeds ⌈ frac(n, k) ⌉. We show that even for larger list sizes the problem can be solved in polynomial time for certain values of k. © 2008 Elsevier B.V. All rights reserved.

World University root node

(SoE) School of Engineering

Fulltext

Discrete Applied Mathematics

Improvements on the Johnson bound for Reed-Solomon codes

Computing all-pairs distances in a graph is a fundamental problem of computer science but there has been a status quo with respect to the general problem of weighted directed graphs. In contrast, there has been a growing interest in the area of algorithms for approximate shortest paths leading to many interesting variations of the original problem. In this article, we trace some of the fundamental developments like spanners and distance oracles, their underlying constructions, as well as their applications to the approximate all-pairs shortest paths. © Springer-Verlag Berlin Heidelberg 2009.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Approximating shortest paths in graphs

The Parallel Disks Model (PDM) has been proposed to alleviate the I/O bottleneck that arises in the processing of massive data sets. Sorting has been extensively studied on the PDM model due to the fundamental nature of the problem - several asymptotically optimal algorithms are known for sorting. Although randomization has been frequently exploited, most of the prior algorithms suffer from complications in memory layouts, implementation, restrictions in range of parameters, and laborious analysis. In this paper, we present a randomized mergesort algorithm based on a simple idea that sorts using an asymptotically optimal number of I/O operations with high probability and has all of the desirable features for practical implementation. In the second part of the paper, we also present several novel algorithms for sorting on the PDM that take only a small number of passes through the data. Recently, considerable interest has been shown by researchers in developing algorithms for problem sizes of practical interest and we are able to obtain several improvements and simplification, in particular for random input. © 2008 IEEE.

IEEE Transactions on Computers

Optimal and practical algorithms for sorting on the PDM

Multiple memory models have been proposed to capture the effects of memory hierarchy culminating in the I-O model of Aggarwal and Vitter (Commun. ACM 31(9):1116-1127, [1988]). More than a decade of architectural advancements have led to new features that are not captured in the I-O model-most notably the prefetching capability. We propose a relatively simple Prefetch model that incorporates data prefetching in the traditional I-O models and show how to design optimal algorithms that can attain close to peak memory bandwidth. Unlike (the inverse of) memory latency, the memory bandwidth is much closer to the processing speed, thereby, intelligent use of prefetching can considerably mitigate the I-O bottleneck. For some fundamental problems, our algorithms attain running times approaching that of the idealized random access machines under reasonable assumptions. Our work also explains more precisely the significantly superior performance of the I-O efficient algorithms in systems that support prefetching compared to ones that do not. © 2008 Springer Science+Business Media, LLC.

Journal of Supercomputing

Combating I-O bottleneck using prefetching: Model, algorithms, and ramifications

Thorup and Zwick, in the seminal paper [Journal of ACM, 52(1), 2005, pp 1-24], showed that a weighted undirected graph on n vertices can be preprocessed in subcubic time to design a data structure which occupies only subquadratic space, and yet, for any pair of vertices, can answer distance query approximately in constant time. The data structure is termed as approximate distance oracle. Subsequently, there has been improvement in their preprocessing time, and presently the best known algorithms [4,3] achieve expected O(n 2) preprocessing time for these oracles. For a class of graphs, these algorithms indeed run in Θ(n2) time. In this paper, we are able to break this quadratic barrier at the expense of introducing a (small) constant additive error for unweighted graphs. In achieving this goal, we have been able to preserve the optimal size-stretch trade offs of the oracles. One of our algorithms can be extended to weighted graphs, where the additive error becomes 2·wmax (u,v) - here wmax(u,v) is the heaviest edge in the shortest path between vertices u, v. © 2008 Springer-Verlag.

Distance oracles for unweighted graphs: Breaking the quadratic barrier with constant additive error

Given a set of points S in any dimension, we describe a deterministic algorithm for finding a T ⊂ S, | T | = O (1 / ε) such that the centroid of T approximates the centroid of S within a factor 1 + ε for any fixed ε > 0. We achieve this in linear time by an efficient derandomization of the algorithm in [M. Inaba, N. Katoh, H. Imai, Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering (extended abstract), in: Proceedings of the Tenth Annual Symposium on Computational Geometry, 1994, pp. 332-339]. © 2007 Elsevier B.V. All rights reserved.

Information Processing Letters

A linear time deterministic algorithm to find a small subset that approximates the centroid

This paper presents improved algorithms for the following problem: given an unweighted directed graph G (V, E) and a sequence of on-line shortest-path/reachability queries interspersed with edge-deletions, develop a data-structure that can answer each query in optimal time, and can be updated efficiently after each edge-deletion. The central idea underlying our algorithms is a scheme for implicitly storing all-pairs reachability/shortest-path information, and an efficient way to maintain this information. Our algorithms are randomized and have one-sided inverse polynomial error for query. © 2004 Elsevier Inc. All rights reserved.

Journal of Algorithms

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

In this paper, we prove that for any polynomial function / of fixed degree without multiple roots, the probability that all the (f(x + l), f(x + 2),..., f(x + k)) are quadratic non-residue is ≈ 1/2k. In particular for f(x) = x3 + ax + b corresponding to the elliptic curve y2 = x3 +ax + b, it implies that the quadratic residues (f(x + 1), f(x + 2),... in a finite field are sufficiently randomly distributed. Using this result we describe an efficient implementation of El-Gamal Cryptosystem. that requires efficient computation of a mapping between plain-texts and the points on the elliptic curve. © Springer-Verlag Berlin Heidelberg 2007.

A result on the distribution of quadratic residues with applications to elliptic curve cryptography

Let G = (V, E) be an undirected weighted graph on |V| = n vertices and |E| = m edges. A t-spanner of the graph G, for any t ≥ 1, is a subgraph (V, ES), ES ⊆ E, such that the distance between any pair of vertices in the subgraph is at most t times the distance between them in the graph G. Computing a t-spanner of minimum size (number of edges) has been a widely studied and well-motivated problem in computer science. In this paper we present the first linear time randomized algorithm that computes a t-spanner of a given weighted graph. Moreover, the size of the t-spanner computed essentially matches the worst case lower bound implied by a 43-year old girth lower bound conjecture made independently by Erdos, Bollobás, and Bondy &amp; Simonovits. Our algorithm uses a novel clustering approach that avoids any distance computation altogether. This feature is somewhat surprising since all the previously existing algorithms employ computation of some sort of local or global distance information, which involves growing either breadth first search trees up to Θ(t)-levels or full shortest path trees on a large fraction of vertices. The truly local approach of our algorithm also leads to equally simple and efficient algorithms for computing spanners in other important computational environments like distributed, parallel, and external memory. © 2006 Wiley Periodicals Inc.

Random Structures and Algorithms

A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs

External Memory models, most notable being the I-O Model [3], capture the effects of memory hierarchy and aid in algorithm design. More than a decade of architectural advancements have led to new features not captured in the I-O model - most notably the prefetching capability. We propose a relatively simple Prefetch model that incorporates data prefetching in the traditional I-O models and show how to design algorithms that can attain close to peak memory bandwidth. Unlike (the inverse of) memory latency, the memory bandwidth is much closer to the processing speed, thereby, intelligent use of prefetching can considerably mitigate the I-O bottleneck. For some fundamental problems, our algorithms attain running times approaching that of the idealized Random Access Machines under reasonable assumptions. Our work also explains the significantly superior performance of the I-O efficient algorithms in systems that support prefetching compared to ones that do not. © 2006 Springer-Verlag.

Algorithmic ramifications of prefetching in memory hierarchy

Let G = (V, E) be an undirected graph on n vertices, and let Δ(u, v) denote the distance in G between two vertices u and v. Thorup and Zwick showed that for any positive integer t, the graph G can be preprocessed to build a data structure that can efficiently report t-approximate distance between any pair of vertices. That is, for any u, v V, the distance reported is at least Δ(u, v) and at most tΔ(u, v). The remarkable feature of this data structure is that, for t3, it occupies subquadratic space, that is, it does not store all-pairs distances explicitly, and still it can answer any t-approximate distance query in constant time. They named the data structure approximate distance oracle because of this feature. Furthermore, the trade-off between the stretch t and the size of the data structure is essentially optimal.In this article, we show that we can actually construct approximate distance oracles in expected O(n2) time if the graph is unweighted. One of the new ideas used in the improved algorithm also leads to the first expected linear-time algorithm for computing an optimal size (2, 1)-spanner of an unweighted graph. A (2, 1) spanner of an undirected unweighted graph G = (V, E) is a subgraph (V, ), E, such that for any two vertices u and v in the graph, their distance in the subgraph is at most 2Δ(u, v) + 1. © 2006 ACM.

ACM Transactions on Algorithms

Approximate distance oracles for unweighted graphs in expected O(n 2) time

We present alternate reductions of the nearest neighbor searching problem to Point Location in Balls that reduces the space bound of Sariel Har-Peled's [S. Har-Peled, A replacement for Voronoi diagrams of near linear size, in: Proc. of IEEE FOCS, 2001, pp. 94-103, full version available from http://www.uiuc.edu/~sariel/papers] recent result on Approximate Voronoi Diagrams to linear while maintaining the logarithmic search time. We do this by simplifying the construction of [S. Har-Peled, A replacement for Voronoi diagrams of near linear size, in: Proc. of IEEE FOCS, 2001, pp. 94-103, full version available from http://www.uiuc.edu/~sariel/papers] that reduces the number of balls generated by algorithm by a logarithmic factor to O (n log n). We further reduce the number of balls by a new hierarchical decomposition scheme and a generalization of PLEBs to achieve linear space decomposition for nearest neighbor searching. The construction of our data structures takes O (n log n) time. © 2006 Elsevier Inc. All rights reserved.

Journal of Computer and System Sciences

Nearest neighbors search using point location in balls with applications to approximate Voronoi decompositions

The traditional zero-one principle for sorting networks states that "if a network with n input lines sorts all 2n binary sequences into nondecreasing order, then it will sort any arbitrary sequence of n numbers into nondecreasing order". We generalize this to the situation when a network sorts almost all binary sequences and relate it to the behavior of the sorting network on arbitrary inputs. We also present an application to mesh sorting. © 2004 Elsevier B.V. All rights reserved.

A generalization of the 0-1 principle for sorting

We live in an era of data explosion that necessitates the discovery of novel out-of-core techniques. The I/O bottleneck has to be dealt with in developing out-of-core methods. The Parallel Disk Model (PDM) has been proposed to alleviate the I/O bottleneck. Sorting is an important problem that has ubiquitous applications. Several asymptotically optimal PDM sorting algorithms are known and now the focus has shifted to developing algorithms for problem sizes of practical interest. In this paper we present several novel algorithms for sorting on the PDM that take only a small number of passes through the data. We also present a generalization of the zero-one principle for sorting. A shuffling lemma is presented as well. These lemmas should be of independent interest for average case analysis of sorting algorithms as well as for the analysis of randomized sorting algorithms.

Proceedings - 19th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2005

PDM sorting algorithms that take a small number of passes

The Parallel Disks Model (PDM) has been proposed to alleviate the I/O bottleneck that arises in the processing of massive data sets. Sorting has been extensively studied on the PDM model due to the fundamental nature of the problem. Several randomized algorithms are known for sorting. Most of the prior algorithms suffer from undue complications in memory layouts, implementation, or lack of tight analysis. In this paper we present a simple randomized algorithm that sorts in optimal time with high probablity and has all the desirable features for practical implementation. © Springer-Verlag Berlin Heidelberg 2005.

A simple optimal randomized algorithm for sorting on the PDM

Matousek [Discrete Comput. Geom. 24 (1) (2000) 61-84] designed an O(nlogn) deterministic algorithm for the approximate 2-means clustering problem for points in fixed dimensional Euclidean space which had left open the possibility of a linear time algorithm. In this paper, we present a simple randomized algorithm to determine an approximate 2-means clustering of a given set of points in fixed dimensional Euclidean space, with constant probability, in linear time. We first approximate the mean of the larger cluster using random sampling. We then show that the problem can be reduced to a set of lines, on which it can be solved by carefully pruning away points of the larger cluster and randomly sampling on the remaining points to obtain an approximate to the mean of the smaller cluster. © 2005 Elsevier B.V.

Computational Geometry: Theory and Applications

A linear time algorithm for approximate 2-means clustering

We generalize the k-means algorithm presented by the authors [14] and show that the resulting algorithm can solve a larger class of clustering problems that satisfy certain properties (existence of a random sampling procedure and tightness). We prove these properties for the k-median and the discrete k-means clustering problems, resulting in O(2(k/ε (1) dn) time (1 + ε)-approximation algorithms for these problems. These are the first algorithms for these problems linear in the size of the input (nd for n points in d dimensions), independent of dimensions in the exponent, assuming k and ε to be fixed. A key ingredient of the k-median result is a (1 + ε)-approximation algorithm for the 1-median problem which has running time O(2(1/ε) d). The previous best known algorithm for this problem had linear running time. © Springer-Verlag Berlin Heidelberg 2005.

Lecture Notes in Computer Science

Linear time algorithms for clustering problems in any dimensions

Let G(V, E) be an unweighted undirected graph on |V| = n vertices. Let δ(u, v) denote the shortest distance between vertices u, v ∈ V. An algorithm is said to compute all-pairs t-approximate shortestpaths/distances, for some t ≥ 1, if for each pair of vertices u, v ∈ V, the path/distance reported by the algorithm is not longer/greater than t δ(u, v). This paper presents two randomized algorithms for computing all-pairs nearly 2-approximate distances. The first algorithm takes expected O(m2/3n log n+n2) time, and for any u, v ∈ V reports distance no greater than 2δ(u, v) + 1. Our second algorithm requires expected O(n2 log3/2) time, and for any it, v ∈ V reports distance bounded by 2δ(u, v) + 3. This paper also presents the first expected O(n 2) time algorithm to compute all-pairs 3-approximate distances. © Springer-Verlag Berlin Heidelberg 2005.

All-pairs nearly 2-approximate shortest-paths in O(n2 polylogn) time

We present the first linear time (1 + ε)-approximation algorithm for the k-means problem for fixed k and ε. Our algorithm runs in O(nd) time, which is linear in the size of the input. Another feature of our algorithm is its simplicity - the only technique involved is random sampling. © 2004 IEEE.

Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

A simple linear time (1 + ε)-approximation algorithm for k-means clustering in any dimensions

Let G(V, E) be an undirected weighted graph with |V| = n, |E| = m. Recently Thorup and Zwick introduced a remarkable data-structure that stores all-pairs approximate distance information implicitly in o(n 2) space, and yet answers any approximate distance query in constant time. They named this data-structure approximate distance oracle because of this feature. Given an integer k &gt; 1, a (2k - 1)-approximate distance oracle requires O(kn 1+1/k) space and answers a (2k - 1)-approximate distance query in O(k) time. Thorup and Zwick showed that a (2k - 1)-approximate distance oracle can be computed in O(kmn 1/k) time, and posed the following question : Can (2k - 1)-approximate distance oracle be computed in Õ(n 2) time? In this paper, we answer their question in affirmative for unweighted graphs. We present an algorithm that computes (2k - 1)-approximate distance oracle for a given unweighted graph in Õ(n 2) time. One of the new ideas used in the improved algorithm also leads to the first linear time algorithm for computing an optimal size (2, 1)-spanner of an unweighted graph.