Research
Research
Research
Research
211+ open-access research outputs.
We develop an analytical framework for Boolean Promise Constraint Satisfaction Problems (PCSPs) that studies polymorphisms through the notion of influence from Fourier analysis of Boolean functions. E…
Since the breakthrough superpolynomial multilinear formula lower bounds of Raz (Theory of Computing 2006), proving such lower bounds against multilinear algebraic branching programs (mABPs) has been a…
The $k$-means problem is a classic objective for modeling clustering in a metric space. Given a set of points in a metric space, the goal is to find $k$ representative points so as to minimize the sum…
The Pareto sum of two-dimensional point sets $P$ and $Q$ in $\mathbb{R}^2$ is defined as the skyline of the points in their Minkowski sum. The problem of efficiently computing the Pareto sum arises fr…
Locally decodable codes (LDCs) are error correction codes that allow recovery of any single message symbol by probing only a small number of positions from the (possibly corrupted) codeword. Relaxed l…
The Spearman footrule is a voting rule that takes as input voter preferences expressed as rankings. It outputs a ranking that minimizes the sum of the absolute differences between the position of each…
This paper investigates the semi-streaming complexity of \textit{$k$-partial coloring}, a generalization of proper graph coloring. For $k \geq 1$, a $k$-partial coloring requires that each vertex $v$ …
Cryptographic digests (e.g., MD5, SHA-256) are designed to provide exact identity. Any single-bit change in the input produces a completely different hash, which is ideal for integrity verification bu…
In this paper, we continue the study of robust satisfiability of promise CSPs (PCSPs), initiated in (Brakensiek, Guruswami, Sandeep, STOC 2023 / Discrete Analysis 2025), and obtain the following resul…
Deploying large language models (LLMs) on heterogeneous edge devices demands frameworks that jointly optimize energy efficiency, inference quality, and reliability. Our prior QEIL v1 (Kumar & Jha, 202…
The Courtade-Kumar conjecture posits that dictatorship functions maximize the mutual information between the function's output and a noisy version of its input over the Boolean hypercube. We present t…
In Bayesian single-item auctions, a monotone bidding strategy--one that prescribes a higher bid for a higher value type--can be equivalently represented as a partition of the quantile space into conse…
With the adoption of multiple digital devices in everyday life, the cyber-attack surface has increased. Adversaries are continuously exploring new avenues to exploit them and deploy malware. On the ot…
A recent work of Goyal, Harsha, Kumar and Shankar gave nearly linear time algorithms for the list decoding of Folded Reed-Solomon codes (FRS) and univariate multiplicity codes up to list decoding capa…
We first extend the results of Chatterjee,Kumar,Shi,Volk(Computational Complexity 2022) by showing that the degree $d$ elementary symmetric polynomials in $n$ variables have formula lower bounds of $\…
Clustering is a fundamental technique in data analysis, with the $k$-means being one of the widely studied objectives due to its simplicity and broad applicability. In many practical scenarios, data p…
Virtual Reality (VR) is often described as the "ultimate empathy machine," framing disability as an experience to be simulated through such technologies, which can reduce disability to a spectacle of …
In the $k$-Edge Connected Spanning Subgraph ($k$-ECSS) problem we are given a (multi-)graph $G=(V,E)$ with edge costs and an integer $k$, and seek a min-cost $k$-edge-connected spanning subgraph of $G…
We show that the GCD of two univariate polynomials can be computed by (piece-wise) algebraic circuits of constant depth and polynomial size over any sufficiently large field, regardless of the charact…
We show that algebraic formulas and constant-depth circuits are closed under taking factors. In other words, we show that if a multivariate polynomial over a field of characteristic zero has a small c…
Free open-access publishing with Google Scholar indexing.
Submission Guide →