Circumference, Chromatic Number and Online Coloring (2008)
Diwan, Ajit A., Kenkre, Sreyash, Vishwanathan, Sundar
Erd\"os conjectured that if $G$ is a triangle free graph of chromatic number at least $k\geq 3$, then it contains an odd cycle of length at least $k^{2-o(1)}$ \cite{sudakovverstraete, verstraete}....
Depth-3 Arithmetic Circuits for S^2_n(X) and Extensions of the Graham-Pollack Theorem (2006)
Radhakrishnan, Jaikumar, Sen, Pranab, Vishwanathan, Sundar
We consider the problem of computing the second elementary symmetric polynomial S^2_n(X) using depth-three arithmetic circuits of the form "sum of products of linear forms". We consider this problem...
The Common Prefix Problem On Trees (2006)
Kenkre, Sreyash, Vishwanathan, Sundar
We present a theoretical study of a problem arising in database query optimization, which we call as The Common Prefix Problem. We present a $(1-o(1))$ factor approximation algorithm for this...
Approximation Algorithms for the Bipartite Multi-cut Problem (2006)
Kenkre, Sreyash, Vishwanathan, Sundar
We introduce the {\it Bipartite Multi-cut} problem. This is a generalization of the {\it st-Min-cut} problem, is similar to the {\it Multi-cut} problem (except for more stringent requirements) and...
Approximation Algorithms for the Achromatic Number (2004)
Amitabh Chaudhary, Sundar Vishwanathan
INTRODUCTION A complete coloring of agY3fi G E# is a partition P =#V of the vertices V such that each induced subgedb #, V i P , is an independent set, and, for each pair of distinct sets V i #V j P...
Competitive Algorithms for Layered Graph Traversal (2002)
Dean P. Foster, Howard Karloff, Yuval Rabani, Yiftach Ravid, Sundar Vishwanathan
A layered graph is a connected graph whose vertices are partitioned into sets L 0 = fsg; L 1 ; L 2 ; :::, and whose edges, which have nonnegative integral weights, run between consecutive layers. Its...
Depth-3 Arithmetic Circuits for S^2_n(X) and Extensions of the Graham-Pollack Theorem (2001)
Radhakrishnan, Jaikumar, Sen, Pranab, Vishwanathan, Sundar
We consider the problem of computing the second elementary symmetric polynomial S^2_n(X) using depth-three arithmetic circuits of the form "sum of products of linear forms". We consider this problem...
Rapidly Mixing Markov Chains (2001)
Dr. Ketan Mulmuley, Dr. Sundar Vishwanathan, Rahul T. Shah
The computational difficulty of the problems of counting the elements of a finite set of combinatorial structures has led to the development of randomized algorithms. The problem of generating at...
Randomized Graph Partitioning Algorithms (1999)
In this project, we have studied and worked on results and algorithms centered around (global) minimum cuts in graphs. A cut is a minimal set of edges whose removal from a connected graph disconnects...
Approximation Algorithms for the Achromatic Number (1999)
Amitabh Chaudhary, Sundar Vishwanathan
The achromatic number for a graph G = hV; Ei is the largest integer m such that there is a partition of V into disjoint independent sets fV1 ; V2 ; : : : ; Vmg such that for each pair of distinct...