Shashank Srivastava

STOC Conference 2025 Conference Paper

Explicit Codes Approaching Generalized Singleton Bound using Expanders

• Fernando Granha Jeronimo
• Tushant Mittal
• Shashank Srivastava
• Madhur Tulsiani

We construct a new family of explicit codes that are list decodable to capacity and achieve an optimal list size of O (1/є). In contrast to existing explicit constructions of codes achieving list decoding capacity, our arguments do not rely on algebraic structure but utilize simple combinatorial properties of expander graphs. Our construction is based on a celebrated distance amplification procedure due to Alon, Edmonds, and Luby [FOCS’95], which transforms any high-rate code into one with near-optimal rate-distance tradeoff. We generalize it to show that the same procedure can be used to transform any high-rate code into one that achieves list decoding capacity. Our proof can be interpreted as a ”local-to-global” phenomenon for (a slight strengthening of) the generalized Singleton bound. Using this construction, for every R , є ∈ (0,1) and k ∈ ℕ + , we obtain an explicit family of rate R codes C ⊆ Σ n that achieve the є-relaxed generalized Singleton bound. The alphabet size of these codes is a constant depending only on є and k , and they can be list decoded up to radius k −1/ k · (1− R −є), in time n O k ,є (1) with a list of size k −1. As a corollary of our result, we also obtain the first explicit construction of LDPC codes achieving list decoding capacity, and in fact arbitrarily close to the generalized Singleton bound.

SODA Conference 2025 Conference Paper

Improved List Size for Folded Reed-Solomon Codes

• Shashank Srivastava

FOCS Conference 2025 Conference Paper

List Decoding Expander-Based Codes up to Capacity in Near-Linear Time

• Shashank Srivastava
• Madhur Tulsiani

We give a new framework based on graph regularity lemmas, for list decoding and list recovery of codes based on spectral expanders. Using existing algorithms for computing regularity decompositions of sparse graphs in (randomized) near-linear time, and appropriate choices for the constant-sized inner/base codes, we prove the following: –Expander-based codes constructed using the distance amplification technique of Alon, Edmonds and Luby [FOCS 1995] can be list decoded to capacity in near-linear time. By known results, the output list is optimal up to constant factors. –The same codes of Alon, Edmonds and Luby, can also be list recovered to capacity in near-linear time, with constant-sized output lists. –The Tanner code construction of Sipser and Spielman [IEEE Trans. Inf. Theory 1996] can be list decoded to its distance in near-linear time, with constant-sized output lists. Our results imply novel combinatorial as well as algorithmic bounds for each of the above explicit constructions. All of these bounds are obtained via combinatorial rigidity phenomena, proved using (weak) graph regularity. The regularity framework allows us to lift the list decoding and list recovery properties for the local base codes, to the global codes obtained via the above constructions.

TMLR Journal 2023 Journal Article

Beyond the Imitation Game: Quantifying and extrapolating the capabilities of language models

• Aarohi Srivastava
• Abhinav Rastogi
• Abhishek Rao
• Abu Awal Md Shoeb
• Abubakar Abid
• Adam Fisch
• Adam R. Brown
• Adam Santoro

Language models demonstrate both quantitative improvement and new qualitative capabilities with increasing scale. Despite their potentially transformative impact, these new capabilities are as yet poorly characterized. In order to inform future research, prepare for disruptive new model capabilities, and ameliorate socially harmful effects, it is vital that we understand the present and near-future capabilities and limitations of language models. To address this challenge, we introduce the Beyond the Imitation Game benchmark (BIG- bench). BIG-bench currently consists of 204 tasks, contributed by 450 authors across 132 institutions. Task topics are diverse, drawing problems from linguistics, childhood develop- ment, math, common-sense reasoning, biology, physics, social bias, software development, and beyond. BIG-bench focuses on tasks that are believed to be beyond the capabilities of current language models. We evaluate the behavior of OpenAI's GPT models, Google- internal dense transformer architectures, and Switch-style sparse transformers on BIG-bench, across model sizes spanning millions to hundreds of billions of parameters. In addition, a team of human expert raters performed all tasks in order to provide a strong baseline. Findings include: model performance and calibration both improve with scale, but are poor in absolute terms (and when compared with rater performance); performance is remarkably similar across model classes, though with benefits from sparsity; tasks that improve gradually and predictably commonly involve a large knowledge or memorization component, whereas tasks that exhibit "breakthrough" behavior at a critical scale often involve multiple steps or components, or brittle metrics; social bias typically increases with scale in settings with ambiguous context, but this can be improved with prompting.

FOCS Conference 2023 Conference Paper

List Decoding of Tanner and Expander Amplified Codes from Distance Certificates

• Fernando Granha Jeronimo
• Shashank Srivastava
• Madhur Tulsiani

We develop new list decoding algorithms for Tanner codes and distance-amplified codes based on bipartite spectral expanders. We show that proofs exhibiting lower bounds on the minimum distance of these codes can be used as certificates discoverable by relaxations in the Sum-of-Squares (SoS) semi-definite programming hierarchy. Combining these certificates with certain entropic proxies to ensure that the solutions to the relaxations cover the entire list, then leads to algorithms for list decoding several families of codes up to the Johnson bound. We prove the following results: - We show that the LDPC Tanner codes of Zémor [IEEE Trans. Inf. Theory 2001] with alphabet size q, block-length n and distance $\delta$, based on an expander graph with degree d, can be list-decoded up to distance $\mathcal{J}_{q}(\delta)-\varepsilon$ in time $n^{O_{d, q}\left(1 / \varepsilon^{4}\right)}$, where $\mathcal{J}_{q}(\delta)$ denotes the Johnson bound. - We show that the codes obtained via the expander-based distance amplification procedure of Alon, Edmonds and Luby [FOCS 1995] can be list-decoded close to the Johnson bound using the SoS hierarchy, by reducing the list decoding problem to unique decoding of the base code. In particular, starting from any base code unique-decodable up to distance $\delta$, one can obtain near-MDS codes with rate R and distance $1-R-\varepsilon$, list-decodable up to the Johnson bound in time $n^{O_{\varepsilon, \delta}(1)}$. - We show that the locally testable codes of Dinur et al. [STOC 2022] with alphabet size q, block-length n and distance $\delta$ based on a square Cayley complex with generator sets of size d, can be list-decoded up to distance $\mathcal{J}_{q}(\delta)-\varepsilon$ in time $n^{O_{d, q}\left(1 / \varepsilon^{4}\right)}$, where $\mathcal{J}_{q}(\delta)$ denotes the Johnson bound.

STOC Conference 2021 Conference Paper

Near-linear time decoding of Ta-Shma's codes via splittable regularity

• Fernando Granha Jeronimo
• Shashank Srivastava
• Madhur Tulsiani

The Gilbert–Varshamov bound non-constructively establishes the existence of binary codes of distance 1/2−є/2 and rate Ω(є 2 ). In a breakthrough result, Ta-Shma [STOC 2017] constructed the first explicit family of nearly optimal binary codes with distance 1/2−є/2 and rate Ω(є 2+α ), where α → 0 as є → 0. Moreover, the codes in Ta-Shma’s construction are є-balanced, where the distance between distinct codewords is not only bounded from below by 1/2−є/2, but also from above by 1/2+є/2. Polynomial time decoding algorithms for (a slight modification of) Ta-Shma’s codes appeared in [FOCS 2020], and were based on the Sum-of-Squares (SoS) semidefinite programming hierarchy. The running times for these algorithms were of the form N O α (1) for unique decoding, and N O є,α (1) for the setting of “gentle list decoding”, with large exponents of N even when α is a fixed constant. We derive new algorithms for both these tasks, running in time Õ є ( N ). Our algorithms also apply to the general setting of decoding direct-sum codes. Our algorithms follow from new structural and algorithmic results for collections of k -tuples (ordered hypergraphs) possessing a “structured expansion” property, which we call splittability . This property was previously identified and used in the analysis of SoS-based decoding and constraint satisfaction algorithms, and is also known to be satisfied by Ta-Shma’s code construction. We obtain a new weak regularity decomposition for (possibly sparse) splittable collections W ⊆ [ n ] k , similar to the regularity decomposition for dense structures by Frieze and Kannan [FOCS 1996]. These decompositions are also computable in near-linear time Õ(| W |), and form a key component of our algorithmic results.

SODA Conference 2020 Conference Paper

List Decoding of Direct Sum Codes

• Vedat Levi Alev
• Fernando Granha Jeronimo
• Dylan Quintana
• Shashank Srivastava
• Madhur Tulsiani

FOCS Conference 2020 Conference Paper

Unique Decoding of Explicit $\varepsilon$-balanced Codes Near the Gilbert-Varshamov Bound

• Fernando Granha Jeronimo
• Dylan Quintana
• Shashank Srivastava
• Madhur Tulsiani

The Gilbert-Varshamov bound (non-constructively) establishes the existence of binary codes of distance $1/2-\varepsilon$ and rate $\Omega(\varepsilon^{2})$ (where an upper bound of $O(\varepsilon^{2}\log(1/\varepsilon))$ is known). Ta-Shma [STOC 2017] gave an explicit construction of $\varepsilon$ -balanced binary codes, where any two distinct codewords are at a distance between $1/2-\varepsilon/2$ and $1/2+\varepsilon/2$, achieving a near optimal rate of $\Omega(\varepsilon^{2+\beta})$, where $\beta\rightarrow 0$ as $\varepsilon\rightarrow 0$. We develop unique and list decoding algorithms for (a slight modification of) the family of codes constructed by Ta-Shma, in the adversarial error model. We prove the following results for $\varepsilon$ -balanced codes with block length $N$ and rate $\Omega(\varepsilon^{2+\beta})$ in this family: –For all $\varepsilon, \beta > 0$, there are explicit codes which can be uniquely decoded up to an error of half the minimum distance in time $N^{O_{\varepsilon, \beta}(1)}$. –For any fixed constant $\beta$ independent of $\varepsilon$, there is an explicit construction of codes which can be uniquely decoded up to an error of half the minimum distance in time $(\log(1/\varepsilon))^{O(1)}\cdot N^{O_{\beta}(1)}$. –For any $\varepsilon > 0$, there are explicit $\varepsilon$ -balanced codes with rate $\Omega(\varepsilon^{2+\beta})$ which can be list decoded up to error $1/2-\varepsilon^{\prime}$ in time $N^{\mathrm{O}_{\varepsilon, \varepsilon^{\prime}, \beta}(1)}$, where $\varepsilon^{\prime}, \beta\rightarrow 0$ as $\varepsilon\rightarrow 0$. The starting point of our algorithms is the framework for list decoding direct-sum codes develop in Alev et al. [SODA 2020], which uses the Sum-of-Squares SDP hierarchy. The rates obtained there were quasipolynomial in $\varepsilon$. Here, we show how to overcome the far from optimal rates of this framework obtaining unique decoding algorithms for explicit binary codes of near optimal rate. These codes are based on simple modifications of Ta-Shma's construction.

JAAMAS Journal 2019 Journal Article

An agent for learning new natural language commands

• Amos Azaria
• Shashank Srivastava
• Tom M. Mitchell

Abstract Teaching via natural language is an intuitive way for end users to add functionality to a virtual assistant, enabling them to personalize their assistant with new commands without requiring the intervention of the system developer, who cannot possibly anticipate all of an end user’s needs. In this paper we introduce our Learning by Instruction Agent (LIA), the first virtual assistant, for an email domain, that is capable of learning how to perform new commands taught by end users in natural language. LIA grounds the semantics of each command in terms of primitive executable procedures. When a user provides LIA with a command that it does not understand, it prompts the user to explain the command through a sequence of natural language steps. From this input, LIA learns the meaning of the new command and how to generalize the command to novel situations. For example, having been taught how to “forward an email to Alice”, it can correctly understand “forward this email to Bob”. We show that users that were assigned to interact with LIA completed the task quicker than users assigned to interact with a non-learning agent. These results demonstrate the potential of natural language teaching to improve the capabilities of intelligent personal assistants. We annotated 4759 natural language statements with their associated computer readable execution commands (logical forms) to form a dataset (which we publicize in this paper). We present the performance of several different parser methods on this dataset.

IJCAI Conference 2017 Conference Paper

Parsing Natural Language Conversations using Contextual Cues

• Shashank Srivastava
• Amos Azaria
• Tom Mitchell

In this work, we focus on semantic parsing of natural language conversations. Most existing methods for semantic parsing are based on understanding the semantics of a single sentence at a time. However, understanding conversations also requires an understanding of conversational context and discourse structure across sentences. We formulate semantic parsing of conversations as a structured prediction task, incorporating structural features that model the `flow of discourse' across sequences of utterances. We create a dataset for semantic parsing of conversations, consisting of 113 real-life sequences of interactions of human users with an automated email assistant. The data contains 4759 natural language statements paired with annotated logical forms. Our approach yields significant gains in performance over traditional semantic parsing.

AAAI Conference 2016 Conference Paper

Inferring Interpersonal Relations in Narrative Summaries

• Shashank Srivastava
• Snigdha Chaturvedi
• Tom Mitchell

Characterizing relationships between people is fundamental for the understanding of narratives. In this work, we address the problem of inferring the polarity of relationships between people in narrative summaries. We formulate the problem as a joint structured prediction for each narrative, and present a general model that combines evidence from linguistic and semantic features, as well as features based on the structure of the social community in the text. We additionally provide a clustering-based approach that can exploit regularities in narrative types. e. g. , learn an affinity for love-triangles in romantic stories. On a dataset of movie summaries from Wikipedia, our structured models provide more than a 30% error-reduction over a competitive baseline that considers pairs of characters in isolation.

AAAI Conference 2016 Conference Paper

Modeling Evolving Relationships Between Characters in Literary Novels

• Snigdha Chaturvedi
• Shashank Srivastava
• Hal Daume III
• Chris Dyer

Studying characters plays a vital role in computationally representing and interpreting narratives. Unlike previous work, which has focused on inferring character roles, we focus on the problem of modeling their relationships. Rather than assuming a fixed relationship for a character pair, we hypothesize that relationships temporally evolve with the progress of the narrative, and formulate the problem of relationship modeling as a structured prediction problem. We propose a semisupervised framework to learn relationship sequences from fully as well as partially labeled data. We present a Markovian model capable of accumulating historical beliefs about the relationship and status changes. We use a set of rich linguistic and semantically motivated features that incorporate world knowledge to investigate the textual content of narrative. We empirically demonstrate that such a framework outperforms competitive baselines.