Amatya Sharma

Amatya Sharma

Ph.D. Candidate, Theoretical Computer Science
University of Michigan, Ann Arbor
amatya@umich.edu

Expected graduation: April 2027

I am on the job market, please reach out to me.

I am a Ph.D. candidate in Theoretical Computer Science at the University of Michigan, fortunate to be co-advised by Nikhil Bansal and Euiwoong Lee. I received my B.Tech. and M.Tech. in Computer Science from IIT Kharagpur.

My research interests include approximation, streaming, online, and parameterized algorithms, with a focus on constraint satisfaction problems, clustering, and combinatorial optimization.

Recent news

2027
Offered a long-term visitor position at the Simons Institute, UC Berkeley, January–April, for Symmetry in Efficient Computation with Local Constraints.
2027
Incoming participant in the Iliad Intensive in Berkeley, January 4–29.
2027
Spectral Dual Fitting for k-Means will appear at SODA 2027.
Nov 2026
New preprint on streaming Boolean CSPs under deletions, in submission to STOC 2027.
2026
Our ESA paper on streaming CSPs was invited to a special issue of Theoretical Computer Science.
Aug 2026
Presented my work on Streaming CSPs in ESA 2026.

My collaborators

I have been fortunate to work with these amazing people.

  • Aditya Anand
  • Nikhil Ayyadevara
  • Aditya Bandekar
  • Nikhil Bansal
  • Joshua Brakensiek
  • Moses Charikar
  • Ashish Chiplunkar
  • Vincent Cohen-Addad
  • Palash Dey
  • Nick Fisher
  • Ruiquan Gao
  • Fabrizio Grandoni
  • Arindam Khan
  • Vaibhav Krishan
  • Euiwoong Lee
  • Aditya Lonkar
  • Arnab Maiti
  • Davide Mazzali
  • Milind Prabhu
  • Aaron (Louie) Putterman
  • Ernest van Wijland
  • Santhoshini Velusamy
  • Andreas Wiese

Publications & manuscripts

Authors are listed alphabetically by surname, following the theory-CS convention.

Published & accepted papers

  1. Spectral Dual Fitting for k-Means

    Aditya Anand, Moses Charikar, Vincent Cohen-Addad, Ruiquan Gao, Fabrizio Grandoni, Euiwoong Lee, Amatya Sharma, Ernest van Wijland

    SODA 2027.

    arXiv
    Abstract

    A new dual fitting algorithm which gives improved approximation ratios of 3+ln2+ϵ (≈3.694) and 4.9+ϵ for k-Means in (high-dimensional) Euclidean and general metrics respectively.

  2. Characterizing Streaming Decidability of CSPs via Non-Redundancy

    Amatya Sharma, Santhoshini Velusamy

    ESA 2026. Invited to a special issue of Theoretical Computer Science.

    PaperarXivSlides
    Abstract

    Characterizes the single-pass streaming complexity of CSP satisfiability, up to logarithmic factors, by the non-redundancy of the constraint language.

  3. Min CSPs on Complete Instances II: A Polylogarithmic Approximation for NAE-3-SAT

    Aditya Anand, Euiwoong Lee, Davide Mazzali, Amatya Sharma

    APPROX 2025.

    arXivSlides
    Abstract

    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.

  4. Min CSPs on Complete Instances

    Aditya Anand, Euiwoong Lee, Amatya Sharma

    SODA 2025.

    PaperarXivSlides
    Abstract

    We initiate the study of complete instances for minimization constraint satisfaction problems and prove algorithmic results for Min-2CSP and related k-CSPs.

  5. A Decomposition Approach to the Weighted k-server Problem

    Nikhil Ayyadevara, Ashish Chiplunkar, Amatya Sharma

    FSTTCS 2024.

    arXivPaper
    Abstract

    We present a decomposition approach for the online weighted k-server problem.

  6. Two-Dimensional Guillotine Strip Packing

    Arindam Khan, Aditya Lonkar, Arnab Maiti, Amatya Sharma, Andreas Wiese

    ICALP 2022.

    arXiv
    Abstract

    We give a (3/2 + ε)-approximation algorithm for 2D Strip Packing in a guillotine-separable setting, including a PPTAS.

  7. On Guillotine Separable Packings for the 2D Geometric Knapsack Problem

    Arindam Khan, Arnab Maiti, Amatya Sharma, Andreas Wiese

    SoCG 2021; contributed talk at HALG 2021.

    PaperarXivSlides (SoCG)Slides (HALG)Poster
    Abstract

    We give a PPTAS for the 2D Knapsack problem in a guillotine-separable setting, improving over the previous best approximation factor of 3.

  8. On Parameterized Complexity of Liquid Democracy

    Palash Dey, Arnab Maiti, Amatya Sharma

    CALDAM 2021.

    arXivPaperVideo
    Abstract

    We study parameterized algorithms for Liquid Democracy, a voting system where voters may delegate their votes.

Preprints

  1. A New Characterization of Streaming Decidability of Boolean CSPs Under Deletions

    Aditya Bandekar, Amatya Sharma, Santhoshini Velusamy

    arXiv preprint. In submission to STOC 2027.

    arXiv
    Abstract

    Characterizes the single-pass streaming space complexity of Boolean CSP satisfiability under insertions and deletions in the strict-turnstile model using the integer capturing degree of the constraint language.

  2. Cores Characterize the One-Pass Streaming Complexity of CSPs

    Joshua Brakensiek, Aaron Putterman, Amatya Sharma, Santhoshini Velusamy

    arXiv preprint. Submitted to ITCS 2027.

    arXiv
    Abstract

    Uses cores of finite-domain CSP relations to characterize one-pass streaming complexity for satisfiability, approximate minimization, and exact optimization, with deterministic algorithms and matching lower bounds up to polylogarithmic factors.

  3. Non-Redundancy of Low-Arity Symmetric Boolean CSPs

    Amatya Sharma, Santhoshini Velusamy

    arXiv preprint. In submission to STACS 2027.

    arXiv
    Abstract

    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.

Manuscripts

  1. A Constant Approximation for Min-sum k-Clustering

    Aditya Anand, Moses Charikar, Ruiquan Gao, Fabrizio Grandoni, Euiwoong Lee, Amatya Sharma, Ernest van Wijland

    Submitted to STOC 2027.

  2. Group-Based Rounding for FPT k-Median

    Aditya Anand, Euiwoong Lee, Amatya Sharma

    Submitted to ITCS 2027.

  3. Treewidth Parameterization of Network Design for Public Goods Games

    Palash Dey, Amatya Sharma

    In submission to IJCAI 2027.

Experience

  1. Offered Long-Term Visitor · Simons Institute for the Theory of Computing, UC BerkeleyJan–Apr 2027

    Symmetry in Efficient Computation with Local Constraints.

  2. IncomingParticipant, Iliad Intensive · Iliad, Berkeley, CAJan 4–29, 2027

    Technical training in foundational AI alignment, including deep learning theory, agent foundations, and interpretability.

  3. Graduate Student Instructor · University of MichiganJan–Apr 2026

    EECS 281: Data Structures & Algorithms.

  4. Research Visitor · Toyota Technological Institute at ChicagoSep–Oct 2025

    Host: Santhoshini Velusamy. Research on streaming complexity and constraint satisfaction problems.

  5. Graduate Student Instructor · University of MichiganAug–Dec 2024

    EECS 477: Introduction to Algorithms.

  6. Teaching Assistant · IIT KharagpurJan–Apr 2022

    Algorithms 1.

  7. Teaching Assistant · IIT KharagpurAug–Dec 2021

    Algorithmic Game Theory.

  8. Research Intern · IIT DelhiApr–Oct 2021

    Host: Ashish Chiplunkar. Research on online algorithms.

  9. Software Engineering Intern · Oracle R&D, ExaCCMay–Jul 2021

    Implemented a Java library for secure HTTP authentication using the Java Cryptography Architecture.

  10. Research Intern · IISc BangaloreMay–Jul 2019; Dec 2019

    Host: Arindam Khan. Research in approximation algorithms and geometric packing.

Service

Selected talks

More

Additional information on awards, coursework, and earlier projects.

Beyond research

I am a coffee aficionado straight from the Himalayas. For coffees, mountains, photos, and music, visit my personal page ☕.

Contact

Amatya Sharma
amatya@umich.edu
Download CV

2741 Bob and Betty Beyester Building
Ann Arbor, MI 48109, US