Research

My work is in theoretical computer science, centred on structure in complex combinatorial and computational objects. One theme runs through much of my research: structure is what makes problems tractable. I look for structure, for example, sparsity in a known basis, invariance under a group of transformations, and use it to design efficient algorithms for learning and verification.

Recently, I have been exploring similar questions in machine learning. For example, if a model claims to satisfy some property — for instance, a fairness criterion — can an independent auditor verify that claim efficiently, with only restricted access to the model? Or can the behaviour of a complex model be described in terms of a small number of meaningful, structured components? On the other hand, I am interested in how cryptographic techniques can allow model owners to provide efficiently verifiable guarantees about their models, without requiring the verifier to simply trust the owner's claim.

More broadly, I am interested in what ideas from theoretical computer science can contribute to trustworthy AI, particularly through methods for making AI systems more transparent and independently checkable.

Below are outputs from my research.

In all my works, authors are listed alphabetically by last name, following the convention in theoretical computer science, except for works marked with an asterisk (*).

Manuscripts

  1. A function is compared with several affine functions to find the nearest one.
    On Nonlinearity Estimation Problem
    Arijit Ghosh, Subhamoy Maitra, and Manmatha Roy
    Under review
  2. A set is organized into cosets as a schematic aid to estimating a sumset.
    Approximating Sumset Size via Dense Coset Decomposition
    Arijit Ghosh and Manmatha Roy
    Under review
  3. A small set of queries leads to a Fourier sparsity decision.
    Testing Fourier Sparsity Near Optimally
    Arijit Ghosh and Manmatha Roy
    Under review
  4. A few observations are used to recover a sparse collection of coefficients.
    Exact Fourier-Sparse Recovery Made Simple
    Arijit Ghosh and Manmatha Roy
    Under review
  5. An irregular pattern is organized into a schematic structured partition.
    Constructive Arithmetic Regularity for Abelian Groups
    Swarnalipa Dutta, Arijit Ghosh, Chandrima Kayal, and Manmatha Roy
    Under review

Publications

  1. Unevenly distributed samples lead to a Fourier sparsity test.
    Distribution Free Fourier Sparsity Testing
    Arijit Ghosh and Manmatha Roy
    NeurIPS 2026
  2. Alice and Bob exchange messages to test equivalence of two functions.
    Spectral Shadows: When Communication Complexity Meets Linear Invariance Testing
    Swarnalipa Dutta, Arijit Ghosh, Chandrima Kayal, Manaswi Paraashar, and Manmatha Roy
    Computational Complexity
  3. Oracle queries form an implicit sketch for a sparsity decision.
    Testing Fourier Sparsity via Implicit Sensing
    Arijit Ghosh, Subhamoy Maitra, and Manmatha Roy
    ICLR 2026
  4. A sieve retains the significant spectral components.
    Spectral Norm, Economical Sieve, and Linear Invariance Testing of Boolean Functions
    Swarnalipa Dutta, Arijit Ghosh, Chandrima Kayal, Manaswi Paraashar, and Manmatha Roy
    STACS 2026
  5. A spectrum with a few dominant components and a smaller residual tail.
    Price of Parsimony: Complexity of Fourier Sparsity Testing
    Arijit Ghosh and Manmatha Roy
    NeurIPS 2025
  6. An automorphism maps one pattern on an Abelian group to another.
    Testing Isomorphism of Boolean Functions over Abelian Groups
    Swarnalipa Dutta, Arijit Ghosh, Chandrima Kayal, Manaswi Paraashar, and Manmatha Roy
    RANDOM 2025
  7. Two branches of a Boolean construction combine in a compact circuit.
    Construction of Maiorana–McFarland type cryptographically significant Boolean functions with good implementation properties*
    Deng Tang, Anupam Chattopadhyay, Bimal Mandal, Subhamoy Maitra, and Manmatha Roy
    Communications in Cryptology
  8. Selected flips in a toy truth table produce a balanced function.
    Modifying Bent Functions to Obtain Balanced Ones with High Nonlinearity
    Subhamoy Maitra, Bimal Mandal, and Manmatha Roy
    INDOCRYPT 2022
  9. Related inputs to an S-box are used to compare output differences.
    Experimental Results on Higher-Order Differential Spectra of 6 and 8-bit Invertible S-Boxes
    Deng Tang, Bimal Mandal, Subhamoy Maitra, and Manmatha Roy
    SPACE 2020