Venkatesh Raman

Research Interests:

Algorithms:

Approximate Algorithms
Parameterized Complexity
Sorting, Selection and related problems

Data Structures:

Succinct (Space Efficient) Data Structures

Selected Recent Publications (in data structures and parameterized complexity):

Data Structures:

• Succinct ordinal Trees with level-ancestor queries

  Richard F. Geary, Rajeev Raman and Venkatesh Raman.
  to appear in Proceedings of ACM-SIAM conference on Discrete Algorithms (SODA) 2004.

• Merging and Sorting by Strip Moves

  Meena Mahajan, Raghavan Rama, Venkatesh Raman and Vijayakumar Sundarrajan.
  to appear in the proceedings of FSTTCS conference 2003.

• Succinct Representations of Permuatations

  Ian Munro, Rajeev Raman, Venkatesh Raman, S. Srinivasa Rao.
  Proceedings of ICALP 2003 (Springer LNCS 2719, 345-.)

• Succinct Indexable Dictionaries with Applications to representations of k-ary trees and multisets

  Rajeev Raman, Venkatesh Raman and S. Srinivasa Rao.
  Proceedings of ACM-SIAM conference of Discrete Algorithms (SODA) 2002.

• Representing Dynamic Trees Succinctly

  Ian Munro, Venkatesh Raman and Adam Storm.
  Proceedings of ACM-SIAM conference of Discrete Algorithms (SODA) 2001.

• A tradeoff between search and update in dictionaries

  Jaikumar Radhakrishnan and Venkatesh Raman.
  Information Processing Letter 80 (2001) 243-247.

• Succinct Dynamic Data Structures

  Rajeev Raman, Venkatesh Raman, S. Srinivasa Rao
  Proceedings of WADS 2001.

• Explicit Deterministic Construction for Membership in the Bitprobe Model

  Jaikumar Radhakrishnan, Venkatesh Raman and S. Srinivasa Rao
  Proceedings of ESA 2001.

• Space Efficient Suffix Trees.

  Ian Munro, Venkatesh Raman and S. Srinivasa Rao.
  Journal of Algorithms 39 (2) (2001) 205-222.

• Succinct Representation of Balanced Parentheses and Static Trees.

  Ian Munro and Venkatesh Raman.
  1997 IEEE Symposium on Foundations of Computer Science.
  SIAM J. Computing, Vol. 31, No.3 762-776.

• Static Dictionaries Supporting Rank

  Venkatesh Raman and S. Srinivasa Rao.
  Proceedings of ISAAC 99 (Springer LNCS 1741) 18-26.

• Representing Trees of Higher Degree

  D. Benoit, E. D. Demaine, J.I.Munro and V. Raman
  Proceedings of WADS 99 (Springer LNCS 1663) 169-180.

• Representing Trees of Higher Degree

  D. Benoit, E. D. Demaine, J. I. Munro, R. Raman, V. Raman and S. S. Rao
  Technical Report of University of Leicester, TR 2001/46.
  (Basically the journal version of the above two papers -- with an extra author.)

• Selecting small ranks in EREW PRAM

  Sarnath Ramnath and Venkatesh Raman.
  Information Processing Letters 71 (1999) 183-186.

• Improved Upper Bounds for Time-Space Tradeoffs for Selection.

  Venkatesh Raman and Sarnath Ramnath.
  Proceedings of SWAT 98, (Springer LNCS 1432) 131-142. Nordic Journal of Computing 6 (1999) 162-180.

• Finding Scores in Tournaments.

  R. Balasubramanian, Venkatesh Raman and G. Srinivasaraghavan.
  Journal of Algorithms 24 (1997) 380-394.

• Selection from Read-Only Memory and Sorting with minimum Data Movement

  Ian Munro and Venkatesh Raman.
  Theoretical Computer Science 165 (1996) 311-323.

  Parameterized Complexity:

• Parameterized Complexity of Directed Feedback Set Problems in Tournaments

  Venkatesh Raman and Saket Saurabh.
  Proceedings of WADS 2003 (Springer LNCS 2748, 484-).

• Parameterized Complexity of Finding Hereditary Properties

  Subhash Khot and Venkatesh Raman.
  Proceedings of COCOON 2000.
  Theoretical Computer Science 289 (2002) 997-1008.

• Approximation Algorithms for some Parameterized Counting Problems

  V. Arvind and Venkatesh Raman.
  Electronic Colloquium on Computational Complexity, 31 (2002). Proceedings of ISAAC 2002 Springer LNCS 2518 453-.

• Faster Fixed Parameter Tractable Algorithms for Undirected Feedback Vertex Set

  Venkatesh Raman, Saket Saurabh and C. R. Subramanian
  Proceedings of ISAAC 2002 (Springer LNCS 2518, 241-.)

• The Complexity of irredundant sets parameterized by size

  R. G. Downey, M. R. Fellows and Venkatesh Raman.
  Discrete Applied Mathematics 100 (2000) 155-167.

• Upper Bounds for MaxSat: Further Improved

  Nikhil Bansal and Venkatesh Raman.
  Proceedings of ISAAC 99 (Springer LNCS 1741) 247-258.

• Parameterizing Above the Guarantee: MAXSAT and MAXCUT

  Meena Mahajan and Venkatesh Raman.
  Journal of Algorithms 31 (1999) 335-354.

• A Simplified NP-Complete MAXSAT Problem

  Venkatesh Raman, B. Ravikumar and S. Srinivasa Rao.
  Information Processing Letters 65 (1998) 1-6.

• An Improved Fixed Parameter Algorithm for Vertex Cover.

  R. Balasubramanian, Michael Fellows and Venkatesh Raman.
  Information Processing Letters, 65 (1998) 163 -168

• Parameterized Complexity.

  Venkatesh Raman.
  in Proceedings of the 7th National Seminar on Theoretical Computer Science, June 1997, (Chennai, India) I-1 to I-18.
  

Personal Information:

• Address (Home):
  
  Plot 3 and 4, Gomathinagar, Ramnagar 9th Street, Ramnagar Extension, Velacheri, Chennai 600 042. India.
• Telephone (IMSc) : (044) 2254 1856, 2254 0588
  
• Telephone (Home) : (044) 2259 0374 or 2259 0394 (the second one if not in the first one and for messages)
  
• FAX (IMSc) : (044) 2254 0586
  
• E-Mail : vraman@imsc.res.in
  

Back to the TCS home page at IMSc