Manan Sanghi

A brief two page resume is available for download in pdf / ps


Academic Background


B. Tech. in Computer Science and Engineering  (1998-2002)

from Indian Institute of Technology, Delhi, India

CGPA 9.135/10.0                     

Departmental Rank 4 / 45




MS in Computer Science

from Northwestern University, USA

CGPA : 4.0/4.0




Ph.D. in Computer Science (underway)

from Northwestern University, USA

Candidate in Department of Computer Science

CGPA (till date) : 4.0/4.0





Research Interests


Design and analysis of Algorithms, combinatorial optimization, bioinformatics, pattern matching, musical information retrieval, online auctions, incentive compatible algorithms







“Polyphonic Musical Sequence Alignment for Database Search”

  Bryan Pardo, and Manan Sanghi

ISMIR 2005, 6th International Conference on Music Information Retrieval, London, England, September 11-15, 2005


“Randomized Fast Design of Short DNA Words”

  Ming-Yang Kao, Manan Sanghi, and Robert  Schweller.

Proceedings of the 32nd International Colloquium on Automata, Languages and  Programming  (ICALP), Lisboa, Portugal, July 11-15, 2005, pp. 1275-1286.


“Sub-linear Algorithms for Landmark Discovery from Black Box Models”

  Manan Sanghi, Praveen Paritosh, and Reuben Thomas.

  Qualitative Reasoning 2005.


“An Optimization Problem in Adaptive Virtual Environments”

   A. Sundararaj, M. Sanghi, J. Lange, and P. Dinda 

Proceedings of the ACM SIGMETRICS Seventh Workshop on Mathematical Performance Modeling and Analysis (MAMA 2005)

To appear in ACM SIGMETRICS Performance Evaluation Review.


“Flexible Word Design and Graph Labeling”

  Ming-Yang Kao, Manan Sanghi, and Robert Schweller.

  Under submission


“An Approximation Algorithm for a Bottleneck Traveling Salesman Problem”

  Ming-Yang Kao, and  Manan Sanghi.

  Under submission


“Hamsa: Fast Signature Generation for Zero-day Polymorphic Worms with Provable Attack Resilience”

    Under submission


“Magnolia: Enabling Keyword Searches in Structured P2P Systems”

    Under preparation (A poster at NSDI 2005, Boston)


“Recognition Algorithms for Tree Interval Graphs”

    Under preparation


“Strategy-proof Posted Price Mechanisms for Digital Goods”

    Under preparation





Teaching Experience


- Teaching Assistant for Mathematical Foundations of Computer Science (Winter 2005)

- Teaching Assistant for Algorithmic Techniques for Bioinformatics (Fall 2003, Fall 2004)

- Teaching Assistant for Analysis and Design of Algorithms (Spring 2004)





Computer related skills 


Experience in: OpenGL, socket programming, simulator design, LaTeX, graphics programming, parsing, GUI development, Matlab, Netlogo, FPGA based designing and synthesis, XILINX hardware  development tools etc.




Programming Languages: C, C++, Java, LISP, Perl, Pascal, SML, Scheme, MIPS assembly language, HTML, VHDL





Awards and Honors


- Piros fellowship award in 2002

- Merit award for being among the top 7% in Computer Science Department, IIT Delhi

- 12th rank in Regional Mathematical Olympiad (RMO)

- 3rd rank in Junior Mathematical Olympiad (JMO)

- 97th rank in IIT-JEE 1998 among 130,000 students

- Won a number of awards in Mathematics, Programming, Debates, Poetry and Group Discussions





Undergraduate Research Experience


Distribution Sensitive Algorithms

(B. Tech. Project under guidance of Prof. Sandeeep Sen, IIT, Delhi)

Conventionally the time complexity of an algorithm is measured with respect to input size. However, often the complexity of the problem depends not only on the input size but also on the input distribution. We explored ways to capture this stronger notion of complexity of algorithms, specifically for the problem of finding maximal vectors.




Algorithms for Passive Network Monitoring

(Summer Internship at IBM, IRL)

The goal of the project was to estimate various metrics like throughput, goodput, losses and delays between two communicating nodes in the internet from an intermediate node lying in the communication path passively (ie without introducing additional traffic in the network). We designed and implemented algorithms for the purpose on the actual network to compare the estimated metrics with the actual.







Randomized Fast Design of Short DNA Words

32nd International Colloquium on Automata, Languages and Programming  (ICALP 2005), Lisboa, Portugal, 2005


Randomized Fast Design of Short DNA Words

50th Midwest Theory Day, University of Illinois, Urbana Champaign, Illinois, USA, 2005


Flexible Word Design and Graph Labeling

51st Midwest Theory Day, University of Wisconsin, Milwaukee, Illinois, USA, 2005






Selected Courses


Computer Science

Algorithm related: Analysis and Design of Algorithms , Advanced Algorithms,  Algorithmic Techniques in Bio-Informatics, Introduction to Logic for Computer Science, Theory of Computation, Computational Geometry,

Others: Compilers, Computer Graphics, Advanced Computer Graphics, Computer Architecture, Computer Networks, File Structures, Operating Systems, Artificial Intelligence, Signals and Systems, Machine Learning





Optimization - Methods & Applications , Probability Theory and Stochastic Processes, Real Analysis, Differential Equations and Complex Analysis.





Game Theory, Strategic Decision Making, Technical Communications, A Constructionist Approach to the Design of Learning Environments