Rakesh Venkat

Other Stuff

Smile! Rakesh Venkat

Contact address:
Academic Block C, Room 312-F Department of Computer Science and Engineering,
I.I.T. Hyderabad,
Sangareddy, Telangana 502285

Contact :
rakeshvenkat AT iith DOT ac DOT in

I am an Assistant Professor in the Department of Computer Science and Engineering, at Indian Institute of Technology, Hyderabad (IIT-H).

Previous affiliations: HUJI, Israel -- TIFR, Mumbai -- IIT-Bombay

Summer Internship Applicants: I am not taking any interns for this summer. If you email me regarding positions, do not expect a reply.


My broad research area is Theoretical Computer Science. In particular, approximation algorithms, hardness of approximation, and communication complexity. Below are links to pre-prints of my publications and manuscripts.


  1. Planted Models for $k$-way vertex and edge expansion. (To appear in FSTTCS 2019)
    With Anand Louis
    arXiv (Full Version)
  2. Semi-Random Models with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery (ICALP 2018)
    With Anand Louis
    Conference Version | arXiv (Full Version)
  3. Approximating Sparsest Cut in Low-Rank Graphs via Embeddings From Approximately Low-Dimensional Spaces. (APPROX 2017)
    With Yuval Rabani
  4. Multiplayer Parallel Repetition for Expanding Games. (ITCS 2017)
    With Irit Dinur, Prahladh Harsha and Henry Yuen
  5. Embedding approximately low dimensional l22 metrics into l1 (FSTTCS 2016)
    With Amit Deshpande and Prahladh Harsha
    Conference Version | arXiv
  6. On Fortification of Projection Games (RANDOM 2015)
    With Amey Bhangale, Ramprasad Saptharshi and Girish Varma
    Conference version | arXiv
  7. Guruswami-Sinop rounding without Higher Level Lasserre (APPROX 2014)
    With Amit Deshpande
    Conference Version | arXiv


  1. Hypergraph two-coloring in the Streaming model (Under submission.)
    With Jaikumar Radhakrishnan and Saswata Shannigrahi
    arXiv preprint

Technical Reports and Theses

  1. On Sparsest Cut and Parallel Repetition Ph.D. Thesis, 2017.
  2. Parallel Repetition Theorem and Related Results Research project report, 2010.
    pdf | Talk slides
  3. Searching and Ranking in Entity Relation Graphs Master's Thesis, 2008.

Courses Offered

Other Interests

I enjoy trekking, long-distance running, playing the piano, and various sports.