Complexity Theory

• V. Chakaravarthy, S. Roy.
  Arthur and Merlin as Oracles. (postscript)
  33rd Symposium on Mathematical Foundations of Computer Science (MFCS), 2008.

• V. Chakaravarthy, S. Roy.
  Finding Irrefutable Certificates for $S_2^p$ via Arthur and Merlin. (postscript)
  25th Symposium on Theoretical Aspects of Computer Science (STACS), 2008.

• V. Chakaravarthy, S. Roy.
  Oblivious Symmetric Alternation. (postscript)
  23rd Symposium on Theoretical Aspects of Computer Science (STACS), 2006.

• J. Cai, V. Chakaravarthy.
  On Zero Error Algorithms Having Oracle Access to One NP Query. (postscript)
  11th International Computing and Combinatorics Conference (COCOON), 2005.
  Journal of Combinatorial Optimization , 11(2), 2006. Special issue on selected papers from the above conference.

• J. Cai, V. Chakaravarthy, D. van Melkebeek.
  Time-Space Tradeoff in Derandomizing Probabilistic Logspace. (postscript)
  21st Symposium on Theoretical Aspects of Computer Science (STACS), 2004.
  Theory of Computing Systems , 39(1), 2006. Special issue on selected papers from the above conference.

• J. Cai, V. Chakaravarthy, L.A. Hemaspaandra, M. Ogihara.
  Competing Provers Yield Improved Karp--Lipton Collapse Results. (postscript)
  20th Symposium on Theoretical Aspects of Computer Science (STACS), 2003.
  Information and Computation , 198(1), 2005.

Databases: Theory & Systems

• V. Chakaravarthy, V. Pandit, Y. Sabharwal.
  Analysis of Sampling Techniques for Association Rule Mining. (pdf)
  12th International Conference on Database Theory (ICDT), 2009.

• M. Bhide, V. Chakaravarthy, K. Ramamritham, P.Roy.
  Keyword Search over Dynamic Categorized Information. (pdf)
  25th International Conference on Data Engineering (ICDE), 2009.

• V. Chakaravarthy, H.Gupta, P. Roy, M. Mohania.
  Efficient Techniques for Document Sanitization. (pdf)
  17th ACM Conference on Information and Knowledge Management (CIKM), 2008.

• V. Chakaravarthy, V. Pandit, S. Roy, P. Awathi, M. Mohania.
  Decision Trees for Entity Identification: Approximation Algorithms and Hardness Results. (postscript)
  26th ACM Symposium on Principles of Database Systems (PODS), 2007.

• V. Chakaravarthy, H. Gupta, P. Roy, M. Mohania.
  Efficiently Linking Text Documents with Relevant Structured Information. (pdf)
  32nd International Conference on Very Large Databases (VLDB), 2006.

• R. Kaushik, R. Ramakrishnan, J. Naughton, V. Chakaravarthy.
  Synopses for Query Optimization: A Space-Complexity Perspective. (postscript)
  23rd ACM Symposium on Principles of Database Systems (PODS), 2004.
  ACM Transactions on Database Systems , 30(4), 2005. Special issue on selected papers from the above conference.

• R. Krishnamurthy, V. Chakaravarthy, R. Kaushik, J. Naughton.
  Recursive XML Schemas, Recursive XML Queries, and Relational Storage: XML-to-SQL Query Translation. (postscript)
  20th International Conference on Data Engineering (ICDE), 2004.

• R. Krishnamurthy, V. Chakaravarthy, J. Naughton.
  On the Difficulty of Finding Optimal Relational Decompositions for XML Workloads: a Complexity Theoretic Perspective. (pdf)
  9th International Conference on Database Theory (ICDT), 2003.

• J. Cai, V. Chakaravarthy, R. Kaushik, J. Naughton.
  On the Complexity of Join Predicates. (postscript)
  20th ACM Symposium on Principles of Database Systems (PODS), 2001.

Other Topics

• V. Chakaravarthy, A. Kumar, S. Roy, Y. Sabharwal
  Resource Allocation for Covering Time Varying Demands. (pdf)
  19th European Symposium on Algorithms (ESA), 2011.

• V. Chakaravarthy, S. Roy.
  Approximating Maximum Weight K-Colorable Subgraphs in Chordal Graphs. (pdf)
  Information Processing Letters 109(7), 2009.

• V. Chakaravarthy.
  New Results on the Computability and Complexity of Points-to Analysis. (postscript)
  30th ACM Symposium on Principles of Programming Languages (POPL), 2003.

• V. Chakaravarthy, R. Krishnamurthy.
  The Problem of Context Sensitive String Matching. (postscript)
  13th Symposium on Combinatorial Pattern Matching (CPM), 2002.

• V. Chakaravarthy, S. Horwitz.
  On the Non-Approximability of Pointer Analysis. (postscript)
  Acta Informatica 38(8), 2002.

• V.Radhakrishnan, V. Chakaravarthy, K.Krithivasan.
  Pattern Matching in Matrix Grammars.
  Journal of Automata, Languages and Combinatorics 3(1), 1998.

• V. Chakaravarthy, K.Krithivasan.
  A Note on Extended H Systems with Permitting/Forbidden Contexts of Radius One.
  Bulletin of the EATCS, Vol 62, 1997.