D. Sivakumar 0001

STOC Conference 2009 Conference Paper

Affiliation networks

• Silvio Lattanzi
• D. Sivakumar 0001

In the last decade, structural properties of several naturally arising networks (the Internet, social networks, the web graph, etc.) have been studied intensively with a view to understanding their evolution. In recent empirical work, Leskovec, Kleinberg, and Faloutsos identify two new and surprising properties of the evolution of many real-world networks: densification (the ratio of edges to vertices grows over time), and shrinking diameter (the diameter reduces over time to a constant). These properties run counter to conventional wisdom, and are certainly inconsistent with graph models prior to their work. In this paper, we present the first model that provides a simple, realistic, and mathematically tractable generative model that intrinsically explains all the well-known properties of the social networks, as well as densification and shrinking diameter. Our model is based on ideas studied empirically in the social sciences, primarily on the groundbreaking work of Breiger (1973) on bipartite models of social networks that capture the affiliation of agents to societies. We also present algorithms that harness the structural consequences of our model. Specifically, we show how to overcome the bottleneck of densification in computing shortest paths between vertices by producing sparse subgraphs that preserve or approximate shortest distances to all or a distinguished subset of vertices. This is a rare example of an algorithmic benefit derived from a realistic graph model. Finally, our work also presents a modular approach to connecting random graph paradigms (preferential attachment, edge-copying, etc.) to structural consequences (heavy-tailed degree distributions, shrinking diameter, etc.).

SODA Conference 2003 Conference Paper

Comparing top k lists

• Ronald Fagin
• Ravi Kumar 0001
• D. Sivakumar 0001

STOC Conference 2003 Conference Paper

Two applications of information complexity

• T. S. Jayram
• Ravi Kumar 0001
• D. Sivakumar 0001

FOCS Conference 2002 Conference Paper

An Information Statistics Approach to Data Stream and Communication Complexity

• Ziv Bar-Yossef
• T. S. Jayram
• Ravi Kumar 0001
• D. Sivakumar 0001

We present a new method for proving strong lower bounds in communication complexity. This method is based on the notion of the conditional information complexity of a function which is the minimum amount of information about the inputs that has to be revealed by a communication protocol for the function. While conditional information complexity is a lower bound on the communication complexity, we show that it also admits a direct sum theorem. Direct sum decomposition reduces our task to that of proving (conditional) information complexity lower bounds for simple problems (such as the AND of two bits). For the latter, we develop novel techniques based on Hellinger distance and its generalizations.

STOC Conference 2002 Conference Paper

Approximate counting of inversions in a data stream

• Miklós Ajtai
• T. S. Jayram
• Ravi Kumar 0001
• D. Sivakumar 0001

(MATH) Inversions are used as a fundamental quantity to measure the sortedness of data, to evaluate different ranking methods for databases, and in the context of rank aggregation. Considering the volume of the data sets in these applications, the data stream model {14, 2] is a natural setting to design efficient algorithms.We obtain a suite of space-efficient streaming algorithms for approximating the number of inversions in a permutation. The best space bound we achieve is $O(\log n \log \log n)$ through a deterministic algorithm. In contrast, we derive an $\Omega(n)$ lower bound for randomized exact computation for this problem; thus approximation is essential.(MATH) We also consider two generalizations of this problem: (1) approximating the number of inversions between two permutations, for which we obtain a randomized $O(\sqrt{n} \log n)$-space algorithm, and (2) approximating the number of inversions in a general list, for which we obtain a randomized $O(\sqrt{n} \log^2 n)$-space two-pass algorithm. In contrast, we derive $\Omega(n)$-space lower bounds for deterministic approximate computation for these problems; thus both randomization and approximation are essential.All our algorithms use only O (log n ) time per data item.

SODA Conference 2002 Conference Paper

Reductions in streaming algorithms, with an application to counting triangles in graphs

• Ziv Bar-Yossef
• Ravi Kumar 0001
• D. Sivakumar 0001

STOC Conference 2001 Conference Paper

A sieve algorithm for the shortest lattice vector problem

• Miklós Ajtai
• Ravi Kumar 0001
• D. Sivakumar 0001

We present a randomized 2^{ O(n) } time algorithm to compute a shortest non-zero vector in an n -dimensional rational lattice. The best known time upper bound for this problem was 2^{ O(n \log n )} first given by Kannan [7] in 1983. We obtain several consequences of this algorithm for related problems on lattices and codes, including an improvement for polynomial time approximations to the shortest vector problem. In this improvement we gain a factor of log log n in the exponent of the approximating factor.

SODA Conference 2001 Conference Paper

On polynomial approximation to the shortest lattice vector length

• Ravi Kumar 0001
• D. Sivakumar 0001

STOC Conference 2001 Conference Paper

Sampling algorithms: lower bounds and applications

• Ziv Bar-Yossef
• Ravi Kumar 0001
• D. Sivakumar 0001

We develop a framework to study probabilistic sampling algorithms that approximate general functions of the form \genfunc , where \domain and \range are arbitrary sets. Our goal is to obtain lower bounds on the query complexity of functions, namely the number of input variables x_i that any sampling algorithm needs to query to approximate f(x_1,\ldots,x_n) . We define two quantitative properties of functions --- the it block sensitivity and the minimum Hellinger distance --- that give us techniques to prove lower bounds on the query complexity. These techniques are quite general, easy to use, yet powerful enough to yield tight results. Our applications include the mean and higher statistical moments, the median and other selection functions, and the frequency moments, where we obtain lower bounds that are close to the corresponding upper bounds. We also point out some connections between sampling and streaming algorithms and lossy compression schemes.

FOCS Conference 2000 Conference Paper

Random graph models for the web graph

• Ravi Kumar 0001
• Prabhakar Raghavan
• Sridhar Rajagopalan
• D. Sivakumar 0001
• Andrew Tomkins
• Eli Upfal

The Web may be viewed as a directed graph each of whose vertices is a static HTML Web page, and each of whose edges corresponds to a hyperlink from one Web page to another. We propose and analyze random graph models inspired by a series of empirical observations on the Web. Our graph models differ from the traditional G/sub n, p/ models in two ways: 1. Independently chosen edges do not result in the statistics (degree distributions, clique multitudes) observed on the Web. Thus, edges in our model are statistically dependent on each other. 2. Our model introduces new vertices in the graph as time evolves. This captures the fact that the Web is changing with time. Our results are two fold: we show that graphs generated using our model exhibit the statistics observed on the Web graph, and additionally, that natural graph models proposed earlier do not exhibit them. This remains true even when these earlier models are generalized to account for the arrival of vertices over time. In particular, the sparse random graphs in our models exhibit properties that do not arise in far denser random graphs generated by Erdos-Renyi models.

SODA Conference 1999 Conference Paper

Roundness Estimation via Random Sampling

• Ravi Kumar 0001
• D. Sivakumar 0001

FOCS Conference 1996 Conference Paper

Efficient Self-Testing/Self-Correction of Linear Recurrences

• Ravi Kumar 0001
• D. Sivakumar 0001

The authors consider the problem of designing self-testers/self-correctors for functions defined by linear recurrences. They present the first complete package of efficient and simple self-testers, self-correctors, and result-checkers for such functions. The results are proved by demonstrating an efficient reduction from this problem to the problem of testing linear functions over certain matrix groups. The tools include spectral analysis of matrices over finite fields, and various counting arguments that extend known techniques. The matrix twist yields simple and efficient self-testers for all linear recurrences. They also show a technique of using convolution identities to obtain very simple self-testers and self correctors. Their techniques promise new and efficient ways of testing VLSI chips for applications in control engineering, signal processing, etc. An interesting consequence of their methods is a completely new and randomness-efficient self-tester for polynomials over finite fields and rational domains. In particular the self-tester for polynomials over rational domains overcomes a main drawback of the result of Rubinfeld and Sudan (1992)-the need for a test domain of much larger size and of much finer precision.