Navin Goyal


I am a postdoc in the Algorithms and Randomness Center in the College of Computing of Georgia Tech.
My host is Santosh Vempala . My research interests are in theoretical computer science, and I also enjoy
working on applied problems where insights from theoretical CS can be brought to bear. Within theoretical CS
I am interested in various aspects including both algorithms and computational complexity.

Contact Information

Teaching
COMP 531 (an introductory graduate course in computational complexity in Winter 2006 at McGill university)

Some selected publications (all of my publications are available here )

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


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


• 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
  

Misc.
A list of open problems I compiled for the AIM Workshop on Algorithmic Convex Geometry

---