Projects

Topic Students
LP-based Approximability for Strict CSPs
Faster and simpler algorithms for multicommodity flow
Dual Lower Bounds for Approximate Degree
Thesis: Satyen Kale, Chapter 2,3.1,3.2. Aakash Lahoti, Anay, Hritvik
Exponential Lower Bounds for Polytopes in Combinatorial Optimization Diptajit, Gargi and Shashank
Strong Parallel Repetition Theorem for Quantum XOR Proof Systems
Approximate max-flow min-cut thm for uniform multicommodity flow Aditya, Omkar, Yash
New Approximation Algorithm for the maximum satisfiablility problem Aman, Ankush and Pushkar
Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue Abhay, Bharat, Harshit
Constructive Algorithms for Discrepancy Minimization Aakash Singh, Kunal and Siddhant
Robust classification Hemant, Mihir, Siddharth
MAP inference in graphical models Abhishek, Mahesh, Suraj
Projection free learning Lavish, Nikhil and Shubham