Rakesh Venkat

Other Stuff

Smile! Rakesh Venkat

Contact address:
Room 210, Academic Block B,
Department of Computer Science and Engineering,
I.I.T. Hyderabad,
Sangareddy, Telangana 502285

Contact :
rakesh AT cse DOT iith DOT ac DOT in
Phone: 040-2301-6369

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 currently taking on summer interns. If you email me regarding a position, please 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. BullsEye : Scalable and Accurate Approximation Framework for Cache Miss Calculation. ACM Trans. Archit. Code Optimization, 2023
    Nilesh Rajendra Shah, Ashitabh Mishra, Antoine Maine, Rakesh Venkat, and Ramakrishna Upadrasta (in authorship order)
    Publisher version
  2. A Refined Approximation for Euclidean k-Means Information Processing Letters, 2022
    with Fabrizio Grandoni, Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman
    Publisher Version | arXiv version
  3. Planted Models for k-way Edge and Vertex Expansion FSTTCS 2019
    With Anand Louis
    Conference Version
  4. Semi-Random Models with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery (ICALP 2018)
    With Anand Louis
    Conference Version | arXiv (Full Version)
  5. Approximating Sparsest Cut in Low-Rank Graphs via Embeddings From Approximately Low-Dimensional Spaces. (APPROX 2017)
    With Yuval Rabani
  6. Multiplayer Parallel Repetition for Expanding Games. (ITCS 2017)
    With Irit Dinur, Prahladh Harsha and Henry Yuen
  7. Embedding approximately low dimensional l22 metrics into l1 (FSTTCS 2016)
    With Amit Deshpande and Prahladh Harsha
    Conference Version | arXiv
  8. On Fortification of Projection Games (RANDOM 2015)
    With Amey Bhangale, Ramprasad Saptharshi and Girish Varma
    Conference version | arXiv
  9. Guruswami-Sinop rounding without Higher Level Lasserre (APPROX 2014)
    With Amit Deshpande
    Conference Version | arXiv


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

Courses Taught

Other Interests

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