Publications

• The VPN Conjecture is true
  (with N. Olver and F. B. Shepherd)
  STOC 2008


• A combinatorial approach to nearest neighbor search
  (with Y. Lifshits and H. Schuetze )
  To appear in First ACM International Conference on Web Search and Data Mining (WSDM 2008)


• An algorithmic approach to identification of rigid domains in proteins
  (with V. Choi)
  Algorithmica 48 (2007), no. 4, 343-362 (special issue on algorithmic methodologies for processing protein structures, sequences and networks)

• Lower bounds for circuits with MOD gates
  (with A. Chattopadhyay, P. Pudlak, D. Therien)
  IEEE Symp. on Foundations of Computer Science (FOCS 2006)

• An Efficient Approximation Algorithm for Point Pattern Matching Under Noise
  (with V. Choi)
  Latin American Theoretical Informatics Conference (LATIN 2006)

• Lower Bounds for The Noisy Broadcast Problem (preliminary full version)
  (with G. Kindler and M. Saks)
  IEEE Symposium on Foundations of Computer Science (FOCS 2005) (conference version)
  To appear in the special issue of SIAM. J. of Comp. for FOCS 05
  

• Rounds vs Queries Trade-off in Noisy Computation (preliminary full version)
  (with M. Saks)
  ACM-SIAM Symposium on Discrete Algorithms (SODA 2005)
  Submitted for journal publication
  

• The Graham-Knowlton Problem Revisited
  (with S. Lodha and S. Muthukrishnan)
  Third International Conference on FUN WITH ALGORITHMS (FUN 2004)
  Theory Comput. Syst. 39 (2006), no. 3, 399-412 (Special issue of Theory of Computing Systems for FUN04)

• A Parallel Search Game
  (with M. Saks)
  Random Structures and Algorithms 27 (2005), no. 2, 227-234

• Combinatorial Characterization of Shape Complementarity in Rigid Protein Docking
  (with V. Choi)
  Fifteenth Annual Symposium on Combinatorial Pattern Matching (CPM 2004), LNCS 3109, pp 285-296

• Optimal Separation between EROW and CROW PRAMs (preliminary full version)
  (with M. Saks and S. Venkatesh)
  Eighteenth IEEE Conf. on Computational Complexity 2003
  

• Optimal Bandwidth Reservation Schedule in Cellular Network
  (with S. Ganguly, B. Nath)
  IEEE INFOCOM 2003

---