Publications

I'm interested in Theoretical Computer Science, including Approximation, Online, Randomized, Parameterized Algorithms, Algorithmic Game Theory. My prior research work revolves around the design and analysis of Approximation and Parameterized Algorithms for Computational Geometric and Game Theoretic Problems. (Note: For theory papers, author names are listed alphabetically.)

A PPTAS (Pseudo-Polynomial Time Approximation Scheme) for 2 Dimensional Knapsack problem in a Guillotine Separable arrangement improves the previous best approximation factor of 3.

(³⁄₂ + ε)-Polynomial time approximation algorithm for the 2 Dimensional Strip problem in a Guillotine Separable arrangement, complementing the lower bound of (³⁄₂ + o(ε)). Also, formulated PPTAS (Pseudo-Polynomial Time Approximation Scheme) for the same.

Design and Analysis of Parameterized Algorithms for the problem of Liquid Democracy that is a democracy with voters allowed to delegate their votes to others.

Algorithmic analysis of PSNE for Game Theoretic Problem of Networked Public Good Games. Established parameterized hardness and formulated XP-algorithms.

Formulated a online randomized algorithm for a variant of weighted k-server problem, and designed a technique towards mitigating the gap between established upper bound and lower bound complexities

Long Survey paper peruse NP-hardness, ∃R − Completeness, bounds and algorithms in approximation and parameterized complexity for the classic Art Gallery Problem and its variants.

Other Projects

Apart from published works, I have explored plenty of other projects, in Theory CS, Computer Architecture, Software Engineering (Full Stack Development), Machine Learning, Compilers etc.

Developed Parameterized Algorithms for Game-Theoretic problem of computing Margin of Victory for tournament solutions

Implemented and experimented with a new model based on image reconstruction and augmentation. Reproduced AAAI’21 paper on Improving Sample Efficiency in Model-Free Reinforcement Learning from Images.

Implemented Java Library for secure HTTP Authentication using Java Cryptography Architecture.

A term project on Local and Global Approximation techniques for Gaussian Process Kernels, followed by experiments on numerous approximation prevailing techniques.

Full Stack development of online bookstore employing HTML, CSS, JSP and MySQL

Implemented a Compiler for language TinyC, a subset of C with a reduced subset of functionalities with a parser and lexer with output as non-optimized machine-level assembly language instructions using Yacc, BISON, FLEX, C, C++

Developed a Reduced Instruction Set Computer Processor and simulated on FPGA Spartan 3 boards using VERILOG

Talks By Me

Presented our work (coauthored with Arindam Khan (IISc), Arnab Maiti (IIT Kharagpur), and Andreas Wiese (UoChile) on Guillotine Separable Packings for the Two-dimensional Geometric Knapsack Problem, held virtually from May 31 - June 3, 2021.

Presents our work (coauthored with Prof. Palash Dey and Arnab Maiti (I.I.T Kharagpur)) on Parameterized Complexity of Liquid Democracy at 7th Annual International Conference on Algorithms and Discrete Applied Mathematics (CALDAM'21) held virtually at I.I.T Ropar from February 11-13, 2021.

Talk on the concept of bidimensionality and bidimensional problems, a tool for developing parameterized algorithms for a vast set of problems employing the concept of tree-width.

Semester Paper Presentation in Deep Learning Course (CS60010) at Indian Institute of Technology (IIT) Kharagpur on a EECVW'20 by Aadarsh Sahoo et al., on Mitigating Dataset Imbalance via Joint Generation and Classification.

Experience

• UMich, Ann Arbor | Teaching Assistant of Intro to Algo (EECS 477). Aug. 2024 - Dec. 2024
• CSE, IIT Kharagpur | Teaching Assistant of Algorithms-1 Jan. 2022 - Apr. 2022
• CSE, IIT Kharagpur | Teaching Assistant of Algorithmic Game Theory Aug. 2021 - Dec. 2021
• CSE, IIT Delhi | Summer Intern Apr. 2021 - Present
• ExaCC, Oracle R&D | Summer Intern May. 2021 - Jul. 2021
• Dept. of Informatics, UiB Norway | Summer Intern May. 2020 - Jun. 2020
• CSA, IISc Bangalore | Summer Intern Dec. 2019
• CSA, IISc Bangalore | Summer Intern May. 2019 - Jul. 2019

Awards & Achievements

• University Rank 8 at IIT Kharagpur 2022
• Department Rank 5 in the Computer Science Department (IIT Kharagpur) 2022
• Awarded GATE Scholarship for Teaching Assistantship at CSE, Kharagpur. 2021
• Department Change (Secured rank in top 10 at IIT Kharagpur first year) 2017
• IIT-JEE Advanced 2017 (All India Rank 1464) 2017
• SJVN Merit Scholar for top performance in CBSE 12th Exam 2017
• National Talent Search Examination (NTSE) Scholar 2015
• Rashtriya Indian Military College (RIMC) Exam 2017 (All India Rank in top 60) 2013

Courses Taken

Most of the curriculum courses I have taken are in close vicinity to Theoretical Computer Science. I have also taken elective classes in the field of 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).

Reinforcement Learning (CS60077), Statistical Foundations of AI & ML (AI61004), Deep Learning (CS60010), Natural Language Processing (CS60075) and Advanced Machine Learning (CS60073).

Discrete Mathematics, Algorithms, Operating Systems, Computer Networks, Software Engineering.

Java Cryptography Architecture, GIT, BitBucket, JUnit, MySQL, LaTex, Matlab, SolidWorks, HTML, CSS, PHP, JSP, Java, Python, C++, C, BISON, Yacc, FLEX.

About Me...

Contact

Amatya Sharma
2741 Bob and Betty Beyester Building
Ann Arbor, MI (US)
48109
Email: amatya[at]umich.edu

Last update: 06/2024. Website adapted from Jon Barron