Viraj Kumar     


Department of Computer Science
University of Illinois at Urbana-Champaign
201, N. Goodwin Av., Urbana, IL-61801, USA
(217) 244-9847

EDUCATION

Ph.D. in Computer Science, University of Illinois at Urbana-Champaign

Dissertation title: Detecting and Explaining Faults in Software Programs

Dissertation committee: Professors Mahesh Viswanathan (advisor), Michael C. Loui, P. Madhusudan and Leonard B. Pitt

Expected date of completion: May, 2007


M.S. in Computer Science, University of Illinois at Urbana-Champaign

GPA: 4.0, Required courses completed in Spring 2002

Thesis title: An Efficient Decision Procedure for the Word Problem in the Union of Equational Theories

Thesis advisor: Professor Mehdi Harandi
  Thesis completed: Summer 2004


M.S. in Applied Statistics and Informatics, Indian Institute of Technology Bombay

GPA: 9.54 (out of 10.0)

Thesis title: Implementing Graph Partitioning using LEDA

Thesis advisor: Professor Sachin B. Patkar

Completion: 2000


B.S. in Mathematics, St. Stephen's College, Delhi University

Grade: First Division

Completion: 1998


TEACHING EXPERIENCE

Instructor, Department of Computer Science, UIUC

CS 273   Introduction to Theory of Computation   Summer 2006, Summer 2007 (anticipated)
CS 232   Computer Architecture II   Fall 2006

Guest Lectures, Department of Computer Science, UIUC

CS 473   Algorithms (Undergraduate section)   Spring 2005
  Lecture on Randomized Algorithms
CS 273   Introduction to Theory of Computation   Summer 2005
  Four lectures on Graph Theory
CS 475   Formal Models of Computation   Fall 2006
  Lecture on simplifying context-free grammars
Two sample clips from this lecture:   Discovering connections   Establishing internal links

Teaching Assistant, Department of Computer Science, UIUC

CS 321   Introduction to Programming Languages   Spring 2002
CS 232   Computer Architecture II   Fall 2005 and Spring 2006
CS 473   Algorithms (Undergraduate section)   Spring 2007

Teaching Awards

I was ranked on the Incomplete List of Teachers Ranked as Excellent by their Students for Fall 2005 and Spring 2006. I was rated "outstanding" for the latter semester. Rankings for Fall 2006 are not available, but I received the following Midterm ratings for the course. These ratings are based on student impressions of the instructor, and are relative to all other courses taught in that semester:

Highest student ratings for the statements: The professor cares if I learn the material and The professor does not merely regurgitate the lecture notes.
Second-highest rating for the statement: I can get help when I need it.
Sixth-highest rating for the statements: The course objectives are clearly stated, The grading criteria are clearly explained, The lecturer clearly presents the material and The lecture notes are useful.


Relevant Coursework
EOL 585, College Teaching: A preparatory course for college teaching, with emphasis on teaching practices based on current research literature on college teaching and learning. The final course project is a proposal for a classroom research project with the following components: a research question, justification for its significance, review of the related literature, and a plan to gather evidence that addresses the question. My research project posed the following question:

Will the ability of students to construct formal proofs improve if they were exposed not just to examples of correct proofs, but also to examples of incorrect proofs?


RESEARCH EXPERIENCE

August 2002 to July 2005

Research assistant with Professor Mahesh Viswanathan, Department of Computer Science, University of Illinois at Urbana-Champaign. My research focused on algorithmic aspects of software verification, with emphasis on:

Conformance testing: Given a correctness specification, a conformance test is a test suite that passes precisely those program implementations that conform to the specification. Without certain strong restrictions, the size of the test suite is exponential in the size of the implementation, which is impractical. Research focused on developing a robust notion of approximate conformance testing that trades precision for feasible (i.e. polynomial-sized) test suites.

Pushdown models: Fault detection for finite-state models has been well studied. However, to faithfully capture function calling in programs, it is necessary to use pushdown automata (PDA) models. Unfortunately, the lack of key decidability and closure properties for the class of PDAs has prevented easy extension of existing results for finite-state models to this larger class. Research focused on extending results to the robust sub-class of visibly pushdown automata (VPA) that retains the necessary properties. Despite restrictions on the way the stack is manipulated, VPAs can model program call-stacks.

Error explanation: Counter-examples (e.g. those generated by conformance tests) demonstrate the existence of errors but are not succinct enough to isolate their cause. Several heuristics for error explanation have been proposed, which make sophisticated use of SAT solvers and model checkers. Research focused on characterizing the complexity of the underlying problems to determine when the use of such tools was justified.

August 2000 to December 2001

Research assistant with Professor Mehdi Harandi, Department of Computer Science, University of Illinois at Urbana-Champaign: Decision procedures for the word problem in the union of equational theories.

Under certain restrictions, decision procedures for the word problem in two equational theories can be combined modularly to solve the word problem in the union of the two theories. Research focused on enhancing and implementing one such algorithm. The enhancements simplified the algorithm and allowed a thorough complexity analysis of running time to be conducted. As a result, some existing exponential bounds were improved to sub-exponential or even polynomial-time bounds.


RESEARCH PAPERS AND PUBLICATIONS

Refereed Conference Papers

  1. Viraj Kumar and Mahesh Viswanathan, Conformance Testing in the presence of Multiple Faults, SODA 2005.

  2. Nirman Kumar, Viraj Kumar and Mahesh Viswanathan, On the Complexity of Error Explanation, VMCAI 2005.

  3. Rajiv Alur, Viraj Kumar, P. Madhusudan and Mahesh Viswanathan, Congruences for Visibly Pushdown Languages, ICALP 2005.

  4. Viraj Kumar, P. Madhusudan and Mahesh Viswanathan, Minimization, Learning, and Conformance Testing of Boolean Programs, CONCUR 2006.

REFERENCES

Available on request.