Amatya Sharma
Department of Computer Science and Engineering
University of Michigan, Ann Arbor
amatya [at] umich.edu
I am a Ph.D. Candidate in Theoretical Computer Science at University of Michigan, Ann Arbor, where I am fortunate to be co-advised by Nikhil Bansal and Euiwoong Lee. I received my Dual Degree (B.Tech. + M.Tech.) from the Department of Computer Science and Engineering at IIT Kharagpur.
My research interests include approximation algorithms, constraint satisfaction problems, online algorithms, randomized algorithms, parameterized algorithms, and algorithmic game theory.
I have been fortunate to collaborate with these amazing people on research papers.
My research spans approximation algorithms, online algorithms, randomized algorithms, parameterized algorithms, and algorithmic game theory. My prior work includes approximation and parameterized algorithms for computational geometric and game-theoretic problems. (Note: For theory papers, author names are listed alphabetically.)
Amatya Sharma, Santhoshini Velusamy
arXiv preprint, 2026.
Characterizes the single-pass streaming complexity of CSP satisfiability, up to logarithmic factors, by the non-redundancy of the constraint language.
Amatya Sharma, Santhoshini Velusamy
arXiv preprint.
Gives a near-complete classification of non-redundancy growth for low-arity symmetric Boolean predicates, exact through arity 4 and for all but two arity-5 predicates.
Aditya Anand, Euiwoong Lee, Davide Mazzali, Amatya Sharma
In APPROX 2025.
We continue the study of complete instances for minimization constraint satisfaction problems and give a polylogarithmic approximation for Min-Not-All-Equal-3-SAT on complete instances.
Aditya Anand, Euiwoong Lee, Amatya Sharma
In SODA 2025.
We initiate the study of complete instances for minimization constraint satisfaction problems and prove algorithmic results for Min-2CSP and related k-CSPs.
Nikhil Ayyadevara, Ashish Chiplunkar, Amatya Sharma
In FSTTCS 2024.
We present a decomposition approach for the online weighted k-server problem.
Arindam Khan, Arnab Maiti, Amatya Sharma, Andreas Wiese
In SoCG 2021; contributed talk at HALG 2021.
We give a PPTAS for the 2D Knapsack problem in a guillotine-separable setting, improving over the previous best approximation factor of 3.
Arindam Khan, Aditya Lonkar, Arnab Maiti, Amatya Sharma, Andreas Wiese
In ICALP 2022.
We give a (3/2 + ε)-approximation algorithm for 2D Strip Packing in a guillotine-separable setting, including a PPTAS.
Palash Dey, Arnab Maiti, Amatya Sharma
In CALDAM 2021.
We study parameterized algorithms for Liquid Democracy, a voting system where voters may delegate their votes.
Selected talks I have given at conferences, workshops, and classes.
Amatya Sharma
HALG 2021 Contributed Talk, May 2021.
Presented joint work with Arindam Khan, Arnab Maiti, and Andreas Wiese.
Amatya Sharma
CALDAM 2021 Paper Presentation, February 2021.
Presented joint work with Palash Dey and Arnab Maiti.
Amatya Sharma
Parameterized Algorithms (CS60083) Course Presentation, November 2020.
Talk on bidimensionality and bidimensional problems, a tool for developing parameterized algorithms via treewidth.
Dewang Modi and Amatya Sharma
Deep Learning (CS60010) Learning Paper Presentation, April 2021.
Semester paper presentation in Deep Learning (CS60010) at IIT Kharagpur on an EECVW 2020 paper on mitigating dataset imbalance via joint generation and classification.
Below is a summary of my experience, including internships and teaching roles.
Below are some of the awards and achievements I have received throughout my academic career.
Most of the curriculum courses I have taken are in close proximity to theoretical computer science. I have also taken elective classes in AI, including reinforcement learning and natural language processing.
Approximation and Online Algorithms (EECS 598-0101, CS60023), Parameterized Algorithms (CS60083), Algorithmic Game Theory (CS60025), Randomized Algorithms (CS60029), Advanced Graph Theory (CS60047), Computational Geometry (CS60064), Theory of Computation (CS41001), Computational Complexity (CS60043), Lattices in Cryptography (EECS 598), Selected Topics in Algorithms (CS60086), Cryptography & Network Security (CS60065), and Linear Algebra (MA20105).
Discrete Mathematics, Algorithms, Operating Systems, Computer Networks, and Software Engineering.
Java Cryptography Architecture, Git, Bitbucket, JUnit, MySQL, LaTeX, MATLAB, SolidWorks, HTML, CSS, PHP, JSP, Java, Python, C++, C, Bison, Yacc, and FLEX.
In addition to published work, I have explored numerous projects, including theory CS, computer architecture, software engineering, machine learning, and compilers.
Palash Dey, Amatya Sharma
We analyze pure-strategy Nash equilibria in binary networked public good games and study associated hardness and XP algorithms.
Palash Dey and Amatya Sharma, 2021.
Developed parameterized algorithms for the game-theoretic problem of computing Margin of Victory for tournament solutions.
Faraaz Mallick, Dewang Modi, Amatya Sharma
Participating in ML Reproducibility Challenge 2021.
Implemented and experimented with a new model based on image reconstruction and augmentation. Reproduced an AAAI 2021 paper on Improving Sample Efficiency in Model-Free Reinforcement Learning from Images.
Amatya Sharma, Shankar Venugopal, and Mohana Kera
Summer Intern Project, ExaCC Team, Oracle R&D Server Technology.
Implemented a Java library for secure HTTP authentication using Java Cryptography Architecture.
Prince Bharadwaj, Adarsh Goyal, Nwe Ni Kyaw, and Amatya Sharma
Advanced Machine Learning Course Term Project.
A term project on local and global approximation techniques for Gaussian process kernels, followed by experiments on numerous approximation techniques.
Udit Desai and Amatya Sharma
Software Engineering Course Term Project, November 2020.
Full-stack development of an online bookstore using HTML, CSS, JSP, and MySQL.
Divyang Mittal and Amatya Sharma
Compilers Course Project, November 2019.
Implemented a compiler for TinyC, a subset of C with a reduced set of functionalities, using Yacc, Bison, FLEX, C, and C++.
Nikhil Shah and Amatya Sharma
Computer Architecture Course Term Project, November 2019.
Developed a reduced instruction set computer processor and simulated it on FPGA Spartan 3 boards using Verilog.
I am a coffee aficionado straight from the Himalayas. To know more about the coffees I have had, scenic places I have been to, or my music taste, check out this webpage.
Amatya Sharma
2741 Bob and Betty Beyester Building
Ann Arbor, MI (US)
48109
Email: amatya[at]umich.edu
Last update: 05/2026. Website adapted from Jon Barron.