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), fortunate to be co-advised by Nikhil Bansal and Euiwoong Lee. I obtained my Dual Degree (BTech+MTech) from Computer Science and Engineering DepartmentIndian Institute of Technology (IIT) Kharagpur. I'm interested in Theoretical CS, including Approximation, Online, Randomized, Parameterized Algorithms, Algorithmic Game Theory. My prior research work revolves around the design and analysis of Approximation, Online and Parameterized Algorithms for Computational Geometric, Game-Theoretic and Graph Problems.

Over the past years, I have had great collaborations including Prof. Ashish Chiplunkar (IIT Delhi), Prof. Arindam Khan (IISc Bangalore), Prof. Andreas Wiese (UofChile), and Prof. Palash Dey (IIT Kharagpur). All of them have led to impactful results as mentioned in Publications Section.

In 2019, We, a group of 5 students, started an initiative Annapurna to fight against food wastage and global hunger. More information here.

Why Date Me??

Erdos Number : 3

News

[Aug 2022] Joined as a PhD in Computer Science, U of Michigan-Ann Arbor, in Fall'22.
[Mar 2022] Received PhD offers from U of Michigan-Ann Arbor, Georgia Tech, U of Toronto, and EPFL Switzerland.
[Oct 2021] Relishing the experience of teaching [1, 2] in Algorithmic Game Theory(CS60025).
[Aug 2021] Will be a teaching Algorithmic Game Theory (CS60025) as a Teaching Assistant under Prof. Palash Dey (CSE, IIT Kharagpur) in Autumn 2021.
[Jul 2021] Received a full time pre-placement offer as a Member of Technical Staff at Server Technology (RnD) Oracle, Bangalore.
[May 2021] I will be presenting our work On Guillotine Separable Packings for the Two-dimensional Geometric Knapsack Problem as a contributed talk in HALG'21.
[Apr 2021] I will be interning at Server Technology (Research and Development) Oracle, Bangalore from May-Jul'21.
[Feb 2021] Our work On Guillotine Separable Packings for the Two-dimensional Geometric Knapsack Problem got accepted at SoCG'21 (link to paper). From IIT Kharagpur, this is the first SoCG publication in the last 26 years.
[Nov 2020] My first publication!!! Our work On Parameterized Complexity of Liquid Democracy got accepted at CALDAM'21 (paper)

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.)

On Guillotine Separable Packings for the 2D Geometric Knapsack Problem
Arindam Khan, Arnab Maiti, Amatya Sharma and Andreas Wiese
In 37th International Symposium on Computational Geometry (SOCG 2021)
Contributed Talk HALG 2021

[SoCG Version] [arXiv] [SoCG Presentation] [HALG Presentation] [Poster]

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.

Two Dimensional Guillotine Strip Packing
Arindam Khan, Aditya Lonkar, Arnab Maiti, Amatya Sharma and Andreas Wiese
The 49th EATCS International Colloquium on Automata, Languages and Programming (ICALP) 2022
[arXiv]

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

On Parameterized Complexity of Liquid Democracy
Palash Dey, Arnab Maiti and Amatya Sharma,
7th Annual International Conference on Algorithms and Discrete Applied Mathematics
CALDAM 2021

Full Version | Conference Version | Video

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.

Network Design for Binary Networked Public Good Games
Palash Dey, and Amatya Sharma
Manuscript | Slides

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

A Decomposition Approach to Weighted k-server problem
Nikhil Ayyadevara, Ashish Chiplunkar, and Amatya Sharma,

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

The Art Gallery Problem : A Survey
Dewang Modi, Adarsh Singh Parihar and Amatya Sharma,
Submitted to ACM Computing Surveys Journal

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.

Parameterized Complexity of Margin of Victory
Palash Dey and Amatya Sharma,

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

Image Augmentation and Auxiliary Loss Duo
Faraaz Mallick Dewang Modi and Amatya Sharma
Participating in ML Reproducibility Challenge 2021
Paper | Presentation

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.

HTTP Authentication
Amatya Sharma,
Shankar Venugopal, and Mohana Kera
Summer Intern Project, ExaCC Team, Oracle (RnD) Server Technology

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

Gaussian Process Kernels
Prince Bharadwaj, Adarsh Goyal, Nwe Ni Kyaw and Amatya Sharma
Advanced Machine Learning Course Term Project
pdf

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

Shoten : An e-BookStore
Udit Desai and Amatya Sharma,
Software Engineering Course Term Project,
November 2020

Github Repository

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

TinyC Compiler
Divyang Mittal and Amatya Sharma,
Compilers Course Project
November 2019

Github Repository

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++

RISC Processor
Nikhil Shah and Amatya Sharma,
Computer Architecture Course Project
November 2019

Github Repository

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

Talks By Me

On Guillotine Separable Packings for the Two-dimensional Geometric Knapsack Problem | HALG'21
Amatya Sharma,
HALG'21 Contributed Talk, May 2021
HALG Presentation | Poster

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.

On Parameterized Complexity of Liquid Democracy | CALDAM'21
Amatya Sharma,
CALDAM'21 Paper Presenation, Feb 2021
YouTube Link | pdf Slides | paper

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.

Bidimensionality : Parameterized Algorithms
Amatya Sharma,
Parameterized Algorithms (CS60083) Course Presentation, November 2020
YouTube Link | pdf Slides

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.

Mitigating Dataset Imbalance via Joint Generation & Classification
Dewang Modiand Amatya Sharma
Deep Learning (CS60010) Learning Paper Presentation April, 2021
Youtube Video | pdf Slides

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

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.

Algorithms & Maths

Approximation and Online Algorithms (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), Selected Topics in Algorithms (CS60086), Cryptography & Network Security (CS60065), and Linear Algebra (MA20105).

Artificial Intelligence & Machine Learning

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

Other Courses and Software Tools/Skills

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...

I am a coffee aficionado straight from the himalayas. To know more about the coffees I have had, scenic places I've been to, or my music taste check out this webpage.

"It ain't easy maintaining monotonicity."
- Aay


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